$n$-cycles and repeated elements

Question

Suppose the cycle $(i \ \sigma(i) \ \sigma^2(i)\ \dots \ \sigma^n(i))$ does not have repeated elements, but the cycle $(i \ \sigma(i) \ \sigma^2(i) \ \dots \ \sigma^{n+1}(i))$ does have repeated elements. The problem is to find $\sigma^{n+1}(i)$.

The first list can be decomposed into a product of transpositions, whereas it looks like the second list cannot. The element $\sigma^{n+1}$ has to be one of the elements $\sigma^{k}$ for some $1\leq k \leq n$, but the problem seems too vague to actually determine what that element is.

I'd like some hints.

Answer 1

Hint: Look at an explicit example. Let $\sigma = (1\,2\,3\,4\,5)$, the cycle that maps $1 \mapsto 2 \mapsto 3 \mapsto 4 \mapsto 5 \mapsto 1$. Say $i=1$, and look at the finite sequence $\{\sigma^k(i)\}$ for $0 \leq i \leq 4$: $$ \{1, 2, 3, 4, 5\}, $$ so with $n=4$, the orbit consists of distinct elements. But the next power wraps the cycle back around: with $n+1 = 5$, we have $\sigma^5(1) = 1$, and this already belongs to the orbit.

Now, convince yourself that

• there's nothing special about the starting seed $1$
• there's nothing special about this particular $5$-cycle
• there's nothing special about the number $5$

In other words, we can conjecture:

Claim. For any cycle of length $n+1$ including $i$, numbers $\{i, \sigma(i), \dots, \sigma^n(i)\}$ are distinct and $\sigma^{n+1}(i) = i$.

But why? (Try it yourself before revealing.)

If there's a repeat, then as you've noted, $\sigma^{n+1}(i) = \sigma^k(i)$ for some $0 \leq k \leq n$. So it remains to show that $k = 0$, i.e. $\sigma^{n+1}(i) = \sigma^0(i) = i$. Suppose, towards a contradiction that $k \geq 1$. Then, applying the inverse $\sigma^{-1}$ to the equation $\sigma^{n+1}(i) = \sigma^k(i)$ yields $\sigma^{n}(i) = \sigma^{k-1}(i)$, where $k - 1 \geq 0$, and now the list $\{1, \sigma(i), \dots \sigma^n\}$ has repeats, contradicting the fact that they are distinct.