Instability has a common-denominator distance table with an explicit height bound
ProvedStableMSR.Recovery.Supplement.small_instability_tableclusteringcomputational-complexityoptimization
For either perturbation convention, let be a feasible exact- partition on points, with rational distance data and rational stability factor . Choose bounding the magnitudes of the reduced numerators and denominators of every and . The partition is unstable if and only if there exist a distinct feasible competitor and an allowed perturbation at which its cost is at most the cost of . The denominator is common to all entries and its magnitude and every are bounded by . The statement includes equal costs and allows the in-cluster centers to change. This is the real-to-rational certificate step of Lemma C.3 with an explicit bound.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement
theorem small_instability_table (metric : Bool) {n k : ℕ} (d : Point n → Point n → ℚ) (γ : ℚ)
(O : StableMSR.Recovery.Partition n) (hO : Feasible Finset.univ k O)
(H : ℕ) (hH : 3 ≤ H) (hk : k+k ≤ H)
(hb : ∀ i j, (d i j).num.natAbs ≤ H ∧ (d i j).den ≤ H ∧
(γ*d i j).num.natAbs ≤ H ∧ (γ*d i j).den ≤ H) :
¬ ConventionStable metric (fun i j => (d i j : ℝ)) k γ O ↔
∃ (D : ℤ) (z : Point n → Point n → ℤ) (Q : StableMSR.Recovery.Partition n),
D ≠ 0 ∧ D.natAbs ≤ (n*n).factorial * (H^2)^(n*n) ∧
(∀ i j, (z i j).natAbs ≤ (n*n).factorial * (H^2)^(n*n)) ∧
Feasible Finset.univ k Q ∧ Q ≠ O ∧
let p := fun i j => (z i j : ℝ) / D
(if metric then MetricPerturbation (fun i j => (d i j : ℝ)) γ p
else Perturbation (fun i j => (d i j : ℝ)) γ p) ∧ cost p Q ≤ cost p O := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3, pp. 25–26 (bounded rational polyhedron and determinant argument). https://arxiv.org/abs/2611.03547