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

I’ve just finished the first draft of my book “Expansion in finite simple groups of Lie type“, which is  based in the lecture notes for my graduate course on this topic that were previously posted on this blog.  It also contains some newer material, such as the notes on Lie algebras and Lie groups that I posted most recently here.

Emmanuel Breuillard, Ben Green, Bob Guralnick, and I have just uploaded to the arXiv our joint paper “Expansion in finite simple groups of Lie type“. This long-delayed paper (announced way back in 2010!) is a followup to our previous paper in which we showed that, with one possible exception, generic pairs of elements of a simple algebraic group (over an uncountable field) generated a free group which was strongly dense in the sense that any nonabelian subgroup of this group was Zariski dense. The main result of this paper is to establish the analogous result for finite simple groups of Lie type (as defined in the previous blog post) and bounded rank, namely that almost all pairs ${a,b}$ of elements of such a group generate a Cayley graph which is a (two-sided) expander, with expansion constant bounded below by a quantity depending on the rank of the group. (Informally, this means that the random walk generated by ${a,b}$ spreads out in logarithmic time to be essentially uniformly distributed across the group, as opposed for instance to being largely trapped in an algebraic subgroup. Thus if generic elements did not generate a strongly dense group, one would probably expect expansion to fail.)

There are also some related results established in the paper. Firstly, as we discovered after writing our first paper, there was one class of algebraic groups for which our demonstration of strongly dense subgroups broke down, namely the ${Sp_4}$ groups in characteristic three. In the current paper we provide in a pair of appendices a new argument that covers this case (or more generally, ${Sp_4}$ in odd characteristic), by first reducing to the case of affine groups ${k^2 \rtimes SL_2(k)}$ (which can be found inside ${Sp_4}$ as a subgroup) and then using a ping-pong argument (in a p-adic metric) in the latter context.

Secondly, we show that the distinction between one-sided expansion and two-sided expansion (see this set of lecture notes of mine for definitions) is erased in the context of Cayley graphs of bounded degree, in the sense that such graphs are one-sided expanders if and only if they are two-sided expanders (perhaps with slightly different expansion constants). The argument turns out to be an elementary combinatorial one, based on the “pivot” argument discussed in these lecture notes of mine.

Now to the main result of the paper, namely the expansion of random Cayley graphs. This result had previously been established for ${SL_2}$ by Bourgain and Gamburd, and Ben, Emmanuel and I had used the Bourgain-Gamburd method to achieve the same result for Suzuki groups. For the other finite simple groups of Lie type, expander graphs had been constructed by Kassabov, Lubotzky, and Nikolov, but they required more than two generators, which were placed deterministically rather than randomly. (Here, I am skipping over a large number of other results on expanding Cayley graphs; see this survey of Lubotzsky for a fairly recent summary of developments.) The current paper also uses the “Bourgain-Gamburd machine”, as discussed in these lecture notes of mine, to demonstrate expansion. This machine shows how expansion of a Cayley graph follows from three basic ingredients, which we state informally as follows:

• Non-concentration (A random walk in this graph does not concentrate in a proper subgroup);
• Product theorem (A medium-sized subset of this group which is not trapped in a proper subgroup will expand under multiplication); and
• Quasirandomness (The group has no small non-trivial linear representations).

Quasirandomness of arbitrary finite simple groups of Lie type was established many years ago (predating, in fact, the introduction of the term “quasirandomness” by Gowers for this property) by Landazuri-Seitz and Seitz-Zalesskii, and the product theorem was already established by Pyber-Szabo and independently by Breuillard, Green, and myself. So the main problem is to establish non-concentration: that for a random Cayley graph on a finite simple group ${G}$ of Lie type, random walks did not concentrate in proper subgroups.

The first step was to classify the proper subgroups of ${G}$. Fortunately, these are all known; in particular, such groups are either contained in proper algebraic subgroups of the algebraic group containing ${G}$ (or a bounded cover thereof) with bounded complexity, or are else arising (up to conjugacy) from a version ${G(F')}$ of the same group ${G =G(F)}$ associated to a proper subfield ${F'}$ of the field ${F}$ respectively; this follows for instance from the work of Larsen and Pink, but also can be deduced using the classification of finite simple groups, together with some work of Aschbacher, Liebeck-Seitz, and Nori. We refer to the two types of subgroups here as “structural subgroups” and “subfield subgroups”.

To preclude concentration in a structural subgroup, we use our previous result that generic elements of an algebraic group generate a strongly dense subgroup, and so do not concentrate in any algebraic subgroup. To translate this result from the algebraic group setting to the finite group setting, we need a Schwarz-Zippel lemma for finite simple groups of Lie type. This is straightforward for Chevalley groups, but turns out to be a bit trickier for the Steinberg and Suzuki-Ree groups, and we have to go back to the Chevalley-type parameterisation of such groups in terms of (twisted) one-parameter subgroups, that can be found for instance in the text of Carter; this “twisted Schwartz-Zippel lemma” may possibly have further application to analysis on twisted simple groups of Lie type. Unfortunately, the Schwartz-Zippel estimate becomes weaker in twisted settings, and particularly in the case of triality groups ${{}^3 D_4(q)}$, which require a somewhat ad hoc additional treatment that relies on passing to a simpler subgroup present in a triality group, namely a central product of two different ${SL_2}$‘s.

To rule out concentration in a conjugate of a subfield group, we repeat an argument we introduced in our Suzuki paper and pass to a matrix model and analyse the coefficients of the characteristic polynomial of words in this Cayley graph, to prevent them from concentrating in a subfield. (Note that these coefficients are conjugation-invariant.)

In this previous post I recorded some (very standard) material on the structural theory of finite-dimensional complex Lie algebras (or Lie algebras for short), with a particular focus on those Lie algebras which were semisimple or simple. Among other things, these notes discussed the Weyl complete reducibility theorem (asserting that semisimple Lie algebras are the direct sum of simple Lie algebras) and the classification of simple Lie algebras (with all such Lie algebras being (up to isomorphism) of the form ${A_n}$, ${B_n}$, ${C_n}$, ${D_n}$, ${E_6}$, ${E_7}$, ${E_8}$, ${F_4}$, or ${G_2}$).

Among other things, the structural theory of Lie algebras can then be used to build analogous structures in nearby areas of mathematics, such as Lie groups and Lie algebras over more general fields than the complex field ${{\bf C}}$ (leading in particular to the notion of a Chevalley group), as well as finite simple groups of Lie type, which form the bulk of the classification of finite simple groups (with the exception of the alternating groups and a finite number of sporadic groups).

In the case of complex Lie groups, it turns out that every simple Lie algebra ${\mathfrak{g}}$ is associated with a finite number of connected complex Lie groups, ranging from a “minimal” Lie group ${G_{ad}}$ (the adjoint form of the Lie group) to a “maximal” Lie group ${\tilde G}$ (the simply connected form of the Lie group) that finitely covers ${G_{ad}}$, and occasionally also a number of intermediate forms which finitely cover ${G_{ad}}$, but are in turn finitely covered by ${\tilde G}$. For instance, ${\mathfrak{sl}_n({\bf C})}$ is associated with the projective special linear group ${\hbox{PSL}_n({\bf C}) = \hbox{PGL}_n({\bf C})}$ as its adjoint form and the special linear group ${\hbox{SL}_n({\bf C})}$ as its simply connected form, and intermediate groups can be created by quotienting out ${\hbox{SL}_n({\bf C})}$ by some subgroup of its centre (which is isomorphic to the ${n^{th}}$ roots of unity). The minimal form ${G_{ad}}$ is simple in the group-theoretic sense of having no normal subgroups, but the other forms of the Lie group are merely quasisimple, although traditionally all of the forms of a Lie group associated to a simple Lie algebra are known as simple Lie groups.

Thanks to the work of Chevalley, a very similar story holds for algebraic groups over arbitrary fields ${k}$; given any Dynkin diagram, one can define a simple Lie algebra with that diagram over that field, and also one can find a finite number of connected algebraic groups over ${k}$ (known as Chevalley groups) with that Lie algebra, ranging from an adjoint form ${G_{ad}}$ to a universal form ${G_u}$, with every form having an isogeny (the analogue of a finite cover for algebraic groups) to the adjoint form, and in turn receiving an isogeny from the universal form. Thus, for instance, one could construct the universal form ${E_7(q)_u}$ of the ${E_7}$ algebraic group over a finite field ${{\bf F}_q}$ of finite order.

When one restricts the Chevalley group construction to adjoint forms over a finite field (e.g. ${\hbox{PSL}_n({\bf F}_q)}$), one usually obtains a finite simple group (with a finite number of exceptions when the rank and the field are very small, and in some cases one also has to pass to a bounded index subgroup, such as the derived group, first). One could also use other forms than the adjoint form, but one then recovers the same finite simple group as before if one quotients out by the centre. This construction was then extended by Steinberg, Suzuki, and Ree by taking a Chevalley group over a finite field and then restricting to the fixed points of a certain automorphism of that group; after some additional minor modifications such as passing to a bounded index subgroup or quotienting out a bounded centre, this gives some additional finite simple groups of Lie type, including classical examples such as the projective special unitary groups ${\hbox{PSU}_n({\bf F}_{q^2})}$, as well as some more exotic examples such as the Suzuki groups or the Ree groups.

While I learned most of the classical structural theory of Lie algebras back when I was an undergraduate, and have interacted with Lie groups in many ways in the past (most recently in connection with Hilbert’s fifth problem, as discussed in this previous series of lectures), I have only recently had the need to understand more precisely the concepts of a Chevalley group and of a finite simple group of Lie type, as well as better understand the structural theory of simple complex Lie groups. As such, I am recording some notes here regarding these concepts, mainly for my own benefit, but perhaps they will also be of use to some other readers. The material here is standard, and was drawn from a number of sources, but primarily from Carter, Gorenstein-Lyons-Solomon, and Fulton-Harris, as well as the lecture notes on Chevalley groups by my colleague Robert Steinberg. The arrangement of material also reflects my own personal preferences; in particular, I tend to favour complex-variable or Riemannian geometry methods over algebraic ones, and this influenced a number of choices I had to make regarding how to prove certain key facts. The notes below are far from a comprehensive or fully detailed discussion of these topics, and I would refer interested readers to the references above for a properly thorough treatment.

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.