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 .
This partly solves a more ambitious conjecture of L. Babai.
- 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.
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,
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.