A stable partition with few large balls has a short distance-order description
ProvedStableMSR.Recovery.FewBallRows.few_ball_seed_completenessalgorithmsclusteringformal-verificationmetric-spaces
For an arbitrary real metric and a stable exact- partition with at most large clusters, there is a string of point indices whose distance comparisons answer every same-cluster query correctly. A single pair realizes the common threshold on all input distances.
Preamble
import Definitions.Def_StableMSR_FewBallRows open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows StableMSR.Recovery.FewBallRows open scoped Classical set_option autoImplicit false set_option maxHeartbeats 1800000 set_option maxRecDepth 10000
Formal statement
theorem StableMSR.Recovery.FewBallRows.few_ball_seed_completeness (x : World) (h : ℕ) (hk : 1 ≤ x.k) (hkn : x.k < x.n) (hh : h < x.k)
(dmet : IsMetricArray x.dist) (e : ℝ) (he : 0 < e) (hlt : e < 1)
(O : Partition x.n) (hs : Stable x.dist x.k (1+e) O)
(hb : (largeClusters x.dist O e).card ≤ h) :
∃u < rows x.n (h+1), FewBallRows.exact O (digitRel x h u) := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1, Branch A, Lemmas 3.3 and 3.8, and the proof of Theorem 4.5 in Appendix A. Distance-oracle implementation and certificate encoding for the Prove2Me formalization.