5
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ 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$. $\endgroup$ Mar 22, 2013 at 12:15
  • $\begingroup$ @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. $\endgroup$
    – Seva
    Mar 22, 2013 at 17:51
  • $\begingroup$ 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? $\endgroup$ Mar 22, 2013 at 18:12
  • $\begingroup$ @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? :-) ) $\endgroup$
    – Seva
    Mar 22, 2013 at 18:46
  • $\begingroup$ 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). $\endgroup$ Mar 22, 2013 at 19:08

1 Answer 1

7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ The argument for the second graph is really nice, thanks! $\endgroup$
    – Seva
    Mar 25, 2013 at 10:07
  • $\begingroup$ 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$)? $\endgroup$
    – Seva
    Mar 26, 2013 at 9:32
  • $\begingroup$ @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)$. $\endgroup$ Mar 27, 2013 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.