The symmetric group, 12

This instalment is about the maximal subgroups of the symmetric group, and the O’Nan–Scott Theorem. There are two versions of this theorem, one of which is sometimes called the Aschbacher–O’Nan–Scott Theorem. One is about maximal subgroups of the symmetric group (this is my main focus), the other about primitive permutation groups; but there are connections.

The subgroup structure of a group gives extremely important information about the group. If we know about the maximal subgroups, we have the possibility of working down the subgroup lattice to understand all subgroups. There is another reason why the maximal subgroups are important. In order to explain this, I’ll start with a crash course in group actions.

Group actions and permutation groups

An action of a group G is a homomorphism from G to the symmetric group on a set Ω. The image of the action is a permutation group, a subgroup of the symmetric group. Most properties of the action in which we are interested are properties of its image; so the theories of group actions and permutation groups are almost identical.

Two actions of G on sets Ω1 and Ω2 are isomorphic if there is a bijection between the two domains such that the permutations induced by any element of G correspond under the bijection. As usual in algebra we don’t need to distinguish between isomorphic actions.

The action of G on Ω is transitive if, for any two elements α and β of Ω, there is an element of G whose corresponding permutation carries α to β; in other words, if no non-trivial subset of Ω is preserved by the image of the action. (For this purpose, the trivial subsets are the empty set and the whole of Ω.) A transitive action(on more than one point) is primitive if no non-trivial partition of Ω is preserved (where the trivial partitions are the partition into singletons and the partition with a single part).

There is a sense in which the study of arbitrary actions or permutation groups can be “reduced” to the study of transitive ones, and the study of transitive actions to that of primitive ones. The details of this are not so important here. We want to be able to describe all transitive or primitive actions of a group G.

Let H be a subgroup of G, and let Ω be the set of all right cosets of H in G. There is an action of G on Ω by right multiplication: the group element g induces the permutation Hx → Hxg of Ω. Now the following result records the main facts:

  • Any transitive action of G is isomorphic to the action on the set of right cosets of a subgroup.
  • The actions on the sets of right cosets of subgroups H and K are isomorphic if and only if the subgroups H and K are conjugate.
  • The action of G on the set of right cosets of H is primitive if and only if H is a maximal subgroup of G.

So maximal subgroups and primitive actions are “the same thing” regarded from different points of view.

Some history

In 1979, a conference on Finite Groups was held in Santa Cruz. At the time, there was a feeling in the air that the Classification of Finite Simple Groups was almost complete, and some people had begun to think about the implications of the result for finite group theory in general. (I imagine that most of the participants would have been surprised then to learn that the proof would not be completed for a quarter of a century.)

I was not at the conference, but I spent a sabbatical in Sydney shortly afterwards. Somebody (I don’t recall who, but it was probably Terry Gagen) had brought the preliminary proceedings of the conference, which I borrowed. These proceedings consisted of preprints of the papers (or in some cases just abstracts) from the conference. The final version was published later in hardback by the American Mathematical Society.

I was struck by a theorem stated independently by Michael O’Nan and Leonard Scott. Each of their papers was about something different, with the theorem stated as a kind of afterthought. I began to think about the theorem, which was a classification of maximal subgroups of symmetric and alternating groups, and its implications for the study of permutation groups. The theorem essentially provided a method for applying the CFSG to the study of primitive permutation groups. There was so much low-hanging fruit waiting to be picked that I offered to give a course of lectures on it; this later became one of my most-cited papers when published as a survey in the Bulletin of the London Mathematical Society.

Later, Peter Neumann showed me that most of the theorem is contained in Camille Jordan’s Traité des Substitutions from 1870. It includes a theorem of Burnside on doubly transitive groups as a special case; it seems that Burnside (and everyone else) was unaware of Jordan’s work. Why? Perhaps the most plausible hypothesis is that, until we had CFSG, the theorem was not of much use, and was not considered worth pursuing.

When the final version of the conference proceedings appeared, O’Nan’s paper was not there, and so the first official reference to it is Scott’s paper entitled “Representations in characteristic p“. I don’t know why.

The O’Nan–Scott Theorem

For shorthand, I will use the term “maximal subgroup of Sn or An” to mean a subgroup of Sn which is either a maximal subgroup of Sn which is not equal to An, or a maximal subgroup of An.

Thus, after the statement of the theorem, some questions will remain:

  • Which of these subgroups are actually contained in An?
  • (The harder question) Which of them are actually maximal?

An intransitive subgroup fixes a subset (of cardinality k, say); so, if it is maximal, then it consists of all permutations fixing this subgroup, which form the direct product Sk × Sn-k.

Similarly, an imprimitive subgroup fixes a partition into m sets of size k, where mk = n; if it is maximal, it consists of all the permutations fixing this partition, and is the wreath product Sk wr Sm. (The given action is called the imprimitive action of the wreath product.)

This wreath product has another action, the product action (or power action) on a set of size km, consisting of all m-element sets which are transversals to the partition.

The affine group AGL(d,p) is the semidirect product of the additive group of a d-dimensional vector space over the integers mod p and the general linear group of invertible linear transformations of this space. It acts on the vector space.

Let T be a non-abelian finite simple group and k an integer at least 2. The diagonal group D(T,k) is an extension of the kth direct power of T by the product of the automorphism group of T (acting in the same way on each factor, with inner automorphisms identified with the diagonal elements (t,t,…,t) of Tk), and the symmetric group Sk permuting the factors. It acts on the set of cosets of the subgroup generated by Aut(T) and Sk.

In all these cases, the group and the action are both specified; this is not so in the remaining case. A group G is almost simple if it lies between a non-abelian simple group T and its automorphism group.

Now the O’Nan–Scott Theorem states:

A maximal subgroup of Sn or An is one of the following:

  • An intransitive group Sk × Sn-k;
  • Sk wr Sm in its imprimitive action, where mk = n;
  • Sk wr Sm in its product action, where km = n;
  • AGL(d,p), where pd = n;
  • D(T,k), where |T|k-1 = n;
  • an almost simple group in some primitive action.

To prove this theorem, we see that the cases where the maximal subgroup H is intransitive, or transitive but imprimitive, are covered. If H is primitive, then it is known that its socle (the product of the minimal normal subgroups) is the product of copies of a finite simple group T. If T is abelian, then H is affine; so suppose not. If there is more than one factor, the hardest part of the argument shows that H is either a wreath product with product action or of diagonal type. If there is just one factor, then H is almost simple, by definition.

Some consequences

The other version of the O’Nan–Scott theorem refers to primitive permutation groups. These fall into five classes, the first four being the last four in the statement above (suitably generalised), and the fifth being a new class, the so-called twisted wreath products. This class was omitted from early statements of the theorem (indeed, as we have seen, it is not necessary for the “maximal subgroups of symmetric and alternating groups” form, since twisted wreath products are contained in wreath products with the product action). It was pointed out by Michael Aschbacher, hence the alternative name which is sometimes used for the theorem.

For the applications I will describe, the form of the theorem I have given will suffice.

The message of these applications is: primitive groups are small, and they are rare. The smallness of primitive groups is needed for accurate estimates connected with Dixon’s Theorem, which I mentioned in the preceding post in the sequence.

To show that primitive groups are small (or rare), it suffices to prove that primitive maximal subgroups are small (or rare).

Bounds for orders of primitive groups are one of the oldest topics in permutation group theory. In the modern period, Laszlo Babai proved a bound of n4√n log n in 1981, by elegant combinatorial methods. Sadly, it was recognised almost immediately that a better bound (and, indeed, far better bounds with known specific exceptions) follows from the O’Nan–Scott Theorem and CFSG. Indeed, it is now known that almost simple primitive groups, with explicitly known exceptions, have order bounded by a polynomial in n.

The rarity of primitive groups is illustrated by the following theorem which I proved with Peter Neumann and David Teague. Let e(x) be the number of positive integers n smaller than x for which a primitive group of degree n, other than the symmetric or alternating group, exists. Then

e(x) ∼ 2π(x) + (1+√2)x1/2+O(x1/2/log x).

Here π(x) is the number of prime numbers not exceeding x. The terms in the asymptotic series correspond to particular types of primitive group. For example, 2π(x) is accounted for by primes p (the cyclic group of order p) and numbers p+1, where p is prime (the groups PSL(2,p). The next term is accounted for by Sm acting on 2-element subsets and the product action of Sm wr S2. And so on; the asymptotic expansion can be contined as far as needed.

A note on the proofs

The proofs illustrate a “bootstrap principle” which applies here. Consider the bounds for the orders of primitive groups. The orders of the wreath products, affine groups, and diagonal groups can be read off directly (using information about the orders of simple groups and their automorphism groups in the last case). For almost simple groups, we need to use CFSG in a more serious way.

If H is a (maximal) subgroup of the almost simple group G, where |G| = N and |H| = M, then G acts (primitively) on the set of cosets of H, with degree n = N/M; so, if M ≤ Nc, then we have |G| ≤ n1/(1-c). ACcording to CSFG, a non-abelian finite simple group is an alternating group, a group of Lie type, or one of the 26 sporadic groups. The sporadic groups usually present no problem, and for the groups of Lie type, easy estimates for orders of subgroups suffice.

Now if T is an alternating group other than A6, then G is Sm or Am, where m is much smaller than n. The maximal subgroup H is described by the O’Nan–Scott Theorem; and the bounds for orders of primitive groups of degree m are far stronger than we need!

Previous | Next

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, symmetric group and tagged , , , . Bookmark the permalink.

6 Responses to The symmetric group, 12

  1. Pingback: The symmetric group, 11 « Peter Cameron's Blog

  2. Yann says:

    I think there is a typographical error in the fourth line of theO’Nan–Scott Theorem: should n=km not be n=k^m?

  3. Lev Glebsky says:

    It is a question. “If T is abelian then H is affine” . I seems to understand that T=Z_p^d, so H is an extension of Z_p^d by
    Aut(Z_p^d). Why the extension split?
    Thank you. Lev.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.