Lemma 14 — Cost and means
ProvedExactKMeans.ProductReduction.lemma_14complexity-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 14 (Cost and means). For any state s ∈ S^b, the partition (Ĉ, −Ĉ) of a selector has means ±µ̂(s). Moreover, both clusters have size bN^12, and the partition has total cost B_2 = B_1 − 2bN^12 r^2 < 4N.
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
- encoding: a selector in ℝ^(2b) → a selector in the first 2b coordinates of ℝ^(2b+1); reason: the extra coordinate is zero, so this is an isometric realization of exactly the same selector
Preamble
import Definitions.Def_ExactKMeans_ProductReduction_Computation open scoped BigOperators Classical open Finset open ExactKMeans.ProductReduction
Formal statement
namespace ExactKMeans.ProductReduction
theorem lemma_14 (p : Parameters) (s : State p) :
mean (selectorPoint p) (prefixSet p s) = mu0 p s ∧
mean (selectorPoint p) (univ \ prefixSet p s) = -mu0 p s ∧
(prefixSet p s).card = p.b * p.N^12 ∧
(univ \ prefixSet p s).card = p.b * p.N^12 ∧
partitionCost p (prefixSet p s) = B2 p ∧ B2 p < 4 * p.N := 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 14, printed p. 31 (PDF 32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.