Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Lemma 7.1, p.20 — an explicit 16-regular undirected multigraph on [2k][2^k][2k] with mean-zero contraction θ0=52/8<1\theta_0=5\sqrt2/8<1θ0​=52​/8<1

Proved
DetANN.lemma_7_1_graph

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let θ0=52/8\theta_0=5\sqrt2/8θ0​=52​/8. For every power of two d=2kd=2^kd=2k, the graph of the proof of Lemma 7.1 on [d][d][d] — the Margulis–Gabber–Galil graph on Zm2\mathbb Z_m^2Zm2​ with every occurrence duplicated if d=m2d=m^2d=m2, its product with {0,1}\{0,1\}{0,1} if d=2m2d=2m^2d=2m2, and the single vertex with 16 loops if d=1d=1d=1 — is a 161616-regular undirected multigraph whose normalized adjacency matrix WWW satisfies

∥Wf∥2≤θ0∥f∥2for every f∈Rd with ∑vf(v)=0,\|Wf\|_2\le\theta_0\|f\|_2\qquad\text{for every }f\in\mathbb R^d\text{ with }\sum_vf(v)=0,∥Wf∥2​≤θ0​∥f∥2​for every f∈Rd with v∑​f(v)=0,

and 0<θ0<10<\theta_0<10<θ0​<1.

This is the graph content of Lemma 7.1 with the explicit constants Δ=16\Delta=16Δ=16, θ0=52/8\theta_0=5\sqrt2/8θ0​=52​/8 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
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me