8 The Margulis construction

Construction 151 8.1, Margulis \(8\)-regular graph

On \(V=\mathbb {Z}_n\times \mathbb {Z}_n\), with \(T_1=\left(\begin{smallmatrix} 1 & 2 \\ 0 & 1 \end{smallmatrix}\right)\), \(T_2=\left(\begin{smallmatrix} 1 & 0 \\ 2 & 1 \end{smallmatrix}\right)\), \(e_1,e_2\) the standard basis, join \(v\) to \(T_1v,T_2v,T_1v+e_1,T_2v+e_2\) and the four inverses; an \(8\)-regular graph.

Definition 152 8.4, Character of a finite abelian group

✓

A character of \(H\) is a homomorphism \(\chi :H\to \mathbb {C}^*\). For \(H=\mathbb {Z}_n^2\), \(\chi _b(a)=\omega ^{a_1b_1+a_2b_2}\) with \(\omega =e^{2\pi i/n}\).

Proposition 153 8.5, Characters form an orthonormal basis

✓

A finite abelian \(H\) has \(|H|\) characters forming an orthonormal basis; every \(f\) has a unique Fourier expansion \(f=\sum _x\hat f(x)\chi _x\).

Definition 154 Fourier transform on \(\mathbb {Z}_n^2\)

\(\hat f(x)=\sum _b\overline{f(b)}\, \omega ^{b_1x_1+b_2x_2}\).

Proposition 155 8.6, Fourier properties

✓

(a) \(\sum _af(a)=0\iff \hat f(0)=0\); (b) \(\langle f,g\rangle =\frac1{n^2}\langle \hat f,\hat g\rangle \) (Parseval); (d) inversion; (e) under an affine change \(g(x)= f(Ax+b)\), \(\hat g(y)=\omega ^{-\langle A^{-1}b,y\rangle }\hat f((A^{-1})^\top y)\).

Theorem 156 8.2, Margulis graph is an expander (Gabber–Galil)

\(\lambda (G_n)\le 5\sqrt2{\lt}8\) for every \(n\).

Proof ▶

By the variational restatement (Theorem 157) it suffices to bound a quadratic form; passing to Fourier coefficients (Theorem 159) and to nonnegative functions (Theorem 160) yields the bound (in a form \({\lt}8\)).

Theorem 157 Variational restatement of 8.2

It suffices to show: if \(\sum _xf(x)=0\) then \(\sum _{(x,y)\in E}f(x)f(y)\le \tfrac {5\sqrt2}2\sum f^2(x)\).

Proof ▶

This is the variational characterization of \(\lambda \) for the \(8\)-regular graph \(G_n\); writing out the edge structure gives Theorem 158.

Theorem 158 8.3, Edge-expansion inequality

For \(\sum _zf(z)=0\), \(\sum _zf(z)[f(T_1z)+f(T_1z+e_1)+f(T_2z)+f(T_2z+e_2)]\le \tfrac {5\sqrt2}2\sum f^2\).

Proof ▶

Writing out the four neighbours of \(z\), this is reduced to the Fourier form Theorem 159.

Theorem 159 8.7, Fourier restatement

For \(F\) with \(F(0,0)=0\), \(\bigl|\sum _z\overline{F(z)}[F(T_2^{-1}z)(1+\omega ^{-z_1})+F(T_1^{-1}z)(1+\omega ^{-z_2})]\bigr| \le \tfrac {5\sqrt2}2\sum |F(z)|^2\).

Proof ▶

Apply Parseval and the affine shift property (Proposition 155); setting \(G=|F|\) and using \(|1+\omega ^{-t}|=2|\cos (\pi t/n)|\) reduces it to Theorem 160.

Theorem 160 8.8, Nonnegative-function inequality

For nonnegative \(G\) with \(G(0,0)=0\), \(\sum _z2G(z)[G(T_2^{-1}z)|\cos (\pi z_1/n)|+G(T_1^{-1}z)|\cos (\pi z_2/n)|]\le \tfrac {5\sqrt2}2\sum G^2\).

Proof ▶

Use \(2\alpha \beta \le \gamma \alpha ^2+\gamma ^{-1}\beta ^2\) with \(\gamma \) depending on a partial order (\(\gamma \in \{ 1,5/4,4/5\} \), \(\gamma (x,y)\gamma (y,x)=1\)), reducing to a per-\(z\) inequality. Outside the diamond \(|\cos (\pi z_1/n)|+|\cos ( \pi z_2/n)|\le \sqrt2\); inside, Proposition 161 bounds the \(\gamma \)-sum, giving the bound.

Proposition 161 8.9, Partial order on \(\mathbb {Z}_n^2\)

There is a partial order so that inside the diamond, for each \(z\), among \(T_1^{\pm 1}z,T_2^{\pm 1}z\) either three exceed \(z\) and one is below, or two exceed \(z\) and two are incomparable.

Proof ▶

Order \((z_1,z_2){\gt}(z_1',z_2')\) if \(|z_1|\ge |z_1'|\), \(|z_2|\ge |z_2'|\) with one strict. WLOG \(z_1{\gt}z_2\ge 0\) with \(z_1+z_2\le n/2\); then \(|z_1-2z_2|{\lt}|z_1|\) gives \(T_1^{-1}z{\lt}z\) while the other three exceed \(z\).