Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv the paper “Suzuki groups as expanders“, to be submitted. The purpose of this paper is to finish off the last case of the following theorem:
Theorem 1 (All finite simple groups have expanders) For every finite simple non-abelian group 
, there exists a set of generators 
of cardinality bounded uniformly in , such that the Cayley graph 
on generated by (i.e. the graph that connects 
with 
for all 
and 
) has expansion constant bounded away from zero uniformly in , or equivalently that 
for all 
with 
and some 
independent of .
To put in an essentially equivalent way, one can quickly generate a random element of a finite simple group with a near-uniform distribution by multiplying together a few (
, to be more precise) randomly chosen elements of a fixed set . (The most well-known instance of this phenomenon is the famous result of Bayer and Diaconis that one can shuffle a 52-card deck reasonably well after seven riffle shuffles, and almost perfectly after ten.) Note that the abelian simple groups 
do not support expanders due to the slow mixing time of random walks in the abelian setting.
The first step in proving this theorem is, naturally enough, the classification of finite simple groups. The sporadic groups have bounded cardinality and are a trivial case of this theorem, so one only has to deal with the seventeen infinite families of finite non-abelian simple groups. With one exception, the groups in all of these families contain a copy of 
for some 
that goes to infinity as 
. Using this and several other non-trivial tools (such as Kazhdan’s property (T) and a deep model-theoretic result of Hrushovski and Pillay), the above theorem was proven for all groups outside of this exceptional family by a series of works culminating in the paper of Kassabov, Lubotzky, and Nikolov.
The exceptional family is the family of Suzuki groups 
, where 
is an odd power of 
. The Suzuki group can be viewed explicitly as a subgroup of the symplectic group 
and has cardinality 
. This cardinality is not divisible by 
, whereas all groups of the form 
have cardinality divisible by ; thus Suzuki groups do not contain copies of 
and the Kassabov-Lubotsky-Nikolov argument does not apply.
Our main result is that the Suzuki groups also support expanders, thus completing the last case of the above theorem. In fact we can pick just two random elements 
of the Suzuki group, and with probability 
, the Cayley graph generated by 
will be an expander uniformly in . (As stated in the paper of Kassabov-Lubotsky-Nikolov, the methods in that paper should give an upper bound on which they conservatively estimate to be 
.)
Our methods are different, instead following closely the arguments of Bourgain and Gamburd, which established the analogue of our result (i.e. that two random elements generate an expander graph) for the family of groups 
(
a large prime); the arguments there have since been generalised to several other major families of groups, and our result here can thus be viewed as one further such generalisation. Roughly speaking, the strategy is as follows. Let 
be the uniform probability measure on the randomly chosen set of generators , and let 
be the 
-fold convolution. We need to converge rapidly to the uniform measure on (with a mixing time of ). There are three steps to obtain this mixing:
- (Early period) When
for some small 
, one wants to spread out a little bit in the sense that no individual element of is assigned a mass of any more than 
for some fixed 
. More generally, no proper subgroup 
of should be assigned a mass of more than .
- (Middle period) Once is somewhat spread out, one should be able to convolve this measure with itself a bounded number of times and conclude that the measure
for some suitable 
is reasonably spread out in the sense that its 
norm is comparable (up to powers of 
for some small ) to the norm of the uniform distribution.
- (Late period) Once is reasonably spread out, a few more convolutions should make it extremely close to uniform (e.g. within
in the 
norm).
The late period claim is easy to establish from Gowers’ theory of quasirandom groups, the key point being that (like all other finite simple nonabelian groups), the Suzuki groups do not admit any non-trivial low-dimensional irreducible representations (we can for instance use a precise lower bound of 
, due to Landazuri and Seitz). (One can also proceed here using a trace formula argument of Sarnak and Xue; the two approaches are basically equivalent.) The middle period reduces, by a variant of the Balog-Szemerédi-Gowers lemma, to a product estimate in which was recently established by Pyber-Szábo and can also be obtained by the methods of proof of the results announced by ourselves. (These arguments are in turn based on an earlier result of Helfgott establishing the analogous claim for .) This requires checking that is a “sufficiently Zariski dense” subgroup of the finite Lie group , but this can be done using an explicit description of the Suzuki group and the Schwartz-Zippel lemma.
The main difficulty is then to deal with the early period, obtaining some initial non-concentration in the random walk associated to away from subgroups of . These subgroups have been classified for some time (see e.g. the book of Wilson); they split into two families, the algebraic subgroups, which in the Suzuki case turn out to be solvable of derived length at most three, and the arithmetic subgroups, which are conjugate to 
, where 
is a subfield of 
.
In the algebraic case, one can prevent concentration using a lower bound on the girth of random Cayley graphs due to Gamburd, Hoory, Shahshahani, Shalev, and Virág (and we also provide an independent proof of this fact for completeness, which fortunately is able to avoid any really deep technology, such as Lang-Weil estimates); this follows an analogous argument of Bourgain-Gamburd in the case fairly closely, and is ultimately based on the fact that all the algebraic subgroups obey a fixed law (in this case, the law arises from the solvability). In the arithmetic case, the main task is to show that the coefficients of the characteristic polynomial of a typical word in does not fall into a proper subfield of , but this can be accomplished by a variant of the Schwartz-Zippel lemma.
Recent Comments