Lemma 16 — Distances between reference centers
ProvedExactKMeans.ProductReduction.lemma_16complexity-theorycomputational-geometryp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the Section 5 normalization, let a,b≥1, ab≥2, and let every color class have the same odd size t≥3; N=abt. All construction constants and point families are those of Definitions 3–5 and equations (7)–(20).
Lemma 16. For any reference center µ̂±_i(s) at states s ∈ S^b, we have • the distance between µ̂±_i(s) and the zero-state µ̂±_i(0) is at most rtα; • the distance between µ̂±_i(s) and any other zero-state-reference center of the different selector i′ is at least |i − i′|h − rtα.
Differences from the source:
- encoding: one-based selector/color indices and centered state integers → Fin indices with source i=i.val+1 and state s=s.val−(t−1)/2; reason: these are bijective reindexings; odd t makes the middle state zero
- encoding: point multisets, sums, and nearest unrestricted centers → indexed occurrences and lists, with unit-weight published k-means optimum and finite minimum squared distances; reason: each occurrence is counted once; all center families used here are nonempty, and at least one center is allowed
Preamble
import Definitions.Def_ExactKMeans_ProductReduction_Computation open scoped BigOperators Classical open Finset open ExactKMeans.ProductReduction
Formal statement
namespace ExactKMeans.ProductReduction
theorem lemma_16 (p : Parameters) (i : Fin p.a) (s : State p) (sg : Bool) :
‖reference p i s sg - reference p i (zeroState p) sg‖ ≤ p.r * p.t * p.alpha ∧
∀ (j : Fin p.a) (sg' : Bool), i ≠ j →
|(i.val : ℝ) - j.val| * 4 - p.r * p.t * p.alpha ≤
‖reference p i s sg - reference p j (zeroState p) sg'‖ := by sorry
end ExactKMeans.ProductReduction
Source
Bai, Fomin, Xu (2026), Exact Euclidean k-Means: Faster in the Plane, Hard Beyond It, held STOC 2027 submission; SHA-256 89f18334320ba73627305c6f8870ae70fef423ca012f8b71a3052e407c7e62ec, Lemma 16, printed p. 36 (PDF 37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.