Exercise 4.4.18 ($\mathrm{Inn}(S_n) = \mathrm{Aut}(S_n)\qquad (n\geq 2, \ n\ne 6)$)

Proof. Fix an integer $n\ge 2$ with $n\ne 6$.

(a)

If $\alpha \in G$, let ${\mathcal{}K}_{\alpha }$ denote the conjugacy class of $\alpha$: $${\mathcal{}K}_{\alpha }=\{\mathit{𝛾𝛼}{\gamma }^{-1}\mid \gamma \in G\}.$$

We prove that for all $\sigma \in \mathrm{Aut}(G)$,

$$\begin{array}{lll}\hfill \sigma ({\mathcal{}K}_{\alpha })={\mathcal{}K}_{\sigma (\alpha )}:& & \hfill \text{(1)}\end{array}$$

• If $\tau \in \sigma ({\mathcal{}K}_{\alpha })$, then $\tau =\sigma (\beta )$, where $\beta \in {\mathcal{}K}_{\alpha }$, so $\beta =\mathit{𝛾𝛼}{\gamma }^{-1}$ for some $\gamma \in G$. Then $\tau =\sigma (\mathit{𝛾𝛼}{\gamma }^{-1})=\sigma (\gamma )\sigma (\alpha )\sigma {(\gamma )}^{-1}\in {\mathcal{}K}_{\sigma (\alpha )}$.

• Conversely, if $\tau \in {\mathcal{}K}_{\sigma (\alpha )}$, then $\tau =\mathit{𝜆𝜎}(\alpha ){\lambda }^{-1}$ for some $\lambda \in G$. Since $\sigma$ is bijective, there is some $\gamma \in G$ such that $\lambda =\sigma (\gamma )$. Then

  $$\begin{array}{llllll}\hfill \tau =\mathit{𝜆𝜎}(\alpha ){\lambda }^{-1}& =\sigma (\gamma )\sigma (\alpha )\sigma {(\gamma )}^{-1}& \hfill & & \hfill & \\ \hfill & =\sigma (\mathit{𝛾𝛼}{\gamma }^{-1})& \hfill & & \hfill & \\ \hfill & =\sigma (\beta ),& \hfill \text{where }\beta \in {\mathcal{}K}_{\alpha }.& & \hfill & & \hfill \end{array}$$

  So $\tau \in \sigma ({\mathcal{}K}_{\alpha })$.

This proves (1), thus for each $\sigma \in \mathrm{Aut}(G)$ and each conjugacy class $\mathcal{}K={\mathcal{}K}_{\alpha }$ of $G$ the set $\sigma (\mathcal{}K)={\mathcal{}K}_{\sigma (\alpha )}$ is also a conjugacy class of $G$.

(b)

All transpositions are conjugate, and an element conjugate to a transposition is also a transposition, thus the transpositions form a conjugacy class $\mathcal{}K={\mathcal{}K}_{\tau }$, where $\tau =(12)$. Let ${\mathcal{}K}^{\prime }={\mathcal{}K}_{\sigma }$ be the conjugacy class of any element $\sigma$ of order $2$ in $S_n$ that is not a transposition. Then $\sigma$ is a product of $k$ disjoint transpositions, where $k>1$. Since the $k$ transpositions are disjoint, $2k\le n$, so $2\le k\le n∕2$.

By Proposition 6 p. 123, we obtain

$$|\mathcal{}K|=\frac{n!}{2(n-2)!}=\frac{n(n-1)}{2},$$

and Exercise 4.3.33 gives

$$|{\mathcal{}K}^{\prime }|=\frac{n!}{(n-2k)!k!2^k}$$

(The cycle type of $\sigma$ is $(1,1,\dots ,1,2,2,\dots 2)$ for $n-2k$ fixed points and $k$ disjoint transpositions).

Note that $|\mathcal{}K|=|{\mathcal{}K}^{\prime }|$ if $k=1$, and also if $n=6,k=3$, values for which $|\mathcal{}K|=|{\mathcal{}K}^{\prime }|=15$ !!! (this explains the hypothesis $n\ne 6$ is the statement).

Assume for the sake of contradiction that $|\mathcal{}K|=|{\mathcal{}K}^{\prime }|$, where $k\ge 2$ and $n\ne 6$. Then

$$\frac{n!}{(n-2k)!k!2^k}=\frac{n!}{2(n-2)!},$$

or equivalently

$$\begin{array}{lll}\hfill \frac{(n-2)!}{(n-2k)!k!}=2^{k-1}\left(2\le k\le \frac{n}{2},n\ne 6\right).& & \hfill \text{(2)}\end{array}$$

We first check that (2) is false for $n=4$ and $n=5$:

• If $n=4$, then $k=2$, and

  $$\frac{(n-2)!}{(n-2k)!k!}=\frac{2!}{0!2!}=1\ne 2^{k-1}=2.$$

• If $n=5$, then $k=2$, and

  $$\frac{(n-2)!}{(n-2k)!k!}=\frac{3!}{1!2!}=3\ne 2^{k-1}=2.$$

We suppose now that $n>6$.

$$2^{k-1}=\frac{(n-2)!}{(n-2k)!k!}=\frac{(n-k)!}{(n-2k)!k!}\cdot \frac{(n-2)!}{(n-k)!}=\left(\genfrac{}{}{0.0pt}{}{n-k}{k}\right)\cdot \frac{(n-2)!}{(n-k)!},$$

where $\left(\genfrac{}{}{0.0pt}{}{n-k}{k}\right)$ is a positive integer, since $2\le k\le n∕2$.

This shows that $\frac{(n-2)!}{(n-k)!}$ divides $2^{k-1}$, hence $\frac{(n-2)!}{(n-k)!}$ is a power of $2$.

• Suppose first that $k\ge 4$ (so that $n\ge 8$). Then $\frac{(n-2)!}{(n-k)!}>1$, thus

  $$(n-2)(n-3)\cdots (n-k+1)=\frac{(n-2)!}{(n-k)!}=2^l,l>0.$$

  Then $(n-2)(n-3)\mid 2^l$. This is impossible, because one of the two consecutive integers $n-2>1$ or $n-3>1$ is odd.

  It remains the cases $k=2$ and $k=3$.

• If $k=2$, then (2) is equivalent to

  $$\frac{(n-2)!}{(n-4)!2!}=2,$$

  thus $(n-2)(n-3)=4$, so $n^2-5n+2=0$, $4n^2-20n+8=0$, ${(2n-5)}^2=17$. This is impossible because $17$ is not a perfect square.

• If $k=3$, then (2) is equivalent to

  $$\frac{(n-2)!}{(n-6)!3!}=2^2,$$

  so

  $$(n-2)(n-3)(n-4)(n-5)=24.$$

  This last equation has solution $n=6$. Since $n\mapsto (n-2)(n-3)(n-4)(n-5)$ is strictly increasing for $n\ge 6$, there is no solution for $n>6$.

In conclusion, if $2\le k\le n∕2$ and $n\ne 6$, there is no solution to $\frac{(n-2)!}{(n-2k)!k!}=2^{k-1}$, so if $n\ge 2,n\ne 6$.

$$|\mathcal{}K|\ne |{\mathcal{}K}^{\prime }|$$

Let $\sigma$ be any automorphism of $S_n$, and $\mathcal{}K={\mathcal{}K}_{\tau }$, where $\tau =(12)$, the conjugacy class of transpositions in $S_n$. Then ${\mathcal{}K}^{\prime }={\mathcal{}K}_{\sigma (\tau )}=\sigma (\mathcal{}K)$. Since $\sigma$ is an automorphism of $S_n$, this implies $|{\mathcal{}K}^{\prime }|=|\mathcal{}K|$. Moreover $|\sigma (\tau )|=|\tau |=2$. If $\sigma (\tau )$ is not a transposition, as proven above, $|{\mathcal{}K}^{\prime }|\ne |\mathcal{}K|$. This is a contradiction, which proves that $\sigma (\tau )$ is a transposition, so that ${\mathcal{}K}^{\prime }={\mathcal{}K}_{\sigma (\tau )}=\mathcal{}K$.

Any automorphism $\sigma$ of $S_n$ sends transpositions to transpositions.

(c)

Let $\sigma \in \mathrm{Aut}(S_n)$. Put $a=\sigma (1)\in [[1,n]]$, so that $a$ is in the support of $\sigma ((1i))$ for any $i$. By part (b), $\sigma$ maps $(1i)$ on a transposition whose support contains $a$, thus $$\sigma :(1i)\mapsto (a{b}_i)(b_i\in [[1,n]],a\ne b_i).$$

Moreover if $i\ne j$, then $(1i)\ne (1j)$. Since $\sigma$ is injective, $\sigma ((1i))\ne \sigma ((1j))$, thus $(a{b}_i)\ne (a{b}_j)$, so that $b_i\ne b_j$. So

$$\sigma :(12)\mapsto (a{b}_2),\sigma :(13)\mapsto (a{b}_3),\dots ,\sigma :(1n)\mapsto (a{b}_n)$$

for some distinct integers $a,b_2,b_3,\dots ,b_n\in \{1,2,\dots ,n\}$.

(d)

Let $G=⟨(12),(13),\dots ,(1n)⟩\le S_n$.

If $i=1$, then $(ij)\in G$, and if $1\le i<j$, then

$$(ij)=(1i)(1j){(1i)}^{-1}.$$

Therefore $G$ contains all the transpositions $(ij)$. Since $S_n$ is generated by the transpositions by Section 3.5, we obtain $G=S_n$, so

$$⟨(12),(13),\dots ,(1n)⟩=S_n.$$

Therefore every permutation $\tau \in S_n$ is a product $\tau ={\tau }_1{\tau }_2\dots {\tau }_k$, where ${\tau }_1,{\tau }_2,\dots {\tau }_k$ are transpositions of the form $(1i)$ for some $i\in [[2,n]]$. If $\sigma ,{\sigma }^{\prime }$ are automorphisms of $S_n$ such that $\sigma ((1i))={\sigma }^{\prime }((1i)$ for all $i\in [[2,n]$, then

$$\sigma (\tau )=\sigma ({\tau }_1)\sigma ({\tau }_2)\cdots \sigma ({\tau }_k)={\sigma }^{\prime }({\tau }_1){\sigma }^{\prime }({\tau }_2)\cdots {\sigma }^{\prime }({\tau }_k)={\sigma }^{\prime }(\tau ),$$

so $\sigma ={\sigma }^{\prime }$: any automorphism of $S_n$ is uniquely determined by its action on the transpositions $(12),(13),\dots ,(1n)$.

By part (c),

$$\sigma :(12)\mapsto (a{b}_2),\sigma :(13)\mapsto (a{b}_3),\dots ,\sigma :(1n)\mapsto (a{b}_n)$$

for some distinct integers $a,b_2,b_3,\dots ,b_n\in \{1,2,\dots ,n\}$.

There are $n$ possible choices for $a$, then $n-1$ choices for $b_2$, $n-2$ for $b_3$, $\cdots$, $n-(n-1)=1$ choice for $b_n$, thus there are at most $n!$ automorphisms in $\mathrm{Aut}(S_n)$:

$$|\mathrm{Aut}(S_n)|\le n!(n\ge 2\mathit{𝑛𝑛}\ne 6).$$

If $n=2$, Then $S_2\simeq Z_2$ is abelian, and $\mathrm{Aut}(Z_2)=\{1\}=\mathrm{Inn}{Z}_2$, so $\mathrm{Aut}(S_2)=\mathrm{Inn}{S}_2$.

Now we assume that $n\ge 3$. By Exercise 4.3.8, $Z(S_n)=\{()\}$ for $n\ge 3$, thus

$$\mathrm{Inn}(S_n)\simeq S_n∕Z(S_n)\simeq S_n.$$

Therefore $|\mathrm{Inn}(S_n)|=n!\ge |\mathrm{Aut}(S_n)|$, where $\mathrm{Inn}(S_n)\le \mathrm{Aut}(S_n)$, so $|\mathrm{Aut}(S_n)|\ge n!$, thus $|\mathrm{Aut}(S_n)|=n!$ and

$$\mathrm{Inn}(S_n)=\mathrm{Aut}(S_n)(n\ge 2,n\ne 6).$$

So every automorphism of $S_n$ is inner for $n\ge 2$, $n\ne 6$. □