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.



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s