Cosine form of the Gabber–Galil inequality
ProvedDetANN.mgg_cosine_inequalityexpander-graphsfourier-analysismargulis-gabber-galil
Let , and let be the representative of . With and : for every with and ,
This is the real form of the Fourier-side inequality mgg_fourier_inequality, obtained by taking moduli and using . The cosine factors are small at high frequencies, and that is where the bound gains on the trivial constant .
Formalization Note. does not depend on which integer representative of is used, so the choice of valMinAbs is immaterial. The hypothesis is kept so that the statement matches HLW's Theorem 8.8. However, the Lean proof submitted for this statement never uses it, and Lean flags it as an unused variable. So the inequality holds for every real-valued with , not only for nonnegative ones.
Preamble
import Mathlib
Formal statement
namespace DetANN
/-- **The real cosine inequality** (HLW06 §8.2, Theorem 8.8, inequality (13)).
For nonnegative `G` on `ℤ_m²` with `G(0,0) = 0`, with `z̃ᵢ` the representative in `(-m/2, m/2]`. -/
theorem mgg_cosine_inequality (m : ℕ) [NeZero m] (G : ZMod m × ZMod m → ℝ)
(hG : ∀ z, 0 ≤ G z) (hG0 : G 0 = 0) :
∑ z, 2 * G z * (G (z.1, z.2 - 2 * z.1) * |Real.cos (Real.pi * (z.1.valMinAbs : ℝ) / m)| +
G (z.1 - 2 * z.2, z.2) * |Real.cos (Real.pi * (z.2.valMinAbs : ℝ) / m)|)
≤ 5 * Real.sqrt 2 / 2 * ∑ z, G 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.8, eq. (13), p. 506