3
$\begingroup$

What is the largest order of an element in the group of permutations of $5$ objects?

Let $\sigma \in S_5$ be arbitrary. We know that $\sigma = \sigma_1...\sigma_k$, where the $\sigma_i$'s are disjoint cycles of some length. We want to maximize $|\sigma| = lcm(|\sigma_1|,...,|\sigma_k|)$, where $|\sigma_i|$ is the order of the permutation $\sigma_i$, which is just its length since it is a cycle. If any of the lengths are the same, then the lcm will be the same, so we may take each $\sigma_i$ to have a different length in our attempt to maximize $|\sigma|$. This leaves us with four different lengths (I am excluding $1$). Thus $\sigma = \sigma_1 ... \sigma_4$; however, as we shall see, it is not possible for $\sigma$ to be a product of 4 disjoint cycles if we are maximizing their lengths. If $\sigma_1$ is a 5-cycle, then none of the 5 numbers will appear in any of the other cycles, and so $\sigma = \sigma_1$ which implies $|\sigma| = 5$. If $\sigma_1$ is a 4-cycle, then 4 of the 5 numbers appear in it, leaving only number left $\sigma_1$ and none to ther others. But this would make $\sigma_2$ and the rest the identity, so that $\sigma = \sigma_1$. In this case $|\sigma| = 4$. Finally, if $\sigma_1$ is a 3-cycle, then $\sigma_2$ can have the rest of the numbers which makes it a 2-cycle. In this case, $|\sigma| = lcm(3,2) = 6$. By symmetry, the rest of the cases are equivalent, and so the maximum value is $6$.

How does that sound?

$\endgroup$
  • 3
    $\begingroup$ It's correct, but a little lengthy for me. $\endgroup$ – Bernard Sep 4 '17 at 10:21
  • $\begingroup$ Your logic appears to be correct. Good job! $\endgroup$ – JamesDixon Sep 4 '17 at 10:21
  • $\begingroup$ @Bernard Is it my writing that is lengthy or did I introduce unnecessary steps in my solution? Because if there is a more direct solution, I am interested in knowing it. $\endgroup$ – user193319 Sep 4 '17 at 10:31
  • 1
    $\begingroup$ For me, it's mainly your writing: some details ore obvious. Also, in $S_5$, if you don't write the $1$-cycles, a permutation is the product of at most two cycles, of orders $2,2$, or $2,3$. This observation should shorten the writing. $\endgroup$ – Bernard Sep 4 '17 at 10:41
3
$\begingroup$

You could be explicit and argue as follows:

The partitions of $5$ are $$\eqalign{ \mbox{type} & \to \mbox{lcm} \cr 5 & \to 5 \cr 4+1 & \to 4 \cr 3+2 & \to 6 \ * \cr 3+1+1 & \to 3 \cr 2+2+1 & \to 2 \cr 2+1+1+1 & \to 2 \cr 1+1+1+1+1 & \to 1 \cr }$$

$\endgroup$
0
$\begingroup$

Let $\sigma \in S_5$ be arbitrary. We know that $\sigma = \sigma_1...\sigma_k$, where the $\sigma_i$'s are disjoint cycles of some length. We want to maximize $|\sigma| = lcm(|\sigma_1|,...,|\sigma_k|)$, where $|\sigma_i|$ is the order of the permutation $\sigma_i$, which is just its length since it is a cycle. If any of the lengths are the same, then the lcm will be the same,

Ok so far.

so we may take each $\sigma_i$ to have a different length in our attempt to maximize $|\sigma|$.

Not quite: this says that we should only look at partitions of $5$ into distinct parts, but actually we want to only look at the distinct parts in partitions of $5$ (or equivalently, at partitions of integers up to $5$ into distinct parts). You sort-of get away with it for $S_5$, but not necessarily for all symmetric groups.

This leaves us with four different lengths (I am excluding $1$). Thus $\sigma = \sigma_1 ... \sigma_4$;

Huh? I suppose this could make sense if some of the $\sigma_i$ are cycles of zero elements, but that's not the standard cycle decomposition.

however, as we shall see, it is not possible for $\sigma$ to be a product of 4 disjoint cycles if we are maximizing their lengths.

Indeed. So it would have been more accurate to say that we only need consider partitions for which $k \le 4$. But that's just equivalent to saying that we don't need to consider the partition $1^5$ (or equivalently the identity element of the group); it suffices to observe that the identity element has order one, and in any group other than the trivial group all of the other elements have order greater than one.

If $\sigma_1$ is a 5-cycle, then none of the 5 numbers will appear in any of the other cycles, and so $\sigma = \sigma_1$ which implies $|\sigma| = 5$.

This should say that if $\sigma_1$ is a 5-cycle then $k=1$ so the LCM is just $\textrm{lcm}(5) = 5$.

If $\sigma_1$ is a 4-cycle, then 4 of the 5 numbers appear in it, leaving only number left $\sigma_1$ and none to ther others. But this would make $\sigma_2$ and the rest the identity, so that $\sigma = \sigma_1$. In this case $|\sigma| = 4$.

I've just realised that by "the 5 numbers" you meant the 5 elements which are permuted. There's an argument to be made that a permutation operates on ordinal numbers in the high-school English sense, moving the ith place to the jth place, but in the interests of clarity it's better to think of a permutation as operating on arbitrary "elements", which might be numbers but might not. Actually, the problem statement explictly talks about "permutations of five objects", so that's probably the best phrasing to use in your answer.

I can figure out the intended meaning of the first sentence here from the context, but even correcting the spelling, "leaving only number left $\sigma_1$ and none to the others" is not at all clear. What this should say is that if $\sigma_1$ is a 4-cycle, that uses 4 of the 5 objects, leaving only a 1-cycle as $\sigma_2$ and forcing $k=2$. Then the order is $\textrm{lcm}(4, 1) = 4$.

Finally, if $\sigma_1$ is a 3-cycle, then $\sigma_2$ can have the rest of the numbers which makes it a 2-cycle. In this case, $|\sigma| = lcm(3,2) = 6$.

Replace "numbers" with "objects" and this is better phrased than the earlier cases. But "Finally"? You haven't considered partitions as $3+1+1$, $2+2+1$, ...

By symmetry, the rest of the cases are equivalent, and so the maximum value is $6$.

Symmetry of what? I think that what you mean, and this would have been better stated at the top rather than at the bottom, is that without loss of generality we can assume that $|\sigma_1| \ge |\sigma_2| \ge \ldots \ge |\sigma_k|$.

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