A small common denominator preserving bounded comparisons of coordinate sums
ProvedStableMSR.Recovery.Supplement.short_sum_rational_representativeclusteringcomputational-complexityoptimization
Let be a real vector with coordinates and let be an integer. There is a vector with a single nonzero integer denominator, with and every at most , which satisfies every weak comparison satisfied by whenever are lists of total length at most and the reduced numerator and denominator of are bounded in magnitude by . Repetitions are allowed. This formulation of the small rational point argument in Lemma C.3 permits simultaneous preservation of equalities, metric triangle inequalities, and comparisons of sums of cluster radii.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement
theorem short_sum_rational_representative {ι : Type} [Fintype ι] (x : ι → ℝ) (H : ℕ) (hH : 1 ≤ H) :
∃ (D : ℤ) (z : ι → ℤ), D ≠ 0 ∧
D.natAbs ≤ (Fintype.card ι).factorial * (H ^ 2) ^ Fintype.card ι ∧
(∀ i, (z i).natAbs ≤ (Fintype.card ι).factorial * (H ^ 2) ^ Fintype.card ι) ∧
∀ (s t : List ι) (q : ℚ), s.length + t.length ≤ H →
q.num.natAbs ≤ H → q.den ≤ H →
(q : ℝ) + (s.map x).sum ≤ (t.map x).sum →
(q : ℝ) + (s.map (fun i => ((z i : ℝ) / D))).sum ≤
(t.map (fun i => ((z i : ℝ) / D))).sum := 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