Upper bound on the order of elements in the symmetric group

Question

In Vinberg's textbook on algebra you are asked in an exercise to prove that the order of any element in the symmetric group on n letters does not exceed e^(n/e), which the book tells you is approximately 1.44^n.

This exercise was stated immediately after showing how to calculate the order of an element by writing it as a product of disjoint cycles and taking the least common multiple of the cycle lengths.

Any hints on how to do this? Unfortunately I've been stuck for a while.

Answer 1

Say you have the disjoint cycle deccomposition $\tau_1\cdots\tau_m$, with $$ \sum |\tau_i| = n$$

And you want to maximize $lcm(|\tau_i|)$. This is always less than $$ \prod |\tau_i| $$

Can you maximize this product, with the constraint $\sum |\tau_i| = n$? Hint: this is like maximizing the area of a box given its perimeter.

To maximize the product, we need all $|\tau_i|$ equal, so we can take $|\tau_i|=\frac{n}{m}$. [Note this is not necessarily an integer, but it doesn't matter.]

Now you can finish by maximizing the expression you just got, over all $m$:

Our maximized product is $\left(\frac{n}{m}\right)^m$. Since $n$ is fixed, we can take the derivative of this with respect to $m$ to find the maximum of this expression is achieved when $m=n/e$. So our overall maximum is $e^{n/e}$.