Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Cosine form of the Gabber–Galil inequality

Proved
DetANN.mgg_cosine_inequality

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

expander-graphsfourier-analysismargulis-gabber-galil

Let m≥1m\ge1m≥1, and let u~∈(−m/2,m/2]\tilde u\in(-m/2,m/2]u~∈(−m/2,m/2] be the representative of u∈Zmu\in\mathbb Z_mu∈Zm​. With T1−1z=(z1−2z2, z2)T_1^{-1}z=(z_1-2z_2,\,z_2)T1−1​z=(z1​−2z2​,z2​) and T2−1z=(z1, z2−2z1)T_2^{-1}z=(z_1,\,z_2-2z_1)T2−1​z=(z1​,z2​−2z1​): for every G:Zm2→RG:\mathbb Z_m^2\to\mathbb RG:Zm2​→R with G≥0G\ge0G≥0 and G(0,0)=0G(0,0)=0G(0,0)=0,

∑z∈Zm22G(z)[G(T2−1z) ∣cos⁡(πz~1/m)∣+G(T1−1z) ∣cos⁡(πz~2/m)∣]≤522∑z∈Zm2G(z)2.\sum_{z\in\mathbb Z_m^2}2G(z)\Bigl[G(T_2^{-1}z)\,\bigl|\cos(\pi\tilde z_1/m)\bigr|+G(T_1^{-1}z)\,\bigl|\cos(\pi\tilde z_2/m)\bigr|\Bigr]\le\frac{5\sqrt2}{2}\sum_{z\in\mathbb Z_m^2}G(z)^2.z∈Zm2​∑​2G(z)[G(T2−1​z)​cos(πz~1​/m)​+G(T1−1​z)​cos(πz~2​/m)​]≤252​​z∈Zm2​∑​G(z)2.

This is the real form of the Fourier-side inequality mgg_fourier_inequality, obtained by taking moduli and using ∣1+ω−t∣=2∣cos⁡(πt/m)∣|1+\omega^{-t}|=2|\cos(\pi t/m)|∣1+ω−t∣=2∣cos(πt/m)∣. The cosine factors are small at high frequencies, and that is where the bound gains on the trivial constant 444.

Formalization Note. ∣cos⁡(πu~/m)∣|\cos(\pi\tilde u/m)|∣cos(πu~/m)∣ does not depend on which integer representative of uuu is used, so the choice of valMinAbs is immaterial. The hypothesis G≥0G\ge0G≥0 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 GGG with G(0,0)=0G(0,0)=0G(0,0)=0, 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

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