The symmetric group, 10

I want to say a few words about the connection of the symmetric group with some of the classic nineteenth-century theorems of group theory, by Lagrange, Cayley and Sylow.

Lagrange

Lagrange’s Theorem states that the order of a subgroup of a group G divides the order of G.

This was originally proved by Lagrange for the case when G is the symmetric group S_n. The context was: How many different values can be taken by a function of n variables, under permutations of the arguments? If H is the set of permutations which preserve the value of the function, then H is a subgroup of S_n, and the number of values was precisely the index of H, hence a divisor of n!.

For n≥5, apart from the alternating group, any subgroup of S_n has index at least n. So, for poynomials of degree n≥5, no “resolvent” equation can have fewer than n roots. This was the first step towards showing the insolubility by radicals of such equations.

Cayley

Cayley’s Theorem states that any group of order n is isomorphic to a subgroup of the symmetric group S_n.

The proof uses the notion of the Cayley table or multiplication table of the group. Its rows are permutations, and form the required subgroup of the symmetric group.

The philosophical importance of Cayley’s Theorem is in the transition of group theory from a descriptive subject (a group is a set of permutations, closed under composition and inversion and containing the identity permutation) to an axiomatic subject (a group is a set with a binary operation satisfying the associative, identity and inverse laws). It is straightforward that every “descriptive” group is an “axiomatic” group (the associative law always holds for composition of mappings); Cayley’s Theorem shows that the converse holds.

So, despite the major shift in philosophy, the subject-matter of group theory was unchanged.

Lagrange and Cayley

How many groups of order n are there? The number does not exceed the number of Cayley tables, which is nⁿ².

Using the theorems of Lagrange and Cayley we can do substantially better.

First, observe that a group of order n can be generated by at most log₂n elements. For if we choose each generator outside the subgroup generated by its predecessors, then by Lagrange’s Theorem each subgroup is at least twice as large as the one before, and we reach the group in at most log₂n steps.

This means that we can choose at most log n rows of the Cayley table which determine the entire table. (Logarithms are to base 2 from now on.) Each row is an element of S_n, so the number of groups does not exceed (n!)^log n, which is at most n^n log n.

Using much more advanced arguments including the Classification of Finite Simple Groups it has been shown that the number of groups of order n is at most n^c(log n)2; this is best possible.

Sylow

The symmetric group can be used to give what is perhaps the simplest possible proof of the existence of Sylow subgroups in finite groups. Recall that, if p is prime, a Sylow p-subgroup is a subgroup whose order is a power of p and whose index is coprime to p.

Step 1 If G has a Sylow p-subgroup, and H is a subgroup of G, then H has a Sylow p-subgroup.

For let G act by right multiplication on the set of right cosets of the Sylow p-subgroup. The number of points is coprime to p, while the order of any point stabiliser is a power of p.

Now restrict the action to H. Clearly there must be an orbit whose size is coprime to p; and the order of the stabiliser of a point in this orbit is a power of p, so this stabiliser is a Sylow p-subgroup of H.

(This argument, phrased in terms of double cosets, was known to Sylow.)

Step 2 The symmetric group S_n has a Sylow p-subgroup.

This is not hard to prove directly. Write n in base p and construct the required subgroup as a direct product of iterated wreath products of cyclic groups of order p.

Now the existence of Sylow subgroups in all finite groups follows from Cayley’s Theorem.

In fact the argument can be made even easier, by handing the key role to the general linear group instead. The symmetric group S_n can be embedded in the general linear group GL(n,p) of n×n invertible matrices over the integers mod p, by means of permutation matrices. Now it is very easy to see that the upper unitriangular matrices form a Sylow p-subgroup of GL(n,p). Then Step 1 gives a Sylow p-subgroup in S_n.

Previous | Next