20
$\begingroup$

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.

  • 5
    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.2012-10-26

3 Answers 3

17

This is Landau's Function.

Asymptotic estimates are known.

9

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.

  • 0
    @Jeremy: You're welcome!2012-10-26
2

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.