Proving results by letting a group act on a finite set

a repository of mathematical know-how

Proving results by letting a group act on a finite set

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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 [[w:Group action|group action]].

[note article incomplete] More examples wanted.[/note]

[EXAMPLE]
Let $G$ be a group and let $H$ be a subgroup of $G$ of [add]index $n.$ {{(This means that $|G|/|H|=n.$)}}[/add] Then there must be a [[w: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 [add]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.$)}}[/add] 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 [[w:First_isomorphism_theorem#First_isomorphism_theorem|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 [[w:Lagrange_theorem_(group_theory)|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]

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 [[w:Cauchy's theorem (group theory) | Cauchy's theorem]]. It is a special case of [[w:Sylow theorems | 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:
[maths]
X := \{ (g_1,\ldots,g_p) \in G^p \, | \,  g_1 \cdots g_p = 1\},
[/maths]
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
[maths]
\sigma(g_1,\ldots,g_p) = (g_2,\ldots,g_p, g_1).
[/maths]
(So in general, if $i = 1,\ldots,p-1,$ then
[maths]
\sigma^i(g_1,\ldots,g_p) = (g_{i+1},\ldots,g_p,g_1,\ldots,g_i),
[/maths]
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]

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.

[frame] '''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.$ [/frame]

[frame] '''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. [/frame]

[note attention] Is Principle 2 a special case of some more general principle? It feels as though it ought to be. [/note]

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Proving results by letting a group act on a finite set

Recent articles

Active forum topics

Recent comments