Lemma 6.1, p.14 — for centered squared Rademacher sums
ProvedDetANN.lemma_6_1approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is an absolute constant with the following property. Let for real coefficients (finitely many) and independent uniform signs , put and , and let be independent copies of . Then for every integer ,
It is the moment estimate that makes the expected potential (24) small.
Differences from the source:
- encoding: independent copies X₁, …, X_L and the expectation → L independent rows of signs σ : Fin L → R → Bool, and the uniform average over all of them; |·|^{2p} written (·)^{2p}; reason: the rows give L independent copies of X; an even power equals the power of the absolute value
Preamble
import Mathlib import Definitions.Def_DetANN_SignedBlocks
Formal statement
namespace DetANN
/-- **Lemma 6.1** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), p.14).
Let `Y = ∑_r a_r σ_r` with independent uniform signs `σ_r`, `v = ∑_r a_r²` and `X = Y² − v`. If
`X₁, …, X_L` are independent copies of `X`, then for every integer `1 ≤ p ≤ L`,
`E|∑_ℓ X_ℓ|^{2p} ≤ (C p L)^p v^{2p}`, where `C` is an absolute constant.
**Formalization Note.** `C > 0` is chosen before the index set `R`, the coefficients, `L` and `p`.
The `L` independent copies are realized by `L` independent rows of signs `σ : Fin L → R → Bool`, and
the expectation is the uniform average over all such `σ`; `|·|^{2p} = (·)^{2p}`. -/
theorem lemma_6_1 :
∃ C : ℝ, 0 < C ∧ ∀ (R : Type) [Fintype R] [DecidableEq R] (a : R → ℝ) (L p : ℕ),
1 ≤ p → p ≤ L →
(Fintype.card (Fin L → R → Bool) : ℝ)⁻¹ *
∑ σ : Fin L → R → Bool,
(∑ ℓ : Fin L, ((∑ r, a r * signOf (σ ℓ r)) ^ 2 - ∑ r, a r ^ 2)) ^ (2 * p) ≤
(C * p * L) ^ p * (∑ r, a r ^ 2) ^ (2 * p) := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Lemma 6.1, p.14 (PDF p.14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.