Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.8, p. 23, with Β§3 p. 12 β€” the algorithm outputs one cluster per point of D₀𝓑 with prominence β‰₯ Ο„ and birth β‰₯ Ο„

Proved
PersistClust.Count.proof_thm_4_8_algorithm_output

by mikedeng1 Β· Oct 8, 2026 Β· Mathlib 0df444a (Lean v4.33.1)

algorithmclusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1persistence-diagramunion-find

Let g∈Rng\in\mathbb R^ng∈Rn, let DDD be a symmetric nΓ—nn\times nnΓ—n matrix with non-negative entries, let Ξ΄β‰₯0\delta\ge0Ξ΄β‰₯0 and Ο„>0\tau>0Ο„>0, and let Οƒ\sigmaΟƒ be any permutation sorting ggg in non-decreasing order. Then the number of clusters output by the clustering algorithm (Procedures 1–2) with processing order Οƒ\sigmaΟƒ equals the number of points qqq of the 000-th persistence diagram D0RΞ΄gD_0\mathcal R^g_\deltaD0​RΞ΄g​ of the upper-star Rips filtration, counted with multiplicity, such that

qxβˆ’qyβ‰₯Ο„andqxβ‰₯Ο„,q_x-q_y\ge\tau\quad\text{and}\quad q_x\ge\tau,qxβ€‹βˆ’qy​β‰₯Ο„andqx​β‰₯Ο„,

the essential points (qx,βˆ’βˆž)(q_x,-\infty)(qx​,βˆ’βˆž) included.

This is the step "the algorithm discards D1RD^{\mathcal R}_1D1R​ and keeps only D2RD^{\mathcal R}_2D2R​" of the main theorem: the union-find procedure with the prominence test gr(e)βˆ’gi<Ο„g_{r(e)}-g_i<\taugr(e)β€‹βˆ’gi​<Ο„ and the output filter gr(e)β‰₯Ο„g_{r(e)}\ge\taugr(e)​β‰₯Ο„ selects exactly the points of the diagram above both thresholds, whatever the tie-breaking of the sort.

Formalization Note The hypothesis Ο„>0\tau>0Ο„>0 is added: with Ο„=0\tau=0Ο„=0 the algorithm may keep equal-valued adjacent peaks whose diagram point has zero persistence and is not counted. The main theorem has Ο„>d1+2cΞ΄>0\tau>d_1+2c\delta>0Ο„>d1​+2cΞ΄>0. The paper asserts this step without proof.

Preamble
import Mathlib
import Definitions.Def_PersistClust_Count_Diagram
import Definitions.Def_PersistClust_Count_Rips
import Definitions.Def_PersistClust_Count_Algorithm
Formal statement
namespace PersistClust.Count

theorem proof_thm_4_8_algorithm_output
    (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 : β„•βˆž) < ripsDiagram Dm g Ξ΄ q.1 ∧
          q.1.2 ≀ q.1.1 - (Ο„ : EReal) ∧ (Ο„ : EReal) ≀ q.1.1}.encard := by sorry

end PersistClust.Count
Source
Chazal, Guibas, Oudot, Skraba, Persistence-Based Clustering in Riemannian Manifolds, INRIA RR-6968 (HAL inria-00389390v1, 2009), p. 23, proof of Theorem 4.8 ("the algorithm discards D^𝓑_1 and keeps only D^𝓑_2"), with p. 12, Β§3 (step 2 and the standard persistence algorithm)
Human review
  • Endorsed by Shuze Chen Β· Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

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