**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 . 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 be a finite simple group of Lie type, . Then for every generating set ,

where depends only on the dimension of , not on .

Corollary 2

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

Theorem 3 (Breuillard, Green, Guralnick, Tao 2011)Let be a finite simple group of Lie type, , . Then there exists such that

** 1.1. Comments **

Remark 1

For , it is due to Bourgain and Gamburd.requires a special treatment.Can one make independent of in Theorem 3 ? Breuillard-Gamburd have partial results for .

**Question**: All Cayley graphs are -expanders, ?

** 1.2. Scheme of proof of Theorem \ref **

}

Recall that is an -expander iff random walk on becomes equidistributed in time logarithmic in . In other words, is close to uniform measure for .

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

for a certain universal constant .

Bourgain-Gamburd trick also generalizes to all finite simple groups. If , then the random walk behaves like that on a tree, at least when . This implies that for . Gamburd and coauthors have proven that for most choices of and .

There remains to fill the gap between and .

** 1.3. Mass of subgroups **

The product theorem allows to show subexponential decay of for . This is shown by comparing with for in this interval. If , then among level sets , one of them will have .

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

The difficulty is that, unlike for , general finite simple groups of Lie type have many different subgroups. We shall use a Fubini type argument.

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

Proposition 5There exist , such that for all non commuting words and in the free group on two generators, the probability

uniformly for , .

Our proof uses algebraic geometry, and does not seem to extend to .

** 1.4. Ingredients of the proof of Proposition \ref **

}

- Classification of subgroups (Larsen-Pink) into
- structural subgroups ;
- subfield groups where divides .

- Lang-Weil type bounds on the number of points of algebraic subvarieties: .
- Existence of strongly dense free subgroups.

** 1.5. Existence of strongly dense free subgroups **

Theorem 6 (Breuillard, Green, Guralnick, Tao 2011)semisimple algebraic group over un uncountable algebraically closed field . Then there exist , such that 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 , the word map , is dominant, i.e. its image contains an open set of .

Then argue by induction on dim (as Borel does).

Finish with a degeneration argument: For every semisimple subgroup in , there is a semisimple subgroup which is not a degeneration of , i.e. for all

Unfortunately, the degeneration property fails for in characteristic .

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