This blog post is about why the number 6 is my favourite number – because the symmetric group on six elements is the only finite permutation group that contains an outer automorphism. In the post we will first look at why there are no other symmetric groups with outer automorphisms and then we will define an outer automorphism of \(S_6\).
Inner and Outer Automorphisms
If \(G\) is any group, then we can construct a new group \(\text{Aut}(G)\) consisting of all bijective group homomorphism \(\phi : G \to G\). This set forms a group under function composition. There is a natural map from \(G\) to \(\text{Aut}(G)\). A group element \(g \in G\) is taken to the function \(\gamma_g : G \to G\) given by \(\gamma_g(h) = ghg^{-1}\). Thus \(\gamma_g\) is conjugation by \(g\).
The kernel of \(g \mapsto \gamma_g\) is called the center of \(G\) and is denoted by \(Z(G)\). That is \(Z(G)\) is the subgroup consisting of group elements that commute with every other group element. The image of this map is denoted by \(\text{Inn}(G) \subseteq \text{Aut}(G)\). An automorphism which is in \(\text{Inn}(G)\) is called an inner automorphism. One can check that the subgroup of inner automorphisms is a normal subgroup. Indeed if we have a group element \(g \in G\) and an automorphism \(\phi \in \text{Aut}(G)\), then \(\phi \circ \gamma_g \circ \phi^{-1} = \gamma_{\phi(g)}\). Thus we can form the quotient \(\text{Aut}(G)/\text{Inn}(G)\) which we will call the outer automorphisms of \(G\) and denote by \(\text{Out}(G)\).
Thus the inner automorphisms of \(G\) are those which come from \(G\) in the form of conjugation. The outer automorphisms of \(G\) are equivalence classes of all the automorphisms of \(G\). Two automorphisms \(\phi, \phi’\) are equivalent in \(\text{Out}(G)\) if there is an inner automorphism \(\gamma_g\) such that \(\gamma_g \circ \phi = \phi’\).
The Symmetric Group
For a natural number \(n \in \mathbb{N}\), \(S_n\) will denote the group of permutations of the set \(\{1,2,\ldots,n\}\). Any permutation \(\sigma \in S_n\) can be written as product of disjoint cycles which we will call its cycle type. For instance, if \(n=5\) and \(\sigma(1)=3\), \(\sigma(2)=5\), \(\sigma(3)=4\), \(\sigma(4)=1\) and \(\sigma(5)=2\), then \(\sigma\) can be written in cycle notation as \((1,3,4)(2,5)\). Cycle notation is very useful for describing conjugation in \(S_n\). If we have two permutations \(\sigma, \tau \in S_n\) and we know the cycle notation for \(\sigma\), then the cycle notation for \(\tau \sigma \tau^{-1}\) can be derived by applying \(\tau\) to every entry in the cycle notation of \(\sigma\). For instance, with \(\sigma = (1,3,4)(2,5)\), we have
\(\tau(1,3,4)(2,5)\tau^{-1} = (\tau(1),\tau(3),\tau(4))(\tau(2),\tau(5))\).
To see why this result about conjugation is true, note the following. If \(\sigma(i)=j\) for some \(i,j \in \{1,2,\ldots,n\}\), then
\((\tau\sigma\tau^{-1})\tau(i)=\tau(\sigma(\tau^{-1}(\tau(i))))=\tau(\sigma(i))=\tau(j)\).
Thus two permutations \(\sigma, \sigma’\) are conjugate to one another if and only if \(\sigma\) and \(\sigma’\) have the same cycle type (ie they have the same number of cycles of any given size). This implies that for \(n \ge 3\), the centre of \(S_n\) must be trivial as for any non-identity \(\sigma \in S_n\), there is at least one other element of the same cycle type. Hence the map \(\sigma \mapsto \gamma_\sigma\) from \(S_n\) to \(\text{Aut}(S_n)\) is injective for \(n \ge 3\).
Counting Conjugacy Classes
Before constructing an outer automorphism for \(S_6\), we will see why such a map is special. In particular we will learn that \(\text{Aut}(S_n)\) consists entirely of inner automorphism for \(n \neq 6\). The argument is based off studying the size of different conjugacy classes in \(S_n\). This is important because if \(\phi\) is an automorphism of \(S_n\) and \(\sigma,\sigma’ \in S_n\) are two permutations, then \(\sigma\) is conjugate to \(\sigma’\) if and only if \(\phi(\sigma)\) is conjugate to \(\phi(\sigma’)\).
In \(S_n\) we know that two elements are conjugate if and only if they have the same cycle type. We can use this to count the size of different conjugacy classes of \(S_n\). In particular the number of permutations with \(n_k\) cycles of size \(k\) for \(k = 1,2,\ldots, n\) is
\(\displaystyle \frac{\displaystyle n!}{\displaystyle \prod\limits_{k=1}^n n_k! k^{n_k}}\).
The transpositions \((j,k)\) for \(1 \le j < k\le n\) generate \(S_n\) and form a conjugacy class which we call \(T\). For any automorphism \(\phi \in \text{Aut}(S_n)\) , the set \(\phi(T)\) must be a conjugacy class that is also of size \(| T | = n(n-1)/2\). Since automorphism preserve order, the elements of \(\phi(T)\) must all be of order two. Thus the cycle type of the conjugacy class \(\phi(T)\) must contain only cycles of size two or size one. Also there must be an odd number of two cycles. If there was an even number of two cycles, then we would have that \(\phi(T)\) is contained in the subgroup \(A_n \subseteq S_n\). However this would imply that \(\phi(S_n) \subseteq \phi(A_n)\) which contradicts the fact that \(\phi : S_n \rightarrow S_n\) is a bijection. Thus the following lemma implies that \(\phi(T)=T\) when \(n \neq 6\).
Lemma: Fix \(n \neq 6\) and an odd number \(k\) such that \(k > 1\) and \(2k \le n\). Let \(m_k\) denote the number of permutations \(\sigma \in S_n\) which have \(k\) cycles of size two and \(n-2k\) cycles of size one, then \(m_k \neq n(n-1)/2\).
Proof: This claim can be manually checked for \(n < 6\). For \(n > 6\), assume in order to get a contradiction that \(m_k = \frac{n(n-1)}{2}\). Note that \(m_k\) is equal to \(\frac{n!}{k! 2^k(n-2k)! 1^{n-2k}}=\frac{n!}{k! (n-2k)! 2^k}\). Thus we have \(\frac{n(n-1)}{2} = \frac{n!}{k!(n-2k)!2^k}\) and hence
\(2^{k-1} = \frac{(n-2)(n-3)\ldots(n-2k+1)}{k!}\).
Now if \(k \ge 5\), then \((n-4)(n-5)\ldots(n-2k+1)\) is a product of at least \(k\) consecutive integers and hence divisible by \(k!\) (see here). Thus
\(2^{k-1} = \frac{(n-2)(n-3)\ldots(n-2k+1)}{k!} = (n-2)(n-3)\frac{(n-4)(n-5)\ldots(n-2k+1)}{k!}\)
and hence \(\frac{(n-2)(n-3)\ldots(n-2k+1)}{k!}\) is divisible by an odd number other than one (either \(n-2\) or \(n-3\)). Thus \(\frac{(n-2)(n-3)\ldots(n-2k+1)}{k!}\) cannot be a power of \(2\), contradicting the above equation.
When \(k = 3\), the above equation becomes:
\(4= \frac{(n-2)(n-3)(n-4)(n-5)}{3!} = (n-2)\frac{(n-3)(n-4)(n-5)}{3!} = \frac{(n-2)(n-3)(n-4)}{3!}(n-5)\).
Thus if \(n\) is odd, \(n-2\) is an odd number other than \(1\) that divides 4, a contradiction. If \(n\) is even, then since \(n > 6\), \(n-5\) is an odd number other than \(1\) that divides \(4\), which is again a contradiction. Thus we cannot have any case when \(m_k = \frac{n(n-1)}{2}\).
\(S_n\) does not have an outer automorphism if \(n \neq 6\)
With the above lemma we can now prove that all the automorphism of \(S_n\) for \(n \neq 6\) are inner. First note that the only automorphism of \(S_2 = \{ \text{id}, (12)\}\) is the identity which is an inner automorphism. When \(n \ge 3\), the map \(\sigma \mapsto \gamma_\sigma\) from \(S_n\) to \(\text{Aut}(S_n)\) is injective. Thus there are exactly \(n!\) inner automorphisms of \(S_n\). We will show that for \(n \neq 6\) there are exactly \(n!\) automorphisms. Hence there can be no outer automorphisms.
Let \(\phi\) be an automorphism of \(S_n\). The symmetric group \(S_n\) is also generated by the \(n-1\) transpositions \(\sigma_i = (i,i+1)\) (for \(i =1, \ldots, n-1\)). By the previous lemma we know that if \(n \neq 6\), then each \(\phi(\sigma_i)\) must be a transposition \((j_i,k_i)\) for some \(j_i, k_i \in \{1,\ldots, n\}\) such that \(j_i \neq k_i\). As the collection \(\sigma_1,\ldots,\sigma_{n-1}\) generates \(S_n\), the automorphism \(\phi\) is determined by the transpositions \(\phi(\sigma_i)= (j_i,k_i)\). We will now show that there are exactly \(n!\) choices for these transpositions.
Since \(\sigma_1\sigma_{2} = (1,2,3)\), we know that \(\phi(\sigma_1)\phi(\sigma_2) = (j_1,k_1)(j_2,k_2)\) must be a three cycle. Thus one of \(j_2,k_2\) must be equal to one of \(j_1,k_1\) and the other must be distinct. By relabeling if necessary, we will require that \(k_1=j_2\) and \(j_1 \neq k_2\). Thus there are \(n\) choices for \(j_1\), \(n-1\) choices for \(k_1=j_2\) and \(n-2\) choices for \(k_2\). This gives us \(n(n-1)(n-2)\) choices for the first two transpositions. Continuing in this manner, we note that \(\sigma_1\sigma_3 = (1,2)(3,4)\) and \(\sigma_2\sigma_3 = (2,3,4)\), we get that one of \(j_3,k_3\) is equal to one of \(k_2\) and the other one is distinct from \(j_1,k_1=j_2,k_2\), thus giving us \(n-3\) choices for the third transposition. In general we will have that \(\sigma_{i-1}\sigma_i\) is a three cycle and \(\sigma_l\sigma_i\) is a pair of disjoint two cycles if \(l < i-1\). Thus one can show inductively that there are \(n-i\) choices for the transposition \(\phi(\sigma_i)\). Hence there are \(n(n-1)(n-2)\ldots 1 = n!\) choices for all the transpositions \(\phi(\sigma_i)\) and hence \(n!\) choices for \(\phi\). Thus, if \(n \neq 6\), all automorphisms of \(S_n\) are inner.
The outer automorphism of \(S_6\).
The key part of showing that \(S_n\) didn’t have any outer automorphisms when \(n \neq 6\) was showing that any automorphism must map transpositions to transpositions. Thus to find the outer automorphism of \(S_6\) we will want to find an automorphism that does not preserve cycle type. In particular we will find one which maps transpositions to the cycle type \((a,b)(c,d)(e,f)\). There are \(\frac{6!}{3!2^3} = 15\) such triple transpositions which is exactly \(\frac{6\cdot 5}{2}\) – the number of single transpositions.
The outer automorphism, \(\psi\), will be determined by the values it takes on \(\sigma_1,\sigma_2,\sigma_3,\sigma_4\) and \(\sigma_5\) (where again \(\sigma_i = (i,i+1)\)). Each of these transpositions will get to a different triple transposition \((a,b)(c,d)(e,f)\). To extend \(\psi\) to the rest of \(S_6\) it suffices to check the Coxeter relations \(\psi(\sigma_k)^2 = (\psi(\sigma_i)\psi(\sigma_{i+1}))^3 = (\psi(\sigma_i)\psi(\sigma_j))^2=\text{id}\) for \(k = 1,2,3,4,5\), \(i =1,2,3,4\) and \(j \ge i+2\).
The relation \(\psi(\sigma_k)^2=\text{id}\) will hold for any triple transposition \(\psi(\sigma_k)\). The other relations are a bit trickier. If we have two triple transpositions \(\tau = (a,b)(c,d)(e,f)\) and \(\tau’ = (a’,b’)(c’,d’)(e’,f’)\), then \(\tau\tau’\) will be a product of two three cycles if none of the transpositions of \(\tau\) is a transposition of \(\tau’\). If \(\tau\) and \(\tau’\) share exactly one transposition, then \(\tau\tau’\) is a product of two two cycles. If \(\tau\) and \(\tau’\) share two or more transpositions they must actually be equal and hence \(\tau\tau’\) is the identity.
With this in mind, one can verify that following assignment extends to a valid group homomorphism from \(S_6\) to \(S_6\):
\(\psi(\sigma_1) = (1,2)(3,4)(5,6)\),
\(\psi(\sigma_2) = (1,3)(2,5)(4,6)\),
\(\psi(\sigma_3) = (1,5)(2,6)(3,4)\),
\(\psi(\sigma_4) = (1,3)(2,4)(5,6)\),
\(\psi(\sigma_5) = (1,6)(2,5)(3,4)\).
We now just need to justify that the group homomorphism \(\psi\) is an automorphism. Since \(S_6\) is a finite group, \(\psi\) is a bijection if and only if \(\psi\) is an injection. Recall that only normal subgroups of \(S_6\) are the trivial subgroup, \(A_6\) and \(S_6\). Thus to prove injectivity of \(\psi\), it suffices to show that \(\psi(\tau) \neq \text{id}\) for some \(\tau \in A_6\). Indeed \(\psi(\sigma_1\sigma_3) = (1,6)(2,5) \neq \text{id}\) as required. Thus we have our outer automorphism!
This isn’t the most satisfying way of defining the outer automorphism as it requires using the generators of the symmetric group. There are many more intrinsic ways to define this outer automorphism which will hopefully be the topic of a later blog post!
References
The proof I give that for \(n \neq 6\), the group \(S_n\) has no outer automorphisms is based off the one given in this paper On the Completeness of Symmetric Group.