## Notes of Emmanuel Breuillard’s talk

Random pairs of elements in finite simple groups generate expanders

Joint work with Bob Guralnick, Ben Green and Terry Tao.

1. Expansion: results

In 2005, there was a breakthrough by Helfgott and Bourgain-Gamburd in the study of expansion properties of Cayley graphs of ${SL_2 (p)}$. A year ago, with Green and Tao (and independently Pyber and Szabo) could generalize it as follows.

Theorem 1 (Breuillard, Green, Tao 2010, Pyber, Szabo 2010) Let ${G}$ be a finite simple group of Lie type, ${G=\mathbb{G}(q)}$. Then for every generating set ${A\subset G}$,

$\displaystyle \begin{array}{rcl} |AAA|\geq \min\{|A|^{1+\epsilon},|G|\} \end{array}$

where ${\epsilon}$ depends only on the dimension ${d}$ of ${\mathbb{G}}$, not on ${q}$.

Corollary 2

$\displaystyle \begin{array}{rcl} \sup_{A\,\mathrm{generating\,set}}diameter(Cay(G,A))\leq C_d (\log |G|)^{C_d}. \end{array}$

This partly solves a more ambitious conjecture of L. Babai.

Theorem 3 (Breuillard, Green, Guralnick, Tao 2011) Let ${G}$ be a finite simple group of Lie type, ${G=\mathbb{G}(q)}$, ${d=dim(\mathbb{G})}$. Then there exists ${\epsilon=\epsilon(d)}$ such that

$\displaystyle \begin{array}{rcl} \lim_{|G|\rightarrow\infty}\mathop{\mathbb P}(Cay(G,\{a,b\})\textrm{ is an }\epsilon-\textrm{expander})=1. \end{array}$

Remark 1

1. For ${\mathbb{G}=SL_2}$, it is due to Bourgain and Gamburd.
2. ${Sp_4 (F_{3^{\ell}})}$ requires a special treatment.
3. Can one make ${\epsilon}$ independent of ${d}$ in Theorem 3 ? Breuillard-Gamburd have partial results for ${SL_2}$.

Question: All Cayley graphs are ${\epsilon}$-expanders, ${\epsilon=\epsilon(d)}$ ?

1.2. Scheme of proof of Theorem \ref

}

Recall that ${Cay(G,\{a,b\})}$ is an ${\epsilon}$-expander iff random walk on ${G}$ becomes equidistributed in time logarithmic in ${|G|}$. In other words, ${\mu^{\star n}}$ is close to uniform measure for ${n=O(\log|G|)}$.

Sarnak and Xue’s trick generalizes to all finite simple groups. Gowers even calls quasirandom a group which has no low dimensional irreducible representation. For such groups, it is enough to show that

$\displaystyle \begin{array}{rcl} \mu^{\star n}(e)\leq O(\frac{1}{|G|^{1-\epsilon}}\quad\textrm{for}\quad n=C_0 \,(\log|G|), \end{array}$

for a certain universal constant ${C_0}$.

Bourgain-Gamburd trick also generalizes to all finite simple groups. If ${girth(Cay(G,\{a,b\}))\geq \Omega(\log|G|)}$, then the random walk behaves like that on a tree, at least when ${n\leq c_0 \log|G|}$. This implies that ${\mu^{\star n}(e)\leq\frac{1}{|G|^{\epsilon'}}}$ for ${n\sim c_0 \log|G|}$. Gamburd and coauthors have proven that ${girth(Cay(G,\{a,b\}))\geq \Omega(\log|G|)}$ for most choices of ${a}$ and ${b}$.

There remains to fill the gap between ${c_0 \log|G|}$ and ${C_0 \log|G|}$.

1.3. Mass of subgroups

The product theorem allows to show subexponential decay of ${\mu^{\star n}(e)}$ for ${c_0 \log|G| \leq n\leq C_0 \log|G|}$. This is shown by comparing ${\mu^{\star n}(e)}$ with ${\mu^{\star 2n}(e)}$ for ${n}$ in this interval. If ${\mu^{\star n}(e)<\mu^{\star 2n}(e)^{1+\epsilon''}}$, then among level sets ${A_a =\{x\,;\,\mu^{\star n}(x)=a\}}$, one of them will have ${|A_a A_a A_a|<|A_a|^{1+\epsilon}}$.

Wigderson: You do not need to consider level sets, there are other ways to proceed, see my 2004 paper with Barak and Impagliazzo on extractors.

Proposition 4

$\displaystyle \begin{array}{rcl} \sup_{H\mathrm{\,proper\, subgroup\,of\,}G}\mu^{\star n}(H)\leq\frac{1}{|G|^\epsilon}\quad\textrm{for}\quad n\sim\log|G|. \end{array}$

The difficulty is that, unlike for ${SL_2 (p)}$, general finite simple groups of Lie type have many different subgroups. We shall use a Fubini type argument.

$\displaystyle \begin{array}{rcl} \mu^{\star n}(H)^2 \end{array}$

is the probability that two independent random walks end in ${H}$. It is less than the probability that the final positions of these random walks do not generate ${G}$. By Fubini and Markov inequality,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}_{a,b}(\sup_{H\mathrm{\,proper\, subgroup\,of\,}G}\mu^{\star n}(H) &>&\frac{1}{|G|^\epsilon})\\ &\leq& \mathop{\mathbb P}_{a,b}(\mathop{\mathbb P}_{w,w'}(\langle w,w' \rangle\not=G)>\frac{1}{|G|^\epsilon})\\ &\leq& |G|^{\epsilon}\mathop{\mathbb P}_{w,w'}(\mathop{\mathbb P}_{a,b}(\langle w,w' \rangle\not=G)>\frac{1}{|G|^\epsilon}). \end{array}$

Proposition 5 There exist ${\gamma}$, ${c>0}$ such that for all non commuting words ${w}$ and ${w'}$ in the free group on two generators, the probability

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}_{a,b}(\langle w(a,b),w'(a,b) \rangle \not= G)\leq \frac{1}{|G|^{\gamma}}, \end{array}$

uniformly for ${|w|}$, ${|w'|\leq C_0 \log|G|}$.

Our proof uses algebraic geometry, and does not seem to extend to ${\mathfrak{S}_n}$.

1.4. Ingredients of the proof of Proposition \ref

}

• Classification of subgroups (Larsen-Pink) into
• structural subgroups ${\mathbb{H}(q)}$;
• subfield groups ${\mathbb{G}(q')}$ where ${q'}$ divides ${q}$.
• Lang-Weil type bounds on the number of points of algebraic subvarieties: ${|V(q)|\leq q^{\mathrm{dim}V}}$.
• Existence of strongly dense free subgroups.

1.5. Existence of strongly dense free subgroups

Theorem 6 (Breuillard, Green, Guralnick, Tao 2011) ${\mathbb{G}}$ semisimple algebraic group over un uncountable algebraically closed field ${K}$. Then there exist ${a}$, ${b\in \mathbb{G}(K)}$ such that ${\langle a,b \rangle}$ is free and every non abelian subgroup is Zariski dense.

Once there exists a pair, almost every pair does the job.

Proof: Use Borel’s density theorem: for any nonzero word ${w}$, the word map ${w:G\times G\rightarrow G}$, ${(a,b)\mapsto w(a,b)}$ is dominant, i.e. its image contains an open set of ${G}$.

Then argue by induction on dim${(\mathbb{G})}$ (as Borel does).

Finish with a degeneration argument: For every semisimple subgroup ${H}$ in ${\mathbb{G}}$, there is a semisimple subgroup ${\mathbb{H}'}$ which is not a degeneration of ${\mathbb{H}}$, i.e. for all

$\displaystyle \begin{array}{rcl} \forall\,(u,v)\in\overline{\bigcup_{g\in\mathbb{G}} g\mathbb{H}g^{-1}\times g\mathbb{H}g^{-1}}^{Z},\quad \mathbb{H}'\not=\overline{\langle u,v \rangle}^{Z}. \end{array}$

Unfortunately, the degeneration property fails for ${Sp_4}$ in characteristic ${3}$. $\Box$

O’Donnel: why tripling instead of doubling ? Answer: there exist small doubling subsets which are very far from subgroups.