Realizing a binary code as a joint-discrepancy projection family
ProvedTightCoreset2027.Euclidean.projection_family_of_binary_codeclusteringcoresetsdiscrepancy
Let , and let consist of distinct binary words with no four distinct words summing to zero. There are distinct unit vectors and a nonempty finite set of vectors of squared norm two. For each and , an integer satisfies
For every and every , one common direction satisfies
This is the geometric and moment component of Lemma 2.1 after its initial code selection. The family depends only on the supplied code, before the coefficients are chosen.
Preamble
import Definitions.Def_TightCoreset2027_Euclidean_projectionModel open scoped BigOperators set_option autoImplicit false
Formal statement
namespace TightCoreset2027.Euclidean
theorem projection_family_of_binary_code (L q : ℕ) (hL : 1 ≤ L) (hq : 1 ≤ q)
(S : Finset (Fin L → ZMod 2)) (hS : S.card = q)
(hfour : ∀ T ⊆ S, T.card = 4 → ∑ x ∈ T, x ≠ 0) :
∃ G : ProjectionFamily L q, ProjectionSpecification G := by sorry
end TightCoreset2027.EuclideanSource
Hu–Huang–Li–Xu, Tight Coreset Bounds for (k,z)-Clustering in Euclidean and Doubling Metrics, STOC 2027 submission #879, §2.4, proof of Lemma 2.1 after the greedy construction, Eqs. (15)–(16), printed pp. 16–18 / PDF pp. 18–20, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/879.pdf