Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Procedure 1 with threshold τ outputs exactly the τ-prominent barcode pairs

Proved
PersistClust.Count.alg_numclust_eq_barcode

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

algorithmsclusteringcombinatoricspersistence

Let L={gi}L=\{g_i\}L={gi​} be a finite point cloud with vertex values ggg, let DmD_mDm​ be a symmetric non-negative distance matrix, δ≥0\delta\ge 0δ≥0 a scale for the Rips graph RδR_\deltaRδ​, τ>0\tau>0τ>0 a prominence threshold, and σ\sigmaσ a sort order of ggg (a permutation with g(σ0)≤⋯≤g(σn−1)g(\sigma_0)\le\dots\le g(\sigma_{n-1})g(σ0​)≤⋯≤g(σn−1​)).

Procedure 1 of the source paper processes the points in decreasing order of ggg with a union-find structure whose entries are trees rooted at local maxima of ggg in RδR_\deltaRδ​. While vertex iii is processed: if no processed Rips-neighbour exists, iii starts a new entry (a peak); otherwise iii joins the entry of its highest processed neighbour, every neighbouring entry whose root rrr satisfies gr−gi<τg_r - g_i < \taugr​−gi​<τ (prominence less than τ\tauτ at the current level) is merged into it, and finally the whole entry is merged into the neighbouring entry with the highest root whenever its own root is not τ\tauτ-prominent. The algorithm outputs the number numClusters of final entries whose root satisfies gr≥τg_r\ge\taugr​≥τ.

Let ripsBarcode(g,Dm,δ,σ)\text{ripsBarcode}(g,D_m,\delta,\sigma)ripsBarcode(g,Dm​,δ,σ) be the elder-rule barcode of the same filtration: the multiplicity function of the persistence pairs (gr,gi)(g_r, g_i)(gr​,gi​) (birth at a peak, death by merging into an older component) with the immortal classes at (gr,−∞)(g_r, -\infty)(gr​,−∞). The theorem states that the algorithm outputs exactly the number of barcode points of prominence at least τ\tauτ born above level τ\tauτ:

numClusters⁡(g,Dm,δ,τ,σ)  =  #{ (b,d,k)  :  k<ripsBarcode(b,d),    d≤b−τ,    τ≤b }.\operatorname{numClusters}(g, D_m, \delta, \tau, \sigma) \;=\; \#\{\,(b,d,k)\;:\; k < \text{ripsBarcode}(b,d),\;\; d\le b-\tau,\;\; \tau\le b\,\}.numClusters(g,Dm​,δ,τ,σ)=#{(b,d,k):k<ripsBarcode(b,d),d≤b−τ,τ≤b}.

Immortal points (b,−∞)(b,-\infty)(b,−∞) always have infinite prominence and contribute exactly when b≥τb\ge\taub≥τ. This is the combinatorial correctness of the τ\tauτ-thresholded merges: they kill exactly the non-τ\tauτ-prominent pairs, which is the step of the proof of Theorem 4.8 where the paper states that the algorithm discards the part D1RD_1^RD1R​ of the Rips diagram and keeps the part D2RD_2^RD2R​ located in ΔτS∩ΛτE\Delta^S_\tau\cap\Lambda^E_\tauΔτS​∩ΛτE​.

Formalization Note. numClusters is defined in Definitions.Def_PersistClust_Count_Algorithm; ripsBarcode g Dm δ σ in Definitions.Def_PersistClust_Count_AlgBarcode (which must be imported). The region count is the cardinality of the set of copies (b,d,k)(b,d,k)(b,d,k) with kkk below the barcode multiplicity; the birth condition is the closed inequality τ≤b\tau\le bτ≤b.

Preamble
import Mathlib
import Definitions.Def_PersistClust_Count_Algorithm
import Definitions.Def_PersistClust_Count_AlgBarcode
Formal statement
namespace PersistClust.Count
theorem alg_numclust_eq_barcode
    (n : ℕ) (g : Fin n → ℝ) (Dm : Fin n → Fin n → ℝ)
    (hDm : ∀ i j, Dm i j = Dm j i) (hDm0 : ∀ i j, 0 ≤ Dm i j)
    (δ τ : ℝ) (hδ : 0 ≤ δ) (hτ : 0 < τ)
    (σ : Fin n ≃ Fin n) (hσ : IsSortOrder g σ) :
    (numClusters g Dm δ τ σ : ℕ∞)
      = {q : (EReal × EReal) × ℕ | (q.2 : ℕ∞) < ripsBarcode g Dm δ σ q.1 ∧
          q.1.2 ≤ q.1.1 - (τ : EReal) ∧ (τ : EReal) ≤ q.1.1}.encard := by sorry
end PersistClust.Count
Source
Chazal\u2013Guibas\u2013Oudot\u2013Skraba, Persistence-Based Clustering in Riemannian Manifolds, INRIA Research Report 6968 (2009), \u00a73 (Procedure 1 with Procedure 2, pp. 17\u201318) and \u00a74.2, proof of Theorem 4.8 (pp. 21\u201323): the algorithm discards D1RD_1^RD1R​ and keeps only D2R⊂ΔτS∩ΛτED_2^R\subset\Delta^S_\tau\cap\Lambda^E_\tauD2R​⊂ΔτS​∩ΛτE​.

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