Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Gabber–Galil quadratic-form bound on Zm2\mathbb Z_m^2Zm2​

Proved
DetANN.mgg_quadratic_form_bound

by milia · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

expander-graphsfourier-analysismargulis-gabber-galil

Let m≥1m\ge1m≥1. Write T1(x,y)=(x+2y, y)T_1(x,y)=(x+2y,\,y)T1​(x,y)=(x+2y,y), T2(x,y)=(x, y+2x)T_2(x,y)=(x,\,y+2x)T2​(x,y)=(x,y+2x), e1=(1,0)e_1=(1,0)e1​=(1,0) and e2=(0,1)e_2=(0,1)e2​=(0,1), all modulo mmm. For every f:Zm2→Rf:\mathbb Z_m^2\to\mathbb Rf:Zm2​→R with ∑zf(z)=0\sum_z f(z)=0∑z​f(z)=0,

∣∑z∈Zm2f(z)[f(T1z)+f(T1z+e1)+f(T2z)+f(T2z+e2)]∣≤522∑z∈Zm2f(z)2.\Bigl|\sum_{z\in\mathbb Z_m^2} f(z)\bigl[f(T_1z)+f(T_1z+e_1)+f(T_2z)+f(T_2z+e_2)\bigr]\Bigr|\le\frac{5\sqrt2}{2}\sum_{z\in\mathbb Z_m^2} f(z)^2.​z∈Zm2​∑​f(z)[f(T1​z)+f(T1​z+e1​)+f(T2​z)+f(T2​z+e2​)]​≤252​​z∈Zm2​∑​f(z)2.

The four maps are the forward moves of the 8-regular Margulis–Gabber–Galil graph, and the left side is half the quadratic form ⟨f,Af⟩\langle f,Af\rangle⟨f,Af⟩ of its adjacency matrix AAA. So the statement bounds every nontrivial eigenvalue of AAA by 525\sqrt252​ in absolute value. That is the Gabber–Galil bound behind the milestone mgg_spectral_bound.

Formalization Note. HLW's Theorem 8.3 is printed one-sided. It is stated here with an absolute value, which the bound on ∥Wf∥\|Wf\|∥Wf∥ requires because it must also control the most negative eigenvalue. This two-sided form is what HLW's argument establishes, since their Theorem 8.7 bounds a modulus.

Preamble
import Mathlib
Formal statement
namespace DetANN

/-- **The MGG quadratic-form bound** (HLW06 §8, Theorem 8.3, two-sided form; [GG81]).
For mean-zero `f` on `ℤ_m²`, the sum of `f(z)` times the four forward MGG neighbours
`T₁z, T₁z + e₁, T₂z, T₂z + e₂` is at most `(5√2/2)‖f‖²` in absolute value. -/
theorem mgg_quadratic_form_bound (m : ℕ) [NeZero m] (f : ZMod m × ZMod m → ℝ)
    (hf : ∑ z, f z = 0) :
    |∑ z, f z * (f (z.1 + 2 * z.2, z.2) + f (z.1 + (2 * z.2 + 1), z.2) +
        f (z.1, z.2 + 2 * z.1) + f (z.1, z.2 + (2 * z.1 + 1)))|
      ≤ 5 * Real.sqrt 2 / 2 * ∑ z, f z ^ 2 := by sorry

end DetANN
Source
Hoory, Linial, Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439–561, https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/, §8, Theorem 8.3, eq. (12), p. 504 (two-sided form); Gabber, Galil, Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci. 22 (1981), 407–420; Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission, Appendix B, p.20

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