Past exam of the mathematics course of the University of Oxford / 2023 / Prelims / Mathematics I / 7 (Automorphisms of symmetric groups)

Conjugating a cycle simply relabels its entries. With permutations composed from right to left,This follows by applying each side to $\rho (a_j)$ and to points outside the displayed cycle. Consequently conjugation preserves the lengths in the disjoint cycle decomposition, including fixed points, and therefore preserves cycle type.

Conversely, suppose two permutations have the same cycle type. Pair their cycles of equal length, including their one-cycles. Define a bijection $\rho$ by mapping the entries of each cycle of the first permutation, in their cyclic order, to the entries of the paired cycle of the second. Because the cycles partition $\{1,\dots ,n\}$, these assignments combine into a permutation. The displayed identity then conjugates the first permutation to the second. Thus they are conjugate group elements exactly when their cycle types agree.

Let the lengths in the disjoint cycle decomposition of $\tau$ be ${\ell }_1,\dots ,{\ell }_s$, with fixed points contributing length one. Disjoint cycles commute, and ${\tau }^m=e$ if and only if every cycle raised to $m$ is the identity, equivalently ${\ell }_j$ divides $m$ for every $j$. Hence the order of a group element isIn particular, the identity has order one.

For $0\le k\le \lfloor n/2\rfloor$, first select an ordered list of $2k$ distinct entries. There are $n!/(n-2k)!$ lists. Pair consecutive entries to obtainEach product of $k$ disjoint transpositions is counted $2^{k}k!$ times: each pair has two orientations, and the $k$ pairs can be ordered in $k!$ ways. There is no other duplication, by uniqueness of the disjoint cycle decomposition. ThereforeIf $2k>n$, there are no such permutations. For $k=0$, $T_0=\{e\}$.

For distinct $i,j\ne 1$, direct conjugation givesThus the given star transpositions generate every transposition. Every cycle can in turn be expressed asBy the disjoint cycle decomposition, every permutation is a product of cycles, hence of transpositions, hence of the given star transpositions. ThereforeFor $n=1$, the empty generating set of a group generates the trivial group $S_1$.

Assume first $n\ge 2$. All transpositions form a single conjugacy class $T_1$. A group automorphism preserves order of a group element, so the image of a transposition is a nonidentity involution. By the order formula, its disjoint cycle decomposition contains only one-cycles and two-cycles, with at least one two-cycle. Thus it lies in some $T_k$, where $1\le k\le \lfloor n/2\rfloor$.

Moreover an automorphism maps the entire conjugacy class onto the conjugacy class of the image: for a fixed transposition $t$,and $\varphi (g)$ runs over all of $S_n$ by surjectivity. Part (a)(i) identifies that latter conjugacy class as $T_k$. Hence $\boxed{\varphi (T_1)=T_k}$, with equality rather than just inclusion. If $n=1$, $T_1$ is empty and the equality holds trivially with $k=1$.

For $n\ge 2$ with $n\ne 6$, bijectivity of $\varphi$ and the previous part implyThe supplied numerical fact forces $k=1$. Thus $\varphi$ permutes the transpositions.

Suppose $n\ge 3$, and write $s_r=\varphi ((1r))$ for $r=2,\dots ,n$. These are distinct transpositions. For $r\ne t$, the product $(1r)(1t)$ has order of a group element three, so $s_r{s}_t$ also has order three. Two distinct transpositions have this property precisely when their two-element sets of moved points meet in one point: disjoint ones have a product of order two, whereas ones sharing one point have a three-cycle as product. The two-element support of a permutation associated with each $s_r$ therefore meets that of every other $s_t$.

We now show that they have a common point. Choose two; the support of a permutation is $\{a,b\}$ for one and $\{a,c\}$ for the other, where $a,b,c$ are distinct. Any further two-element set meeting both either contains $a$ or is $\{b,c\}$. If $\{b,c\}$ occurs, any two-element set meeting all three must itself be one of $\{a,b\},\{a,c\},\{b,c\}$: a set containing $a$ must also contain $b$ or $c$, and a set omitting $a$ must contain both $b,c$. Hence a pairwise-intersecting family with no common point consists of exactly those three edges of a triangle.

For $n\ge 5$, there are $n-1\ge 4$ distinct $s_r$, ruling out that triangle. For $n=3$, the two sets already have a common point. For $n=4$, the triangle alternative would make all three $s_r$ fix the fourth point. They would then generate a proper subgroup of $S_4$, contrary to surjectivity of $\varphi$ and part (a)(iv), which imply that the $s_r$ generate $S_4$. Thus in every case $n\ge 3$ there is a common point $a$, and we may writeThe $b_r$ are distinct and different from $a$, so they exhaust the remaining $n-1$ points. Define a permutation $\sigma$ byThenThe two group homomorphisms $\tau \mapsto \varphi (\tau )$ and $\tau \mapsto {\sigma }^{-1}\tau \sigma$ agree on a generating set of a group, so agree on every product of its elements, hence throughout $S_n$:Finally, $S_1$ is trivial and $S_2$ has a unique nonidentity element, so every automorphism of either is the identity and we can take $\sigma =e$. This completes all degrees $n\ne 6$ and proves that every such automorphism is an inner automorphism.