Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.5 copy-routing predicates: off-diagonal copies, closeness, and demand routing

Definition
PersistClust_Count_MatchingGate

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

clusteringpersistencetopological-data-analysis

This file defines the copy-level bookkeeping used in the multi-bijection construction of Theorem 4.5 (RR-6968, §4, pp. 18–21).

A persistence diagram is represented as a function DDD from the extended plane [−∞,+∞]2[-\infty,+\infty]^2[−∞,+∞]2 to the cardinals. Its off-diagonal part carries copies: offD D is the type of pairs (p,k)(p,k)(p,k) with k<D(p)k < D(p)k<D(p), one copy for each unit of multiplicity of each off-diagonal point ppp, and offPt returns the point ppp a copy stands for. Two off-diagonal copies are ε\varepsilonε-close (CloseCopy2) when both coordinates of their points are within ε\varepsilonε in the extended-real closeness of the report (where ±∞\pm\infty±∞ is close only to itself), and birth-close (CloseCopy1) when only the birth (first) coordinate is.

The demand predicate DemandsOff identifies the off-diagonal copies that cannot be absorbed by the diagonal at radius ε\varepsilonε: prominent copies (PromQNE) — points strictly above the level α\alphaα in both coordinates admitting no diagonal point ε\varepsilonε-close in both coordinates — and high far south-east copies — birth above α+ε\alpha + \varepsilonα+ε and death more than 2ε2\varepsilon2ε below the birth. For such copies, the clause of Theorem 4.5 at a nearby diagonal slot would force a second-coordinate match that the geometry forbids, so they must be routed to genuine off-diagonal partners; all other off-diagonal copies can be sent to the diagonal.

Formalization Note These predicates are the hypotheses under which the standalone assembly theorem theorem_4_5_matching_assembly produces the multi-bijection; the definitions are pure declarations, verified to compile in the platform's default environment.

Definition code
import Mathlib
import Definitions.Def_PersistClust_Count_Diagram

namespace PersistClust.Count

/-! ### Copy-routing predicates for the multi-bijection assembly (Theorem 4.5)

The bookkeeping layer between an interleaving of two persistence modules and the
multi-bijection of Theorem 4.5: off-diagonal copies of a diagram, the copy-closeness
predicates, and the demand predicates describing which off-diagonal copies must be
routed to genuine off-diagonal partners (as opposed to being absorbed by the diagonal). -/

/-- The off-diagonal copies of a diagram `D`: pairs `(p, k)` with `k < D p`, i.e. the left
summand of `Copies D`. -/
abbrev offD (D : EReal × EReal → ℕ∞) :=
  {q : (EReal × EReal) × ℕ // (q.2 : ℕ∞) < D q.1}

/-- The off-diagonal point of the extended plane that a copy stands for. -/
abbrev offPt {D : EReal × EReal → ℕ∞} (q : offD D) : EReal × EReal := q.1.1

/-- ε-closeness of two off-diagonal copies in both coordinates. -/
def CloseCopy2 (ε : ℝ) {D D' : EReal × EReal → ℕ∞} (a : offD D) (b : offD D') : Prop :=
  closeE (offPt a).1 (offPt b).1 ε ∧ closeE (offPt a).2 (offPt b).2 ε

/-- ε-closeness of two off-diagonal copies in the first (birth) coordinate only. -/
def CloseCopy1 (ε : ℝ) {D D' : EReal × EReal → ℕ∞} (a : offD D) (b : offD D') : Prop :=
  closeE (offPt a).1 (offPt b).1 ε

/-- `a` is a prominent copy: its point lies in the quadrant `Q^NE_α` strictly above the
level `α` in both coordinates, and it cannot be absorbed by the diagonal at radius `ε`
(no diagonal point is ε-close to it in both coordinates). -/
def PromQNE (α ε : ℝ) {D : EReal × EReal → ℕ∞} (a : offD D) : Prop :=
  offPt a ∈ QNE α ∧ ¬ (∃ x : EReal, closeE (offPt a).1 x ε ∧ closeE (offPt a).2 x ε)

/-- The copies the diagonal cannot absorb at radius `ε`, which therefore need genuine
off-diagonal partners: prominent QNE copies (non-killable by definition), and "high far"
QSE copies — birth above `α + ε` and more than `2ε` above the diagonal. For such a QSE
copy any ε-birth-close diagonal slot sits above `α`, so the slot's `pt = (x,x)` is a
QNE point and clause (ii) of Theorem 4.5 would additionally demand ε-closeness in the
death coordinate, which `b − d > 2ε` forbids. All other off-diagonal copies kill to the
diagonal: non-prominent QNE and near-diagonal QSE by their `∃x`-witnesses, low QSE
(`b ≤ α + ε`) at `x = b − ε ≤ α`, and QSW anywhere below. -/
def DemandsOff (α ε : ℝ) {D : EReal × EReal → ℕ∞} (a : offD D) : Prop :=
  PromQNE α ε a ∨
  (offPt a ∈ QSE α ∧ α + ε < (offPt a).1 ∧ 2 * ε < (offPt a).1 - (offPt a).2)

end PersistClust.Count
Source
Chazal–Guibas–Oudot–Skraba, Persistence-Based Clustering in Riemannian Manifolds, INRIA RR-6968, 2009, pp. 18–21, the copy and multi-bijection bookkeeping of §4 (Definitions 4.1 and the proof of Theorem 4.5)

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