# More expanders?

Having received several exhausting answers to my recent question about the expansion properties of a certain graph, I now wonder whether anything is known on the following graphs of a similar nature:

1) The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$, where $g$ is a fixed primitive root mod $p$.

2) The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$, where $e$ is a fixed non-zero element, and $g$ is a generating element of ${\rm GF}(2^n)$.

3) The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.

Are these (families of) graphs known to be good expanders? Can one investigate them using Selberg's 3/16-theorem or other "standard" tools used to study the graph my original question concerned with?

• My guess is that (1) and (2) are doomed not to expand because they are "too abelian", or "too nilpotent". So for (1), a set like $\{\pm g^{n} : 0 \le n \le N \}$ for $N$ large (but small compared to $p$) is likely to contradict expansion. Something similar should work in (2), considering a set of bounded length words on both your generators. I think this is closely related to this MO question. (3) has a very different flavour. It might be related to expansion in $SL_2$. Mar 22, 2013 at 12:15
• @Freddie Manners: concerning the first graph I mentioned - you are absolutely right, pretty stupid of me not to notice this myself. Concerning the second graph - I still don't see any obvious reason for it not to be an expander.
– Seva
Mar 22, 2013 at 17:51
• The second graph has bounded degree and diameter logarithmic in the number of vertices (because any field element is $e$ times a polynomial in $g$); isn't that enough to make it an expander? Mar 22, 2013 at 18:12
• @Noam: sorry, do not get it. First, any (non-zero) field element is actually just a power of $g$. Second, I do not see why the diameter being logarithmic implies that the graph is an expander. (To my understanding, it does not - am I missing something? Could you expand? :-) )
– Seva
Mar 22, 2013 at 18:46
• Any field element is $e P(g)$ for some polynomial $P$ of degree $<n$. Thus it can be reached from $0$ in at most $2n$ steps. But I'm not sure whether this implies that the graph is an expander (the reverse direction is known). Mar 22, 2013 at 19:08

Freddie Manners is right: graphs (1) and (2) are not expanders for any choice of $g$. For (1), he already showed this by exhibiting large vertex sets with $O(1)$ neighbors. For (2) we prove it below by contructing vectors $v$ orthogonal to the all-$1$ vector for which the Rayleigh quotient $\langle Av, v \rangle / \langle v, v \rangle$ is within $o(1)$ (indeed $O(1/n)$) of the graph degree, thus proving that there is no spectral gap. Graph (3) is probably an expander, because the maps taking $z$ to $z^{-1}$ and $z+2$ generate a congruence subgroup of index 3 in ${\rm PSL}_2({\bf Z})$ (as Serre notes in the very last section of A Course in Arithmetic), and the graph vertices can be identified with an orbit of cusps of a modular curve of level $2^n$, so one should be able to use the $3/16$ bound on that curve; but I'll leave that to the folks who actually know these techniques.

For (2): let $k$ be a finite field of $2^n$ elements, and consider the graph where each $z$ is adjacent to $gz$ $-$ and thus also to $g^{-1} z$ $-$ and to $z+e$. Fix a nontrivial homomorphism $\epsilon$ from $(k,+)$ to the group $\lbrace\pm1\rbrace$; the usual choice is $\epsilon(x) = (-1)^{{\rm Tr}(x)}$. Then for each $c \in k$ we have a homomorphism $\epsilon_c: (k,+) \rightarrow \lbrace\pm1\rbrace$ defined by $\epsilon_c(x) = \epsilon(cx)$, and these $\epsilon_c$ form an orthonormal basis for the Euclidean space of real-valued functions on $k$ with inner product $$\langle f, g \rangle := \frac1{2^n} \sum_{x\in k} f(x) g(x).$$ So we're seeking a linear combination of the $\epsilon_c$ with $c \neq 0$ that is almost fixed by the adjacency matrix $A$ in the sense that $\langle Av, v \rangle / \langle v, v \rangle = 3 - O(1/n)$.

Write $A = A_1+A_2$ where $A_1$ is induced by translation by $e$ and $A_2$ is induced by multiplication by $g^{\pm 1}$. Then for each $c \in k$ we have $A_1 \epsilon_c = \epsilon(ce) \epsilon_c$ and $A_2 \epsilon_c = \epsilon_{gc} + \epsilon_{g^{-1}c}$. We shall take $v = \sum_{i=1}^{n-1} \epsilon_{g^i c}$ for some $c\neq 0$, so $\langle v, v \rangle = n-1$ and $\langle A_2 v, v \rangle = 2n-4$. We next show that $c$ can be chosen so that $v$ is an eigenvector of $A_1$, corresponding to the eigenvalue $1$. Because $\lbrace c : \epsilon(ce) = +1 \rbrace$ is a $({\bf Z}/2{\bf Z})$-subspace of $k$ of codimension $1$, the same is true of $\lbrace c : \epsilon(g^i ce) = +1 \rbrace$ for each $i$, so the intersection of these $n-1$ subspaces has positive dimension. Choosing nonzero $c$ in this intersection makes $A_1 v = v$ as claimed. Then $$\langle A v, v \rangle = \langle A_1 v, v \rangle + \langle A_2 v, v \rangle = (n-1) + (2n-4) = 3n-5 = (3-O(1/n)) \langle v, v \rangle,$$ QED.

Exercise: Adapt this technique to show that the graph on ${\bf Z} / p {\bf Z}$ where each $z$ is connected to $z \pm 1$ and $g^{\pm 1} z$ is not an expander either for any $g \in ({\bf Z} / p {\bf Z})^*$. (That's what I first thought graph (1) was when I quickly read the question.)

• The argument for the second graph is really nice, thanks!
– Seva
Mar 25, 2013 at 10:07
• It is my understanding, by the way, that the situation changes significantly, and the argument does not work any longer, if one fixes two non-zero elements $e_1$ and $e_2$, and has every $z$ adjacent to both $z+e_1$ and $z+e_2$ (in addition to $g^{\pm1}z$)?
– Seva
Mar 26, 2013 at 9:32
• @Seva i) Thanks! ii) Actually it's much the same with two generators, or any fixed number of generators. With two generators, $\epsilon(ce_1) = \epsilon(ce_2) = +1$ cuts out a codimension-$2$ subspace of $k$, so we can still choose $c$ such that $g^i c$ is in that subspace for $n/2 - O(1)$ consecutive values of $i$, again deducing that the spectral gap is $O(1/n)$. Mar 27, 2013 at 19:05