= Minimum number of symbols for a permutation of prescribed order
{title2=$\mu(m)=\sum_{p^a\parallel m}p^a\quad(m>1)$}
Write the <prime factorization> of $m>1$ as $m=q_1\cdots q_t$, with each $q_j$ a positive power of a distinct <prime number>. The least $n$ such that $S_n$ contains a <permutation> of order $m$ is $q_1+\cdots+q_t$.
For existence, take <disjoint permutation cycles> of lengths $q_j$. Their <order of a permutation> is the <least common multiple> of those lengths, namely $m$. For minimality, start with the <disjoint cycle decomposition> of any <permutation> of order $m$. Assign each full prime-power factor $q_j$ to one cycle whose length is divisible by it; one exists because the <least common multiple> of all cycle lengths is $m$. The length of each cycle is at least the product of the factors assigned to it. For integers $a,b\geq2$, $ab\geq a+b$, so a product of at least two assigned factors is at least their sum; the assertion is immediate for one factor. Summing over cycles gives at least $\sum_jq_j$ symbols. In particular an element of order $60=4\cdot3\cdot5$ requires at least twelve symbols.
Back to article page
