The order of a $k$-cycle in $S_n$ is $k$.

Question

Here's what I have right now:

---

The order of a $k$-cycle in $S_n$ is $k$.

Proof. Let $\sigma$ represent the $k$-cycle $$\sigma=(x_1 \ x_2 \ \cdots \ x_k)$$with distinct elements $x_i$. Note that the cycle of distinct $x_i$ implies $k \leq n$. There are two cases to consider: $k$ even and $k$ odd. Suppose $k$ is even. It follows that $$\sigma^2=(x_1 \ x_2 \ \cdots \ x_k)(x_1 \ x_2 \ \cdots \ x_k)=(x_1 \ x_3 \ \cdots \ x_{k-1})(x_2 \ x_4 \ \cdots \ x_k)$$ $$\sigma^3=(x_1 \ x_2 \ \cdots \ x_k)\left[(x_1 \ x_3 \ \cdots \ x_{k-1})(x_2 \ x_4 \ \cdots \ x_k) \right]$$ $$=(x_1 \ x_4 \ \cdots \ x_{k-2})(x_2 \ x_5 \ \cdots \ x_{k-1})(x_3 \ x_6 \ \cdots \ x_k).$$ Thus, we can construct the general formula as a product of disjoint cycles $$\sigma^j=\prod_{i=1}^{j} (x_i \ x_{i+j} \ x_{i+2j}\ \cdots \ x_{k-j+i})$$ where $k$ is even. Now suppose $k$ is odd. Then $$\sigma^2=(x_1 \ x_2 \ \cdots \ x_k)(x_1 \ x_2 \ \cdots \ x_k)=(x_1 \ x_3 \ \cdots \ x_{k-2} \ x_k \ x_2 \ x_4 \ \cdots \ x_{k-1})$$ which differs from the case when $k$ is even. Interestingly, $$\sigma^3=(x_1 \ x_2 \ \cdots \ x_k)\left[(x_1 \ x_3 \ \cdots \ x_{k-2} \ x_k \ x_2 \ x_4 \ \cdots \ x_{k-1}) \right]$$ $$=(x_1 \ x_4 \ \cdots \ x_{k-2})(x_2 \ x_5 \ \cdots \ x_{k-1})(x_3 \ x_6 \ \cdots \ x_k)$$ which gives the same result as $k$ even. The reader can verify that all $\sigma^{j>2}$ are equal for $k$ even and $k$ odd. Thus, the general formula can be revised: $$\sigma^{j>2}=\prod_{i=1}^{j} (x_i \ x_{i+j} \ x_{i+2j} \ \cdots \ x_{k-j+i})$$ where $k>2$. For the case $k=2$, the $k$-cycle is a transposition which, by definition, has order 2. For the case $k=1$, the permutation is trivially the identity which has order 1. Thus, the theorem holds for $k=1,2$. For $k>2$, we know $$\sigma^{k}=\prod_{i=1}^{k} (x_i \ x_{i+k} \ x_{i+2k}\ \cdots \ x_{(k-k)+i}).$$ But for $n>0$ we see that $i+nk>k$ so it is not in the permutation. Thus, we simplify the above equation to $$\sigma^{k}=\prod_{i=1}^{k} (x_i)=e$$ We conclude that the order of a $k$-cycle in $S_n$ is $k$. QED.

---

The glaring problem seems to be my poor construction of the general case$$\sigma^{j>2}=\prod_{i=1}^{j} (x_i \ x_{i+j} \ x_{i+2j}\ \cdots \ x_{k-j+i})$$ which I considered replacing with$$\sigma^{j>2}=\prod_{i=1}^{j} (x_{i \bmod{j}})$$ but then I thought using this form is just as unenlightening as my original representation. I am just trying to convey that each disjoint cycle can only contain the elements $x_{i\leq k}$. A problem with using the $(x_{i \bmod{j}})$ notation is that we can run into a problem where elements of the form $x_{k<i\leq n}$ start appearing. Can you offer an elegant solution to this?

Also, I would appreciate advice on improving vague statements like this: "But for $n>0$ we see that $i+nk>k$ so it is not in the permutation." There are several lame statements like that in my proof that I just couldn't improve. I need help rewriting this proof in the most clear and concise manner.

Thank you!

Answer 1

Unfortunately, I can't quite grasp where $i + nk$ is coming from, as I thought we were manipulating subscripts modulo $k$. If subscripts are computed modulo $k$, then the cycle $(x_i, x_{i + k}, \ldots, x_{i + (k-k)})$ must be the 1-cycle $(x_i)$, since $i \equiv_k i + k$. In this case, you can conclude that $\sigma^k = e$, without mentioning $i + nk$.

You had me up to there, but I'm just not sure how you bring it all together. You definitely figured out a lot about the structure of $\sigma^m$, which means there's a more direct route find the order of the $k$-cycle $\sigma$.

Personally, I would use the fact that your permutation $\sigma = (x_1 x_2 \ldots x_k)$ is in the symmetric group $S_n$, which acts on the set $[n] = \{1, 2, \ldots, n\}$.

So, we could show that if we apply the map $\sigma: [n] \to [n]$ exactly $k$ times to any $i \in [n]$, then we wind up back at $i$; that is, $\sigma^k(i) = i$, and that $\sigma^m \neq e$ when $m < k$ and $k > 1$.

For $i \notin \{x_1, \ldots, x_k\}$, $\sigma^k(i)$ is clearly $i$, since $\sigma(i) = i$.

Otherwise, we know that $\sigma(x_j) = x_{j+1}$, with subscripts computed mod $k$, as you pointed out. It follows that $\sigma^m(x_i) = x_{i + m}$, which will be $x_i$ only when $m = k$, since the subscripts are computed mod $k$ and $x_i \neq x_j$ whenever $i \not\equiv_k j$