Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
PersistClust.Count.proof_thm_4_8_partition_count_transport_reverse

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 reverse 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}\} \;\ge\; \#\{(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 D′D'D′ with p∈ΔτS∩ΛτEp \in \Delta^S_\tau \cap \Lambda^E_\taup∈ΔτS​∩ΛτE​ to its preimage γ−1(p,k)\gamma^{-1}(p,k)γ−1(p,k): assertions (i), (ii) and (iv) at threshold cδc\deltacδ, together with the membership p2≤p1−τp_2 \le p_1 - \taup2​≤p1​−τ, force the preimage point qqq to satisfy q2≤q1−(τ−2cδ)q_2 \le q_1 - (\tau - 2c\delta)q2​≤q1​−(τ−2cδ), hence q∉Δd1Nq \notin \Delta^N_{d_1}q∈/Δd1​N​ because d1+2cδ<τd_1 + 2c\delta < \taud1​+2cδ<τ; a diagonal preimage copy is excluded since its equal coordinates together with p2≤p1−τp_2 \le p_1 - \taup2​≤p1​−τ would force τ≤2cδ\tau \le 2c\deltaτ≤2cδ, contradicting τ>d1+2cδ≥2cδ\tau > d_1 + 2c\delta \ge 2c\deltaτ>d1​+2cδ≥2cδ. The preimage point carries a copy of DDD and, since DDD is (d1,d2)(d_1, d_2)(d1​,d2​)-separated and does not lie in Δd1N\Delta^N_{d_1}Δd1​N​, it must lie in Δd2S∩Λd2E\Delta^S_{d_2} \cap \Lambda^E_{d_2}Δd2​S​∩Λd2​E​. Injectivity of γ−1\gamma^{-1}γ−1 makes the map injective.

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_reverse
    (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 τ ∩ LamE τ}.encard
      ≤ {q : (EReal × EReal) × ℕ | (q.2 : ℕ∞) < D q.1 ∧ q.1 ∈ DeltaS d₂ ∩ LamE d₂}.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. 22–23): reverse 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 (separation into Δd1N\Delta^N_{d_1}Δd1​N​ versus Δd2S∩Λd2E\Delta^S_{d_2} \cap \Lambda^E_{d_2}Δd2​S​∩Λd2​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