## Showing non-expansion for x->x+1, x->2*x.

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.

-
This is, essentially, Problem 7.9 from the Open problems in additive combinatorics (available at math.haifa.ac.il/~seva/Papers/montpr.dvi) by Ernie Croot and myself. The sad thing is, I absolutely cannot recall now what was my motivation for the last sentence of the problem... – Seva Oct 19 at 9:45
Thanks! What you ask there is whether there is a lambda for which (if 2 is replaced by lambda) the graph above is an expander. I would also think the answer to your question should be "no" for lambda=O(1). In fact I am suggesting that that's close to proved, but that we don't quite have a neat, completely closed answer yet (though Fiz essentially gives one for lambda a square). – H A Helfgott Oct 19 at 10:14

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.

-

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

-
Harald: I think his name is Gonzalo Fiz-Pontiveros. – Ben Green Oct 19 at 12:22
Ben: All Spanish names are double-barrelled - in Spanish. Thus, for example, I am Harald Helfgott Seier. You are Benjamín Green ..., actually, I don't know. – H A Helfgott Oct 19 at 12:51
A positive integer much less than $1$? I am confused. – David Speyer Oct 19 at 13:30
Ah, the delights of dialectal differences within mathematics. $f\ll g$ means $f=O(g)$. – H A Helfgott Oct 19 at 13:54
Seems that some of the $2$s should actually be $\lambda$s, do they? – Seva Oct 19 at 18:54