Tricki

Proving results by letting a group act on a finite set

Quick description

There are a number of group theoretic statements that do not mention group actions, but which can be solved by defining a set on which a given group acts and studying that action. Typically (but not always), the set is defined in terms of the group itself. This article gives several examples, and tips for choosing an appropriate action.

Prerequisites

Basic definitions of group theory, and the notion of a group action.

Example 1

Let be a group and let be a subgroup of of index (This means that ) Then there must be a normal subgroup of of index dividing .

How on earth can we prove this? At first, there doesn't seem to be enough to go on: all we have is one subgroup of an utterly arbitrary group. However, it is very important to remember that although the definition of a normal subgroup is that it is a subgroup closed under conjugation, the real importance of normal subgroups is that they are kernels of homomorphisms. (In one direction, it is easy to check that the kernel of a homomorphism is a normal subgroup. And if is a normal subgroup of a group then is the kernel of the quotient map from to ) So for our problem it makes sense to look for a homomorphism with a nice big kernel.

An action of a group on a set is just a homomorphism from to the group of all permutations of So this gives us a good reason to think about group actions when trying to solve our problem: they are a source of homomorphisms. But how can we create a set on which acts, given just the information that has a subgroup of index ?

While we are thinking about this, let us also think about what property we would like to have. We want our normal subgroup to have index dividing , so we would like the kernel of the homomorphism from to to have index dividing . That is, we would like the quotient group to have order dividing . But the first isomorphism theorem tells us that is isomorphic to the image of the homomorphism, so we want the image to have size dividing . The obvious way to ensure that is to take a set of size If we do that, then has size , and by Lagrange's theorem every subgroup of including the image of the homomorphism, has size dividing .

How can we create a set of size out of the information that has a subgroup of index ? Pretty well the only choice is to take a set of cosets. But because is not normal, we have to choose either the set of all left cosets of or the set of all right cosets. Let's go for left cosets. Now we have to turn elements of into permutations of the left cosets of in a natural way. That is, given and a left coset of we want to use and to define another left coset of Again, the choice is pretty obvious: we take the coset Does that work? Well, let be the map that takes a coset to the coset Then So it does work, and our problem is solved. (It turns out that right cosets do not work – the natural definition has the property that which is a sort of "reverse action".)

Example 2

Suppose that is a prime dividing the order of the finite group . Then contains an element of order . This result is known as Cauchy's theorem. It is a special case of Sylow's theorem, but it was proved a generation earlier than Sylow's theorem.

One difference between this example and the previous one is that the group that we make act will not be , but rather will be the cyclic group of order . More precisely, we define the set as follows:

the collection of -tuples of elements of whose product is trivial.

We define an action of on by permuting the factors. That is, if is some fixed generator of (just choose one), we define the -action on via

(So in general, if then

and of course which is the identity of , acts trivially.)

A second difference is that we are using the action in a different way. In the first example we chose an action because it gave us a homomorphism. But what is the reason for choosing this action of ?

The answer is that an element of order is an element not equal to the identity, such that And we will get such an element if we can find an element that is a fixed point of the action. Indeed, the fact that it is fixed tells us that however we cyclically permute we get the same sequence, which forces the all to be equal to some element ; and the fact that it belongs to tells us that And one thing that the elementary theory of group actions is good at is proving the existence of fixed points.

Let us see how this is done. The cyclic group contains no non-trivial proper subgroups, so the stabilizer of any point is either trivial or all of . Equivalently, the order of the orbit of any point under the action of is either of order , or of order (and hence just consists of the single point , which must then be fixed by ).

Now the cardinality of equals , and hence is divisible by (since is divisible by , by assumption). Also, is the union of its orbits under the action of . Consequently, since any orbit has order either or , we see that the number of orbits of order must itself be divisible by . In particular, the number of such orbits is either , or at least .

Recall that each orbit corresponds to an element such that Thus the number of such elements is divisible by , and in particular, is either or else at least .

However, the identity of certainly is such an element, and thus the number of such elements is not . Consequently, it is at least , which implies that we can find a non-identity element such that . This proves Cauchy's theorem.

Example 3

Let be a group of order , where and are primes such that . Then has a normal subgroup of order .

First, we use Cauchy's theorem to conclude that has an element of order , which generates a subgroup of of order . Now has index , and it follows by the first example that has a normal subgroup contained in of index dividing . By Lagrange's theorem, also has index dividing . But what is the greatest common divisor of and ? Well, any prime dividing must divide some positive integer at most , since is the product of such integers; so cannot be larger than . This means that does not divide ; on the other hand does divide , so the greatest common divisor is exactly . Hence has index at most ; but it is contained in , which already has index . So we have , giving the required normal subgroup of order .

General discussion

From the above proofs we can extract two general principles about how to use group actions to prove results about groups.

Principle 1. If you want to find a homomorphism defined on a group either for its own sake or so that you can define a normal subgroup by taking kernel of then try defining an action of on some set that you define in terms of and the information you have about

Principle 2. If you want to prove that a group contains an element with a certain property, then see if you can associate elements that have that property with fixed points of some group action, and then use standard techniques to get a lower bound for the number of fixed points of that action.

One of the best examples of a

One of the best examples of a proof using group actions in a non-obvious way is Wielandt's proof of Sylow's theorem. (Other proofs use group actions, but it seems Wielandt's proof is the most popular.) It's a fairly well known example and can be found on the Wikipedia page for Sylow's theorem, but seeing as it's probably the easiest known proof of the most important theorem of finite group theory, one which was seen as an extremely difficult result when originally obtained, it warrants an extensive exposition here. I'll write something about it on this page at some point unless someone else wants to.

I like the following proof of

I like the following proof of the existence part of Sylow best:

1. Show that if there exists a p-Sylow subgroup for G, there exists one for every subgroup H of G (by using double cosets).
2. Show that there exists a p-Sylow subgroup of GL_n(F_p) (upper triangular matrices with 1 on diagonal).
3. GL_n(F_p) are cogenerators in the category of finite groups. (Every finite group can be embedded into a GL_n(F_p) for n = |G|.)

This shows also a general algebraic trick: If there is a class of generators of an (at the best abelian) category, show the result for the (simpler) generators, and then for all quotients of them. (Here, use the dual strategy.)

reduction to a univeral example

A strategy in a similar spirit:

Reduction to a univeral example. If there exists a classifying object (a moduli space) M with a universal object (universal family) X for objects (P) on it, i.e. every object with the property (P) is the pullback of X by a morphism to M, and if one wants to show something about all objects with (P) that is preserved by pullbacks, it suffices to show it for X/M.

Example: For the construction of Chern classes, it suffices to calculate the cohomology of infinite Grassmannians.