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.

This article is incomplete. More examples wanted.

Example 1

Let $G$ be a group and let $H$ be a subgroup of $G$ of index $n.$ (This means that $|G|/|H|=n.$ ) Then there must be a normal subgroup of $G$ of index dividing $n!$ .

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 $H$ 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 $H$ is a normal subgroup of a group $G,$ then $H$ is the kernel of the quotient map from $G$ to $G/H.$ ) So for our problem it makes sense to look for a homomorphism with a nice big kernel.

An action of a group $G$ on a set $X$ is just a homomorphism from $G$ to the group $S(X)$ of all permutations of $X.$ 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 $X$ on which $G$ acts, given just the information that $G$ has a subgroup $H$ of index $n$ ?

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

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

Example 2

Suppose that $p$ is a prime dividing the order of the finite group $G$ . Then $G$ contains an element of order $p$ . 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 $G$ , but rather will be the cyclic group $C_p$ of order $p$ . More precisely, we define the set $X$ as follows:

$= \{ (g_1,\ldots,g_p) \in G^p \, | \, g_1 \cdots g_p = 1\},$

the collection of $p$ -tuples of elements of $G$ whose product is trivial.

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

$\sigma(g_1,\ldots,g_p) = (g_2,\ldots,g_p, g_1).$

(So in general, if $i = 1,\ldots,p-1,$ then

$\sigma^i(g_1,\ldots,g_p) = (g_{i+1},\ldots,g_p,g_1,\ldots,g_i),$

and of course $\sigma^0,$ which is the identity of $C_p$ , 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 $C_p$ ?

The answer is that an element of order $p$ is an element $g,$ not equal to the identity, such that $g^p=1.$ And we will get such an element if we can find an element $(g_1,g_2,\dots,g_p)\in X$ that is a fixed point of the action. Indeed, the fact that it is fixed tells us that however we cyclically permute $(g_1,g_2,\dots,g_p)$ we get the same sequence, which forces the $g_i$ all to be equal to some element $g$ ; and the fact that it belongs to $X$ tells us that $g^p=1.$ 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 $C_p$ contains no non-trivial proper subgroups, so the stabilizer of any point $x \in X$ is either trivial or all of $C_p$ . Equivalently, the order of the orbit of any point $x \in X$ under the action of $C_p$ is either of order $p$ , or of order $1$ (and hence just consists of the single point $x$ , which must then be fixed by $C_p$ ).

Now the cardinality of $X$ equals $|G|^{p-1}$ , and hence is divisible by $p$ (since $|G|$ is divisible by $p$ , by assumption). Also, $X$ is the union of its orbits under the action of $C_p$ . Consequently, since any orbit has order either $1$ or $p$ , we see that the number of orbits of order $1$ must itself be divisible by $p$ . In particular, the number of such orbits is either $0$ , or at least $p$ .

Recall that each orbit corresponds to an element $g\in G$ such that $g^p=1.$ Thus the number of such elements is divisible by $p$ , and in particular, is either $0$ or else at least $p$ .

However, the identity of $G$ certainly is such an element, and thus the number of such elements is not $0$ . Consequently, it is at least $p$ , which implies that we can find a non-identity element $g \in G$ such that $g^p = 1$ . This proves Cauchy's theorem.

Example 3

Let $G$ be a group of order $pq$ , where $p$ and $q$ are primes such that $p<q$ . Then $G$ has a normal subgroup of order $q$ .

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

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 $\phi$ defined on a group $G,$ either for its own sake or so that you can define a normal subgroup $H$ by taking kernel of $\phi,$ then try defining an action of $G$ on some set that you define in terms of $G$ and the information you have about $G.$

Principle 2. If you want to prove that a group $G$ 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.

This article is in need of attention. Is Principle 2 a special case of some more general principle? It feels as though it ought to be.

Comments

One of the best examples of a

Sun, 19/04/2009 - 01:04 — Colin Reid

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

Sun, 19/04/2009 - 07:58 — Anonymous (not verified)

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

Sun, 19/04/2009 - 08:05 — Anonymous (not verified)

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.

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

view commented text

There is a way

Sun, 19/04/2009 - 08:53 — Jungle

Edit: Misread the given condition $p<q$ . I had proved that there exists an element with order the smallest prime (which I had misread as $q$ ). I am working on it..

factorisation of morphisms

Sun, 19/04/2009 - 08:54 — Anonymous (not verified)

If you have to show something for all morphisms (of type P), factorise then (e.g. into mono/epi: abelian category, fibration/cofibration: model category, closed immersion/projection: projective morphisms -> this strategy is used in the proof of the Grothendieck-Riemann-Roch theorem) and show it for all the factorisations and that it is preserved by composition.