# Show that the order of a cycle is the length of the cycle

## Homework Statement

Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \{1,2, \dots , m \}##, ##\sigma^i (a_k) = a_{k+i}##. Deduce that ##\sigma^m (a_k) = a_k##

## The Attempt at a Solution

I will try to do this by induction. Clearly, ##\sigma (a_k) = a_{k+1}##, as that is how ##\sigma## is defined. Now, suppose that for some ##n \in \mathbb{N}## ##\sigma^n (a_k) = a_{k+n}##. Then ##\sigma^{n+1} (a_k) = \sigma( \sigma^n (a_k) ) = \sigma (a_{k+n}) = \sigma_{a + k + 1} ##.

So I feel like I'm done, but I also feel that I've proved this statement for all ##i \in \mathbb{N}##, rather than for all ##i \in \{1,2, \dots , m \}##. How do I modify it to get it correct?

fresh_42
Mentor
2021 Award

## Homework Statement

Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \{1,2, \dots , m \}##, ##\sigma^i (a_k) = a_{k+i}##. Deduce that ##\sigma^m (a_k) = a_k##

## The Attempt at a Solution

I will try to do this by induction. Clearly, ##\sigma (a_k) = a_{k+1}##, as that is how ##\sigma## is defined. Now, suppose that for some ##n \in \mathbb{N}## ##\sigma^n (a_k) = a_{k+n}##. Then ##\sigma^{n+1} (a_k) = \sigma( \sigma^n (a_k) ) = \sigma (a_{k+n}) = \sigma_{a + k + 1} ##.

So I feel like I'm done, but I also feel that I've proved this statement for all ##i \in \mathbb{N}##, rather than for all ##i \in \{1,2, \dots , m \}##. How do I modify it to get it correct?
It is correct and you've proven it for all ##n \in \mathbb{N}##. However, the question is poorly worded. It should have been ##\sigma^i (a_k) = a_{k+i~\operatorname{mod}m}## since ##\sigma(a_m)=a_1## and not ##a_{m+1}##. Hence the induction basis is already wrong without the modulo on the index.

Mr Davis 97
It is correct and you've proven it for all ##n \in \mathbb{N}##. However, the question is poorly worded. It should have been ##\sigma^i (a_k) = a_{k+i~\operatorname{mod}m}## since ##\sigma(a_m)=a_1## and not ##a_{m+1}##. Hence the induction basis is already wrong without the modulo on the index.
I see what you mean. But I'm still a little confused. Why was my induction where ##i \in \mathbb{N}## valid if it is states that ##i \in \{1,2, \dots , m \}##?

fresh_42
Mentor
2021 Award
I see what you mean. But I'm still a little confused. Why was my induction where ##i \in \mathbb{N}## valid if it is states that ##i \in \{1,2, \dots , m \}##?
If it's true for all natural numbers, then it's true for a few of them. The restriction to ##1 \leq i \leq m## comes into play as we don't have other indices. The modulo solves this problem. There is simply no ##a_{m+1}## in our cycle, so ##a_{k+i}## doesn't make sense if it exceeds ##m##. To place a modulo ##m## behind the index is the shortest way of saying ##\in \{\,1,\ldots ,m\,\}##. It's simply a sloppiness by whoever has written the text. Your induction is equally wrong without the modulo, as in case ##i=1## and ##k=m## we have ##\sigma^1(a_m) \neq a_{m+1}##. And with the modulo, we only need the numbers up to ##m##.

If it's true for all natural numbers, then it's true for a few of them. The restriction to ##1 \leq i \leq m## comes into play as we don't have other indices. The modulo solves this problem. There is simply no ##a_{m+1}## in our cycle, so ##a_{k+i}## doesn't make sense if it exceeds ##m##. To place a modulo ##m## behind the index is the shortest way of saying ##\in \{\,1,\ldots ,m\,\}##. It's simply a sloppiness by whoever has written the text. Your induction is equally wrong without the modulo, as in case ##i=1## and ##k=m## we have ##\sigma^1(a_m) \neq a_{m+1}##. And with the modulo, we only need the numbers up to ##m##.
So would a less sloppy problem statement be

Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \mathbb{N}##, ##\sigma^i (a_{k \mod m}) = a_{k+i \mod m}##. Deduce that ##\sigma^m (a_{k \mod m}) = a_{k \mod m}## and so ##| \sigma | = m##.

fresh_42
Mentor
2021 Award
So would a less sloppy problem statement be

Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \mathbb{N}##, ##\sigma^i (a_{k \mod m}) = a_{k+i \mod m}##. Deduce that ##\sigma^m (a_{k \mod m}) = a_{k \mod m}## and so ##| \sigma | = m##.
Yes and no. Yes, because the index problem is solved, no because there is no need for the modulo in the notation as a variable of ##\sigma## since ##\sigma## is only defined modulo ##m##. To write ##\sigma^m (a_{k \mod m})## creates unnecessary confusion. But for the results, we have to make sure that the formula is defined! So the index of the result has to be wrapped around. For ##a_k## in the role of a variable, it has already been done the moment you wrote ##\sigma=(a_1,\ldots,a_m)##.

Mr Davis 97
Yes and no. Yes, because the index problem is solved, no because there is no need for the modulo in the notation as a variable of ##\sigma## since ##\sigma## is only defined modulo ##m##. To write ##\sigma^m (a_{k \mod m})## creates unnecessary confusion. But for the results, we have to make sure that the formula is defined! So the index of the result has to be wrapped around. For ##a_k## in the role of a variable, it has already been done the moment you wrote ##\sigma=(a_1,\ldots,a_m)##.
I think this is the last thing. What is the difference between the following two wordings of the question:

1) Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \{1,2, \dots , m \}##, ##\sigma^i (a_k) = a_{k+i}##, where ##k+i## is replaced by its least positive residue mod m.

2) Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \mathbb{N}##, ##\sigma^i (a_k) = a_{k+i}##, where ##k+i## is replaced by its least positive residue mod m.

fresh_42
Mentor
2021 Award
Formally: the second implies the first; within the context: none. As ##\sigma^m=1##, with this information the two are equivalent, because all other exponents, even the negative ones, can be reduced to the case ##1\leq i \leq m##.

Formally: the second implies the first; within the context: none. As ##\sigma^m=1##, with this information the two are equivalent, because all other exponents, even the negative ones, can be reduced to the case ##1\leq i \leq m##.
So if we were given problem statement 1), would the best thing be to prove 2) using induction and say clearly this implies 1 is true?

I ask this because it doesn't seem like you could do induction on ##i## formally if the variable isn't defined for all natural numbers.

fresh_42
Mentor
2021 Award
I ask this because it doesn't seem like you could do induction on ##i## formally if the variable isn't defined for all natural numbers.
But you did the induction on the exponent which is defined for all numbers!

But you did the induction on the exponent which is defined for all numbers!
Doesn't the original statement say that ##i## only varies from 1 to m?

fresh_42
Mentor
2021 Award
Doesn't the original statement say that ##i## only varies from 1 to m?
O.k. in this case, it isn't an induction, but an "and so on". Or you use the induction and show it for all ##n##. The "and so on" case goes with dots: Let ##i \in \{\,1,\ldots ,m\,\}##, then
$$\sigma^i(a_k)=\underbrace{\sigma(\sigma(\sigma(\ldots (\sigma}_{i \text{ times }}(a_k)\ldots )= \underbrace{\sigma(\sigma(\sigma(\ldots (\sigma}_{i-1 \text{ times }}(a_{k+1})\ldots )= \ldots = \underbrace{(\sigma)}_{1 \text{ times }}(a_{k+i-1})=a_{k+i}$$
but the induction is nicer and covers the ##i## stated as it covers all ##n \in \mathbb{N}_0##.

Mr Davis 97