Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Geometric interleaving (corrected): superlevel and Rips filtrations are cδ-interleaved above α in box-expansion rank form

Proved
PersistClust.Count.theorem_4_5_interleaving_corrected

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

clusteringpersistencetopological-data-analysis

This is the corrected form of the geometric ingredient in the proof of Theorem 4.5 (p. 21), which adapts the proof of Theorem 4.4 of [6, §3.1].

Let XXX be a Riemannian manifold of positive convexity radius, f:X→Rf : X \to \mathbb Rf:X→R tame (IsTame0) and ccc-Lipschitz, and LLL a finite geodesic (δ/4)(\delta/4)(δ/4)-sample of the superlevel set Fα=f−1([α,∞))F^\alpha = f^{-1}([\alpha,\infty))Fα=f−1([α,∞)), with 0<δ0 < \delta0<δ below the convexity radius. Then the superlevel-set filtration {Fβ}\{F^\beta\}{Fβ} of fff and the upper-star Rips filtration {Rδf(Lβ)}\{\mathcal R^f_\delta(L^\beta)\}{Rδf​(Lβ)} of the sample are both genuine 0-dimensional persistence filtrations (their stage families decrease and their join relations are the component equivalences — the FiltrationLaw conjuncts), their 0-th persistence diagrams are diagram-like with finite off-diagonal support, and the two filtrations are strongly cδc\deltacδ-interleaved above α\alphaα. In rank form this yields the box-expansion inequalities: for all s≥t+2cδs \ge t + 2c\deltas≥t+2cδ with t≥αt \ge \alphat≥α,

superRank⁡f(s,t)≤ripsRank⁡δ(s−cδ, t+cδ),ripsRank⁡δ(s,t)≤superRank⁡f(s−cδ, t+cδ),\operatorname{superRank} f(s,t) \le \operatorname{ripsRank}_\delta(s-c\delta,\,t+c\delta), \qquad \operatorname{ripsRank}_\delta(s,t) \le \operatorname{superRank} f(s-c\delta,\,t+c\delta),superRankf(s,t)≤ripsRankδ​(s−cδ,t+cδ),ripsRankδ​(s,t)≤superRankf(s−cδ,t+cδ),

where superRank⁡f(s,t)\operatorname{superRank} f(s,t)superRankf(s,t) is the number of path components of FtF^tFt meeting FsF^sFs and ripsRank⁡δ(s,t)\operatorname{ripsRank}_\delta(s,t)ripsRankδ​(s,t) is the number of connected components of the Rips graph Rδ(Lt)R_\delta(L^t)Rδ​(Lt) meeting LsL^sLs.

This is the reusable geometric lemma for Theorem 4.5; its conclusion is exactly the hypothesis set of the corrected algebraic child, with rX=superRank⁡fr_X = \operatorname{superRank} frX​=superRankf, rY=ripsRank⁡δr_Y = \operatorname{ripsRank}_\deltarY​=ripsRankδ​ and ε=cδ\varepsilon = c\deltaε=cδ.

Formalization Note. The inequalities are asserted only in the box s≥t+2cδs \ge t + 2c\deltas≥t+2cδ, t≥αt \ge \alphat≥α, the region where the interleaving maps factor and hence genuinely constrain the ranks. 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 falsified at s=t=αs = t = \alphas=t=α by elementary examples on X=RX = \mathbb RX=R (it probes ranks below the sampled level α\alphaα); the box-expansion form avoids this.

Preamble
import Mathlib
import Definitions.Def_PersistClust_Count_Setting
import Definitions.Def_PersistClust_Count_Diagram
import Definitions.Def_PersistClust_Count_Rips
import Definitions.Def_PersistClust_Count_FiltrationLaw
open Bundle
open scoped ContDiff Manifold
Formal statement
namespace PersistClust.Count

theorem theorem_4_5_interleaving_corrected
    {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)) :
    FiltrationLaw (superlevel f) (fun t => JoinedIn (superlevel f t)) ∧
    FiltrationLaw (fun t => {i | t ≤ (fun x : L => f x) i})
      (ripsJoined (fun x y : L => dist (x : X) (y : X)) (fun x : L => f x) δ) ∧
    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 : ℝ, t + 2 * (c * δ) ≤ s → α ≤ t →
       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. 20–21, Theorem 4.5 (proof via Theorem 4.4 of Chazal–Oudot, Geometric Inference for Probability Measures, [6, §3.1]); https://hal.inria.fr/inria-00389352

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