Exercise :
Find the maximum possible order of an element of the group of permutations $S_7$. Do the same thing for $S_{10}$.
Discussion :
Recalling that any permutation can be written as a product of disjoint cycles :
$$c=c_1 c_2\dots c_r$$
the order of $|σ|=\text{lcm}(|σ_1||σ_2|\dots|c_r|)$ and if $c_i$ has length $k_i$ then it will be $|c_i|=k_i$.
So what I have to do is find all the possible products of disjoint cycles, which will be :
$$(1,2) \space \text{ of order } \space 2$$
$$(1,2,3) \space \text{ of order } \space 3$$
$$(1,2,3,4) \space \text{ of order } \space 4$$
$$(1,2)(3,4) \space \text{ of order } \space 2$$
$$(1,2,3,4,5) \space \text{ of order } \space 5$$
$$(1,2,3)(4,5) \space \text{ of order } \space 6$$
$$(1,2,3,4,5,6) \space \text{ of order } \space 6$$
$$(1,2,3,4)(5,6) \space \text{ of order } \space 4$$
$$(1,2)(3,4)(5,6) \space \text{ of order } \space 2$$
$$(1,2,3)(4,5,6) \space \text{ of order } \space 3$$
$$(1,2,3)(4,5)(6,7) \space \text{ of order } \space 6$$
$$(1,2,3,4,5)(6,7) \space \text{ of order } \space 10$$
$$(1,2,3,4)(5,6,7) \space \text{ of order } \space 12$$
$$(1,2,3,4,5,6,7) \space \text{ of order } \space 7$$
So, the maximum possible order of an element in $S_7$ is $12$.
Question :
What I wanted to ask is $(1)$ am I correct, first of all?
And $(2)$ how am I supposed to find the maximum order of an element in $S_{10}$ ? Judging from all the possible cycle products in $S_7$ it will be a pretty big list for $S_{10}$. Am I missing a trick or some clever way to reach the desired result faster ?
P.S. : I know that Landau's function calculates exactly that thing, but we haven't been taught about it yet.
Best Answer
First of all yes, your answer for $S_7$ is correct. And indeed listing all cycle types quickly becomes unmanageable as $n$ grows.
It is quite helpful and not difficult to prove that the maximum is always assumed for a permutation that is the product of disjoint cycles of prime power lengths. For increasing values of $n$ this eliminates an increasing proportion of permutations; for $n=7$ and $n=10$ it does not eliminate much.
It is also quite helpful and not difficult to prove that the maximum is always assumed for a permutation that has at most one fixed point. This eliminates a large proportion of permutations for any $n$.
With these two facts in mind, for $n=7$ we are left with permutations of cycle types $$(7),\ (5,2),\ (4,3),\ (4,2,1),\ (3,3,1),\ (3,2,2)\quad \text{and}\quad (2,2,2,1).$$ For $n=10$ we are left with permutations of cycle types $$(9,1),\ (8,2),\ (7,3),\ (7,2,1),\ (5,5),\ (5,4,1),\ (5,3,2),\ (4,4,2),\ (4,3,3),\ (4,3,2,1),\ (3,3,3,1),\ (3,3,2,2),\quad\text{and}\quad (2,2,2,2,2).$$ Of course one can already see some recursion in this problem; given that the maxima for $n=3$ and $n=5$ are assumed for cycle types $(3)$ and $(3,2)$, respectively, for $n=10$ we can eliminate the cycle types $$(7,2,1),\ (5,5)\quad\text{and}\quad(5,4,1).$$ There are a lot of simple facts to note that each reduce the number of cycle types to consider by a little bit. For your problem there aren't that many to begin with, and the facts above are enough to make the problem manageable by hand. But it can just as well be done by hand for $n=100$ and $n=1000$, though this requires more careful analysis of the problem which I won't go into here. I'll leave you with this vague intuition though:
Heuristically, for large $n$ the maximum is assumed when writing $n$ as a sum of prime powers close to $\sqrt{n}$, and padding the remainder with small primes. It is not easy to compute the maximum precisely for large values of $n$, though asymptotically it is $\exp((1+o(1))\sqrt{n\ln{n}})$.