# How do I find the permutation with the highest order in a symmetric group?

My professor gives this text, but I don't understand what it's saying, could someone explain it to me?

Let $M(n)$ denote the largest order of an element in $S_n$. By Theorem 1 $M(n)$ is the largest number we can get looking at $k_1\cdot k_2 \cdot \ldots \cdot k_n$ where $n = k_1 + k_2 + \ldots + k_m$ and the $k_i,k_j$ are relatively prime for $i \neq j$.

Theorem 1 says: Let $c_1,c_2,\ldots ,c_m$ be disjoint cycles with lengths $l_1,l_2, \ldots l_m$ then $o(c_1c_2\ldots c_m) = \operatorname{lcm}(l_1, l_2, \ldots l_m)$.

How can I go about finding the largest order of an element using this information given?

• Try to work out small examples, for $n=3,4,5$, to get a feeling for the theorem. – Nicky Hekster Apr 11 '15 at 21:37
• Try the advice in meta.math.stackexchange.com/q/5020/139123 to make this question easier to read. – David K Apr 11 '15 at 21:41
• Are you trying to find the largest order, or to find an example of a permutation with the largest order? Your last line says the first, while the title says the second. To find the largest order, you have to find the set of $k$'s with the highest product. – Ross Millikan Apr 11 '15 at 21:55
• @achillehui: your link that says it is to OEIS does not go there. The link to Landau's function also does not go where you intended. They both go to www.meipai.com – Ross Millikan Apr 11 '15 at 21:58
• @RossMillikan strange, let me try that again. – achille hui Apr 11 '15 at 22:02

To start with a concrete example: Let's look at the permutation $\pi = (1 4 6)(2 3)(5789) \in S_9$.

Permutations that are disjoint commute with each other; that's why writing a permutation as disjoint cycles is so useful. This means that if we want to compute $\pi^k$, it's as easy is just raising each of those disjoint cycles to the $k$th power:

$$\pi^k = (146)^k(23)^k(5789)^k.$$

What's the smallest power of $k$ we need, in order to have $\pi^k = 1$? It's exactly the least common multiple of the cycle lengths; $o(\pi) = \operatorname{lcm}(3, 2, 4) = 12$.

What we have 'more efficiently' achieved the same, or higher, order? Well, for one, the $2$-cycle $(23)$ didn't affect $o(\pi)$ at all, since $\operatorname{lcm}(3, 2, 4) = \operatorname{lcm}(3, 4)$.

This leads naturally to the stipulation that we need only look cycle-decompositions that are pairwise coprime. Let's look at what can happen in $S_{16}$.

Let's say our cycle-decomposition is $6 + 10$, where $\gcd(6, 10) = 2$. Now $\operatorname{lcm}(6, 10) = 30$, but it's also true that $\operatorname{lcm}(2, 3, 5) = 30$, where $2 + 3 + 5 = 10$. This means that, instead of using a $6$- and $10$-cycle, we could achieve the same order with the product a $2$-, $3$-, and $5$-cycle, permuting only $2 + 3 + 5 = 10$ elements, rather than all $16$. We could fit an extra $4$-cycle in the latter product, yielding an element whose order is now $\operatorname{lcm}(2, 3, 4, 5) = 60$, while $2 + 3 + 4 + 5 = 14$ is still less than the original $16$. Now we could throw away the $2$-cycle for a cycle-decomposition of $3 + 4 + 5 = 12$ for an element of order $60$.

But a cycle-decomposition in $S_{16}$ that takes the cake? That would be $4 + 5 + 7 = 16$, which would yield a permutation of order $\operatorname{lcm}(4, 5, 7) = 4\cdot 5 \cdot 7 = 140$. Note that since $4, 5,$ and $7$ are pairwise coprime, their least common multiple is just their product. Among all partitions of $16$, it has the highest least common multiple (note that lots of permutations in $S_{16}$ have order $140$; any with the cycle-decomposition $4+5+7$.

Fact: Every permutation in $S_n$ can be written as a product of disjoint cycles.

As your theorem 1 states, if $\sigma = c_1 \dotsm c_k$ then its order is $\text{lcm}(l_1,\dotsc,l_k)$, with $l_i$ the length of $c_i$. So to maximise the order of $\sigma \in S_n$ you have to maximise $\text{lcm}(l_1,\dotsc,l_k)$.

Clearly if $c$ is a cycle disjoint from $\sigma$, then $o(c\sigma) \geq o(\sigma)$, so you should consider as many cycles as possible. Since they must be disjoint the sum of their lengths is bounded by $n$, thus you should consider only lengths with $l_1 + \dotsc + l_k = n$.

Finally, $\text{lcm}(l_1,\dotsc,l_k) \leq l_1 \dotsm l_k$, with equality if and only if $l_1,\dotsc,l_k$ are parwise coprime.

• There is a catch for the statement "you should consider only lengths with $\ell_1 + \cdots + \ell_k = n$". If one want to insists this, then for some $n$ (e.g $n = 22$), one also need to allow some $\ell_i$ equal to $1$. – achille hui Apr 11 '15 at 23:47
• @achillehui Yes, I was implicitly doing so and it doesn't seem so odd to me (though maybe it is). Thanks for pointing it out, though. – A.P. Apr 12 '15 at 10:08