# Outer Automorphisms of $S_n$

There are a lots of questions (and several good explanations) on understanding the non-trivial outer automorphism of $S_6$. What I haven't seen, though, is a good explanation of why there are no such outer automorphisms for $n\neq 6$. Wikipedia makes a passing mention of this fact here.

In particular, they have this cryptic claim:

For every symmetric group other than $S_6$, there is no other conjugacy class of elements of order 2 with the same number of elements as the class of transpositions.

This seems like the natural thing to prove, given the knowledge that you can construct an outer automorphism of $S_6$ which takes transpositions to products of three transpositions (i.e. things like $(12)\mapsto (12)(34)(56)$.) Also, the second reason Wikipedia gives doesn't feel very intuitive to me.

My question, then, is how does one justify the original (quoted) statement above?

Here is the naive computation of sizes of conjugacy classes: We need to show that when $n, k\neq 6,3$ $$\frac{n!}{2^k k! (n-2k)!}\neq\frac{n!}{2(n-2)!},$$which is equivalent to $$2^k k!(n-2k)!\neq 2(n-2)!$$

What I want to say is something like, if $n{-}2$ is bigger than $k$, then there is always some factor on the RHS that doesn't appear in the LHS (except when it is a power of two). Will this type of analysis get me anywhere, or is there a better way to think about this?

-
Try counting powers of two? $2$ divides $m!$ $\sum\limits_{i=1}^\infty \lfloor m/2^i\rfloor$ times. Thus $$k+\sum_{i=1}^\infty\lfloor k/2^i\rfloor+\sum_{i=1}^\infty \lfloor(n-2k)/2^i\rfloor=\sum_{i=1}^\infty\lfloor(n-2)/2^i\rfloor+1$$ but $$k+\sum\limits_{i=1}^\infty \lfloor k/2^i\rfloor+\sum\limits_{i=1}^\infty \lfloor (n-2k)/2^i\rfloor = \sum\limits_{i=1}^\infty \lfloor 2k/2^i\rfloor+\sum\limits_{i=1}^\infty \lfloor (n-2k)/2^i\rfloor$$ which is usually $<<\sum\limits_{i=1}^\infty \lfloor n/2^i\rfloor$, which is rarely $>>\sum\limits_{i=1}^\infty \lfloor (n-2)/2^i\rfloor+1$. – Alex Becker Sep 16 '12 at 20:13

Yes, as you mention, $S_n$ has $n\choose2$ transpositions and the conjugacy class whose elements consist of $2\le k\le \frac n2$ disjoint transposition has $\frac{n!}{(n-2k)!2^kk!}$ elements. As you say, the condition that these numbers are the same is equivalent to $$\tag1 (n-2k)!2^{k-1}k!= (n-2)!$$

For $k=2$ this becomes $4(n-4)!=(n-2)!$ or equivalently $(n-2)(n-3)=4$, which has no integer solution.

For $k=3$, we obtain $24(n-6)!=(n-2)!$ or equivalently $(n-5)(n-4)(n-3)(n-2)=24$. This has integer solutions $n=6$ and $n=1$, the first leading to the exceptional situation with $S_6$, the other being invalid because it has $n<2k$.

For the rest of the argument, we may assume $k>3$. Then Bertrand's postulate states that there is a prime $p$ with $k<p<2k-2$. This $p$ does not divide $2^{k-1}k!$ but $n-2\ge2k-2$ implies that $p$ divides $(n-2)!$ so that we conclude that $p$ divides $(n-2k)!$ and finally that $p\le n-2k$. Rewrite (1) as $$\underbrace{2\cdot2\cdots 2}_{k-1}\cdot \underbrace{k\cdot (k-1)\cdots 2}_{k-1} = \underbrace{(n-2)(n-3)\cdots(n-2k+1)}_{2k-2}$$ Each of the $2k-2$ factors on the left is $\le k$, each of the $2k-2$ factors on the right is $>p>k$, hence equality cannot hold (as $2k-2\ne0$).

-

Just for interest, I'll treat the case $k >3$, trying to avoid the use of Bertrand's Postulate. Note that for $k >1$, $(n-2)!$ is divisible by $(n-2k)!(2k-2)!$. It suffices when $k > 3$ to prove that $2^{k-1}k! < (2k-2)!$, or equivalently that $(2k-2) \ldots (k+1) > 2^{k-1}$. There are $k-2$ terms in the left product, all at least $4.$ Also, we have $4^{k-2} > 2^{k-1}$ as $k >3.$

-
Just to make clear: my answer appeared after Hagen's, and I was taking advantage of the fact that he had dealt with the case $k \leq 3.$ – Geoff Robinson Sep 16 '12 at 23:20

As an alternative to Hagen von Eitzen's answer for the $k>3$ case, we can avoid using Bertrand's postulate. Write the equation as \begin{align*} \underbrace{k(k-1)\cdots 2}_{k-1} \cdot \underbrace{2\cdot2\cdots 2}_{k-1} = \underbrace{(n-2)(n-3)\cdots(n-2k+1)}_{2k-2} \end{align*} and compare terms pairwise (i.e. compare $k$ and $n-2$, then $k-1$ and $n-3$, etc.). There are two cases: $2k=n$ and $2k<n$.

For the first case ($2k=n$), note that since $k > 3$, we have $n \geq 8$. Note that each term on the right is greater than or equal to its corresponding term on the left, except for the last term on the right which is 1. We want to show that the right side has another factor of two to show that it's greater than the left. Consider the last non-1 term of $k!$, 2, on the left side and its correspond term on the right side, $n-k=\frac{n}{2}$. Divide both of these terms by 2 (and rearrange them) to get \begin{align*} \underbrace{k(k-1)\cdots 3}_{k-2}\cdot\underbrace{2\cdot 2\cdots 2}_{k-1} = \underbrace{(n-2)(n-3)\cdots(n-k+1)}_{k-2}\cdot \underbrace{(n-k-1)(n-k-2)\cdots 3 \cdot 2 \cdot \frac{n}{4}}_{k-1} \end{align*} Since $n \geq 8$, we have $\frac{n}{4} \geq 2$, so that comparing terms pairwise, each term on the right is greater than or equal to its corresponding term on the left, and since $n-2>\frac{n}{2}=k$ for $n \geq 8$, the right side is strictly greater than the left.

For the second case ($2k<n$), all terms on the right are immediately greater than or equal to their corresponding terms on the left, and since once again $n-2>\frac{n}{2}>k$ for $n \geq 8$, the right hand side is strictly greater than the left.

-

It takes a little work, but first you want to show that for $n \not= 6$, any automorphism of $S_n$ will take transpositions to transpositions. Next, note that $S_n$ is generated by $\{(12),(13),...,(1n)\}$. Now show that any automorphism will take this set to a set of the form $\{(ab_1),(ab_2),...,(ab_{n-1})\}$, which also generates $S_n$. Since each automorphism is uniquely determined by how it acts on the generators of the group, this gives at most $n!$ choices for automorphisms. That is, $|Aut(S_n)|\leq n!$. This implies that $Aut(S_n)=Inn(S_n)$, thus $Out(S_n)=\{1\}$.

-
From the post, it seems that the OP is stuck on the first step you mention. – Alex Becker Sep 16 '12 at 19:49
Also, you need to mention that $S_n\to\operatorname{Inn}(S_n)$ is injective (which follows e.g. by explicitly checking $g^{-1}tg\ne t$ when $t$ is a transposition of elements that $g$ does not transpose). – Hagen von Eitzen Sep 16 '12 at 19:58
I see now. You are on the right track, the cases where $n<5$ or $k=2$ are easy to show. The tricky part is showing that for $n>6$ and $k>2$, $$\frac{(n-2)}{k}\cdot\cdot\cdot\frac{n-(k-1)}{3}$$\frac{(n-k)}{2} \cdot\cdot\cdot \frac{(n-(2k-1))}{2}$>1$. Use the fact that $k\leq \frac{n}{2}$. – Tarnation Sep 16 '12 at 19:59