0
$\begingroup$

I am aware that i have posted this question before, but the comments i received did not really help silly old me. So i would appreciate it if someone can walk me through some parts of the problem. I have revised my attempt from the previous post, accounting for the comments i have received as i understood them.

Let $n>1$ be a natural number. the m-cycle $\sigma=(a_1,a_2,a_3,\dots,a_m)$ denotes a permutation in $S_n$ where $\sigma(a_1)=a_2,\sigma(a_2)=a_3,\dots, \text{ and }\sigma(a_m)=a_1$.

Prove by induction on $k \geq 1$ that if $k+i\equiv j (mod\text{ m})$, then $\sigma^k(a_i)=a_j$ whenever $1\leq i \leq m$ and $1\leq j \leq m$.

Pained Attempt :

Let $n>1$ be a natural number. the m-cycle $\sigma=(a_1,a_2,a_3,\dots,a_m)$ denotes a permutation in $S_n$ where $\sigma(a_1)=a_2,\sigma(a_2)=a_3,\dots, \text{ and }\sigma(a_m)=a_1$.

[Base Step]

For the base case,$k=1$, assume that $1+i\equiv j (mod\text{ m})$ and prove that $\sigma^1(a_i)=a_j$ whenever $1\leq i \leq m$ and $1\leq j \leq m$.

Since $1+i\equiv j (mod\text{ m})$ then $j \equiv 1+i (mod\text{ m})$ and $m | j-(1+i)$ hence $j = mh+i+1$ for some $h \in \Bbb{Z}$.

[case:$1 \leq i \lt m$]

Since $j=mh+i+1$ then $a_j=a_{mh+i+1}$. By assumption $\sigma(a_{mh+i})=a_{mh+i+1}=a_j$.

I am not sure how to proceed further here..

I thought: With $1 \leq i \lt m$ and mh+i+1 being constrained to lie between 1 and m given the definition of the m-cycle, this implies that h must be 0 (?).Therefore $\sigma(a_{m(0)+i})=a_{m(0)+i+1}=a_j$ and $\sigma(a_{i})=a_{i+1}=a_j$ as required (?)

...this feels iffy.

[case: $i=m$]

Since $j=mh+i+1$ then $a_j=a_{mh+m+1}$ and $a_j=a_{m(h+1)+1}$ . By assumption $\sigma(a_{m(h+1)})=a_{m(h+1)+1}=a_j$.

I am not sure how to proceed further either..

Any help would be much appreciated.

$\endgroup$
  • 2
    $\begingroup$ When reposting a question, you should link to the old question. It's also good to be as specific as possible about what you didn't understand about the given responses. $\endgroup$ – Theo Bendit May 2 at 7:33
1
$\begingroup$

You are getting hung up on completely irrelevant details. Once you know $k$ and $i$, you know $j$. There's no need to delve into modular arithmetic and introduce new variables. Here's a complete proof of the base step:

Base case:

Let $k=1$ and let $1\leq i,j\leq m$ be such that $k+i\equiv j\pmod{m}$. We distinguish two cases:

  1. If $1\leq i<m$ then $1<k+i\leq m$ and so $j=k+i=1+i$. Then $\sigma^1(a_i)=\sigma(a_i)=a_{i+1}=a_j$.
  2. If $i=m$ then $k+i=m+1$ and so $j=1$. Then $\sigma^1(a_i)=\sigma(a_m)=a_1=a_j$.

Can you now prove the induction step?

$\endgroup$
  • 2
    $\begingroup$ You are given as the definition of $\sigma$ that $\sigma(a_m)(=\sigma^1(a_m))=a_1$. That step is where the modulo comes in. $\endgroup$ – Robert Shore May 2 at 8:15
  • 1
    $\begingroup$ @HalfAFoot Since $k=1$ and $i=m$, it is immediate from the definition that $$1+m\equiv j\pmod{m}.$$ Everything you wrote before that is completely irrelevant. Further, the implication $$m\mid(j-1)\quad\implies\quad m\leq(j-1),$$ is false. Instead simply note that $$1+m\equiv 1\pmod{m}\qquad\text{ so }\qquad j\equiv1\pmod{m}.$$ Because $1\leq j\leq m$ it follows that $j=1$. Do not focus on the modular arithmetic, it is just a formality here. $\endgroup$ – Servaes May 2 at 10:20
  • 1
    $\begingroup$ What do you mean by 'artificially choosing'? For any value of $x$ the congruence $$j\equiv x\pmod{m},$$ has a unique solution $j$ with $1\leq j\leq m$. For $x=1$ this is clearly $j=1$. $\endgroup$ – Servaes May 2 at 10:44
  • 1
    $\begingroup$ I do not understand your question. It should be more than obvious that $1+m\equiv1\pmod{m}$ by definition. $\endgroup$ – Servaes May 2 at 10:51
  • 1
    $\begingroup$ @Servaes, you are ofcourse right..! Thank you very much for walking me through this :) ...i did not realise your point about there being a unique solution j with 1<=j<=m..after flipping through my book the closest result i have found is : For each integer a there is exactly one integer r in the list 0,...,m-1 s.t. a is congruent to r (modulo m) or more precisely : 0<=r<m...Thanks again $\endgroup$ – HalfAFoot May 2 at 11:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.