Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics I / 5

A transposition in the symmetric group $S_n$ exchanges two distinct symbols and fixes all others. A permutation cycle $(a_1{a}_2\cdots a_k)$ sends $a_j$ to $a_{j+1}$, sends $a_k$ to $a_1$, and fixes the other symbols. Its entries are distinct. For $k=1$ this is the identity permutation.

A group element has order of a group element $k$ if $k$ is the least positive integer for which its $k$th power is the identity element. For the displayed permutation cycle, its $j$th power sends $a_i$ forward $j$ places, with subscripts read modulo $k$. Hence the $k$th power fixes every symbol, whereas for $0<j<k$ the image of $a_1$ is different from $a_1$. Thus its order of a group element is exactly $k$, including $k=1$.

For each symbol $a$, iterate the permutation $\sigma$. Since the symbol set is finite, some iterate repeats. Applying an inverse power of $\sigma$ shows that the first return is to $a$ itself, givingwith the displayed symbols distinct. This is a permutation cycle. If two such lists share a symbol, applying powers of $\sigma$ shows that they contain exactly the same symbols. Hence these group orbits form a partition of a set $\{1,\dots ,n\}$. On each group orbit, $\sigma$ acts as the corresponding permutation cycle, and these disjoint permutation cycles multiply to $\sigma$.

The disjoint cycle decomposition is unique up to reordering the cycles and cyclically rotating the entries within each cycle, with fixed points optionally omitted. Indeed, each cycle must consist of one of the uniquely determined group orbits, and its successive entries must follow the action of $\sigma$.

With products acting from right to left, a permutation cycle satisfiesThe right side sends $a_1$ to $a_2$, each $a_j$ to $a_{j+1}$ for $2\le j<k$, and $a_k$ to $a_1$, while fixing all other symbols. This verifies the formula. Applying it to every cycle in the disjoint cycle decomposition expresses any permutation as a product of transpositions. The identity is represented by the empty product.

Suppose $\sigma$ has order of a group element two. On a cycle of length $k$, ${\sigma }^2$ moves each entry two places. Since ${\sigma }^2=e$, every such $k$ divides two, so $k=1$ or $k=2$. After omitting the fixed points, the disjoint cycle decomposition is therefore a product of disjoint permutation cycles of length two, which are transpositions. There is at least one, because $\sigma \ne e$.

If a permutation has disjoint cycle lengths $d_1,\dots ,d_t$, then its $k$th power is the identity exactly when every $d_j$ divides $k$. Thus its order of a permutation is $\mathrm{lcm}(d_1,\dots ,d_t)$.

Suppose $n=p^r$ is a prime power and $\sigma \in S_n$ has order $n$. Each $d_j$ divides $p^r$, so is a power of $p$. Their least common multiple is therefore their maximum, forcing some $d_j=p^r=n$. This cycle already uses all $n$ symbols, so $\sigma$ is an $n$-cycle.

Conversely, if $n>1$ is not a prime power, choose a prime-power factor $a=p^r$ containing the full power of one prime divisor of $n$, and put $b=n/a$. Then $a,b>1$, they are coprime, and $ab=n$. Moreoverso $a+b\le n$. We can therefore take disjoint cycles of lengths $a$ and $b$ in $S_n$, fixing all remaining symbols. Their product has order of a permutation $\mathrm{lcm}(a,b)=ab=n$, but it is not an $n$-cycle. This proves the prime-power characterization by full permutation cycles:

Acting separately on disjoint sets of four and eight symbols embeds the direct product of groups $S_4\times S_8$ into $S_{12}$. The action is injective since fixing all twelve symbols forces both factors to be identities.

For the lower bound, $S_4$ contains a cycle of order four and $S_8$ contains disjoint cycles of lengths five and three, whose product has order fifteen. The corresponding element of $S_4\times S_8$ has order of a group element $\mathrm{lcm}(4,15)=60$. Every isomorphic subgroup of $S_n$ must therefore contain a permutation of order sixty. We can bound the minimum number of symbols for a permutation of prescribed order directly here.

In the disjoint cycle decomposition of such a permutation, all cycle lengths divide $60$, and their least common multiple must contain the factors $4$, $3$, and $5$. If these factors occur in three distinct cycles, those cycles use at least $4+3+5=12$ symbols. If two occur in the same cycle, that cycle has length at least their product: combining $4,3$ costs at least $12$, combining $4,5$ costs at least $20$, and combining $3,5$ costs at least $15$. Each possibility already requires at least twelve symbols. Thus $n\ge 12$, and