Showing non-expansion for $x\rightarrow x+1, x\rightarrow 2x.$ 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 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.
 A: 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. 
A: 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.)
A: 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})$.
