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$.

• 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!