Pointwise weight bound for the Gabber–Galil inequality
ProvedDetANN.mgg_pointwise_weight_boundexpander-graphsfourier-analysismargulis-gabber-galil
Let , let be the representative of , and let be the weight of the definition DetANN_MGGOrder. Write , , and , all modulo . For every with ,
This is HLW's term-by-term inequality (15), to which the cosine inequality mgg_cosine_inequality is reduced by applying edge by edge.
Formalization Note. HLW prove (15) only with , which gives the weaker constant (their (16) and Proposition 8.9). They state that "a different choice for and a more careful analysis" yields . This statement is (15) with , the choice for which the bound holds.
Preamble
import Mathlib import Definitions.Def_DetANN_MGGOrder
Formal statement
namespace DetANN
/-- **The local inequality** (HLW06 §8.2, inequality (15) with `α = √2`; Proposition 8.9).
For every `z ≠ 0` in `ℤ_m²`, the weights of the four moves `T₂^{±1}z`, `T₁^{±1}z`, damped by the
cosines of the fixed coordinate, sum to at most `5√2/2`. -/
theorem mgg_pointwise_weight_bound (m : ℕ) [NeZero m] (z : ZMod m × ZMod m) (hz : z ≠ 0) :
|Real.cos (Real.pi * (z.1.valMinAbs : ℝ) / m)| *
(mggWeight (Real.sqrt 2) z (z.1, z.2 + 2 * z.1) +
mggWeight (Real.sqrt 2) z (z.1, z.2 - 2 * z.1)) +
|Real.cos (Real.pi * (z.2.valMinAbs : ℝ) / m)| *
(mggWeight (Real.sqrt 2) z (z.1 + 2 * z.2, z.2) +
mggWeight (Real.sqrt 2) z (z.1 - 2 * z.2, z.2))
≤ 5 * Real.sqrt 2 / 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: inequality (15) with α = √2 (pp. 506–507), Proposition 8.9 and the remark after it (pp. 507–508); Gabber, Galil, Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci. 22 (1981), 407–420