Metric input and Rips diagram stability

Fix a finite labelled vertex type V and two real-valued metrics d,e on V. The labels identify the vertices being compared. The metrics are explicit MetricSpace V values; the API does not require two metric instances on V at once.

Diameter filtration

The full simplex complex contains every nonempty finite subset of V. For a finite subset s, define

f_d(s) = max {d(v,w) : v,w ∈ s},

with the auxiliary empty maximum equal to zero. The empty set is excluded from the complex. A singleton has diameter zero, and an edge has value exactly its endpoint distance. Increasing a face can only increase its diameter.

The diameter values define a FilterFunction on this fixed full complex. Its sublevel at r consists exactly of nonempty s with d(v,w) ≤ r for all v,w ∈ s, including self-pairs. Thus vertices appear at zero and every stage below zero is empty. This is the closed Rips filtration with diameter as its time parameter; no ball-radius rescaling is used.

Perturbation bound

Define the distance-matrix discrepancy

δ = max { |d(v,w) − e(v,w)| : v,w ∈ V },

with δ = 0 when V is empty. For every finite s,

|f_d(s) − f_e(s)| ≤ δ.

Indeed, d(v,w) ≤ e(v,w) + δ ≤ f_e(s) + δ for each pair in s. Taking the maximum, including its zero seed, gives f_d(s) ≤ f_e(s) + δ. Reversing the metrics proves the absolute-value estimate. The zero seed also handles s empty without choosing a vertex.

Let dgm_k(f_d,n) be the existing diagram of simplicial sublevel homology in degree n over a field k. The face supremum discrepancy is at most δ, so the existing finite-face stability theorem gives

bottleneck(dgm_k(f_d,n), dgm_k(f_e,n)) ≤ δ.

In Lean the right side is ENNReal.ofReal δ. The theorem uses V : Type u with LinearOrder V and Fintype V, and k : Type u with Field k, exactly as required by the existing diagram interface after specializing to a finite carrier. It holds for every n. It retains occurrence multiplicity, finite interval conventions and essential deaths at ⊤; no essential-cardinality or genericity hypothesis is added.

The finite persistence-image consumer composes this bound with Gaussian pixel stability and an explicit finite-bar-count factor. Essential bars remain in the bottleneck comparison and are omitted from the image.

Interfaces and examples

TDA.Filtration.Rips defines fullComplex, diameter, filter and pairwiseDiscrepancy. mem_sublevel_iff identifies the closed Rips complex, and abs_diameter_sub_le_pairwiseDiscrepancy supplies the elementary input estimate. TDA.Persistence.RipsStability proves faceSupDifference_filter_le and bottleneck_dgm_le_pairwiseDiscrepancy. Ordinary Filtration and Persistence imports include their respective modules. These are noncomputable mathematical definitions; they do not provide an executable distance-matrix or point-cloud reduction pipeline.

The example module checks the empty carrier and a singleton, then compares two metrics on Fin 2 with off-diagonal distances one and two. Their edge entry times are one and two, their discrepancy is one, and their diagrams satisfy the stated bound in every degree.

Source correspondence and scope

The diameter threshold at nonnegative scales matches Chazal–de Silva–Oudot §4.2.1. Section 4.2 defines correspondence distortion; for the identity relation on a nonempty finite labelled set, its displayed distance discrepancy has the same formula as δ. This observation does not introduce a formal correspondence interface.

The source's nonpositive-scale vertex remark is not used here: the support-aware library convention assigns singleton value zero and empty stages below zero. No full real-indexed convention equivalence is claimed. The same-label diagram estimate is independently derived through bottleneck_dgm_le_faceSupDifference; it does not formalize the source's Lemma 4.3 interleaving or Theorem 5.2 Gromov–Hausdorff theorem. The supplied-relation construction below compares different metric vertex types. Čech comparison and Gromov–Hausdorff selection use separate constructions.

Relations between different metric label types

Let X and Y carry explicit genuine metrics dX and dY. Supply a native relation C and ε≥0 with |dX(x,x′)−dY(y,y′)|≤ε whenever (x,y),(x′,y′) belong to C. This includes pairs with x=x′: two images of the same vertex can have distance at most ε. For a source face at t, each pair in a nonempty finite subset of its relational image has antecedents in that face. Hence dY≤dX+ε≤t+ε, proving the shifted Rips face condition without totality or a finite-image premise. Reversing the relation and the absolute difference proves the converse geometry.

When C and its native transpose are ambient-total, Rips.relationInterleaving uses the canonical relation maps to construct a homology interleaving. Both fields are exposed exactly; their double-shift composites are the inclusion-induced transitions. This works over every ring, every natural homology degree, empty types and infinite types, with independent orders in a common vertex universe. It bounds the existing extended interleaving distance. For finite types and a field in the diagram universe, bottleneck_dgm_le_of_relation derives constructibility and finite dimensionality separately for the two filters. The existing different-grid matching theorem then bounds their full diagrams, including essential occurrences.

Fixtures compare distance-two and distance-three pairs on different types, and a singleton with a distance-two pair. Nonzero H₀ images and triangles are evaluated; a two-vertex difference survives before an edge enters and collapses after the required transition. Quantitative negative controls refute the geometric predicate when the bound is too small. Empty, infinite, repeated-point metric obstruction, noncentral matrix coefficient and trivial-ring cases retain the same maps.

This implements the supplied-distortion mechanism in CDSO Lemma 4.3's proof, through Proposition 4.2, at nonnegative scales. The target-distance estimate is derived directly from the absolute bound; the printed proof's first displayed comparison is not used without its additive allowance. No erratum is asserted. The supplied-relation theorem accepts the relation as input. The finite GH bridge below supplies one; the source's whole-real H₀ convention remains distinct. Arbitrary-ring signed chains and the finite-diagram corollary are library extensions. An arbitrary noninjective cloud has no genuine label metric agreeing with all ambient pair distances; no pseudometric or quotient-cloud foundation is supplied.

Gromov–Hausdorff stability and sampling

For finite nonempty metric spaces X and Y, every field k and every degree n,

bottleneck(dgm_k(Rips(X), n), dgm_k(Rips(Y), n)) ≤ 2 d_GH(X,Y).

RipsGromovHausdorff proves this bound for the full diagrams, with their finite and essential occurrences. The Lean bound is ENNReal.ofReal (2 * GromovHausdorff.ghDist X Y). The GH normalization is the usual half-distortion normalization; the constant two accompanies the library's diameter time. There is no equal-cardinality or supplied-correspondence hypothesis.

In a common metric ambient space, let f and g be isometric embeddings of X and Y, and put r = d_H(range f, range g). The relation

C = {(x,y) | dist(f(x),g(y)) ≤ r}

is total on both sides: each finite image is compact, so the distance to it is attained. The triangle inequality bounds the distortion of C by 2r, including pairs sharing a source or target. The existing canonical relation interleaving then bounds the diagrams by 2r. Mathlib's optimal coupling realizes r = d_GH(X,Y), so the GH bound follows without assuming an optimizing correspondence or taking a limit of diagram matchings. The ambient space itself need not be compact or proper.

bottleneck_dgm_le_two_mul_ghDist is the ordered-label entry point. diagram k X n also accepts an arbitrary finite metric space without a vertex order, even when the field and the two spaces live in different universes. It is the existing diagram on isometric finite labels in the field's universe. diagram_eq_dgm identifies it with the existing diagram for every vertex order; dgm_eq_of_isometryEquiv permits isometric relabellings that reverse that order. The chosen finite enumeration changes neither the full diagram nor the estimates.

For finite samples isometrically embedded in one ambient space, Hausdorff error at most ε gives bottleneck error at most 2ε. If two finite samples are within extended Hausdorff errors ε and δ of the same possibly infinite set, their finite diagrams are within 2(ε+δ). Extended Hausdorff distance is used for those hypotheses so that an empty or unbounded target cannot create a spurious zero error through the real-valued convention at infinity. Convergence in Hausdorff distance to a fixed finite nonempty target therefore gives convergence of the full diagrams in bottleneck distance, with varying sample cardinalities allowed.

The correspondence argument specializes the mechanism of CDSO13-v3 §4.2 and Lemma 4.3 to finite metric spaces, using mathlib's GH coupling and the library's sublevel-diagram theorem. It retains the library's empty negative tail; it makes no whole-real H₀ identification with the source's nonpositive-time vertex convention. The finite sampling comparison above compares only finite diagrams. The sections below construct the q-tame diagram of a possibly infinite target and prove its exact Hausdorff and compact Gromov–Hausdorff stability.

These results are abstract existence and correctness statements. Finite labels can support executable consumers when exact distance comparisons are available; no algorithm for optimizing GH distance over arbitrary real data or for computing homology over an arbitrary abstract field is asserted.

Totally bounded spaces

For a field k, a real persistence module M is q-tame if the image of M(a) → M(b) is finite-dimensional whenever a < b. The fibers M(a) need not be finite-dimensional. In Lean, PModule.QTame uses FiniteDimensional k (LinearMap.range (structureMapLinear M hab.le)).

Let X be any totally bounded metric space. Its closed diameter Rips homology module is q-tame over every field and in every degree. Fix a < b and put ε = (b−a)/2 > 0. Total boundedness supplies a finite ε/2-net F ⊆ X. The relation

C = {(x,f) ∈ X × F | dist(x,f) < ε/2}

is total on both sides, since the net covers X and every f is related to itself. The triangle inequality bounds its pairwise distortion by ε. The canonical relation interleaving gives a composite

M_X(a) → M_F(a+ε) → M_X((a+ε)+ε) = M_X(b).

The interleaving law identifies this composite with the structure map, and the middle homology is finite-dimensional because F is finite. The range is therefore finite-dimensional. This proof works for the empty space and all real source times; no vertex is added to the negative tail.

Rips.exists_finite_net_relation proves the finite-net geometry and Rips.qTame_of_totallyBounded gives the module theorem. The reusable finiteDimensional_range_of_factorization and RealInterleaving.finiteDimensional_range_structureMap expose the linear and interleaving steps. Vertex and coefficient universes are independent; the auxiliary vertex order may be chosen arbitrarily. Rips.sublevelModuleIsoOfIsometryEquiv compares the modules under any isometric relabelling, using the graph relation and its zero-interleaving, without requiring order preservation or finiteness.

At time zero a genuine metric admits only singleton faces, so an infinite vertex type gives infinite-dimensional unreduced H₀. Rips.not_finiteDimensional_zero_homology proves this fact. RipsQTameExamples applies both results to the infinite compact interval [0,1] ⊆ ℝ. It witnesses finite-dimensional images across every strict gap and an infinite-dimensional fiber at zero in the same example.

The finite-net argument formalizes the Rips part of CDSO13-v3 Proposition 5.1 through Lemma 4.3. The library retains closed thresholds and its empty negative tail. The finite-net argument supplies q-tameness; the next construction consumes that fact to obtain actual decorated diagram counts.

Decorated diagrams of infinite Rips spaces

For every totally bounded X, field k and homological degree n, Rips.qTameDiagramMultiplicity specializes the q-tame module's canonical finite-death and essential multiplicities to the existing closed-diameter Rips homology. The construction takes no finite sample or finite-dimensional fiber. For each separated finite rectangle, the sum of positive decorated multiplicities equals the Rips module's image-and-kernel quotient dimension. On a birth strip at death infinity, it equals the stabilized essential quotient count. On each separated tail rectangle, including finite deaths surviving the tail threshold and the infinite-death boundary, it equals the actual finite-target image quotient dimension. The tail has finite positive support; the full diagram has countable positive support.

RipsQTameDiagramExamples.unitInterval_infinite_fiber_with_diagram combines these conclusions for the compact interval [0,1] with its infinite-dimensional unreduced H₀ fiber at time zero. This tests the intended q-tame infinite-space case rather than a finite-only barcode. The result uses the finite-net factorization of Chazal–de Silva–Oudot, Proposition 5.1, and the integer-content extraction of Chazal–de Silva–Glisse–Oudot, Theorem 2.8 and §2.6, under the library's closed-threshold and empty-negative-tail conventions.

For finite metric spaces, Rips.qTameDiagramMultiplicity_eq_diagramOccurrenceCount identifies each canonical q-tame multiplicity with the occurrence count in the existing finite Rips diagram. A finite occurrence (b,d) maps to (minusCut b, minusCut d); an essential occurrence (b,⊤) maps to (minusCut b, infinityCut). Thus the existing finite barcode's half-open endpoint decorations and essential bars are preserved. The Lean theorem uses k : Type u when the vertex type is X : Type u, matching the universe restriction of the current rank-to-diagram API; no q-tameness or finite-fiber assumption is passed by the caller. The mathematical compatibility statement holds over every coefficient field.

LocallyFiniteDiagramBottleneck builds the canonical decorated occurrence diagram of any q-tame real module directly from its persistence-measure multiplicity. It retains countable support, finite separated rectangles and finite tail rectangles, and defines an extended bottleneck matching-cost infimum on finite and essential occurrence tokens. Decorations remain part of the multiplicity; the cost forgets them only through their real endpoints.

For the existing full finite Diagram ℝ type, Diagram.toLocallyFinite takes an explicit Diagram.IsPositive proof and preserves point multiplicities. bottleneck_toLocallyFinite proves an isometry for positive finite diagrams. Positivity is required because the legacy Diagram type also permits reverse bars, while q-tame finite-death multiplicity is supported only on the positive half of the decorated endpoint plane. For finite metric spaces, Rips.qTameLocallyFiniteDiagram_bottleneck_eq_finite combines this result with Rips.qTameDiagramMultiplicity_eq_diagramOccurrenceCount; the generic endpoint map is definitionally the existing Rips occurrence map, including the true infinityCut for essential deaths.

The finite results above are joined by a global compactness theorem. For the finite-birth diagrams extracted from arbitrary q-tame modules, qTame_bottleneck_le_of_realInterleaving bounds the bottleneck distance by the parameter of each actual interleaving; exists_occurrenceMatching_cost_le_of_realInterleaving exposes the global occurrence matching with cost at most that parameter that the proof builds. It uses finite saturation on each finite set of required vertices and a coherent section of the resulting finite inverse system; no decomposition or global-matching hypothesis is assumed. The generic diagram representation does not include birth-at-minus-infinity strata.

For those finite-birth diagrams, RealInterleaving.exists_finite_saturating_matching proves finite saturation from an actual interleaving: given finite prescribed sets of finite bars longer than 2ε and essential occurrences on each side, it constructs finite injective edge sets that cover those tokens with pair costs at most ε. The proof uses local finite-window counts and a coefficient-one continuation argument, and does not assume a matching or interval decomposition. As a metric consumer, Rips.qTameLocallyFiniteDiagram_bottleneck_le_of_hausdorff_lt combines global algebraic stability with the existing actual Rips Hausdorff interleaving for totally bounded spaces embedded isometrically in a common ambient space. Under strict slack 2 * hausdorffDist < ε, it bounds the bottleneck distance of the complete locally finite q-tame diagrams by ε. The Rips modules vanish at negative times, so their finite-birth diagrams have no omitted birth-at-minus-infinity occurrences.

Exact metric stability for the q-tame diagrams

If X and Y are nonempty totally bounded metric spaces with isometric embeddings f : X → Z and g : Y → Z into a common metric space, then

bottleneck(D_X, D_Y) ≤ ENNReal.ofReal (2 * hausdorffDist (range f) (range g)).

Here D_X and D_Y include every finite-death and essential occurrence of the q-tame Rips homology modules. The image sets need not be closed and no nearest point is assumed to exist. The proof first uses each positive slack above twice the Hausdorff distance in the strict interleaving theorem, then takes the infimum of the slack in ℝ≥0∞. Total boundedness makes the real Hausdorff distance finite. The vertex types X and Y currently share a Lean universe, as required by the Rips relation-interleaving construction; the coefficient field and ambient space may use independent universes. The public theorem requires an auxiliary linear order on each vertex type, but the diagram itself is order-independent: a module isomorphism preserves both separated-rectangle and essential birth-strip contents, hence their actual multiplicities.

For nonempty compact metric spaces, mathlib's optimal compact Gromov–Hausdorff coupling specializes the ambient theorem to bottleneck(D_X,D_Y) ≤ ENNReal.ofReal (2 * ghDist X Y). The isometries in the optimal coupling need not preserve either auxiliary order. On finite spaces, the exact compatibility theorem identifies these complete diagrams with the existing full finite Rips diagrams.

There is also a convergence statement with varying finite sample types and cardinalities. If nonempty finite Rips spaces embed isometrically in one ambient space and their Hausdorff distances to a fixed nonempty totally bounded target tend to zero, then the bottleneck distances of their q-tame diagrams to the target diagram tend to zero. The target need not be finite or compact. The checked fixture RipsQTameInfiniteMetricStabilityExamples uses increasing initial samples of the genuinely infinite compact space {0} ∪ {1/(n+1) : n ∈ ℕ}.

These Rips consumers use finite-net q-tameness and algebraic stability for q-tame modules. They do not claim a theorem for arbitrary q-tame modules with birth-at-minus-infinity strata, which are outside the current locally finite diagram representation.