Skip to main content
3 of 3
added 104 characters in body
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Non-linear expanders?

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?

H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126