Lemma 2.1 — discrete projections and a discrepancy bound
ProvedTightCoreset2027.Euclidean.discrete_projections_discrepancyclusteringcomputational-geometrycoresetsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be integers such that . There exist distinct unit vectors and a nonempty finite set with for every . Every projection has a level satisfying . For every integer and every fixed coefficient family ,
The vectors and directions are chosen before the coefficient family. This supplies both the finite projection grid and the common direction required by the error estimate.
Differences from the source:
- encoding: distinct vectors, a finite direction set, and the induced level index → a raw ProjectionFamily satisfying all clauses of ProjectionSpecification; reason: the index is stored with its defining equality; positivity of L makes the grid injective
- encoding: a lower bound on the maximum over V → there exists a direction in V attaining at least the displayed bound; reason: V is finite and nonempty, so the two statements are equivalent
- encoding: indices starting at 1 and levels from 0 through L → Fin q, Fin t and Fin (L+1); reason: bijections preserve every vector, coefficient family, norm and sum
Preamble
import Definitions.Def_TightCoreset2027_Euclidean_projectionModel set_option autoImplicit false
Formal statement
namespace TightCoreset2027.Euclidean
theorem discrete_projections_discrepancy (L q : ℕ) (hL : 1 ≤ L) (hq : 1 ≤ q)
(hcode : q + Nat.choose q 3 < 2 ^ L) :
∃ G : ProjectionFamily L q, ProjectionSpecification G := by sorry
end TightCoreset2027.Euclidean
Source
Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu, STOC 2027 submission #879 (October 2026), Lemma 2.1, Eq. (3)–(4), printed p. 10 / PDF p. 12; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/879.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.