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

Suppose that ${G = (G,\cdot)}$ is a finite group of even order, thus ${|G|}$ is a multiple of two. By Cauchy’s theorem, this implies that ${G}$ contains an involution: an element ${g}$ in ${G}$ of order two. (Indeed, if no such involution existed, then ${G}$ would be partitioned into doubletons ${\{g,g^{-1}\}}$ together with the identity, so that ${|G|}$ would be odd, a contradiction.) Of course, groups of odd order have no involutions ${g}$, thanks to Lagrange’s theorem (since ${G}$ cannot split into doubletons ${\{ h, hg \}}$).

The classical Brauer-Fowler theorem asserts that if a group ${G}$ has many involutions, then it must have a large non-trivial subgroup:

Theorem 1 (Brauer-Fowler theorem) Let ${G}$ be a finite group with at least ${|G|/n}$ involutions for some ${n > 1}$. Then ${G}$ contains a proper subgroup ${H}$ of index at most ${n^2}$.

This theorem (which is Theorem 2F in the original paper of Brauer and Fowler, who in fact manage to sharpen ${n^2}$ slightly to ${n(n+2)/2}$) has a number of quick corollaries which are also referred to as “the” Brauer-Fowler theorem. For instance, if ${g}$ is a an involution of a group ${G}$, and the centraliser ${C_G(g) := \{ h \in G: gh = hg\}}$ has order ${n}$, then clearly ${n \geq 2}$ (as ${C_G(g)}$ contains ${1}$ and ${g}$) and the conjugacy class ${\{ aga^{-1}: a \in G \}}$ has order ${|G|/n}$ (since the map ${a \mapsto aga^{-1}}$ has preimages that are cosets of ${C_G(g)}$). Every conjugate of an involution is again an involution, so by the Brauer-Fowler theorem ${G}$ contains a subgroup of order at least ${\max( n, |G|/n^2)}$. In particular, we can conclude that every group ${G}$ of even order contains a proper subgroup of order at least ${|G|^{1/3}}$.

Another corollary is that the size of a simple group of even order can be controlled by the size of a centraliser of one of its involutions:

Corollary 2 (Brauer-Fowler theorem) Let ${G}$ be a finite simple group with an involution ${g}$, and suppose that ${C_G(g)}$ has order ${n}$. Then ${G}$ has order at most ${(n^2)!}$.

Indeed, by the previous discussion ${G}$ has a proper subgroup ${H}$ of index less than ${n^2}$, which then gives a non-trivial permutation action of ${G}$ on the coset space ${G/H}$. The kernel of this action is a proper normal subgroup of ${G}$ and is thus trivial, so the action is faithful, and the claim follows.

If one assumes the Feit-Thompson theorem that all groups of odd order are solvable, then Corollary 2 suggests a strategy (first proposed by Brauer himself in 1954) to prove the classification of finite simple groups (CFSG) by induction on the order of the group. Namely, assume for contradiction that the CFSG failed, so that there is a counterexample ${G}$ of minimal order ${|G|}$ to the classification. This is a non-abelian finite simple group; by the Feit-Thompson theorem, it has even order and thus has at least one involution ${g}$. Take such an involution and consider its centraliser ${C_G(g)}$; this is a proper subgroup of ${G}$ of some order ${n < |G|}$. As ${G}$ is a minimal counterexample to the classification, one can in principle describe ${C_G(g)}$ in terms of the CFSG by factoring the group into simple components (via a composition series) and applying the CFSG to each such component. Now, the “only” thing left to do is to verify, for each isomorphism class of ${C_G(g)}$, that all the possible simple groups ${G}$ that could have this type of group as a centraliser of an involution obey the CFSG; Corollary 2 tells us that for each such isomorphism class for ${C_G(g)}$, there are only finitely many ${G}$ that could generate this class for one of its centralisers, so this task should be doable in principle for any given isomorphism class for ${C_G(g)}$. That’s all one needs to do to prove the classification of finite simple groups!

Needless to say, this program turns out to be far more difficult than the above summary suggests, and the actual proof of the CFSG does not quite proceed along these lines. However, a significant portion of the argument is based on a generalisation of this strategy, in which the concept of a centraliser of an involution is replaced by the more general notion of a normaliser of a ${p}$-group, and one studies not just a single normaliser but rather the entire family of such normalisers and how they interact with each other (and in particular, which normalisers of ${p}$-groups commute with each other), motivated in part by the theory of Tits buildings for Lie groups which dictates a very specific type of interaction structure between these ${p}$-groups in the key case when ${G}$ is a (sufficiently high rank) finite simple group of Lie type over a field of characteristic ${p}$. See the text of Aschbacher, Lyons, Smith, and Solomon for a more detailed description of this strategy.

The Brauer-Fowler theorem can be proven by a nice application of character theory, of the type discussed in this recent blog post, ultimately based on analysing the alternating tensor power of representations; I reproduce a version of this argument (taken from this text of Isaacs) below the fold. (The original argument of Brauer and Fowler is more combinatorial in nature.) However, I wanted to record a variant of the argument that relies not on the fine properties of characters, but on the cruder theory of quasirandomness for groups, the modern study of which was initiated by Gowers, and is discussed for instance in this previous post. It gives the following slightly weaker version of Corollary 2:

Corollary 3 (Weak Brauer-Fowler theorem) Let ${G}$ be a finite simple group with an involution ${g}$, and suppose that ${C_G(g)}$ has order ${n}$. Then ${G}$ can be identified with a subgroup of the unitary group ${U_{4n^3}({\bf C})}$.

One can get an upper bound on ${|G|}$ from this corollary using Jordan’s theorem, but the resulting bound is a bit weaker than that in Corollary 2 (and the best bounds on Jordan’s theorem require the CFSG!).

Proof: Let ${A}$ be the set of all involutions in ${G}$, then as discussed above ${|A| \geq |G|/n}$. We may assume that ${G}$ has no non-trivial unitary representation of dimension less than ${4n^3}$ (since such representations are automatically faithful by the simplicity of ${G}$); thus, in the language of quasirandomness, ${G}$ is ${4n^3}$-quasirandom, and is also non-abelian. We have the basic convolution estimate

$\displaystyle \|1_A * 1_A * 1_A - \frac{|A|^3}{|G|} \|_{\ell^\infty(G)} \leq (4n^3)^{-1/2} |G|^{1/2} |A|^{3/2}$

(see Exercise 10 from this previous blog post). In particular,

$\displaystyle 1_A * 1_A * 1_A(0) \geq \frac{|A|^3}{|G|} - (4n^3)^{-1/2} |G|^{1/2} |A|^{3/2} \geq \frac{1}{2n^3} |G|^2$

and so there are at least ${|G|^2/2n^3}$ pairs ${(g,h) \in A \times A}$ such that ${gh \in A^{-1} = A}$, i.e. involutions ${g,h}$ whose product is also an involution. But any such involutions necessarily commute, since

$\displaystyle g (gh) h = g^2 h^2 = 1 = (gh)^2 = g (hg) h.$

Thus there are at least ${|G|^2/2n^3}$ pairs ${(g,h) \in G \times G}$ of non-identity elements that commute, so by the pigeonhole principle there is a non-identity ${g \in G}$ whose centraliser ${C_G(g)}$ has order at least ${|G|/2n^3}$. This centraliser cannot be all of ${G}$ since this would make ${g}$ central which contradicts the non-abelian simple nature of ${G}$. But then the quasiregular representation of ${G}$ on ${G/C_G(g)}$ has dimension at most ${2n^3}$, contradicting the quasirandomness. $\Box$

The classification of finite simple groups (CFSG), first announced in 1983 but only fully completed in 2004, is one of the monumental achievements of twentieth century mathematics. Spanning hundreds of papers and tens of thousands of pages, it has been called the “enormous theorem”. A “second generation” proof of the theorem is nearly completed which is a little shorter (estimated at about five thousand pages in length), but currently there is no reasonably sized proof of the classification.

An important precursor of the CFSG is the Feit-Thompson theorem from 1962-1963, which asserts that every finite group of odd order is solvable, or equivalently that every non-abelian finite simple group has even order. This is an immediate consequence of CFSG, and conversely the Feit-Thompson theorem is an essential starting point in the proof of the classification, since it allows one to reduce matters to groups of even order for which key additional tools (such as the Brauer-Fowler theorem) become available. The original proof of the Feit-Thompson theorem is 255 pages long, which is significantly shorter than the proof of the CFSG, but still far from short. While parts of the proof of the Feit-Thompson theorem have been simplified (and it has recently been converted, after six years of effort, into an argument that has been verified by the proof assistant Coq), the available proofs of this theorem are still extremely lengthy by any reasonable standard.

However, there is a significantly simpler special case of the Feit-Thompson theorem that was established previously by Suzuki in 1957, which was influential in the proof of the more general Feit-Thompson theorem (and thus indirectly to the proof of CFSG). Define a CA-group to be a group ${G}$ with the property that the centraliser ${C_G(x) := \{ g \in G: gx=xg \}}$ of any non-identity element ${x \in G}$ is abelian; equivalently, the commuting relation ${x \sim y}$ (defined as the relation that holds when ${x}$ commutes with ${y}$, thus ${xy=yx}$) is an equivalence relation on the non-identity elements ${G \backslash \{1\}}$ of ${G}$. Trivially, every abelian group is CA. A non-abelian example of a CA-group is the ${ax+b}$ group of invertible affine transformations ${x \mapsto ax+b}$ on a field ${F}$. A little less obviously, the special linear group ${SL_2(F_q)}$ over a finite field ${F_q}$ is a CA-group when ${q}$ is a power of two. The finite simple groups of Lie type are not, in general, CA-groups, but when the rank is bounded they tend to behave as if they were “almost CA”; the centraliser of a generic element in ${SL_d(F_q)}$, for instance, when ${d}$ is bounded and ${q}$ is large), is typically a maximal torus (because most elements in ${SL_d(F_q)}$ are regular semisimple) which is certainly abelian. In view of the CFSG, we thus see that CA or nearly CA groups form an important subclass of the simple groups, and it is thus of interest to study them separately. To this end, we have

Theorem 1 (Suzuki’s theorem on CA-groups) Every finite CA-group of odd order is solvable.

Of course, this theorem is superceded by the more general Feit-Thompson theorem, but Suzuki’s proof is substantially shorter (the original proof is nine pages) and will be given in this post. (See this survey of Solomon for some discussion of the link between Suzuki’s argument and the Feit-Thompson argument.) Suzuki’s analysis can be pushed further to give an essentially complete classification of all the finite CA-groups (of either odd or even order), but we will not pursue these matters here.

Moving even further down the ladder of simple precursors of CSFG is the following theorem of Frobenius from 1901. Define a Frobenius group to be a finite group ${G}$ which has a subgroup ${H}$ (called the Frobenius complement) with the property that all the non-trivial conjugates ${gHg^{-1}}$ of ${H}$ for ${g \in G \backslash H}$, intersect ${H}$ only at the origin. For instance the ${ax+b}$ group is also a Frobenius group (take ${H}$ to be the affine transformations that fix a specified point ${x_0 \in F}$, e.g. the origin). This example suggests that there is some overlap between the notions of a Frobenius group and a CA group. Indeed, note that if ${G}$ is a CA-group and ${H}$ is a maximal abelian subgroup of ${G}$, then any conjugate ${gHg^{-1}}$ of ${H}$ that is not identical to ${H}$ will intersect ${H}$ only at the origin (because ${H}$ and each of its conjugates consist of equivalence classes under the commuting relation ${\sim}$, together with the identity). So if a maximal abelian subgroup ${H}$ of a CA-group is its own normaliser (thus ${N(H) := \{ g \in G: gH=Hg\}}$ is equal to ${H}$), then the group is a Frobenius group.

Frobenius’ theorem places an unexpectedly strong amount of structure on a Frobenius group:

Theorem 2 (Frobenius’ theorem) Let ${G}$ be a Frobenius group with Frobenius complement ${H}$. Then there exists a normal subgroup ${K}$ of ${G}$ (called the Frobenius kernel of ${G}$) such that ${G}$ is the semi-direct product ${H \ltimes K}$ of ${H}$ and ${K}$.

Roughly speaking, this theorem indicates that all Frobenius groups “behave” like the ${ax+b}$ example (which is a quintessential example of a semi-direct product).

Note that if every CA-group of odd order was either Frobenius or abelian, then Theorem 2 would imply Theorem 1 by an induction on the order of ${G}$, since any subgroup of a CA-group is clearly again a CA-group. Indeed, the proof of Suzuki’s theorem does basically proceed by this route (Suzuki’s arguments do indeed imply that CA-groups of odd order are Frobenius or abelian, although we will not quite establish that fact here).

Frobenius’ theorem can be reformulated in the following concrete combinatorial form:

Theorem 3 (Frobenius’ theorem, equivalent version) Let ${G}$ be a group of permutations acting transitively on a finite set ${X}$, with the property that any non-identity permutation in ${G}$ fixes at most one point in ${X}$. Then the set of permutations in ${G}$ that fix no points in ${X}$, together with the identity, is closed under composition.

Again, a good example to keep in mind for this theorem is when ${G}$ is the group of affine permutations on a field ${F}$ (i.e. the ${ax+b}$ group for that field), and ${X}$ is the set of points on that field. In that case, the set of permutations in ${G}$ that do not fix any points are the non-trivial translations.

To deduce Theorem 3 from Theorem 2, one applies Theorem 2 to the stabiliser of a single point in ${X}$. Conversely, to deduce Theorem 2 from Theorem 3, set ${X := G/H = \{ gH: g \in G \}}$ to be the space of left-cosets of ${H}$, with the obvious left ${G}$-action; one easily verifies that this action is faithful, transitive, and each non-identity element ${g}$ of ${G}$ fixes at most one left-coset of ${H}$ (basically because it lies in at most one conjugate of ${H}$). If we let ${K}$ be the elements of ${G}$ that do not fix any point in ${X}$, plus the identity, then by Theorem 3 ${K}$ is closed under composition; it is also clearly closed under inverse and conjugation, and is hence a normal subgroup of ${G}$. From construction ${K}$ is the identity plus the complement of all the ${|G|/|H|}$ conjugates of ${H}$, which are all disjoint except at the identity, so by counting elements we see that

$\displaystyle |K| = |G| - \frac{|G|}{|H|}(|H|-1) = |G|/|H|.$

As ${H}$ normalises ${K}$ and is disjoint from ${K}$, we thus see that ${KH = H \ltimes K}$ is all of ${G}$, giving Theorem 2.

Despite the appealingly concrete and elementary form of Theorem 3, the only known proofs of that theorem (or equivalently, Theorem 2) in its full generality proceed via the machinery of group characters (which one can think of as a version of Fourier analysis for nonabelian groups). On the other hand, once one establishes the basic theory of these characters (reviewed below the fold), the proof of Frobenius’ theorem is very short, which gives quite a striking example of the power of character theory. The proof of Suzuki’s theorem also proceeds via character theory, and is basically a more involved version of the Frobenius argument; again, no character-free proof of Suzuki’s theorem is currently known. (The proofs of Feit-Thompson and CFSG also involve characters, but those proofs also contain many other arguments of much greater complexity than the character-based portions of the proof.)

It seems to me that the above four theorems (Frobenius, Suzuki, Feit-Thompson, and CFSG) provide a ladder of sorts (with exponentially increasing complexity at each step) to the full classification, and that any new approach to the classification might first begin by revisiting the earlier theorems on this ladder and finding new proofs of these results first (in particular, if one had a “robust” proof of Suzuki’s theorem that also gave non-trivial control on “almost CA-groups” – whatever that means – then this might lead to a new route to classifying the finite simple groups of Lie type and bounded rank). But even for the simplest two results on this ladder – Frobenius and Suzuki – it seems remarkably difficult to find any proof that is not essentially the character-based proof. (Even trying to replace character theory by its close cousin, representation theory, doesn’t seem to work unless one gives in to the temptation to take traces everywhere and put the characters back in; it seems that rather than abandon characters altogether, one needs to find some sort of “robust” generalisation of existing character-based methods.) In any case, I am recording here the standard character-based proofs of the theorems of Frobenius and Suzuki below the fold. There is nothing particularly novel here, but I wanted to collect all the relevant material in one place, largely for my own benefit.