14
$\begingroup$

This question already has an answer here:

Given the following groups, what is the maximum possible order for an element for

(a) $S_5$ (b) $S_6$ (c) $S_7$ (d) $S_{10}$ (e) $S_{15}$

My book justifies the answer as

(a) The greatest order is $6$ and comes from a product of disjoint cycles of length 2 and 3

(b) The greatest order is $6$ and comes from a cycle of length $6$

The other answers were justified exactly the same way, that is (c) 12, (d) 30, (e) 105

I do not understand how in (a) we even got the number "6" from $S_5$ and what disjoint cycles they are referring to. Could someone at least justify one for me?

$\endgroup$

marked as duplicate by José Carlos Santos, jgon, The Phenotype, ahulpke, Riccardo Jan 22 '18 at 19:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ The order of a product of disjoint cycles is the lcm of the order of the individual cycles which is where the 6 comes from. $\operatorname{lcm}(2,3)=6$ To get the max element, you want to max $\operatorname{lcm}(|\sigma_1||\sigma_2|\ldots|\sigma_n|)$ such that $\sum{|\sigma_i|}=n$ in $S_n$. $\endgroup$ – Jemmy Nov 7 '12 at 3:38
  • $\begingroup$ How we can finde individual cycles in $S_n$? $\endgroup$ – erfan soheil Jan 29 '15 at 16:31
  • $\begingroup$ See math.stackexchange.com/questions/221211/… $\endgroup$ – Gerry Myerson Oct 31 '17 at 4:16
11
$\begingroup$

You will have to write out the possible forms a given permutation (expressed as the product of disjoint cycles) can take, and then use the convenient fact that for disjoint cycles $\sigma_{1}, \dots, \sigma_{k} \in S_{n}$,

$$|\sigma_{1} \dots \sigma_{k}| = \textrm{lcm}(|\sigma_{1}|, \dots, |\sigma_{k}|).$$

For example, in $S_{5}$, you have (up to isomorphism) the following forms that a given permutation (written as the product of disjoint cycles) can take:

  1. $(1 2 3 4 5)$
  2. $(1 2 3)(4 5)$
  3. $(1 2 3 4)$
  4. $(1 2)(34)$
  5. $(1 2 3)$
  6. $(1 2)$

Then figure out which of the above forms will have the greatest order.

There is a sequence of values (of Landau's function, $g(n)$) that you can refer to for many values of $n$.

There is a known upper bound on the function:

$$g(n) < e^{n/e}.$$

A0000793: Landau's function g(n): largest order of permutation of n elements, Equivalently, largest lcm of partitions of n.

$\endgroup$
4
$\begingroup$

Consider the permutation $p = (1 2)(3 4 5)$. It is an element of $S_5$, but it has order 6. The "disjoint cycles" are $(1 2)$ and $(3 4 5)$, which have lengths of 2 and 3, respectively.

If you don't understand the "cycle notation" $(1 2)(3 4 5)$ leave a comment and I will explain further. The short version is that $(1 2)(3 4 5)$ is the permutation which sends $1\mapsto 2$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 5$, and $5\mapsto 3$.

$\endgroup$
  • $\begingroup$ No my question is do they expect you to come up with your own cycles? $\endgroup$ – Hawk Nov 7 '12 at 3:35
  • $\begingroup$ They do, but it's easy to do that. $\endgroup$ – MJD Nov 7 '12 at 3:36
  • $\begingroup$ OKay maybe a better question would be, "what is the correct approach or thinking to solving to this problem?" instead of asking you to explain the solution to me. $\endgroup$ – Hawk Nov 7 '12 at 3:37
  • 2
    $\begingroup$ Work out some small cases and you'll start to see how to shortcut the big cases. Try $S_4$, then $S_5$. $\endgroup$ – MJD Nov 7 '12 at 3:58
  • 1
    $\begingroup$ I don't know where you got that from. I said if you work out some small cases you'll start to see how to shortcut the big cases. How could that be true if there was no shortcut? $\endgroup$ – MJD Nov 7 '12 at 4:04

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