Gabber-Galil analysis of Margulis’ expanders

I’m currently teaching a course on spectral graph theory, and I decided to lecture on Margulis’ expander construction and the analysis of its spectral gap by Gabber and Galil. I had never realized how intuitive the analysis could be; the lectures notes I had seen didn’t quite reflect this. In particular, we won’t do any unsightly calculations. Everything I’m about to say is probably well-known, but I thought I would write it down anyway.

The idea is to first start with an initial “expanding object,” and then try to construct a family of graphs out of it. First, consider the infinite graph ${G}$ with vertex set ${\mathbb Z^2}$ . The edges are given by two maps ${S}$ and ${T}$ , where ${S(x,y) = (x,x+y)}$ and ${T(x,y) = (x+y,y)}$ . So the edges are ${\{(x,y), S(x,y)\}}$ and ${\{(x,y), T(x,y)\}}$ . Clearly ${(0,0)}$ is not adjacent to anything. Except for the origin, this graph is an expander in the following sense.

Lemma 1 For any subset ${A \subseteq \mathbb Z^2 \setminus \{0\}}$ , we have

$\displaystyle |E(A)| \geq \frac{1}{3} |A|\,,$

where ${E(A)}$ denotes the edges leaving ${A}$ .

The following simple proof is inspired by a paper of Linial and London.

Proof: First consider a subset ${A}$ that does not intersect the coordinate axes. Let ${Q_1, Q_2, Q_3, Q_4}$ represent the four quadrants of ${\mathbb Z^2}$ , and let ${A_i = A \cap Q_i}$ . Consider that ${S(A_1), T(A_1) \subseteq Q_1}$ and ${S(A_1) \cap T(A_1) = \emptyset}$ . The latter fact follows because if ${(x,x+y)=(x'+y',y')}$ then ${x'=-y}$ . Similarly, ${S^{-1}(A_2), T^{-1}(A_2) \subseteq Q_2}$ and ${S(A_3), T(A_3) \subseteq Q_3}$ and ${S^{-1}(A_4), T^{-1}(A_4) \subseteq Q_4}$ , while all the respective pairs ${S^{-1}(A_2), T^{-1}(A_2)}$ and ${S(A_3), T(A_3)}$ and ${S^{-1}(A_4), T^{-1}(A_4)}$ are disjoint.

Combining this with the fact that ${S}$ and ${T}$ are bijections on ${\mathbb Z^2}$ immediately shows that ${|S(A) \cup S^{-1}(A) \cup T(A) \cup T^{-1}(A)|}$ is at least

$\displaystyle |S(A_1)| + |T(A_1)| + |S^{-1}(A_2)| + |T^{-1}(A_2)|$

$\displaystyle + |S(A_3)| + |T(A_3)| + |S^{-1}(A_4)| + |T^{-1}(A_4)|$

$\displaystyle = 2(|A_1| + |A_2| + |A_3| + |A_4|)$

$\displaystyle = 2 |A|\,.$

Dealing with the coordinate axes is not too hard. Suppose now that ${A \subseteq \mathbb Z^2 \setminus \{0\}}$ is arbitrary. Let ${A_{+} = A \cap \{ (x,0), (0,x) : x \in \mathbb Z \}}$ . The preceding argument shows ${|E(A)| \geq |A\setminus A_+|-|A_+| = |A|-2|A_+|}$ . We will show that ${|E(A)| \geq |A_+|}$ . Averaging these two inequalities with weights ${1/3}$ and ${2/3}$ completes the proof.

Let ${A_\times = A \cap \{ (x,x), (x,-x) : x \in \mathbb Z \}}$ , and ${A_\circ = A \setminus (A_1 \cup A_2)}$ . Then we have the bounds:

$\displaystyle |E(A_+, \bar A)| \geq |A_+| - |A_\times|$

$\displaystyle |E(A_\times, \bar A)| \geq 2|A_\times| - |A_\circ|$

$\displaystyle |E(A_\circ, \bar A)| \geq |A_\circ| - |A_\times|\,.$

The first equation follows since each element of ${A_+}$ is connected to exactly two elements of ${A_{\times}}$ , and each element of ${A_{\times}}$ is connected to exactly two elements of ${A_+}$ . For instance, ${(x,0)}$ is connected to ${(x,x)}$ and ${(x,-x)}$ , while ${(x,x)}$ is connected to ${(x,0)}$ and ${(0,x)}$ .

The second follows because every point of ${A_\times}$ is connected to two unique points of ${A_\circ}$ , e.g. ${(x,x)}$ is connected to ${(x,2x)}$ and ${(2x,x)}$ . The final inequality follows from the fact that ${|E(A_\circ)| \geq |A_\circ|}$ from our first argument (since ${A_{\circ}}$ does not touch the axes), and because ${A_\circ}$ has no edges to ${A_+}$ . Summing these three inequalities yields ${|E(A)| \geq |A_+|}$ . $\Box$

Of course, ${\mathbb Z^2}$ is not a finite graph, so for a parameter ${n}$ , we define the graph ${G_n=(V_n,E_n)}$ with vertex set ${V_n = \mathbb Z_n \oplus \mathbb Z_n}$ , where ${\mathbb Z_n = \mathbb Z/(n \mathbb Z)}$ . There are four types of edges in ${E_n}$ : A vertex ${(x,y)}$ is connected to the vertices

$\displaystyle \{(x,y+1), (x+1, y), (x,x+y), (x+y,y)\}\,.$

This yields a graph of degree at most 8.

Theorem 2 There is a constant ${c > 0}$ such that for every ${n \in \mathbb N}$ ,

$\displaystyle \lambda_2(G_n) \geq c\,,$

where ${\lambda_2}$ is the second-smallest eigenvalue of the Laplacian on ${G_n}$ .

Of course, the graphs ${\{G_n\}}$ now have torsion, and thus our expansion result for ${\mathbb Z^2}$ is not, a priori, very useful. The non-trivial idea of the proof is that the torsion doesn’t matter, making Lemma 1 applicable. This is not difficult to show using some Fourier analysis. It turns out to be better though, if we first move to the continuous torus.

Recall that,

$\displaystyle \lambda_2(G_n) = \min_{f : V_n \rightarrow \mathbb R} \left\{\frac{\sum_{uv \in E_n} (f(u)-f(v))^2}{\sum_{u \in V_n} f(u)^2} : \sum_{u \in V_n} f(u) = 0\right\}\,,$

Let ${\mathbb T^2 = \mathbb R^2/\mathbb Z^2}$ be the 2-dimensional torus equipped with the Lebesgue measure, and consider the complex Hilbert space

$\displaystyle L^2(\mathbb T^2) = \left\{ f : \mathbb T^2 \rightarrow \mathbb C : \int_{\mathbb T^2} |f|^2 < \infty \right\}\,.$

equipped with the inner product ${\langle f,g\rangle_{L^2} = \int_{\mathbb T^2} f \bar g}$ .

We might also define a related value,

$\displaystyle \lambda_2(\mathbb T^2) = \min_{f \in L^2(\mathbb T^2)} \left\{\frac{\|f-f\circ S\|_{L^2}^2 + \|f-f \circ T\|_{L^2}^2}{\|f\|_{L^2}^2} : \int_{\mathbb T^2} f = 0\right\}\,. \ \ \ \ \ (1)$

Note that this is just defined as a number; the eigenvalue notation is merely suggestive, but we have not introduced an operator on the torus.

Claim 1 There is some ${\varepsilon > 0}$ such that for any ${n \in \mathbb N}$ , we have ${\lambda_2(G_n) \geq \varepsilon \lambda_2(\mathbb T^2)}$ \

Proof: We simply sketch a proof, which is rather intuitive. Suppose we are given some map ${f : V_n \rightarrow \mathbb R}$ such that ${\sum_{u \in V_n} f(u)=0}$ . Define its continuous extension ${\tilde f : \mathbb T^2 \rightarrow \mathbb R}$ as follows: Under the natural embedding of ${\mathbb Z_n \oplus \mathbb Z_n}$ into ${\mathbb T^2}$ , every point ${z \in \mathbb T^2}$ sits inside a grid square with four corners ${u_1,u_2,u_3,u_4 \in \mathbb Z_n \oplus \mathbb Z_n}$ . Writing a local convex combination ${z = \lambda_1 u_1 + \lambda_2 u_2 + \lambda_3 u_3 + \lambda_4 u_4}$ , we define

$\displaystyle \tilde f(z) = \lambda_1 f(u_1) + \lambda_2 f(u_2) + \lambda_3 f(u_3) + \lambda_4 f(u_4)\,.$

Now it is elementary to verify that ${\int_{\mathbb T^2} \tilde f = 0}$ . It is also easy to verify that ${\|\tilde f\|^2_{L^2} \geq c\frac{1}{n} \sum_{v \in V} f(v)^2}$ for some ${c > 0}$ . (Even if ${f(u_1)+f(u_2)+f(u_3)+f(u_4)=0}$ , we still get a contribution from ${f(u_1)^2 + f(u_2)^2 + f(u_3)^2 + f(u_4)^2}$ to ${\|\tilde f\|_{L^2}}$ on this square because we are taking a weighted average.)

Finally, for any ${z \in \mathbb T^2}$ , there is a path of length ${O(1)}$ in ${G_n}$ connecting each of the corners of ${z}$ ‘s square to the corners of ${S(z)}$ ‘s square. A similar fact holds for ${T(z)}$ . In fact, this is the only place where we need to use the fact that edges of the form ${(x,y) \leftrightarrow (x,y+1)}$ and ${(x,y) \leftrightarrow (x+1,y)}$ are present in ${G_n}$ . Thus any contribution ${|\tilde f(z)-\tilde f(S(z))|^2}$ to ${\|\tilde f-\tilde f\circ S\|_{L^2}^2}$ can be charged against a term in ${\sum_{uv \in E_n} (f(u)-f(v))^2}$ , and similarly for ${T}$ . $\Box$

Now our goal is to show that ${\lambda_2(\mathbb T^2) > 0}$ . We will use the Fourier transform to “remove the torsion.” The point is that ${S}$ and ${T}$ , being shift operators, will act rather nicely on the Fourier basis.

We recall that if ${m,n \in \mathbb N}$ and we define ${\chi_{m,n} \in L^2(\mathbb T^2)}$ by ${\chi_{m,n}(x,y) = \exp(2\pi i(mx+ny))}$ , then ${\{\chi_{m,n}\}}$ forms an orthonormal Hilbert basis for ${L^2(\mathbb T^2)}$ . In particular, every ${f \in L^2(\mathbb T^2)}$ can be written uniquely as

$\displaystyle f = \sum_{m,n \in \mathbb Z} \hat f_{m,n} \chi_{m,n}\,,$

where ${\hat f_{m,n} = \langle f, \chi_{m,n}\rangle_{L^2}}$ . The Fourier transform is defined as a map ${\mathcal F~:~L^2(\mathbb T^2) \rightarrow \ell^2(\mathbb Z^2)}$ , where ${\mathcal F f(m,n) = \hat f_{m,n}}$ . In particular, ${\mathcal F}$ is a linear isometry.

Define ${S^*(f) = f \circ S}$ and ${T^*(f) = f \circ T}$ . Then for any ${m,n \in \mathbb Z}$ , we have

$\displaystyle S^*(\chi_{m,n}) = \chi_{m+n,n} \quad\textrm{ and }\quad T^*(\chi_{m,n}) = \chi_{m,n+m}.$

In particular, for any ${f \in L^2(\mathbb T^2)}$ , we have ${\widehat{S^*(f)} = \sum_{m,n} \hat f_{m-n,n} \chi_{m,n}}$ and ${\widehat{T^*(f)} = \sum_{m,n} \hat f_{m,n-m} \chi_{m,n}}$ . The final thing to note is that ${\hat f(0,0) = \langle f, \chi_{0,0} \rangle = \int_{\mathbb T^2} f}$ . So now if we simply apply the Fourier transform (a linear isometry) to the expression in (1), we get a reformulation that ${\lambda_2(\mathbb T^2)}$ is precisely

$\displaystyle \min_{g \in \ell^2(\mathbb Z^2)} \left\{ \frac{\sum_{z \in \mathbb Z^2} |g(z)-g(S(z))|^2 + |g(z)-g(T(z))|^2}{\|g\|^2_{\ell^2}}: g(0,0)=0 \right\}\,.$

Here we have simply replaced ${f}$ by ${\mathcal F f}$ in (1), and then written ${g = \mathcal F f}$ .

But now recall our initial infinite graph ${G}$ on ${\mathbb Z^2}$ . If we denote by ${L_G}$ the Laplacian on ${G}$ , then we can rewrite this as,

$\displaystyle \lambda_2(\mathbb T^2) = \min_{g \in \ell^2(\mathbb Z^2)} \left\{ \frac{\langle g, L_G g\rangle_{\ell^2}}{\|g\|^2_{\ell^2}}: g(0,0)=0 \right\}\,.$

In other words, it is precisely the first Dirichlet eigenvalue on ${G}$ , subject to the boundary condition ${g(0,0)=0}$ .

But now the discrete Cheeger inequality tells us that

$\displaystyle \lambda_2(\mathbb T^2) \geq \frac1{2 d_{\max}} h^2,$

where ${h}$ is the minimal expansion of any set not containing the origin. Thus we have indeed unwrapped the torsion and returned to our initial question. Lemma 1 shows that ${h \geq 1/3}$ , yielding the desired lower bound on ${\lambda_2(\mathbb T^2)}$ .

2 thoughts on “Gabber-Galil analysis of Margulis’ expanders”

Suresh Venkat says:

April 20, 2012 at 10:02 pm

What does it mean for a graph (or graph family) to have torsion ?
James Lee says:

April 21, 2012 at 12:03 am

Perhaps it was a poor choice of words–the underlying group $\mathbb Z_n \oplus \mathbb Z_n$ has torsion in the sense that it contains elements of finite order, i.e. non-zero elements $g \in \mathbb Z_n$ such that $g+g+\cdots+g=0$ . In general such a non-identity element of a group is called a torsion element. So in this case torsion for the graphs just meant “wrap around.”