Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.5, demand routing: prominent and high far south-east copies route injectively under the interleaving

Open
PersistClust.Count.theorem_4_5_demand_routing

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

clusteringpersistencetopological-data-analysis

This is the demand-routing step in the proof of Theorem 4.5 of RR-6968: under a strong ε\varepsilonε-interleaving above α\alphaα between two tame 000-dimensional persistence modules, the off-diagonal copies of the XXX-diagram that cannot be absorbed by the diagonal — prominent copies (points of QαNEQ^{NE}_\alphaQαNE​ admitting no diagonal point ε\varepsilonε-close in both coordinates) and high far south-east copies (birth above α+ε\alpha + \varepsilonα+ε, more than 2ε2\varepsilon2ε above the death) — can be routed injectively into the copies of the YYY-diagram, with prominent copies landing ε\varepsilonε-close in both coordinates and high far south-east copies landing ε\varepsilonε-close in the birth coordinate on points that again lie in QαSEQ^{SE}_\alphaQαSE​.

Formally: for two finite-type modules X,YX, YX,Y strongly ε\varepsilonε-interleaved above α\alphaα, there is an injection FFF from the demanding copies of DX=mult⁡(rX)D_X = \operatorname{mult}(r_X)DX​=mult(rX​) to the copies of DYD_YDY​ such that FFF maps prominent copies to ε\varepsilonε-close copies (both coordinates) and high far south-east copies to south-east copies ε\varepsilonε-close in the birth coordinate.

Together with the assembly child theorem_4_5_matching_assembly — which turns two such routings (one per direction) into the multi-bijection with guarantees (i)–(iv) via a Schröder–Bernstein argument — this yields the gate theorem_4_5_gate_matching. The routing is where the interleaving does its work: prominent XXX-bars must have YYY-partners born and dying within ε\varepsilonε (window inequalities, census counting, image-birth transport), and high far south-east bars must have birth-close south-east partners.

Formalization Note The demand predicates are those of PersistClust_Count_MatchingGate; the modules enter through FiltrationLaw, IsTameModule, and StrongInterleavingAbove as defined in PersistClust_Count_MatchingCensus.

Preamble
import Mathlib
import Definitions.Def_PersistClust_Count_Diagram
import Definitions.Def_PersistClust_Count_FiltrationLaw
import Definitions.Def_PersistClust_Count_MatchingCensus
import Definitions.Def_PersistClust_Count_MatchingGate
Formal statement
import Mathlib
import Definitions.Def_PersistClust_Count_Diagram
import Definitions.Def_PersistClust_Count_FiltrationLaw
import Definitions.Def_PersistClust_Count_MatchingCensus
import Definitions.Def_PersistClust_Count_MatchingGate

namespace PersistClust.Count

theorem theorem_4_5_demand_routing
    {ιX ιY : Type*}
    {stageX : ℝ → Set ιX} {JX : ℝ → ιX → ιX → Prop} {stageY : ℝ → Set ιY} {JY : ℝ → ιY → ιY → Prop}
    (hLawX : FiltrationLaw stageX JX) (hLawY : FiltrationLaw stageY JY)
    (hTameX : IsTameModule stageX JX) (hTameY : IsTameModule stageY JY)
    {α ε : ℝ} (hε : 0 ≤ ε)
    (hIL : StrongInterleavingAbove stageX JX stageY JY hLawX hLawY α ε hε) :
    ∃ F : {a : offD (mult (rankFn stageX JX)) // DemandsOff α ε a}
           → offD (mult (rankFn stageY JY)),
      Function.Injective F ∧
      (∀ a, PromQNE α ε a.1 → CloseCopy2 ε a.1 (F a)) ∧
      (∀ a, offPt a.1 ∈ QSE α → CloseCopy1 ε a.1 (F a) ∧ offPt (F a) ∈ QSE α) := by sorry

end PersistClust.Count
Source
Chazal–Guibas–Oudot–Skraba, Persistence-Based Clustering in Riemannian Manifolds, INRIA RR-6968, 2009, pp. 18–21, the partner-routing construction in the proof of Theorem 4.5; stated with the demand predicates of the assembly step

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