# Maximal order of an element in a symmetric group

If we let $$S_n$$ denote the symmetric group on $$n$$ letters, then any element in $$S_n$$ can be written as the product of disjoint cycles, and for $$k$$ disjoint cycles, $$\sigma_1,\sigma_2,\ldots,\sigma_k$$, we have that $$|\sigma_1\sigma_2\ldots\sigma_k|=\operatorname{lcm}(\sigma_1,\sigma_2,\ldots,\sigma_k)$$.

So to find the maximum order of an element in $$S_n$$, we need to maximize $$\operatorname{lcm}(\sigma_1,\sigma_2,\ldots,\sigma_k)$$ given that $$\sum_{i=1}^k{|\sigma_i|}=n$$. So my question:

How can we determine $$|\sigma_1|,|\sigma_2|,\ldots,|\sigma_k|$$ such that $$\sum_{i=1}^k{|\sigma_i|}=n$$ and $$\operatorname{lcm}(\sigma_1,\sigma_2,\ldots,\sigma_k)$$ is at a maximum?

## Example

For $$S_{10}$$ we have that the maximal order of an element consists of 3 cycles of length 2,3, and 5 (or so I think) resulting in an element order of $$\operatorname{lcm}(2,3,5)=30$$.

I'm certain that the all of the magnitudes will have to be relatively prime to achieve the greatest lcm, but other than this, I don't know how to proceed. Any thoughts or references? Thanks so much.

• I've wanted to know this for quite a while, ever since I noticed that $Z_6$ is a subgroup of $S_5$, so thanks for asking. – MJD Oct 26 '12 at 0:34

This is Landau's Function.

Asymptotic estimates are known.

André has already provided the name and the link; here's a derivation of the bound $g(n)\lt\mathrm e^{n/\mathrm e}$ in the article. If we could choose all the $l_i:=|\sigma_i|$ freely, only constrained by their sum $n$, we'd want to find the stationary points of the objective function

$$\prod_il_i-\lambda\sum_il_i\;.$$

Differentiating with respect to $\sigma_j$ yields

$$\prod_il_i=\lambda l_j\;,$$

so not surprisingly the only stationary point is where all the $l_i$ are equal. Then we can optimize their number $k$ by writing $l_i=n/k$, and we want to maximize

$$\left(\frac nk\right)^k\;,$$

or equivalently

$$\log\left(\frac nk\right)^k=k\left(\log n-\log k\right)\;.$$

Taking the derivative with respect to $k$ yields $\log n-\log k=1$ and thus $k=n/\mathrm e$, so ideally we'd want all the $l_i$ to be $\mathrm e$. In that case the product would be $\mathrm e^{n/\mathrm e}$, and the constraints that the $l_i$ have to be coprime integers can only lower that value (quite considerably, as the asymptotic result in the article shows).

This calculation also shows that $\mathrm e$ would be the optimal radix for a Fast Fourier Transform.

• Thank you for this derivation. It is very helpful. – Jemmy Oct 26 '12 at 10:06
• @Jeremy: You're welcome! – joriki Oct 26 '12 at 10:11

For more detail you can see this paper.

The maximum order of an element of finite symmetric group by William Miller, American Mathematical Monthly, page 497-506.