Let $n=2m$. What is the order of the following permutation $\sigma$?

$$1\leq k\leq m \Rightarrow \sigma(k)=2k , \quad \sigma(m+k)=2k-1$$

  • $\begingroup$ Could you share your data for small $m$? $\endgroup$
    – LSpice
    Feb 17 at 18:06
  • $\begingroup$ There is only one guess: if $n=2^m$ then $|\sigma|=2^m$ (have no clear proof yet!) $\endgroup$
    – ABB
    Feb 17 at 18:19
  • $\begingroup$ If one may check by computer, a mysterious irregularity is observed for different cases $n$ $\endgroup$
    – ABB
    Feb 17 at 18:21
  • $\begingroup$ Aside from a guess, presumably you have gathered data on specific values of small $m$. (If not, then that's where you should start!) What irregularity have you observed? $\endgroup$
    – LSpice
    Feb 17 at 19:12
  • $\begingroup$ @ABB is not $|\sigma|=2m$ for $n=2^m$? $\endgroup$ Feb 17 at 20:19

1 Answer 1


By adding a fixed point at $0$ (which preserves the order), the permutation $\sigma$ considered is just the multiplication by $2$ modulo $2m+1$. Thus, for $k \ge 0$, $\sigma^k$ is the identity map if and only if it fixes $1$, namely if and only if $2m+1$ divides $2^k-1$.

Hence, the order of $\sigma$ is the order of $2$ in $(\mathbb{Z}/(2m+1)\mathbb{Z})^\times$. I do not think that there are formulas for this, although the order necessarily divides $\phi(2m+1)$ by Lagrange theorem.

  • $\begingroup$ I wonder if this was what OP was actually interested in, but ABB reformulated it to a permutation type question.. $\endgroup$ Feb 18 at 7:18
  • $\begingroup$ @Per Alexandersson, Yes, you are right. If this problem could be figured out, then probably one may find an approach to compute the eigenvalues/eigenvectors of some non-symmetric discrete trigonometric transforms which are coming from signal processing in electrical engineering! $\endgroup$
    – ABB
    Feb 18 at 9:01
  • $\begingroup$ In more detail, this reduces to the case when $2m+1$ is a prime $p$, since the order of $2$ modulo $p^\nu$ is $p^{\nu-1}$ times the order of $2$ modulo $p$, while the order of $2$ modulo $mn$ for $m$, $n$ coprime is the lcm of orders modulo $m$ and $n$. $\endgroup$ Feb 23 at 5:56
  • 1
    $\begingroup$ @მამუკაჯიბლაძე Is it easy to prove that the order of 2 modulo $p^\nu$ is $p^{\nu-1}$ times the order of 2 modulo $p$? I am a bit surprised by this statement. $\endgroup$ Feb 23 at 17:11
  • 1
    $\begingroup$ Sorry, this is not actually true. The smallest counterexample I found is this: order of $2$ modulo $1093$ is the same as order of $2$ modulo $1093^2$, namely $364$. For a proof that once the order of some $1<a<p$ modulo $p^k$ is divisible by $p$ then order of $a$ modulo $p^{k+1}$ is $p$ times order of $a$ modulo $p^k$, see math.stackexchange.com/a/2217138/214353 It seems also true that these orders remain the same before becoming divisible by $p$. The smallest example when order modulo $p^3$ is not divisible by $p$ seems to be $p=113$, $a=68$. $\endgroup$ Feb 24 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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