Automorphism Group of the Symmetric Group of Order n (4.4.18)

Dummit and Foote Abstract Algebra, section 4.4, exercise 18:

This exercise shows that for n≠6 every automorphism of S_n is inner. Fix an integer n > 1 with n≠6.
(a) Prove that ∀σ∈Aut(G) and each conjugacy class K of G the set σ(K) is also a conjugacy class of G, ie σ permutes the conjugacy classes of G.
(b) Let K be the conjugacy class of transpositions in S_n and let K' be the conjugacy class of any element of order 2 in S_n that is not a transposition. Prove that |K|≠|K'|. Deduce that any automorphism of S_n maps transpositions to transpositions [see exercise 33 in section 3].
(c) Prove that for any σ∈Aut(S_n), we have σ: ( 1 2 ) → ( a b₂ ), ( 1 3 ) → ( a b₃ ), ..., ( 1 n ) → ( a b_n ), for distinct integers a, b₂, b₃, ..., b_n.
(d) Show that the transpositions moving 1 generate S_n and deduce that any automorphism of S_n is determined by its action on these elements. Use (c) to show that S_n has at most n! automorphisms and conclude that Aut(S_n) = Inn(S_n) for n≠6.

Proof: (a) Take a representative x of K. We have that for any y∈K, y = gxg^-1 for some g, so that σ(y) = σ(gxg^-1) = σ(g)σ(x)σ(g)^-1∈σ(K), thus every element of σ(K) is within the same conjugacy class. Furthermore, for any g, σ(g)σ(x)σ(g)^-1 = σ(gxg^-1)∈σ(K), so that σ(K) contains the conjugacy class of σ(x). Therefore, σ(K) is exactly one conjugacy class.

(b) For σ a transposition S_n, we have that its cycle type consists of n-2 1s and exactly one 2. For z∈S_n of order 2 but not a transposition, we have that its cycle type consists of n-2x 1s and x 2s for some integer x > 1. By the aforementioned exercise, we can calculate their conjugacy class sizes in general form: σ's conjugacy class is of order n!/((n-2)!*2), and z's conjugacy class is of order n!/((n-2x)!*x!*2^x). The two being equal would imply that (n-2)!*2 = (n-2x)!*x!*2^x. Prove that this is impossible for n > 6 using induction: If for all 2 ≤ x ≤ n/2 we have (n-2)!*2 > (n-2x)!*x!*2^x, then for all 2 ≤ x ≤ (n+2)/2 we have ((n+2)-2)!*2 = (n-2)!*2*(n-1)*n > ((n+2)-2x)!*x!*2^x = (n-2x)!*x!*2^x*(n-2x+1)*(n-2x+2). This is evident for 2 ≤ x ≤ n/2 since (n-1)*n > (n-2x+1)*(n-2x+2) for x > 2. There is only one other possibility for x, then, namely x = (n+2)/2 if n is even, or x = (n+1)/2 if n is odd. Even if x is maximized to (n+2)/2 regardless of n's evenness or oddness, we have, after the substitution and cleaning up, (n-2)! > (n/2 + 1)!*2^n/2, since it's true for the base cases n = 7 and n = 8, and if it's true for n > 6, then it's true for n+2, as the left side of the inequality gets multiplied by (n-1)*n, and the right side only by (n/2+2)*2. Now, since the original inductively attacked equation has base cases true for n = 7 and n = 8 (easily checked by force), we have the complete result proven after routinely checking that the equation does not hold for n = 2, 3, 4, or 5 and any possible values of x.

(c) Keep in mind isomorphisms preserve the order of the elements they permute. Take σ( ( m k ) ) = ( a b₂ ) and σ( ( m n ) ) = ( x bn ) for n≠1,2. If a = x and b₂ = bn, then we have σ( ( 1 2 )( 1 n) ) (aka σ( ( 1 n 2 ) ) ) is the identity permutation, which obviously violates the automorphism. If a ≠ x and b₂ ≠ bn , then σ( ( 1 2 )( 1 n) ) is the product of two disjoint transpositions, and thus of order two, despite how σ( ( 1 n 2 ) ) is of order 3. This implies that for every pair of transpositions moving one common integer, their images under an automorphism move one common integer (if a ≠ x and b₂ = bn then just "flip" the transposition around to obtain the proper form). Now, inductively prove that if two transpositions move exactly one common element both under S_n and σ(S_n), then all transpositions under these two groups move exactly one common element. Take the two that move exactly one common element under S_n, and take an arbitrary third that moves exactly one common element with the first and the second under S_n and exactly one with the first and then the second (proved by the preceding manipulations):

Note not that the three under the map need not move a common element

in unison by the above logic alone, however.

But, we can prove that they must by an additional progression. Assume that x distinct transpositions ordered ( 1 2 ), ( 1 3 ), ..., ( 1 x-1 ) move one common element before (the integer 1) and after the automorphism (the integer a). Assume ( 1 x ) does not move a. We know that ( 1 x )( 1 x-1 )...( 1 2) is an x-cycle, and yet since σ( ( 1 x ) ) moves a common element with every transposition before it and therefore fixes nothing not already moved by the preceding transpositions under the automorphism, we have that σ( ( 1 x )( 1 x-1 )...( 1 2) ) only moves x-1 indices and is thus something less than an x-cycle, not in the same conjugacy class as its premapped counterpart, and therefore a contradiction by part (a). So ( 1 x ) moves a. Using this progression, every mapped transposition obeys the sequence hypothesized above.

(d) Any transposition ( i j ) within σ(S_n) can be constructed by the transpositions permuted to the set of transpositions moving a (demonstrated in the previous part) as such: ( a j )( a i )( a j ). Therefore, since σ(S_n) = S_n is clearly generated by transpositions, we have that an automorphism's action on the transpositions moving 1 in S_n are all that's necessary to determine its action on the whole group. Since there are n-1 of these transpositions with n-1 available slots after determining one of the n common integers these transpositions move, we have | Aut(S_n) | ≤ n!. Since S_n / Z(S_n) ≅ Inn(S_n) ≤ Aut(S_n) and | S_n / Z(S_n) | = | S_n / 1 | = | S_n | = n!, we have that Inn(S_n) = Aut(S_n) for n ≠ 6.

∎