Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.5, geometric step: superlevel-set and upper-star Rips filtrations are strongly cδc\deltacδ-interleaved above the sampled level

Open
PersistClust.Count.theorem_4_5_interleaving

by fabianroll · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

clusteringpersistenceriemannian-geometrytopological-data-analysis

This is the geometric half of the proof of Theorem 4.5: it constructs the strong cδc\deltacδ-interleaving, above the sampled level α\alphaα, between the superlevel-set filtration of a tame function and the upper-star Rips filtration of a geodesic (δ/4)(\delta/4)(δ/4)-sample of one of its superlevel sets.

Let XXX be a Riemannian manifold, possibly non-compact, possibly with boundary, whose convexity radius ϱc(X)\varrho_c(X)ϱc​(X) is positive. Let f:X→Rf : X \to \mathbb{R}f:X→R be a tame (finite-type) ccc-Lipschitz function with constant c≥0c \ge 0c≥0, let L⊆XL \subseteq XL⊆X be a finite point cloud, and let δ>0\delta > 0δ>0 be below the convexity radius. Suppose that for some α∈R\alpha \in \mathbb{R}α∈R the point cloud LLL is a geodesic (δ/4)(\delta/4)(δ/4)-sample of the superlevel set Fα=f−1([α,∞))\mathbb{F}^\alpha = f^{-1}([\alpha,\infty))Fα=f−1([α,∞)), that is, every point of Fα\mathbb{F}^\alphaFα lies within distance δ/4\delta/4δ/4 of some point of LLL.

Consider the superlevel-set filtration {Fβ}β∈R\{\mathbb{F}^\beta\}_{\beta\in\mathbb{R}}{Fβ}β∈R​ of fff and the upper-star Rips filtration {Rδ(Lβ)}β∈R\{R_\delta(L^\beta)\}_{\beta \in \mathbb{R}}{Rδ​(Lβ)}β∈R​, where Lβ={x∈L:β≤f(x)}L^\beta = \{x \in L : \beta \le f(x)\}Lβ={x∈L:β≤f(x)} and Rδ(Lβ)R_\delta(L^\beta)Rδ​(Lβ) is the Rips graph of the points of LβL^\betaLβ at scale δ\deltaδ. Write rXr_XrX​ and rYr_YrY​ for their 000-th rank functions (for s≥ts \ge ts≥t, the number of connected components of the stage at level ttt that meet the stage at level sss). Then:

  1. both 000-th persistence diagrams D0f=mult⁡(rX)D_0 f = \operatorname{mult}(r_X)D0​f=mult(rX​) and D0Rδf(L)=mult⁡(rY)D_0 \mathcal{R}^f_\delta(L) = \operatorname{mult}(r_Y)D0​Rδf​(L)=mult(rY​) are off-diagonal (every point of positive multiplicity has death smaller than birth) and have finite off-diagonal support;
  2. the two filtrations are strongly cδc\deltacδ-interleaved above the time α\alphaα; expressed at the level of the rank functions, for all s≥αs \ge \alphas≥α and all t≤st \le st≤s,
rX(s,t)≤rY(s−cδ, t−cδ)andrY(s,t)≤rX(s−cδ, t−cδ).r_X(s,t) \le r_Y(s - c\delta,\, t - c\delta) \quad\text{and}\quad r_Y(s,t) \le r_X(s - c\delta,\, t - c\delta).rX​(s,t)≤rY​(s−cδ,t−cδ)andrY​(s,t)≤rX​(s−cδ,t−cδ).

The interleaving is obtained exactly as in the proof of Theorem 4.4 of the report (following [6, Sec. 3.1]): the (δ/4)(\delta/4)(δ/4)-sample property guarantees that every connected component of Fβ\mathbb{F}^\betaFβ with β≥α\beta \ge \alphaβ≥α contains a point of LβL^\betaLβ; nearest-sample maps φβ:H0(Rδ(Lβ))→H0(Fβ−cδ)\varphi_\beta : H_0(R_\delta(L^\beta)) \to H_0(\mathbb{F}^{\beta-c\delta})φβ​:H0​(Rδ​(Lβ))→H0​(Fβ−cδ) and ψβ:H0(Fβ)→H0(Rδ(Lβ−cδ))\psi_\beta : H_0(\mathbb{F}^\beta) \to H_0(R_\delta(L^{\beta-c\delta}))ψβ​:H0​(Fβ)→H0​(Rδ​(Lβ−cδ)) are then defined for β≥α\beta \ge \alphaβ≥α, the Lipschitz bound moving function values by at most cδc\deltacδ and the geodesic convexity (a Rips edge joins points at distance ≤δ<ϱc(X)\le \delta < \varrho_c(X)≤δ<ϱc​(X), so the shortest geodesic between them stays within the relevant superlevel set up to the Lipschitz slack) ensuring the maps land where claimed; the commutation of the interleaving diagrams then yields the rank inequalities above. The finiteness assertions follow from the tameness of fff and the finiteness of the point cloud LLL.

This lemma is the companion of PersistClust.Count.theorem_4_5_lemma_4_6 (Lemma 4.6, the algebraic half): feeding this interleaving into Lemma 4.6 with ε=cδ\varepsilon = c\deltaε=cδ produces the multi-bijection asserted by Theorem 4.5.

Formalization Note The statement is taken with the same hypotheses as Theorem 4.5 (tame ccc-Lipschitz function, positive convexity radius, δ\deltaδ below it, geodesic (δ/4)(\delta/4)(δ/4)-sample of Fα\mathbb{F}^\alphaFα). The filtrations are the ones defined by superRank f and ripsRank.

RETIRED (2026-10-09). This statement is FALSE as literally written: the naive shift r(s,t)≤r′(s−ε,t−ε)r(s,t) \le r'(s-\varepsilon, t-\varepsilon)r(s,t)≤r′(s−ε,t−ε), quantified over all t≤st \le st≤s with s≥αs \ge \alphas≥α, is refuted at s=t=αs = t = \alphas=t=α by elementary examples on X=RX = \mathbb RX=R (it probes ranks below the sampled level α\alphaα). It is replaced by the corrected child PersistClust.Count.theorem_4_5_interleaving_corrected, which asserts the box-expansion inequalities only in the region s≥t+2εs \ge t + 2\varepsilons≥t+2ε, t≥αt \ge \alphat≥α where the interleaving maps factor, together with the FiltrationLaw structure of both filtrations.

Preamble
import Mathlib
import Definitions.Def_PersistClust_Count_Setting
import Definitions.Def_PersistClust_Count_Diagram
import Definitions.Def_PersistClust_Count_Rips

open Bundle
open scoped ContDiff Manifold
Formal statement
namespace PersistClust.Count

theorem theorem_4_5_interleaving
    {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
    {H : Type*} [TopologicalSpace H] {I : ModelWithCorners ℝ E H}
    {X : Type*} [MetricSpace X] [ChartedSpace H X] [IsManifold I ∞ X]
    [RiemannianBundle (fun x : X ↦ TangentSpace I x)]
    [IsContMDiffRiemannianBundle I ∞ E (fun x : X ↦ TangentSpace I x)]
    [IsRiemannianManifold I X]
    (hconv : 0 < convexityRadius X)
    (L : Finset X) (f : X → ℝ) (c : ℝ) (hc : 0 ≤ c) (hLip : ∀ x y, |f x - f y| ≤ c * dist x y)
    (htame : IsTame0 f)
    (δ : ℝ) (hδ : 0 < δ) (hδρ : ENNReal.ofReal δ < convexityRadius X)
    (α : ℝ) (hL : IsGeodesicSample (L : Set X) (superlevel f α) (δ / 4)) :
    IsDiagramLike (diagram0 f) ∧
    IsDiagramLike (ripsDiagram (fun x y : L => dist (x : X) (y : X)) (fun x : L => f x) δ) ∧
    {p : EReal × EReal | (diagram0 f) p ≠ 0}.Finite ∧
    {p : EReal × EReal |
        (ripsDiagram (fun x y : L => dist (x : X) (y : X)) (fun x : L => f x) δ) p ≠ 0}.Finite ∧
    (∀ s t : ℝ, α ≤ s → t ≤ s →
       superRank f s t ≤
         ripsRank (fun x y : L => dist (x : X) (y : X)) (fun x : L => f x) δ
           (s - c * δ) (t - c * δ) ∧
       ripsRank (fun x y : L => dist (x : X) (y : X)) (fun x : L => f x) δ s t ≤
         superRank f (s - c * δ) (t - c * δ)) := by sorry

end PersistClust.Count
Source
Chazal–Guibas–Oudot–Skraba, Persistence-Based Clustering in Riemannian Manifolds, INRIA RR-6968, 2009, pp. 21, proof of Theorem 4.5 (adapting the proof of Theorem 4.4 from [6, §3.1])

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me