Partial order and edge weight on (HLW §8)
DefinitionDetANN_MGGOrderexpander-graphsfourier-analysismargulis-gabber-galil
Let . Represent each residue by , so is the distance from to on the cycle . For , say that is farther out than , written , if
For , the edge weight is
These are the partial order and the weight function of Hoory–Linial–Wigderson's proof of the Gabber–Galil bound. Since is a strict partial order, , which is HLW's identity (14). The weight is what makes the term-by-term analysis of that proof possible.
Formalization Note. HLW use representatives in , while Mathlib's ZMod.valMinAbs takes values in . Only absolute values enter, and they agree, so the order is the same. mggFarther z w means , and mggWeight α z w is .
Definition code
import Mathlib
namespace DetANN
/-- Coordinatewise "strictly farther from the origin" on `ℤ_m²`, measuring each coordinate by
its distance to `0` (absolute value of the representative in `(-m/2, m/2]`).
Source: Hoory–Linial–Wigderson, *Expander graphs and their applications*, Bull. AMS 43 (2006), §8.2,
the partial order defined after Proposition 8.9. -/
def mggFarther {m : ℕ} (z w : ZMod m × ZMod m) : Prop :=
z.1.valMinAbs.natAbs ≤ w.1.valMinAbs.natAbs ∧ z.2.valMinAbs.natAbs ≤ w.2.valMinAbs.natAbs ∧
(z.1.valMinAbs.natAbs < w.1.valMinAbs.natAbs ∨ z.2.valMinAbs.natAbs < w.2.valMinAbs.natAbs)
open Classical in
/-- The edge weight `γ(z, w)` of HLW §8.2: `α⁻¹` if `w` is farther out than `z`, `α` if `w`
is nearer, and `1` otherwise. -/
noncomputable def mggWeight (α : ℝ) {m : ℕ} (z w : ZMod m × ZMod m) : ℝ :=
if mggFarther z w then α⁻¹ else if mggFarther w z then α else 1
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: the weight γ and identity (14) on p. 506; the partial order on p. 508.