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?
Best Answer
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$.