29
$\begingroup$

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete Laplacian (or the adjacency matrix) has spectral gap $|\lambda_0-\lambda_1|\geq \delta$. (Assume all graphs in the family have the same degree (= valency) $d$.)

If, for every $p$, we specify some maps from $\mathbb{Z}/p\mathbb{Z}$ to itself, then we are defining a graph with vertex set $\mathbb{Z}/p\mathbb{Z}$ for each $p$: a vertex is adjacent to the vertices it is mapped to.

If we consider the maps $x\to x+1$, $x\to 3x$ (say), then we do not get expanders. On the other hand, if we take $x\to x+1$, $x\to x^{-1}$, then, as is widely known, we do get an expander family.

Consider the maps

$x\mapsto x+1$, $x\mapsto x^3$.

Do they (and their inverses, if you wish) give an expander family? (Let $p$ range only over primes $p\equiv 2 \mod 3$, so as to keep the map $x\mapsto x^3$ injective.)

What about the maps $x\mapsto x+1$, $x\mapsto 3 x$, $x\mapsto x^3$? Do they, taken together, give an expander family?

(Is there a way to relate these maps to the action of a linear group? Are there examples of sets of not neessarily linear maps giving rise to expander families?)

UPDATE: What if these were shown not to be expanders? What would be some interesting consequences?

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ As for the last question, as you well know, it was proven long ago by Pinsker that any pair of random permutations will form an expander on $\{1,\dots,n\}$ with probability $1-o(1)$. Absent any obvious nilpotent or solvable structure (as with the $x \mapsto x+1, x \mapsto 3x$ case) I would conjecture that $x \mapsto x+1, x \mapsto x^3$ behaves like two random maps for the purposes of expansion, since there do not appear to be any local relations between these maps (in contrast to the former case in which we have $3(x+1) = 3x + 1 + 1 + 1$). $\endgroup$
    – Terry Tao
    Commented May 28, 2014 at 15:55
  • 3
    $\begingroup$ ... proving expansion rigorously, though, would probably require substantial new ideas since there does not appear to be any natural group involved other than the free group. But one could imagine that sum-product theorems could at least give some non-trivial bounds on diameter and mixing time, even if they fall short of true expansion. $\endgroup$
    – Terry Tao
    Commented May 28, 2014 at 15:57
  • 1
    $\begingroup$ Agreed - yes, these are my reasons for asking! But what about diameter bounds? I actually want expansion, but that might already be somewhat interesting. $\endgroup$
    – H A Helfgott
    Commented May 28, 2014 at 16:59
  • 2
    $\begingroup$ It looks like Bourgain-Konyagin type exponential sum estimates may be able to prove a very weak expansion result of the form $|A \cup (A+1) \cup A^{\cdot 3} | \geq |A| + |A|^\delta$ when $p^\varepsilon \leq |A| \leq p^{1-\varepsilon}$, where $A^{\cdot 3} = \{ a^3: a \in A \}$, which would almost give a non-trivial diameter bound, but the improvement is slight and one also would have to treat the case of very small or very large A somehow. [Maybe a Weyl differencing argument would work?] $\endgroup$
    – Terry Tao
    Commented May 28, 2014 at 18:15
  • 2
    $\begingroup$ Actually, thinking about it more, Bourgain-Konyagin (which has to do with how arithmetic progressions and geometric progressions interact) is more relevant for the $x \mapsto x+1, x \mapsto 3x$ case. For $x \mapsto x+1, x \mapsto x^3$, it is indeed Weyl differencing which is the key: to show that if A is basically the union of a small number of intervals, then $A^{\cdot 3}$ does not behave like the union of a small number of intervals. $\endgroup$
    – Terry Tao
    Commented May 28, 2014 at 18:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .