Notes of Emmanuel Breuillard’s talk

Posted on March 23, 2011 by metric2011

 

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}

 

1.1. Comments

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 http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged , . Bookmark the permalink.

Leave a comment