Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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$. –  Jeremy Nov 7 '12 at 3:38

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
No my question is do they expect you to come up with your own cycles? –  sidht Nov 7 '12 at 3:35
    
They do, but it's easy to do that. –  MJD Nov 7 '12 at 3:36
    
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. –  sidht Nov 7 '12 at 3:37
2  
Work out some small cases and you'll start to see how to shortcut the big cases. Try $S_4$, then $S_5$. –  MJD Nov 7 '12 at 3:58
1  
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? –  MJD Nov 7 '12 at 4:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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