Proof of Lemma 7.1, p.20 — an explicit 16-regular undirected multigraph on with mean-zero contraction
ProvedDetANN.lemma_7_1_graphapproximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . For every power of two , the graph of the proof of Lemma 7.1 on — the Margulis–Gabber–Galil graph on with every occurrence duplicated if , its product with if , and the single vertex with 16 loops if — is a -regular undirected multigraph whose normalized adjacency matrix satisfies
and .
This is the graph content of Lemma 7.1 with the explicit constants , of its proof.
Formalization Note The graph is the definition DetANN.lemma71Nbr; the operation count of Lemma 7.1 is part of the resource bounds of Theorem 1.1, not of this statement.
Differences from the source:
- encoding: a graph on ℤ²_m or ℤ²_m × {0, 1} regarded as a graph on [d] → the same graph transported to Fin (2^k) by a fixed bijection; degree 16 as neighbor lists indexed by Fin 16; reason: Lemma 7.1 asks for a graph on [d]; relabeling vertices changes nothing
- encoding: ‖Wf‖₂ ≤ θ₀‖f‖₂ → Σ_u (Wf)_u² ≤ θ₀² Σ_v f_v²; reason: equivalent for θ₀ ≥ 0
Preamble
import Mathlib import Definitions.Def_DetANN_Multigraph import Definitions.Def_DetANN_MGG
Formal statement
namespace DetANN
/-- **Proof of Lemma 7.1, the graphs** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), Appendix B, p.20; Lemma 7.1, p.17).
For every power of two `d = 2^k`, the explicit graph of the proof of Lemma 7.1 on `[d]` (built from the
Margulis–Gabber–Galil graph) is a `16`-regular undirected multigraph whose normalized adjacency matrix
`W` satisfies `‖W f‖ ≤ θ₀‖f‖` for every mean-zero `f`, with `θ₀ = 5√2/8 < 1`.
**Formalization Note.** This is the graph content of Lemma 7.1 with the explicit constants `Δ = 16`
and `θ₀ = 5√2/8` of its proof; the clause "the neighbor lists can be constructed in `O(d)` arithmetic
operations" is not stated here (the resource bounds of `DetANN.theorem_1_1` account for it).
Regularity is the type `Fin 16` of the neighbor lists. The spectral bound is stated squared. -/
theorem lemma_7_1_graph (k : ℕ) :
0 < theta0 ∧ theta0 < 1 ∧ IsUndirected (lemma71Nbr k) ∧
ContractsMeanZero (adjMatrix (lemma71Nbr k)) theta0 := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Proof of Lemma 7.1, Appendix B, p.20 (PDF p.20); Lemma 7.1, p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.