# tcs math – some mathematics of theoretical computer science

## January 27, 2013

### Expanders from the action of GL(2,Z)

Filed under: Math — Tags: , , , — James Lee @ 8:14 pm

Many months (and only one post) ago, I wrote about an analysis of the Gabber-Galil graphs using a simple combinatorial lemma and the discrete Cheeger inequality. Here is a note I posted recently carrying the study a bit further.

Given any two invertible, integral matrices ${S,T \in GL_2(\mathbb Z)}$, one can consider the family of graphs ${G_n^{S,T} = (V_n, E_n^{S,T})}$, where ${E_n^{S,T}}$ contains edges from every ${(x,y) \in V_n}$ to each of

$\displaystyle (x \pm 1,y), (x,y\pm 1), S(x,y), S^{-1}(x,y), T(x,y), T^{-1}(x,y)\,.$

The Gabber-Galil graphs correspond to the choice ${S = \left(\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\right)}$ and ${T = \left(\begin{smallmatrix} 1 & 0 \\ 1 & 1 \end{smallmatrix}\right)}$.

Consider also the countably infinite graph ${G^{S,T}}$ with vertex set ${\mathbb Z^2 \setminus \{0\}}$ and edges

$\displaystyle E^{S,T} = \left\{ \{z,S z\}, \{z, T z\} : z \in \mathbb Z^2 \setminus \{0\} \right\}\,.$

Using some elementary Fourier analysis and a discrete Cheeger inequality, one can prove the following relationship (we use $S'$ to represent the transpose of a matrix $S$).

Theorem 1 For any ${S,T \in GL_2(\mathbb Z)}$, if ${G^{S',T'}}$ has positive Cheeger constant, then ${\{G_n^{S,T}\}}$ is a family of expander graphs.

We recall that an infinite graph ${G=(V,E)}$ with uniformly bounded degrees has positive Cheeger constant if there is a number ${\epsilon > 0}$ such that every finite subset ${U \subseteq V}$ has at least ${\epsilon |U|}$ edges with exactly one endpoint in ${U}$.

While Theorem 1 may not seem particularly powerful, it turns out that in many interesting cases, proving a non-trivial lower bound on the Cheeger constant of ${G^{S,T}}$ is elementary. For the Gabber-Galil graphs, the argument is especially simple. The following argument is, in fact, significantly simpler than the analysis of the previous post.

In the next lemma, let $G=G^{S,T}$ where $S(x,y)=(x+y,x)$ and $T(x,y)=(x,y+x)$ and let $E=E^{S,T}$ be the corresponding edge set. We will prove that $G$ has positive Cheeger constant.

Lemma 2 For any finite subset ${A \subseteq \mathbb Z^2 \setminus \{0\}}$, we have ${ |E(A, \bar A)| \geq |A| }$.

Proof: Define ${Q_1 = \{ (x,y) \in \mathbb Z^2 : x > 0, y \geq 0 \}}$. This is the first quadrant, without the ${y}$-axis and the origin. Define ${Q_2, Q_3, Q_4}$ similarly by rotating ${Q_1}$ by ${90}$, ${180}$, and ${270}$ degrees, respectively, and note that we have a partition ${\mathbb Z^2 \setminus \{0\} = Q_1 \cup Q_2 \cup Q_3 \cup Q_4}$.

Let ${A_i = A \cap Q_i}$. We will show that ${|E(A_1, \bar A \cap Q_1)| \geq |A_1|}$. Since our graph is invariant under rotations of the plane by ${90^{\circ}}$, this will imply our goal:

$\displaystyle |E(A, \bar A)| \geq \sum_{i=1}^4 |E(A_i, \bar A \cap Q_i)| \geq \sum_{i=1}^4 |A_i| = |A|\,.$

It is immediate that ${S(A_1), T(A_1) \subseteq Q_1}$. Furthermore, we have ${S(A_1) \cap T(A_1) = \emptyset}$ because ${S}$ maps points in ${Q_1}$ above (or onto) the line ${y=x}$ and ${T}$ maps points of ${Q_1}$ below the line ${y=x}$. Furthermore, ${S}$ and ${T}$ are bijections, thus ${|S(A_1) + T(A_1)| = |S(A_1)| + |T(A_1)| = 2|A_1|\,.}$ In particular, this yields ${|E(A_1, \bar A \cap Q_1)| \geq |A_1|}$, as desired. $\Box$

One can generalize the Gabber-Galil graphs in a few different ways. As a prototypical example, consider the family ${\{G_n^{S,S'}\}}$ for any ${S \in GL_2(\mathbb Z)}$. An elementary analysis yields the following characterization.

Theorem 3 For any ${S =\left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right) \in GL_2(\mathbb Z)}$, it holds that ${\{G_n^{S,S'}\}}$ is an expander family if and only if ${(a+d)(b-c) \neq 0}$.

For instance, the preceding theorem implies that if ${S}$ has order dividing ${4}$ then ${\{G_n^{S,S'}\}}$ is not a family of expander graphs, but if ${S}$ has order ${3, 6, 12}$ or infinite order (the other possibilities) and ${S \neq S'}$ then the graphs are expanders.

Here is a different sort of generalization. Let ${R = \left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)}$ be the reflection across the line ${y=x}$. The Gabber-Galil graphs can also be seen as ${G_n^{S,T}}$ where ${S = \left(\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\right)}$ and ${T = RSR}$. We can characterize expansion of these graphs as well.

Theorem 4 For any ${S =\left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right) \in GL_2(\mathbb Z)}$, it holds that ${\{G_n^{S,RSR}\}}$ is an expander family if and only if ${(a+d)(b+c) \neq 0}$.

It is an interesting open problem to find a complete characterization of the pairs ${S,T \in GL_2(\mathbb Z)}$ such that ${\{G_n^{S,T}\}}$ is a family of expanders.

## April 18, 2012

### Gabber-Galil analysis of Margulis’ expanders

Filed under: Math — Tags: , , — James Lee @ 8:11 pm

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)}$.