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

[Mr Davis 97]

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$

Homework Equations

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]

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$

Homework Equations

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]

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

 

[Mr Davis 97]

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]

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]

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

 

[Mr Davis 97]

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]

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!

 

[Mr Davis 97]

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]

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