Showing non-expansion for $x\rightarrow x+1, x\rightarrow 2x.$

Question

Construct a graph having $V=\mathbb{Z}/p\mathbb{Z}$ as its set of vertices and $\{\{x,x+1\}: x \in V\}\cup \{\{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 \cup (A+1) \cup 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 $0$'s than $1$'s 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 https://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 Link 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.)

Answer 3

Just noticed this. The problem has been already solved in two ways, but not the generalization suggested by H A Helfgott where the multiplier $2$ is replaced by an arbitrary constant (though the solution may be implicit in Alain Valette's answer). In fact, for any fixed $r$, $s$ and any $a_j$ ($1 \leq j \leq r$) and $m_k$ ($1 \leq k \leq s$) the graph of degree $2(r+s)$ on ${\bf Z} / p {\bf Z}$ obtained by joining every $x \bmod p$ to the $2(r+s)$ residues $x \pm a_j$ and $m_k^{\pm 1} x$ is not an expander as $p \rightarrow \infty$, no matter how the addends $a_j$ and multiplicands $m_k$ are chosen. This is basically what I gave as the "Exercise" at the end of my accepted answer to question MO.125251 on the analogous graphs on finite fields of $2^n$ elements. (The exercise concerned only $r=s=1$, but a comment noted that the same argument applies in for any fixed $r,s$).

To spell it out: Let $A = \sum_j A_j$ and $M = \sum_k M_k$ be the corresponding operators on ${\bf C}^p$, so that $A_j$ (respectively $M_k$) sends the unit vector $e_x$ to $e_{x+a_j} + e_{x-a_j}$ (resp. $e_{m_k x} + e_{m_k^{-1} x}$ The all-$1$ vector ${\bf 1}$ has eigenvalue $2(r+s)$ for $A+M$. We show that there is no spectral gap by finding a vector $v$ orthogonal to ${\bf 1}$ such that the Rayleigh quotient $\langle v, (A+M) v \rangle / \langle v, v \rangle$ is $2(r+s) - o(1)$ as $p \rightarrow \infty$, uniformly over all choices of $a_j$ and $m_k$. (The inner product is $\langle v, w \rangle = \frac1p \sum_{x \in {\bf Z}/p{\bf Z}} v_x \overline w_x$.)

Fix $N$. We'll construct $v$ such that $\langle v, (A+M) v \rangle / \langle v, v \rangle > 2(r+s) - 2s/N - o(1)$. For $u \in {\bf Z} / p{\bf Z}$ let $\chi_u$ be the character $x \mapsto e^{2\pi i u x/p}$ on ${\bf Z}/p{\bf Z}$, so that the $\chi_u$ form an orthonormal basis for ${\bf C}^p$. Set $$ v = \sum_c \chi_{m^c u_0} $$ for some nonzero $u_0 \in {\bf Z} / p{\bf Z}$ to be chosen later; here the sum extends over all integer vectors $c = (c_1,c_2,\ldots,c_s)$ with each $c_k \in [1,N]$, and $m^c := m_1^{c_1} m_2^{c_2} \cdots m_s^{c_s}$. Then $$ \langle v, M v \rangle \geq \frac{N-1}{N} 2s \langle v, v \rangle $$ (the inequality may be strict if there are small multiplicative relations among the $m_k$). Now each $\chi_u$ is an eigenvector for $A$ with eigenvalue $2\sum_{j=1}^r \cos (2 a_j u/p)$. We want to choose $u_0$ so that each of the $N^r s$ multiples $a_j m^c u_0$ is $o(p)$, so that $A \chi_{m^c u_0}$ has eigenvalue $2r-o(1)$ and $\langle v, A v \rangle = (2r-o(1)) \langle v, v \rangle$. By a standard pigeonhole argument such $u_0$ exists that makes each $a_j m^c u_0 / p$ within $O(p^{-1/N^r s})$ of an integer, uniformly over choices of $a_j$ and $m_k$. This gives the desired estimate as $p \rightarrow \infty$. Since $N$ can be taken arbitrarily large, we are done.

The special case $r=s=1$, $m_1=2$ is a bit easier: we can always take $u_0=1$ and obtain a bound $O(2^N/p)$ that decreases faster than $O(p^{-1/N})$.