The Alternating Group is Simple III

I will now conclude my series of posts about the alternating group by proving that $A_n$ is simple for $n \geq 5$. Just as with $A_5$ I stole this argument from Dummit & Foote; while I feel I might have been able to come up with the argument for $A_5$ on my own, the argument for $A_n$ is a bit too clever for me. If anyone knows who came up with it, please let me know.

We are going to use again and again the formula for conjugating permutations from my last post, so I will repeat it here for reference:

Lemma 1: Let $\sigma = (a_1 a_2 \ldots a_k)$ be a cycle and let $\tau$ be any permutation. Then $\tau \sigma \tau^{-1} = (\tau(a_1) \tau(a_2) \ldots \tau(a_k))$

Let us jump right into the proof of the main result:

Theorem: $A_n$ is simple for every $n \geq 5$.

Proof: We use induction on $n$. The base case, $n = 5$, was handled in the last post. So assume that $A_{n-1}$ is simple, and let $H$ be a proper normal subgroup of $A_n$, $n \geq 6$. Our aim is to show that $H$ is the trivial group.

Our first step is to prove that no non-identity element of $H$ can fix any symbol. Let $G_i$ denote the subgroup of $A_n$ consisting of all elements that fix the symbol $i$; by Lemma 1 we have $\tau G_i \tau^{-1} = G_{\tau(i)}$ for any permutation $\tau$. Note that $G_i \cong A_{n-1}$ for each $i$, so if $H$ intersects some $G_i$ nontrivially then $G_i \subseteq H$ by the induction hypothesis. Moreover, since any $G_j$ can be obtained from $G_i$ by conjugation and $H$ is normal, we have that $G_j \subseteq H$ for all $H$.

Now, any element of $A_n$ can be written as the product of pairs of transpositions. A pair of transpositions can only permute up to four symbols, so since $n \geq 5$ every pair of transpositions fixes at least one symbol and hence is in some $G_i$. Thus every element of $A_n$ can be written as a product of permutations each of which is in some $G_i$; since $G_i \subseteq H$, it follows that $A_n \subseteq H$, contradicting our assumption that $H$ is a proper subgroup.

So no non-identity element of $H$ can fix any symbol. Consequently, if two elements of $H$ agree on even one symbol then they must be the same, for if $\tau_1(i) = \tau_2(i)$ then $\tau_1 \tau_2^{-1}$ fixes $i$ and hence is the identity. To complete the proof we will use this observation to show that the identity is the only element of $H$.

• No element of $H$ can contain a $k$-cycle for $k \geq 3$:
Suppose $\sigma \in H$ contains a $k$-cycle $(a_1 a_2 a_3 \ldots)$. Since $n \geq 5$ it is possible to choose $\tau$ which fixes $a_1$ and $a_2$ but not $a_3$. By Lemma 1 we have:
$\tau (a_1 a_2 a_3 \ldots) \tau^{-1} = (a_1 a_2 \tau(a_3) \ldots)$
Thus $\sigma$ and $\tau \sigma \tau^{-1}$ are two permutations in $H$ which agree on $a_1$ but not on $a_2$; this is a contradiction.
• No element of $H$ can be the product of disjoint $2$-cycles:
Suppose such an element $\sigma$ were to exist. Since $n \geq 6$ and $\sigma$ can’t fix any symbols, it must be the product of at least three disjoint $2$-cycles:
$\sigma = (a_1 a_2)(a_3 a_4)(a_5 a_6)\ldots$
Let $\tau = (a_1 a_2)(a_3 a_5)$. We have:
$\tau \sigma \tau^{-1} = (a_1 a_2)(a_5 a_4)(a_3 a_6)\ldots$
This time $\sigma$ and $\tau \sigma \tau^{-1}$ agree on $a_1$ and $a_2$ but not on $a_3$, a contradiction.

We conclude that no element of $H$ can have a cycle of length larger than $1$; this means that $H$ is the trivial group.
QED

The Alternating Group is Simple II

In my last post I described the alternating group and its place in the world of groups. I will now prove that $A_5$ is simple, and in the third and final post of this series I will prove that $A_n$ is simple for $n \geq 5$. The plan of attack is as follows: first I will carry out some preliminary analysis of conjugacy in $S_n$ and $A_n$, and then by identifying all conjugacy classes in $A_5$ I will prove that $A_5$ is simple. I will then prove that $A_n$ is simple for $n \geq 5$ by induction. I’m not sure who invented this argument; all I know is that I learned it in Dummit & Foote.

Conjugacy Classes in the Alternating Group

To understand the normal subgroups of a group it is very useful to first think carefully about its conjugacy classes; this is because a normal subgroup is by definition the union of conjugacy classes. Fortunately conjugation in the symmetric group is easy to understand using “cycle notation”. A $k$-cycle in $S_n$ is a permutation which fixes all but $k$ symbols $a_1, \ldots, a_k$ which acts on these symbols as:

$a_1 \to a_2 \to \ldots \to a_k \to a_1$

The notation for this cycle is $(a_1 a_2 \ldots a_k)$. It is not hard to show that every permutation decomposes as the product of disjoint cycles, and the decomposition is unique up to reordering the cycles. Indeed, cycle notation makes it particularly easy to understand conjugation.

Lemma 1: Let $\sigma = (a_1 a_2 \ldots a_k)$ be a cycle and let $\tau$ be any permutation. Then $\tau \sigma \tau^{-1} = (\tau(a_1) \tau(a_2) \ldots \tau(a_k))$

Proof: For $i < k$ we have $\tau \sigma \tau^{-1}(\tau(a_i)) = \tau \sigma(a_i) = \tau(a_{i+1})$ and similarly $\tau \sigma \tau^{-1}(\tau(a_k)) = \tau(a_1)$.
QED

The lemma extends easily to the case where $\sigma$ is the product of cycles, so we see that conjugation by $\tau$ preserves the cycle structure of $\sigma$ while relabelling the symbols in the cycle. In particular, two elements of $S_n$ are conjugate if and only if the number and lengths of cycles are the same. For instance, $(12)(345)$ is conjugate to $(124)(35)$ in $S_5$ but not to $(12345)$.

Note that conjugacy in $A_n$ is a little more subtle. A $k$-cycle is even if and only if $k$ is odd, but not all $k$-cycles are conjugate in $A_n$. For instance the transposition $\tau = (45)$ conjugates $(12345)$ to $(12354)$ in $S_5$, but there is no even permutation which conjugates $(12345)$ to $(12354)$ and hence they are not conjugate in $A_5$.

To prove that $A_5$ is simple, we will need to determine the sizes of all of its conjugacy classes. We will do this using the following tool:

Lemma 2: Let $g$ be an element of a group $G$, let $Z_G(g)$ be the centralizer of $g$ (i.e. the set of all elements of $G$ which commute with $g$) and let $C_G(g)$ denote the conjugacy class of $g$. Then $|Z_G(g)| \cdot |C_G(g)| = |G|$

Proof: Let $G$ act on itself by conjugation. The orbit of $g$ under this action is $C_G(g)$ and the stabilizer is $Z_G(g)$, so the result follows from the orbit-stabilizer theorem.
QED

We will apply this lemma as follows. First we will use our understanding of conjugacy in $S_n$ to identify the centralizer of a cycle. From that it is easy to identify the centralizer of a cycle in $A_n$, and that will allow us to count the conjugates of a cycle in $A_n$.

Proposition 3: Let $\sigma \in S_n$ be a $k$-cycle. Then:
$Z_{S_n}(\sigma) = \{\sigma^i \tau:\: 0 \leq i < k,\, \tau \in S_{n-k}\}$

Proof: By Lemma 1, the conjugates of $\sigma$ in $S_n$ are precisely the $k$-cycles. To specify a $k$-cycle one must specify the symbols in the $k$-cycle and the order in which they appear; there are $\frac{n!}{k!(n-k)!}$ ways to choose $k$ symbols and $k!$ different orders in which they can appear, though $k$ of the orders define the same cyclic permutation. Thus there are $\frac{n!}{k!(n-k)!} \cdot (k-1)! = \frac{n!}{k \cdot (n-k)!}$ conjugates of $\sigma$; by Lemma 2, $|Z_{S_n}(\sigma)| = k \cdot (n-k)!$.

The permutation $\sigma^i$ clearly commutes with $\sigma$. Any permutation $\tau$ which fixes the $k$ symbols that $\sigma$ acts on also commutes with $\sigma$, and the subgroup of all such permutations is isomorphic to $S_{n-k}$. Thus the permutations $\sigma^i \tau$, $\tau \in S_{n-k}$, all commute with $\sigma$; there are $k \cdot (n-k)!$ distinct permutations of this form, so they make up the entire centralizer of $\sigma$.
QED

Simplicity of $A_5$

We are now ready to prove the main result of this post:

Theorem: $A_5$ is simple.

Proof: The only possible cycle structures of non-identity elements in $A_5$ are $(123)$, $(12345)$, and $(12)(34)$. Recall that in $S_5$ the cycle structure completely determines the conjugacy class; in $A_5$ some of these conjugacy classes may split. Let us analyze each conjugacy class in turn using Proposition 3.

• $(123)$: The centralizer of $(123)$ in $S_5$ consists of the six permutations $(123)^i \tau$ where $i = 0, 1, 2$ and $\tau$ is either the identity or $(45)$, so $(123)$ has $120/6 = 20$ conjugates in $S_5$. If $\tau = (45)$ then $(123)^i \tau$ is odd, so the centralizer in $A_5$ has only three elements and hence the number of conjugates is still $60/3 = 20$. Thus all $3$-cycles are conjugate in $A_5$.
• $(12345)$: The centralizer of $(12345)$ in both $S_5$ and $A_5$ is just the cyclic subgroup $\{(12345)^i\}$, so there are $120/5 = 24$ conjugates in $S_5$ and $60/5 = 12$ conjugates in $A_5$. The other $12$ elements in the $S_5$ conjugacy class are accounted for by the $A_5$ conjugacy class of $(12354)$ which is disjoint from that of $(12345)$.
• $(12)(34)$: It is straightforward to check that $(12)(34)$ commutes with the identity, itself, $(13)(24)$ and $(14)(23)$. If $\tau$ does not fix the symbol $5$ then $\tau (12)(34) \tau \neq (12)(34)$ by Lemma 1, so $(12)(34)$ does not commute with $\tau$. A similar argument shows that $(12)(34)$ does not commute with any $3$-cycle, so the centralizer has exactly $4$ elements and hence $(12)(34)$ has $60/4 = 15$ conjugates in $A_5$.

Including the identity, we have accounted for the conjugacy classes of all $60$ elements of $A_5$: $60 = 1 + 20 + 12 + 12 + 15$. So let $H$ be a normal subgroup of $A_5$. Since $H$ is normal it is the union of conjugacy classes (including the identity), so $|H|$ is the sum of $1$ and some subset of $\{20, 12, 12, 15\}$. But $|H|$ must also divide $|A_5| = 60$; checking cases the only possible choices for $|H|$ are $1$ and $60$.
QED

The Alternating Group is Simple I

This past week I covered an abstract algebra course at Columbia, and I decided to prove that the alternating group $A_n$ is simple. I in fact did this in the same algebra class last year, but in the intervening months I almost entirely forgot how the argument goes. So I decided to write it up here while it’s still fresh in my mind. It’s a very nice – and fairly elementary – little application of some important ideas in group theory. In this post I’m going to give some background and explain the significance of the simplicity of $A_n$, and in the sequel I will go through the proof.

The Alternating Group

I am forced to assume that the reader is comfortable with basic group theory, but I’ll begin by reviewing some of the key ideas. Recall that the symmetric group $S_n$ is the group of permutations of $n$ symbols $1, 2, \ldots, n$. A transposition is a permutation which swaps exactly two symbols and leaves the others fixed; it is not hard to see that any permutation can be expressed as the product of transpositions. A permutation is said to be even (respectively, odd) if it can be written as the product of an even (respectively, odd) number of transpositions.

Definition: The alternating group $A_n$ is the subgroup of $S_n$ consisting of all even permutations.

$A_n$ is a normal subgroup of $S_n$ of index $2$; the objective of this series of posts is to prove that $A_n$ is simple for $n \geq 5$, meaning its only normal subgroups are itself and the trivial group. The significance of this property is that if a group $G$ has a normal subgroup $H$ then one can form the quotient group $G/H$, and often one can infer properties of $G$ from properties of $H$ and $G/H$. So simple groups are in a sense the “atoms” from which all other groups are built, though it should be noted that $H$ and $G/H$ alone do not uniquely determine $G$.

The Classification of Simple Groups

Classifying all finite simple groups was one of the great achievements of 20th century mathematics, and like many great mathematical achievements it went almost completely unnoticed by the rest of the world. The classification theorem asserts that all finite simple groups fit into a few infinite families (one of which is the family of alternating groups) with precisely 26 exceptions, the so-called sporadic simple groups. A shameless plug: when I was an undergraduate I did an REU project with Igor Kriz which involved making little computer games based on the sporadic simple groups; later we wrote a Scientific American article about them.

In any event, the classification program took decades to complete and spans thousands of pages written by dozens of mathematicians, and its completion seems to have essentially killed off finite group theory as an active area of research (though from what I understand there are lots of open problems in representation theory for finite groups). Given how monumental the effort was and how few people are still working in finite group theory, I worry that in a few decades all the experts will retire or die and there will be nobody left who understands the proof. It’s a good illustration of the principle that mathematicians tend to care much more about questions than answers.

The Alternating Group and Galois Theory

Aside from their role in the classification program, the alternating groups play a crucial role in the theory of polynomial equations. Indeed, the very notion of a group was invented to understand the structure of solutions to polynomial equations, and the group $A_5$ is the star of the show.

Everyone learns in high school algebra that there is a formula for the roots of a quadratic equation $ax^2 + bx + c = 0$:

$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

Less well known is that there is also a cubic formula and quartic formula for degree three and four equations, respectively. These formulas date back to the 16th century, and it was a frustratingly difficult open problem to find a formula for the roots of a polynomial equation of degree five. It wasn’t until the 19th century that Abel and Galois independently realized that no such formula exists! Abel’s proof came first, but I don’t know what it was; Galois’ argument is the one that survived. Here is a brief sketch.

Galois’ key idea was to focus on the symmetries exhibited by the roots of a polynomial equation. More precisely, he considered their symmetries relative to the rational numbers; there are well-known techniques for finding rational roots of polynomials, so he was interested in the structure of the irrational roots. Let’s look at a couple examples:

• The roots of $x^2 - 2$ are $\pm \sqrt{2}$, so you can get from one root to the other by multiplying by $-1$. Thus the cyclic group $C_2$ naturally exhibits the symmetries of the roots.
• The roots of $x^4 - 1$ are $i$, $-i$, $1$, and $-1$. Notice that you can cycle through the roots just by looking at powers of $i$: $i^0 = 1$, $i^1 = i$, $i^2 = -1$, $i^3 = -1$ and $i^4 = 1$. Thus the symmetries of the roots are given by the cyclic group $C_4$.
• The roots of $(x^2 - 2)(x^2 - 3)$ are $\pm \sqrt{2}$ and $\pm \sqrt{3}$. The roots $\sqrt{2}$ and $-\sqrt{2}$ are interchangeable, as are $\sqrt{3}$ and $-\sqrt{3}$, but over the rational numbers there is a sort of asymmetry between $\sqrt{2}$ and $\sqrt{3}$. Thus the symmetry group is $C_2 \times C_2$.

Of course, one can make all this precise using the language of field extensions. The upshot is that the symmetry groups help characterize what it means to find a formula for the roots of a polynomial equation. As in the example above, equations of the form $x^n - a = 0$ have cyclic symmetry group $C_n$. So if the quintic formula had the form $\sqrt[5]{a + \sqrt[3]{b}}$, for instance, then the symmetry group could be decomposed into a $C_5$ part and a $C_3$ part corresponding to the fifth root and cube root, respectively. More precisely, a polynomial equation can be solved by radicals if and only if its symmetry group $G$ has a decomposition

$G = G_0 \supseteq G_1 \supseteq \ldots \supseteq G_n = \{1\}$

where $G_i$ is a normal subgroup of $G_{i-1}$ and $G_{i-1}/G_i$ is cyclic. Groups with this property are said to be solvable due to the connection with solving equations.

Now, there exist polynomials of degree $5$ whose symmetry group is the full symmetric group $S_5$ (in fact there are many). $S_5$ contains $A_5$ as a normal subgroup with quotient $C_2$, but once we have proved that $A_5$ is simple we will know that it is not solvable: it has no nontrivial normal subgroups whatsoever, let alone one with a cyclic quotient. This argument shows that there cannot be a general formula in the spirit of the quadratic, cubic, or quartic formulas, but it also shows even more: it gives you a criterion (solvability of the symmetry group) to determine when there is a formula for the roots of a specific polynomial.