8
$\begingroup$

Find an element of largest order in the symmetric group $S_{10}$.

I know that given any element in $S_{10}$ there is a cycle decomposition and the order of it is the lcm of lengths of the cycles. So, we have to maximize $n_1.n_2....n_k$ so that $gcd(n_i, n_j)=1$ for $i\neq j$ and $n_1+n_2+...+n_k=10$. Moreover, $(n_1.n_2....n_k)|10!$. So, $n_1,...n_k$ must be a combination of some numbers of the set $\{1,2,...,10\}$. So how do I find that combination rigorously? Do I need to write all possibilities and decide?(I think there are many). Intuitively, I think the solution must be $2\times 3\times 5=30$. But how?

$\endgroup$
  • $\begingroup$ Note: if a number is not a prime power, we can rule it out as a possible length of a cycle. So, for example, we won't have a cycle of length $6$ because it's more efficient to have cycles length $2$ and $3$. Unfortunately, that only eliminates lengths $1,6,10$. $\endgroup$ – Omnomnomnom Dec 19 '15 at 5:28
  • $\begingroup$ No, that's genius, it makes it a lot easier to code. $\endgroup$ – Jorge Fernández Hidalgo Dec 19 '15 at 5:46
6
$\begingroup$

As you know the order is the least common multiple of the lengths of its cycle in its unique factorization into disjoint cycles.

We can break into cases depending of the largest length in the cycle decomposition:

If largest length is $10$ then max is $10$.

If largest length is $9$, then max is $9$.

If largest length is $8$ then max is $8$.

If largest length is $7$ then max is $21$ (since there is at most one other length greater than $1$, which can be $2$ or $3$)

If largest length is $6$ then max is $12$. If we have two other lengths larger than $1$ they must be $2$ and $2$. The other option is having just one other cycle of length greater than $1$, and the length can be $2,3$ or $4$. The max is reached with $4$ and is $12$.

If largest length is $5$ then max is $30$. Notice there can be at most two more cycles of length greater than $1$. And the options in this case are $2,3$ and $2,2$ ( out of these options max is $30$). The other option is having only one more cycle of length greater than $1$. And the options for this length are $2,3$ and $4$ (out of these options max is $20$).

If largest length is smaller than $5$ then the least common multiple is under $4\times3=12$.

Hence max is $30$.

$\endgroup$

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.