You are currently browsing the tag archive for the ‘Suzuki groups’ tag.

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 {G}, there exists a set of generators {S} of cardinality bounded uniformly in {G}, such that the Cayley graph {\hbox{Cay}(G,S)} on {G} generated by {S} (i.e. the graph that connects {g} with {sg} for all {g \in G} and {s \in S}) has expansion constant bounded away from zero uniformly in {G}, or equivalently that {|A \cdot S| \geq (1+\epsilon) |A|} for all {A \subset G} with {|A| < |G|/2} and some {\epsilon>0} independent of {G}.

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 ({O(\log |G|)}, to be more precise) randomly chosen elements of a fixed set {S}. (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 {{\bf Z}/p{\bf Z}} 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 {G} in all of these families contain a copy of {SL_2({\bf F}_q)} for some {q} that goes to infinity as {|G| \rightarrow \infty}. 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 {Sz(q)}, where {q = 2^{2n+1}} is an odd power of {2}. The Suzuki group {Sz(q)} can be viewed explicitly as a subgroup of the symplectic group {Sp_4(q)} and has cardinality {q^2 (q^2+1)(q-1) \approx q^5}. This cardinality is not divisible by {3}, whereas all groups of the form {SL_2(k)} have cardinality divisible by {3}; thus Suzuki groups do not contain copies of {SL_2} 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 {a, b} of the Suzuki group, and with probability {1-o_{q \rightarrow \infty}(1)}, the Cayley graph generated by {S = \{a,b,a^{-1},b^{-1}\}} will be an expander uniformly in {q}. (As stated in the paper of Kassabov-Lubotsky-Nikolov, the methods in that paper should give an upper bound on {S} which they conservatively estimate to be {1000}.)

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 {SL_2({\bf F}_p)} ({p} 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 {\mu} be the uniform probability measure on the randomly chosen set of generators {S}, and let {\mu^{(n)}} be the {n}-fold convolution. We need {\mu^{(n)}} to converge rapidly to the uniform measure on {G} (with a mixing time of {O(\log |G|)}). There are three steps to obtain this mixing:

  • (Early period) When {n \sim c \log |G|} for some small {c > 0}, one wants {\mu^{(n)}} to spread out a little bit in the sense that no individual element of {G} is assigned a mass of any more than {|G|^{-\epsilon}} for some fixed {\epsilon > 0}. More generally, no proper subgroup {H} of {G} should be assigned a mass of more than {|G|^{-\epsilon}}.
  • (Middle period) Once {\mu^{(n)}} is somewhat spread out, one should be able to convolve this measure with itself a bounded number of times and conclude that the measure {\mu^{(Cn)}} for some suitable {C} is reasonably spread out in the sense that its {L^2} norm is comparable (up to powers of {|G|^{\epsilon}} for some small {\epsilon > 0}) to the {L^2} norm of the uniform distribution.
  • (Late period) Once {\mu^{(n)}} is reasonably spread out, a few more convolutions should make it extremely close to uniform (e.g. within {|G|^{-10}} in the {L^\infty} 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 {\gg q^{3/2}}, 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 {Sz(q)} 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 {SL_2({\bf F}_p)}.) This requires checking that {Sz(q)} is a “sufficiently Zariski dense” subgroup of the finite Lie group {Sp_4(q)}, 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 {S} away from subgroups {H} of {Sz(q)}. 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 {Sz(q_0)}, where {{\bf F}_{q_0}} is a subfield of {{\bf F}_q}.

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 {SL_2} 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 {S} does not fall into a proper subfield of {{\bf F}_q}, but this can be accomplished by a variant of the Schwartz-Zippel lemma.

Archives

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 3,595 other followers