4
$\begingroup$

The only solution would be going through all cycle types of all permutations which is a lot of work. Is there any smarter solution than this one?

Thank you in advance!

$\endgroup$
  • $\begingroup$ Looks like a duplicate of this. Anyway Landau's function is what you want. Not voting to close, in case there are smart tricks for settling this specific case. $\endgroup$ – Jyrki Lahtonen Apr 12 at 15:05
  • $\begingroup$ @JyrkiLahtonen Oh, I see what you mean. What the OP thought was "a lot of work" was what I thought was already very economical. $\endgroup$ – rschwieb Apr 12 at 17:54
  • $\begingroup$ Please check out this entry: math.stackexchange.com/questions/221211/… $\endgroup$ – Nicky Hekster Apr 12 at 18:16
4
$\begingroup$

The maximum order of an element of $S_n$ is assumed for a permutation which is a product of cycles of distinct lengths. So in stead of considering all cycle types, you only need to consider the cycle types $$(1,2,4),\qquad (1,6),\qquad(2,5),\qquad(3,4),\qquad(7),$$ which quickly shows that the maximum order is $12$.

In fact more is true; the maximum is assumed for a cycle type of which the entries are pairwise coprime prime powers, where $1$ also counts as a prime power. This leaves only the latter three cycle types above, and for larger symmetric groups this reduces the number of cycle types to check significantly. This is harder to prove though.

Edit: To clarify, the sequences above are not cycles in $S_7$, but cycle types of elements of $S_7$. For example, the cycle type of $(2\ 3)(4\ 5\ 6\ 7)\in S_7$ is $(1,2,4)$, because it is the product of a $1$-cycle, a $2$-cycle and a $4$-cycle.

$\endgroup$
  • 4
    $\begingroup$ Triviality: you need to consider $(7)$ as well. $\endgroup$ – ancientmathematician Apr 12 at 16:04
  • 1
    $\begingroup$ @Servaes: Could you please explain me why I do not have to consider, for instance, the cycle type $(2,2,3)$? How can I deduce this case from you cases? $\endgroup$ – Diglett Apr 12 at 16:34
  • $\begingroup$ @ancientmathematician You are very right. $\endgroup$ – Inactive - Objecting Extremism Apr 12 at 16:52
  • 2
    $\begingroup$ @Diglett If two cycles have the same length, you can replace them by one cycle of twice the length, and the order will not decrease. In your example $\operatorname{lcm}\{2,2,3\}\leq\operatorname{lcm}\{4,3\}$. $\endgroup$ – Inactive - Objecting Extremism Apr 12 at 16:53
  • 1
    $\begingroup$ What does "type" mean here? 3 and 1 cycles I get... but why are there three random 2-cycles? I think i'm probably just missing something simple, but what eliminates 4-5-6-7 cycles at the start (besides inspection?) $\endgroup$ – rschwieb Apr 12 at 17:46

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.