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.

  • 2
    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 '12 at 9:45
  • 1
    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 '12 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 '12 at 12:22
  • 2
    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 '12 at 12:51
  • 2
    A positive integer much less than $1$? I am confused. – David E Speyer Oct 19 '12 at 13:30
  • 2
    Ah, the delights of dialectal differences within mathematics. $f\ll g$ means $f=O(g)$. – H A Helfgott Oct 19 '12 at 13:54
  • Seems that some of the $2$s should actually be $\lambda$s, do they? – Seva Oct 19 '12 at 18:54

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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