Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Forward bound: copies of DDD of prominence ≥d2\ge d_2≥d2​ inject into the τ\tauτ-window of D′D'D′

Proved
PersistClust.Count.proof_thm_4_8_partition_count_transport_forward

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

clusteringcombinatoricspersistencetopology

Let DDD and D′D'D′ be persistence diagrams in the extended plane R‾×R‾\overline{\mathbb{R}} \times \overline{\mathbb{R}}R×R, i.e. multiplicity functions D,D′:R‾×R‾→N∪{∞}D, D' : \overline{\mathbb{R}} \times \overline{\mathbb{R}} \to \mathbb{N} \cup \{\infty\}D,D′:R×R→N∪{∞} that are diagram-like: every point (b,d)(b,d)(b,d) of positive multiplicity lies strictly off the diagonal, d<bd < bd<b. Write Copies⁡(D)\operatorname{Copies}(D)Copies(D) for the multiset of copies of DDD: for each point ppp it contains D(p)D(p)D(p) copies (p,k)(p,k)(p,k), k<D(p)k < D(p)k<D(p), together with countably many copies of every diagonal point.

Let γ:Copies⁡(D)≃Copies⁡(D′)\gamma : \operatorname{Copies}(D) \simeq \operatorname{Copies}(D')γ:Copies(D)≃Copies(D′) be a multi-bijection (a bijection of copies) satisfying assertions (i)–(iv) of Theorem 4.5 of the source paper at threshold α=cδ\alpha = c\deltaα=cδ and radius r=cδr = c\deltar=cδ: whenever the point of a copy lies in the quadrant QαNEQ^{NE}_\alphaQαNE​ (both coordinates >α> \alpha>α), both coordinates of the point of the matched copy — in either direction of γ\gammaγ — are within rrr in the sense that x≤x′+rx \le x' + rx≤x′+r and x′≤x+rx' \le x + rx′≤x+r in the extended reals (±∞\pm\infty±∞ being close only to itself); whenever the point of a copy lies in the quadrant QαSEQ^{SE}_\alphaQαSE​ (first coordinate >α> \alpha>α, second coordinate ≤α\le \alpha≤α), only the first coordinate of the matched point is guaranteed within rrr, again in either direction.

Fix real numbers c>0c > 0c>0, δ>0\delta > 0δ>0, 0≤d10 \le d_10≤d1​ and d2d_2d2​ with δ<(d2−d1)/(5c)\delta < (d_2 - d_1)/(5c)δ<(d2​−d1​)/(5c), i.e. 5cδ<d2−d15c\delta < d_2 - d_15cδ<d2​−d1​, and a window point τ\tauτ with d1+2cδ<τ<d2−3cδd_1 + 2c\delta < \tau < d_2 - 3c\deltad1​+2cδ<τ<d2​−3cδ. Assume DDD is (d1,d2)(d_1, d_2)(d1​,d2​)-separated: every point of DDD of positive multiplicity lies in the open half-plane Δd1N\Delta^N_{d_1}Δd1​N​ above the line y=x−d1y = x - d_1y=x−d1​, or in Δd2S∩Λd2E\Delta^S_{d_2} \cap \Lambda^E_{d_2}Δd2​S​∩Λd2​E​, where ΔdS={(x,y):y≤x−d}\Delta^S_d = \{(x,y) : y \le x - d\}ΔdS​={(x,y):y≤x−d} is the closed half-plane of prominence at least ddd, ΔdN\Delta^N_dΔdN​ is its open complement, and ΛdE={(x,y):d<x}\Lambda^E_d = \{(x,y) : d < x\}ΛdE​={(x,y):d<x} is the open half-plane of births above ddd.

This lemma is the forward half of the equality that counts the copies of DDD of prominence at least d2d_2d2​ against the copies of D′D'D′ lying in the τ\tauτ-window:

#{(p,k):k<D(p),  p∈Δd2S∩Λd2E}  ≤  #{(p,k):k<D′(p),  p∈ΔτS∩ΛτE},\#\{(p,k) : k < D(p),\; p \in \Delta^S_{d_2} \cap \Lambda^E_{d_2}\} \;\le\; \#\{(p,k) : k < D'(p),\; p \in \Delta^S_{\tau} \cap \Lambda^E_{\tau}\},#{(p,k):k<D(p),p∈Δd2​S​∩Λd2​E​}≤#{(p,k):k<D′(p),p∈ΔτS​∩ΛτE​},

where both counts range over copies (a point together with an index below its multiplicity) and are computed as extended cardinalities of the corresponding copy sets.

The inequality is realized by the map sending a copy (p,k)(p,k)(p,k) of DDD with p∈Δd2S∩Λd2Ep \in \Delta^S_{d_2} \cap \Lambda^E_{d_2}p∈Δd2​S​∩Λd2​E​ to its image γ(p,k)\gamma(p,k)γ(p,k): assertions (i) and (iii) at threshold cδc\deltacδ, together with the window inequality τ<d2−3cδ\tau < d_2 - 3c\deltaτ<d2​−3cδ, place the image point in ΔτS∩ΛτE\Delta^S_\tau \cap \Lambda^E_\tauΔτS​∩ΛτE​; for a source point with second coordinate ≤cδ\le c\delta≤cδ the second coordinate of the image is first bounded by 2cδ2c\delta2cδ using assertion (i) along γ−1\gamma^{-1}γ−1 after bootstrapping the image point into the quadrant QcδNEQ^{NE}_{c\delta}QcδNE​; and γ\gammaγ being a bijection makes the map injective, while diagonal copies are never hit because the image point satisfies y≤x−τy \le x - \tauy≤x−τ with τ>0\tau > 0τ>0.

Formalization Note. All notions live in Definitions.Def_PersistClust_Count_Diagram (namespace PersistClust.Count): Copies, pt, IsDiagramLike, SatisfiesIIV (assertions (i)–(iv) via closeE, at threshold and radius c * δ), IsSeparated, and the regions DeltaS d = {p | p.2 ≤ p.1 - ↑d} (closed) and LamE d = {p | ↑d < p.1} (open). The count is Set.encard of the set of copies q=(p,k)q = (p,k)q=(p,k) with the natural-number index kkk coerced into N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞} and compared strictly against the multiplicity at ppp.

Preamble
import Mathlib
import Definitions.Def_PersistClust_Count_Diagram
Formal statement
namespace PersistClust.Count
theorem proof_thm_4_8_partition_count_transport_forward
    (D D' : EReal × EReal → ℕ∞) (hD : IsDiagramLike D) (hD' : IsDiagramLike D')
    (c δ : ℝ) (hc : 0 < c) (hδ : 0 < δ)
    (γ : Copies D ≃ Copies D') (hγ : SatisfiesIIV γ (c * δ) (c * δ))
    (d₁ d₂ : ℝ) (hd₁ : 0 ≤ d₁) (hδc : δ < (d₂ - d₁) / (5 * c))
    (hsep : IsSeparated D d₁ d₂)
    (τ : ℝ) (hτ₁ : d₁ + 2 * c * δ < τ) (hτ₂ : τ < d₂ - 3 * c * δ) :
    {q : (EReal × EReal) × ℕ | (q.2 : ℕ∞) < D q.1 ∧ q.1 ∈ DeltaS d₂ ∩ LamE d₂}.encard
      ≤ {q : (EReal × EReal) × ℕ | (q.2 : ℕ∞) < D' q.1 ∧ q.1 ∈ DeltaS τ ∩ LamE τ}.encard := by sorry
end PersistClust.Count
Source
Chazal–Guibas–Oudot–Skraba, Persistence-Based Clustering in Riemannian Manifolds, INRIA Research Report 6968 (2009), §4.2, proof of Theorem 4.8 (pp. 21–23): forward half of the transport of the d2d_2d2​-prominence count of DDD to the τ\tauτ-window count of D′D'D′ along the multi-bijection γ\gammaγ of Theorem 4.5 (five-region analysis, regions III–V).

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