Showing non-expansion for x->x+1, x->2*x. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T07:07:25Z http://mathoverflow.net/feeds/question/110077 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110077/showing-non-expansion-for-x-x1-x-2x Showing non-expansion for x->x+1, x->2*x. H A Helfgott 2012-10-19T09:06:16Z 2012-10-22T08:53:41Z <p>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.</p> <p>Question: what is the simplest way to show that this graph is not an expander?</p> <p>An obvious strategy is to construct a set A such that |A union A+1 union 2A| &lt; (1+epsilon) |A| (for epsilon arbitrary and p large enough in terms of epsilon). How to construct a set A is less obvious.</p> <p>Two possible constructions:</p> <p>(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.</p> <p>(b) For general p, J. Cilleruelo points out to me that the set A constructed by Gonzalo Fiz in Proposition 3.2 of <a href="http://arxiv.org/abs/1203.2659" rel="nofollow">http://arxiv.org/abs/1203.2659</a> (based on a Lemma of Rokhlin´s) should give an answer, at least if 2 is replaced by 4 (or any other constant square).</p> <p>Any other proposals? I'd like something that can be shown quickly to work in a survey or in a class.</p> http://mathoverflow.net/questions/110077/showing-non-expansion-for-x-x1-x-2x/110086#110086 Answer by H A Helfgott for Showing non-expansion for x->x+1, x->2*x. H A Helfgott 2012-10-19T10:41:02Z 2012-10-22T08:53:41Z <p>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)$.</p> <p>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,</p> <ul> <li>we have $p\ll_\lambda |f^{-1}(B)|\leq p/2 + O_{\lambda,n}(1)$, </li> <li>the boundary of $B$ under $x\mapsto \lambda x$ is of size $O(1/2n)+O_\lambda(1)$,</li> <li>the boundary of $B$ under $x\mapsto x+1$ is of size $O_\lambda(1)$,</li> </ul> <p>and so the problem is solved.</p> <p>(Note: this is very close to what Fiz does.)</p> http://mathoverflow.net/questions/110077/showing-non-expansion-for-x-x1-x-2x/110225#110225 Answer by Alain Valette for Showing non-expansion for x->x+1, x->2*x. Alain Valette 2012-10-21T08:47:12Z 2012-10-21T08:47:12Z <p>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 <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.em/1045952352" rel="nofollow">http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.em/1045952352</a> F. Martin and I prove that the spectrum of the adjacency matrix of the Cayley graph of $BS(1,2)$ w.r.t. <code>$\{a^{\pm 1},b^{\pm 1}\}$</code>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. </p>