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$
$\endgroup$
5
-
$\begingroup$ Could you share your data for small $m$? $\endgroup$– LSpiceFeb 17, 2023 at 18:06
-
$\begingroup$ There is only one guess: if $n=2^m$ then $|\sigma|=2^m$ (have no clear proof yet!) $\endgroup$– ABBFeb 17, 2023 at 18:19
-
$\begingroup$ If one may check by computer, a mysterious irregularity is observed for different cases $n$ $\endgroup$– ABBFeb 17, 2023 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$– LSpiceFeb 17, 2023 at 19:12
-
$\begingroup$ @ABB is not $|\sigma|=2m$ for $n=2^m$? $\endgroup$– Fedor PetrovFeb 17, 2023 at 20:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
answered Feb 17, 2023 at 20:25
-
$\begingroup$ I wonder if this was what OP was actually interested in, but ABB reformulated it to a permutation type question.. $\endgroup$ Feb 18, 2023 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$– ABBFeb 18, 2023 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, 2023 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, 2023 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, 2023 at 6:19