The Alternating Group is Simple III

Leave a comment

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

Advertisements

The Alternating Group is Simple II

Leave a comment

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

Leave a comment

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.