Given $n \ge 3$ and $2 \le r \le n$, let's define the permutation $\rho \in S_n$ (the symmetric group of degree $n$) by:

  • $\rho(k)=k+1$, for $k \in I_<:=\lbrace 1,...,r-1 \rbrace$
  • $\rho(r)=1$
  • $\rho(k)=k$, for $k\in I_>:=\lbrace r+1,...,n \rbrace$

I've thought to prove that $\rho^r=\iota_{S_n}$ -the identical permutation- in the following manner (reductio ad absurdum). Could you double check if the proof is correct, please?

Proof. Let's suppose that $\rho^r \ne \iota_{S_n}$; then, $\exists \tilde k \in I:=\lbrace 1,...,n \rbrace$, such that $\rho^r(\tilde k)=\rho(\rho^{r-1}(\tilde k)) \ne \tilde k$. By the very same definition of $\rho$, it follows that $\rho^{r-1}(\tilde k) \in I_<^*:=\lbrace 1,...,r-1 \rbrace \cup \lbrace r \rbrace$. Now, let's assume that $\rho^j(\tilde k) \in I_<^*$ for some $0 \le j \le r-2$ (inductive hypothesis); then $\rho^{j-1}(\tilde k)=\rho^{-1}(\rho^j(\tilde k)) \in I_<^*$, because the restriction $\rho_{|I_<^*}$ is a bijection of $I_<^*$ into itself; so, finally, $\rho^j(\tilde k) \in I_<^*$ $\forall j=0,\dots,r-1$. This means that $\tilde k+j \in I_<^*$, $\forall j=0,\dots,r-1$, which in its turn implies $\tilde k=1$: contradiction, because by definition of $\rho$, it is $\rho^r(1)=1$.

  • $\begingroup$ "This means that $\tilde k+j \in I_<^*$, $\forall j=0,\dots,r-1$," Why? If you have intermediate claims, it makes sense to delimit them (and their proofs) clearly, particularly when you are trying to formalize the proof. $\endgroup$ – darij grinberg Nov 20 '18 at 4:04
  • $\begingroup$ @darij grinberg - You're right, that conclusion is undue, and frankly I'm stuck there. Any chance to conclude on that way? $\endgroup$ – Luca Nov 20 '18 at 14:55
  • $\begingroup$ A quick way is by proving (by induction) that $\rho^i \left(k\right) \in \left\{1,2,\ldots,r\right\}$ and $\rho^i \left(k\right) \equiv k+i \mod r$ for each $k \in \left\{1,2,\ldots,r\right\}$ $\endgroup$ – darij grinberg Nov 20 '18 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.