Certified finite F₂ persistence from simplex lists

First run

FiniteInput and its matching Examples.filled fixture are present in the v0.3.0 release. The output below was checked against the current checkout.

In an existing Lean/Lake project, make TDA available using the project setup instructions. From that project's root, save the block below as FinitePHExample.lean and run lake env lean FinitePHExample.lean. The #eval commands print the results shown below.

This seven-entry list adds vertices at grade 0, edges at 1, and the filled triangle at 2:

import TDA.Persistence.Reduction.FiniteInput

open TDA.Persistence.Reduction.FiniteInput

def filledTriangle : Input :=
  [({0}, 0), ({1}, 0), ({2}, 0),
    ({0, 1}, 1), ({1, 2}, 1), ({0, 2}, 1),
    ({0, 1, 2}, 2)]

#eval validBool filledTriangle
#eval run filledTriangle

def missingEdge : Input :=
  [({0}, 0), ({1}, 0), ({2}, 0),
    ({0, 1}, 1), ({1, 2}, 1),
    ({0, 1, 2}, 2)]

#eval validBool missingEdge
#eval run missingEdge

For filledTriangle, validBool is true, and run returns some containing the full four-record list shown here, in order:

Degree Birth Death
0 0 Death.finite 1
0 0 Death.finite 1
1 1 Death.finite 2
0 0 Death.essential

The equal degree-zero rows are separate finite H₀ occurrences. Death.essential represents unbounded death, not an integer sentinel. missingEdge omits the {0, 2} edge, so validBool is false and run returns none; the input is not repaired.

For cycles in the original face-index basis and fillings for finite deaths, continue to cycle representatives. That API was added in v0.4.0.

Contract and representation

TDA.Persistence.Reduction.FiniteInput.Input is a list of (Finset ℕ, ℤ) pairs. A list position is a zero-based face index. The natural numbers are vertex labels, not an ambient vertex interval: only listed nonempty faces belong to complex. Thus an empty list represents the empty complex, and a face using vertex 900 does not introduce vertices 0 through 899. The vertex order within a face is the canonical increasing order given by Finset.orderEmbOfFin.

Valid records five conditions: nonempty simplices, unique simplices regardless of grades, presence of every nonempty subset, strict face-before-coface order, and nondecreasing grades at all ordered list positions. validBool decides this whole proposition by finite list, powerset, natural-order, and integer-order decisions; validBool_iff proves both directions. run returns none on invalid data and the computed occurrence list on valid data. run_isSome_iff, run_eq_some_iff, and run_eq_none_iff link acceptance, successful output, and rejection exactly. No input normalization is performed. Negative grades, tied grades, and empty input are valid when the five conditions hold.

For a valid list, complex has exactly its listed faces (mem_complex), and listEquiv pairs positions bijectively with its total faces. gradeFilter assigns each face its unique listed integer grade. Face precedence together with nondecreasing list grades proves monotonicity. compatibleOrder takes the given list order as the compatible face enumeration. These semantic objects and their proof-derived equivalences may be noncomputable; none occurs in the transitive definition path of run.

Computation and indices

boundary reads faces at two list positions. For a codimension-one candidate it sums the oriented deletion terms in canonical vertex order, specializing the signs to ZMod 2; all other entries are zero. Its definition uses only finite indexing, Finset deletion and equality, and finite sums. The vertex column is zero in ordinary unaugmented homology. In particular, an isolated vertex contributes an essential H₀ class. The computation does not insert an empty face as a chain generator.

boundary_eq_faceBoundaryMatrix compares every computed entry with the existing faceBoundaryMatrix under the position equivalence. boundary_reindex is the whole-matrix version. The existing face-boundary theorems then yield boundary_sq_zero, boundary_strict (nonzero rows precede their columns), and boundary_lowersDegree (the column degree is one above its row degree). This bridge uses the signed simplicial deletion convention already formalized in SimplicialAdapter.lean; specializing to F₂ makes each deletion coefficient one.

trace invokes the existing chronological matrixReductionTrace on that computed matrix, and reduced invokes replay. reduced_reindex shows that this is the reducedFaceBoundary used by the semantic certificate. pivotPairs produces one pair (i,j) for each nonzero reduced column j, where i = columnPivot (reduced.col j). A pivot at row zero is some 0; none means a zero column. essentialIndices selects zero columns outside the image of the pivot map. The two extraction lemmas compare these finite lists, converted to multisets by degree, with the existing pivotIndexPairs and pivotEssentialIndices. Neither path quotients a list to a set, so equal value intervals can occur more than once.

A pair gets the degree of face i, birth grade of face i, and finite death grade of face j. An essential index gets its face degree and birth grade, with the distinct Death.essential constructor. pairOccurrence drops an equal-grade finite pair only at the value-output step. finite_birth_lt_death proves that every retained finite occurrence has a strictly later death. An essential death is interpreted as ⊤ : WithTop ℤ, never as an integer sentinel or the largest attained grade. outputDiagram filters the occurrence list by homological degree and maps it to a multiset of diagram points, retaining duplicate points.

The face indices above start at zero. The face-prefix filtration in the reduction theorem counts stages: face index i enters at stage i+1. The finite index-bar death stage is likewise one past its final live prefix. The index sentinel after all m faces is m+1 in the shifted stage model; it marks an essential index interval and is not an integer death grade. After the largest attained integer grade, the semantic sublevel is the full represented complex, so an essential class persists along the constant tail. For empty input there is no attained maximum, and the sublevel remains empty.

Correctness route

pairValuesAtDegree_semantic and essentialBirthsAtDegree_semantic identify the computed grade multisets with the existing pivot template's grade maps. outputDiagram_points separates the finite off-diagonal and essential contributions. The final outputDiagram_eq_dgm invokes merged evaluatePivotTemplate_eq_dgm from SimplicialAdapterTemplate.lean, which already connects the boundary reducer and filtered normal form to simplicial homology. The proof-only nonempty_facePrefixHomologyIsoPivotBarcode additionally exposes the genuine natural interval isomorphism of that prefix module. Thus, for every valid input and every degree, the interpreted records equal dgm (ZMod 2) (gradeFilter xs h) p as a Diagram ℤ. This is a statement about the integer sublevel filtration, not a declared pairing or a separately assumed barcode decomposition.

outputDiagram_eq_of_same_graded_complex states the order-independence consequence at the diagram level: valid presentations whose represented complexes and filters agree have equal interpreted diagrams. The occurrence list order and position pairs can differ. Examples.equal_grade_reordering checks a concrete equal-grade edge swap whose pivot pairs differ.

FiniteInputExamples.lean proves evaluations through the public run path, including the filled-triangle first run. Its zero-based pivot pairs are (1,3), (2,4), (5,6) and its essential index is 0. Removing the triangle leaves an essential H₁ birth at 1; tying the triangle to grade 1 removes its zero-length value interval. Further fixtures cover empty input, a delayed single vertex, negative grades, duplicate intervals on disjoint edges, equal-grade reordering, and sparse vertex labels. Five negative fixtures reject an empty simplex, duplicate simplex with different grade, missing face, coface-first list, and decreasing grades. The negative runs together with run_eq_none_iff justify their invalidity.

Dependency and source scope

The computational dependencies are pinned Lean/mathlib finite lists and sets, Finset.orderEmbOfFin, integer comparisons, ZMod 2, Matrix, the existing columnPivot, matrixReductionTrace, and replay. The semantic chain uses SimplicialAdapter.lean for the signed boundary; FilteredNormalForm.lean for the reducer-to-normal-form theorem; SimplicialAdapterTemplate.lean for the merged simplicial-homology diagram equality; and SublevelDiagram.lean/IndexDiagram.lean for the value diagram and essential-tail interpretation. The earlier mathematical source inventory and precise correspondence for reduction are in persistence-reduction.md, and the sublevel convention is in finite-sublevel-diagram.md. This unit specializes those results to finite F₂ input with integer grades. It adds no sparse-matrix optimization, file parser, real-grade computation, or performance bound.