Fourier-side Gabber–Galil inequality
ProvedDetANN.mgg_fourier_inequalityexpander-graphsfourier-analysismargulis-gabber-galil
Let and , so is well defined for . Write and . For every with ,
This is the frequency-side form of the Gabber–Galil bound. Under the Fourier transform on , the translations by and become the phase factors , and the shears become their inverse transposes. Applied to , the inequality yields the quadratic-form bound mgg_quadratic_form_bound.
Formalization Note. is Mathlib's ZMod.stdAddChar t . As in HLW, the inequality is stated for every , not only for Fourier transforms.
Preamble
import Mathlib
Formal statement
namespace DetANN
/-- **The Fourier-side inequality** (HLW06 §8.2, Theorem 8.7). For every
`F : ℤ_m² → ℂ` with `F(0,0) = 0`, with `ω^t = stdAddChar t`,
`T₂⁻¹z = (z₁, z₂ - 2z₁)` and `T₁⁻¹z = (z₁ - 2z₂, z₂)`. -/
theorem mgg_fourier_inequality (m : ℕ) [NeZero m] (F : ZMod m × ZMod m → ℂ) (hF : F 0 = 0) :
‖∑ z, starRingEnd ℂ (F z) *
(F (z.1, z.2 - 2 * z.1) * (1 + ZMod.stdAddChar (-z.1)) +
F (z.1 - 2 * z.2, z.2) * (1 + ZMod.stdAddChar (-z.2)))‖
≤ 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.2, Theorem 8.7, p. 505