2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Try to work out small examples, for $n=3,4,5$, to get a feeling for the theorem. $\endgroup$ – Nicky Hekster Apr 11 '15 at 21:37
  • $\begingroup$ Try the advice in meta.math.stackexchange.com/q/5020/139123 to make this question easier to read. $\endgroup$ – David K Apr 11 '15 at 21:41
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 11 '15 at 21:55
  • $\begingroup$ @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 $\endgroup$ – Ross Millikan Apr 11 '15 at 21:58
  • $\begingroup$ @RossMillikan strange, let me try that again. $\endgroup$ – achille hui Apr 11 '15 at 22:02
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – achille hui Apr 11 '15 at 23:47
  • $\begingroup$ @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. $\endgroup$ – A.P. Apr 12 '15 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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