Binary words with no four-word zero sum
ProvedTightCoreset2027.Euclidean.binary_code_existsclusteringcoding-theorycoresets
Let be nonnegative integers satisfying . There is a set such that
Addition is coordinatewise modulo two. This is the coding component of Lemma 2.1, providing distinct words and the even-parity cancellations used in its fourth-moment argument. The statement also includes the empty-set case, for which the same construction is valid.
Preamble
import Mathlib.Data.ZMod.Basic import Mathlib.Data.Finset.Powerset import Mathlib.Algebra.BigOperators.Group.Finset.Basic open scoped BigOperators set_option autoImplicit false
Formal statement
namespace TightCoreset2027.Euclidean
theorem binary_code_exists (L q : ℕ) (hcode : q + Nat.choose q 3 < 2 ^ L) :
∃ S : Finset (Fin L → ZMod 2), S.card = q ∧
∀ T ⊆ S, T.card = 4 → ∑ x ∈ T, x ≠ 0 := 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, first paragraph, printed p. 16 / PDF p. 18, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/879.pdf