Question

Construct a graph having V=Z/pZ as its set of vertices and {{x,x+1}: x in V} union {{x,2x}: x in V} as its set of edges. This graph is not an expander - quite unsurprisingly, since it is induced by a solvable group of actions.

Question: what is the simplest way to show that this graph is not an expander?

An obvious strategy is to construct a set A such that |A union A+1 union 2A| < (1+epsilon) |A| (for epsilon arbitrary and p large enough in terms of epsilon). How to construct a set A is less obvious.

Two possible constructions:

(a) If p = 2^n+1, or more generally p = 2^n+O(1), then A = (reductions modulo p of itnegers between 0 and p-! with more 0s than 1s in their binary expansion) should work.

(b) For general p, J. Cilleruelo points out to me that the set A constructed by Gonzalo Fiz in Proposition 3.2 of http://arxiv.org/abs/1203.2659 (based on a Lemma of Rokhlin´s) should give an answer, at least if 2 is replaced by 4 (or any other constant square).

Any other proposals? I'd like something that can be shown quickly to work in a survey or in a class.

Answer 1

Harald, I certainly will not claim that this is simpler, but there is a spectral approach to your question, which has been considered. Consider the subgroup $BS(1,2)$ of the affine group of the real line, generated by $a:x\mapsto 2x$ (dilation by 2) and $b:x\mapsto x+1$ (translation by 1). If $p$ is an odd prime, reducing modulo $p$ we have a homomorphism $BS(1,2)\rightarrow Aff_1(p)$ (the affine group of $Z/pZ$) and your graphs can be viewed as Schreier graphs of $BS(1,2)$. In that paper http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.em/1045952352 F. Martin and I prove that the spectrum of the adjacency matrix of the Cayley graph of $BS(1,2)$ w.r.t. $\{a^{\pm 1},b^{\pm 1}\}$is the interval $[-3,4]$, and that it is the closure of the union of the spectra of your graphs. This implies that your graphs cannot have a spectral gap.

Answer 2

Wait, this isn't that hard. Let a positive integer $\lambda\ll 1$ be given. Let $A=[0,1/2n]\subset \mathbb{R}/\mathbb{Z}$. Let $\phi$ be the multiplication-by-$\lambda $ map; then $\phi^{-k}(A)$ is a union of $\lambda^k$ intervals with total measure $1/2n$. We let $B$ be the union of the sets $\phi^{-k}(A)$ for $k$ going from $0$ to $n-1$; we show that there isn't too much overlap, so that $1\ll |B|\leq 1/2$. Then the boundary of $B$ under $x\mapsto \lambda x$ is of size $O(1/2n)$.

Now let $f$ be the natural homomorphism of abelian groups $f:\mathbb{Z}/p\mathbb{Z}\to \mathbb{R}/\mathbb{Z}$. Of course, multiplication by $\lambda$ (i.e., addition $\lambda$ times) gets taken to multiplication by $\lambda$. Because $B$ is the union of $O_{\lambda,n}(1)$ intervals,

• we have $p\ll_\lambda |f^{-1}(B)|\leq p/2 + O_{\lambda,n}(1)$,
• the boundary of $B$ under $x\mapsto \lambda x$ is of size $O(1/2n)+O_\lambda(1)$,
• the boundary of $B$ under $x\mapsto x+1$ is of size $O_\lambda(1)$,

and so the problem is solved.

(Note: this is very close to what Fiz does.)