9
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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... $\endgroup$
    – Seva
    Oct 19, 2012 at 9:45
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 19, 2012 at 10:14

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Harald: I think his name is Gonzalo Fiz-Pontiveros. $\endgroup$
    – Ben Green
    Oct 19, 2012 at 12:22
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 19, 2012 at 12:51
  • 2
    $\begingroup$ A positive integer much less than $1$? I am confused. $\endgroup$ Oct 19, 2012 at 13:30
  • 2
    $\begingroup$ Ah, the delights of dialectal differences within mathematics. $f\ll g$ means $f=O(g)$. $\endgroup$ Oct 19, 2012 at 13:54
  • $\begingroup$ Seems that some of the $2$s should actually be $\lambda$s, do they? $\endgroup$
    – Seva
    Oct 19, 2012 at 18:54
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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