23
$\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.

$\endgroup$
3
  • 7
    $\begingroup$ 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. $\endgroup$
    – MJD
    Oct 26, 2012 at 0:34
  • $\begingroup$ @MJD How is it a subgroup ? $\endgroup$ Jun 7, 2020 at 13:14
  • 1
    $\begingroup$ @ashishyadaveee11 The subgroup of $S_5$ generated by the element $(a b c)(d e)$ is cyclic of order 6. $\endgroup$
    – MJD
    Jun 7, 2020 at 19:49

3 Answers 3

21
$\begingroup$

This is Landau's Function.

Asymptotic estimates are known.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you for this derivation. It is very helpful. $\endgroup$
    – Jemmy
    Oct 26, 2012 at 10:06
  • $\begingroup$ @Jeremy: You're welcome! $\endgroup$
    – joriki
    Oct 26, 2012 at 10:11
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .