Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 6 down vote accepted

This is Landau's Function.

Asymptotic estimates are known.

share|improve this answer

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.

share|improve this answer
    
Thank you for this derivation. It is very helpful. –  Jeremy 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.