For all n except 6, every automorphism of Sym(n) is inner

This exercise shows that for n \neq 6 every automorphism of S_n is inner. Fix an integer n \geq 2 with n \neq 6.

  1. Prove that every automorphism of a group G permutes the conjugacy classes of G. That is, if K \subseteq G is a conjugacy class and \varphi an automorphism of G, then \varphi[K] is a conjugacy class of G.
  2. Let K be the conjugacy class of transpositions in S_n and let L be the conjugacy class containing any element of order 2 in S_n that is not a transposition. Prove that |K| \neq |L|. Deduce that any automorphism of S_n sends transpositions to transpositions. [Hint: Use §4.3 #33.]
  3. Prove that for each \sigma \in \mathsf{Aut}(S_n), (1\ 2) \mapsto (a\ b_2), (1\ 3) \mapsto (a\ b_3), …, (1\ n) \mapsto (a\ b_n) for some distinct integers a, b_2, \ldots, b_n \in \{1,2,\ldots,n\}.
  4. Show that (1\ 2), (1\ 3), …, (1\ n) generate S_n and deduce that any automorphism of S_n is uniquely determined by its action on these elements. Use (c) to show that S_n has at most n! automorphisms. Conclude that \mathsf{Aut}(S_n) = \mathsf{Inn}(S_n) for n \neq 6.

  1. [Short way]

    Let \sigma be an automorphism of G, and let G \cdot a be a conjugacy class. Note that \sigma(g \cdot a) = \sigma(g^{-1}ag) = \sigma(g) \cdot \sigma(a), so that \sigma[G \cdot a] = \sigma[G] \cdot \sigma(a) = G \cdot \sigma(a). In particular, \sigma[G \cdot a] is a conjugacy class of G.

    [Long way]

    Let \sigma \in \mathsf{Aut}(G) and let K \subseteq G be a conjugacy class. We claim that \sigma[K] is a conjugacy class. Let a,b \in \sigma[K]. Then a = \sigma(x) and b = \sigma(y) for some x,y \in K. Since K is a conjugacy class, there exists an element z \in G such that zxz^{-1} = y; then \sigma(z)\sigma(x)\sigma(z)^{-1} = \sigma(y), so we have \sigma(z) a \sigma(z)^{-1} = b. Thus a and b are conjugate.

    Let a \in \sigma[K] and b \notin \sigma[K] and suppose that a and b are conjugate; then for some c \in G, cac^{-1} = b. Now since \sigma is surjective, we have a = \sigma(x), b = \sigma(y), and c = \sigma(z) for some x \in K, b \notin K, and c \in G. Now \sigma(zxz^{-1}) = \sigma(y), and since \sigma is injective, we have zxz^{-1} = y. Thus x and y are conjugate, a contradiction since K is a conjugacy class.

    Thus \sigma[K] is a conjugacy class for all automorphisms \varphi and conjugacy classes K. Moreover, we have \mathsf{id}[K] = K and (\varphi \circ \psi)[K] = \varphi[\psi[K]], so that \mathsf{Aut}(G) acts on the set of conjugacy classes of G by function application.

  2. We now prove some lemmas.

    Lemma 1: If k \geq 4, then \frac{2(2k-2)!}{k! \cdot 2^k} > 1. Proof: We proceed by induction on k. For the base case (k = 4) note that \frac{2(8-2)!}{4! \cdot 2^4} = \frac{2 \cdot 6!}{4! \cdot 2^4} = \frac{6 \cdot 5}{8} = \frac{15}{4} > 1. For the inductive step, suppose that the conclusion holds for some k \geq 4. Now note that the polynomial p(k) = 4k^2 - 4k - 2 has roots \frac{1 \pm \sqrt{3}}{2} and opens upward; thus for k \geq 4, p(k) > 0. Now 4k^2 - 2k > 2k + 2, so that \frac{2k(2k-1)}{2(k+1)} > 1. Thus 1 < \frac{2(2k-2)!}{k! \cdot 2^k} \cdot \frac{2k(2k-1)}{2(k+1)} = \frac{2(2(k+1) - 2)!}{(k+1)! \cdot 2^{k+1}}. By induction, the conclusion holds for all k \geq 4. \square

    Lemma 2: Suppose 4 \leq 2k \leq n. If \frac{2(n-2)!}{k! 2^k (n-2k)!} > 1, then \frac{2((n+1)-2)!}{k! 2^k ((n+1) - 2k)!} > 1. Proof: Note that 1 < k, so that 2 < 2k. Hence -2k + 1 < -1, so that n - 2k + 1 < n-1. Thus 1 < \frac{2(n-2)!}{k! 2^k (n-2k)!} \cdot \frac{n-1}{n+1-2k} = \frac{2((n+1)-2)!}{k! 2^k ((n+1)-2k)!}. \square

    Lemma 3: If n \geq 8 and 4 \leq 2k \leq n, then \frac{2(n-2)!}{k! 2^k (n-2k)!} > 1. Proof: We proceed by induction on n. For the base case (n = 8), there are three possibilities for k. If k = 2, we have \frac{2(8-2)!}{2! 2^2 (8-4)!} = \frac{15}{2} > 1. If k = 3, we have \frac{2(8-2)!}{3! 2^3 (8-6)!} = \frac{5}{2} > 1. For k = 4 the inequality holds by Lemma 1. Now for the inductive step, suppose that for some n \geq 8 the inequality holds for all 4 \leq 2k \leq n. If n is even, then 4 \leq 2k \leq n+1 if and only if 4 \leq 2k \leq n. Thus by Lemma 2, \frac{2((n+1)-2)!}{k! 2^k ((n+1)-2k)!} > 1 for all 4 \leq 2k \leq n+1. If n is odd, then 4 \leq 2k \leq n+1 if and only if 4 \leq 2k \leq n or 2k = n+1. In the first case, use Lemma 2 as before. In the second case, the inequality holds by Lemma 1. Thus for all 4 \leq 2k \leq n+1, we have \frac{2((n+1)-2)!}{k! 2^k ((n+1)-2k)!} > 1. By induction, the inequality holds for all n \geq 8 and all 4 \leq 2k \leq n. \square

    Lemma 4: If n \in \{ 4,5,7 \} and 4 \leq 2k \leq n, then \frac{2(n-2)!}{k! 2^k (n-2k)!} \neq 1. Proof: If n=4, then k = 2. Now \frac{2(4-2)!}{2! 2^2 (4-4)!} = \frac{1}{2} \neq 1. If n=5, then k=2. Now \frac{2(5-2)!}{2! 2^2 (5-4)!} = \frac{3}{2} \neq 1. If n=7, then k=2 or k=3. If k=2, then \frac{2(7-2)!}{2! 2^2 (7-4)!} = 5 \neq 1. If k=3, then \frac{2(7-2)!}{3! 2^3 (7-6)!} = 5 \neq 1. \square.

    Now we move to the main result. Note that if n is 2 or 3, then all elements of order 2 are transpositions; thus any automorphism of S_n sends transpositions to transpositions. Now if n \geq 4 and \sigma is an element of order 2, then \sigma is a product of k disjoint 2-cycles. If \sigma is not a transposition, then k \geq 2; note then that 4 \leq 2k \leq n. By §4.3 #33, the number of transpositions in S_n is \frac{n!}{2(n-2)!}, and the number of conjugates of \sigma is \frac{n!}{k! 2^k (n-2k)!}. These two numbers are not equal for n \neq 6 and all 4 \leq 2k \leq n, since otherwise we have \frac{2(n-2)!}{k! 2^k (n-2k)!} = 1, which contradicts Lemmas 3 and 4. Now if \varphi is an automorphism of S_n and K \subseteq S_n the conjugacy class of transpositions, then \varphi[K] is a conjugacy class of elements of order 2. If \varphi[K] \neq K, we have a contradiction since |K| \neq |\varphi[K]|. Thus every automorphism of S_n maps transpositions to transpositions if n \neq 6.

  3. We begin with some lemmas.

    Lemma 5: Let \varphi \in \mathsf{Aut}(G). Then for all x,y \in G, xy = yx if and only if \varphi(x)\varphi(y) = \varphi(y)\varphi(x). Proof: xy = yx if and only if \varphi(xy) = \varphi(yx) since \varphi is injective, if and only if \varphi(x)\varphi(y) = \varphi(y)\varphi(x) since \varphi is a homomorphism. \square

    Lemma 6: Let \varphi \in \mathsf{Aut}(S_n) with n \geq 3. Then |\bigcap_{k=2}^n M(\varphi((1\ k)))| = 1. Proof: For each k, \varphi((1\ k)) is a transposition by part (b). Thus |M(\varphi((1\ k)))| \leq 2. Suppose \bigcap_{k=2}^n M(\varphi((1\ k))) = \emptyset; then for some k \neq \ell, we have M(\varphi((1\ k))) \neq M(\varphi(1\ \ell)). But then \varphi((1\ k)) and \varphi((1\ \ell)) are disjoint and thus commute, a contradiction since (1\ k) and (1\ \ell) do not commute. Now suppose |\bigcap_{k=2}^n M(\varphi((1\ k)))| = 2; since each \varphi((1\ k)) is a transposition, we have \varphi((1\ k)) = \varphi((1\ \ell)) for all k and \ell, a contradiction since \varphi is injective and (since n \geq 3) there exist 2 \leq k, \ell \leq n with k \neq \ell. Thus |\bigcap_{k=2}^n M(\varphi((1\ k)))| = 1. \square

    Now to the main result. If n=2, then S_n has only the trivial automorphism, under which (1\ 2) \mapsto (1\ 2). If n \geq 3, then by part (b) each of \varphi((1\ k)) is a transposition for 2 \leq k \leq n, and by Lemma 6 the \varphi((1\ k)) move a common element a. Since \varphi is a bijection, the second element moved by the \varphi((1\ k)) are pairwise distinct. Thus for some distinct a,b_2,\ldots,b_n \in \{ 1,2,\ldots,n\} we have \varphi((1\ 2)) = (a\ b_2), \varphi((1\ 3)) = (a\ b_3), …, \varphi((1\ n)) = (a\ b_n).

  4. In §3.5 #3, we saw that S_n is generated by \{(a\ a+1) \ |\ 1 \leq a < n \}. Note that (a\ a+1) = (1\ a)(1\ a+1)(1\ a). Thus S_n = \langle \{ (1\ a) \ |\ 2 \leq a \leq n \} \rangle, and so any automorphism of S_n is uniquely determined by its action on these transpositions. By part (c), there are at most n! possible choices for the images of the (1\ k) under an automorphism \varphi (one for each assignment of the a,b_i to the integers \{1,2,\ldots,n\}). Thus \mathsf{Aut}(S_n) = \mathsf{Inn}(S_n) for n \neq 6.
Advertisements
Post a comment or leave a trackback: Trackback URL.

Comments

  • Gobi Ree  On December 15, 2011 at 3:02 am

    How about this for part 1: Let K=G \cdot a be a conjugacy class in G. Then for each \sigma \in \mathsf{Aut}(G), \sigma(K)=\sigma(G \cdot a)=\sigma(G) \cdot \sigma(a) = G \cdot \sigma(a).

    • nbloomf  On December 15, 2011 at 9:55 am

      I like it!

  • Gobi Ree  On December 15, 2011 at 3:47 am

    Some typos: I don’t know what is “ell” in Lemma6, and “with \latex k\neq l$” also looks like a miss.

    • nbloomf  On December 15, 2011 at 11:18 am

      Thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: