Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 3 / 3

An group automorphism preserves element orders and sizes of conjugacy classes. A nonidentity involution in $S_n$ has cycle type $2^k{1}^{n-2k}$ and class sizeFor its class to have the same size as the transposition class, it must satisfyFor fixed $k\ge 2$ the left side grows strictly with $n$. When $k=2$, it is $(n-2)(n-3)$, which is two at $n=4$ and at least six at $n=5$, never the required four. For $k=3$ equality first occurs at $n=6$, since $4!=2^2\cdot 3!$, and thereafter the left side is larger. For $k\ge 4$ it is already larger at $n=2k$: the ratio $(2k-2)!/[2^{k-1}k!]$ is $15/4$ at $k=4$, and increases with $k$, its successive ratio being $k(2k-1)/(k+1)>1$. This proves the symmetric-group involution class-size collision result. Therefore, for $n\ne 6$, every group automorphism maps transpositions to transpositions.

Now recover the underlying points from transpositions. Two distinct transpositions fail to commute exactly when their two-element supports meet. A maximal family of pairwise intersecting edges of a complete graph is either a vertex star or a triangle. Indeed, after selecting edges $\{1,2\}$ and $\{1,3\}$, every edge either contains 1 or is $\{2,3\}$; if the latter occurs, all edges lie in that triangle. For $n\ge 5$, the stars have size $n-1\ge 4$ and triangles size three, so stars are recognized purely by the multiplication structure of $S_n$.

An group automorphism must thus permute the stars, giving a permutation $\tau$ of the points. The unique transposition shared by stars $i,j$ is $(ij)$, so its image is $(\tau (i)\tau (j))$. Since transpositions generate $S_n$, the whole group automorphism is conjugation by $\tau$.

At $n=4$, stars and triangles both have three elements, but their generated subgroups distinguish them: the transpositions in a star generate all of $S_4$ (since $(ij)=(ai)(aj)(ai)$ for its center $a$), while a triangle generates the $S_3$ fixing the fourth point. The same reconstruction follows. At $n=3$, conjugation by $S_3$ induces every permutation of its three transpositions (a transposition swaps the other two, and a three-cycle rotates all three), so a transposition-preserving group automorphism is again inner. At $n=2$ the only group automorphism of $C_2$ is the identity, and $n=0,1$ are trivial (if the empty-set degree is included). ThusThe small-degree adjustments are necessary: a cardinality-only star argument would not cover $n=4$.

Use the six-point matching geometry. A duad is an edge of the complete graph on six points, a syntheme is a perfect matching of its three pairs, and a pentad is a one-factorization: five pairwise edge-disjoint synthemes covering all fifteen duads.

First count the pentads without assuming their number. There are fifteen synthemes: the partner of the first point has five choices, the least remaining point then has three possible partners, and the last pair is forced. For a fixed syntheme $M$, eight others share no edge with it: inclusion-exclusion gives $15-3\cdot 3+3\cdot 1-1=8$. Two edge-disjoint synthemes $M,M^{\prime }$ have union a six-cycle. The complement of that cycle is a triangular prism, consisting of two triangles with three corresponding cross edges. It has precisely four perfect matchings: the all-cross matching and three matchings using one cross edge plus one edge from each triangle. The all-cross matching leaves two odd triangles and therefore cannot be completed by two matchings. The other three matchings are pairwise edge-disjoint and partition the prism. Hence $M,M^{\prime }$ extend to exactly one pentad.

Each pentad through $M$ uses four of its eight disjoint partners, and every partner gives exactly one completion. Thus $M$ lies in two pentads. Counting incidences gives $15\cdot 2/5=6$ pentads in total. Distinct pentads cannot share two synthemes because two disjoint synthemes determine their unique completion. Every syntheme therefore identifies a distinct pair of pentads; there are fifteen such pairs, so this incidence map is a bijection.

Permuting the six original points permutes the six pentads, defining a group homomorphism $\Phi :S_6\to \mathrm{Sym}(\text{pentads})$. It is faithful. If an element fixes every pentad, it fixes every syntheme by the pair-incidence bijection. A duad is the unique common edge of two distinct synthemes containing it, so every duad is fixed as well. A permutation fixing all two-element subsets fixes every point, by intersecting $\{i,j\}$ and $\{i,k\}$ for distinct $i,j,k$. The kernel of a group homomorphism is therefore trivial. Both groups have order $6!$, so labeling the pentads produces an group automorphism of $S_6$.

It remains to prove this group automorphism is outer. A transposition, say $(12)$, fixes no pentad. If it fixed one, the unique syntheme in that pentad containing the duad $\{1,2\}$ would be fixed. Every other syntheme $M^{\prime }$ in the pentad contains 1 and 2 in separate edges. Swapping them changes those two edges but leaves the third edge unchanged. Hence $(12)M^{\prime }$ is a distinct syntheme sharing an edge with $M^{\prime }$, impossible for two members of the same pentad. Thus $(12)$ acts without fixed points on the six pentads and becomes a product of three disjoint transpositions.

Inner automorphisms preserve cycle type, whereas $\Phi$ sends a single transposition to a triple transposition. ConsequentlyThis realizes the exceptional class-size coincidence from part (a). It is the full symmetric-group version of the pentad construction of the exceptional alternating-group automorphism, with faithfulness proved directly from incidence rather than borrowed from a simplicity theorem.