Fix $k \geq 2$ and let $[n]$ denote the set $\{0, 1, \ldots, n-1\}$. A polynomial $p(x) = \sum_{i=0}^d a_i x^i$ with integer coefficients in $[2^k]$ is a permutation polynomial modulo $2^k$ if $p(x) \mod 2^k$ permutes the elements of $[2^k]$. It is known (due to Rivest) that $p(x)$ is a permutation polynomial modulo $2^k$ if and only if $a_1$ is odd and $\Delta_1$ and $\Delta_2$ are even, where $\Delta_1 = a_2 + a_4 + \ldots$ and $\Delta_2 = a_3 + a_5 + \ldots$.

I am interested in the opposite question. In particular, given a permutation $\pi: [2^k] \to [2^k]$, under what conditions does there exist a permutation polynomial $p$ modulo $2^k$ such that $p$ and $\pi$ produce the same permutation? I suspect that there are permutations that have no such polynomial, but I haven't been able to find or construct a class of examples.


A class of permutations that cannot be constructed is where $\pi(0)$ and $\pi(1)$ are both even based on Rivest's criterion.

First note that $x \bmod 2^k$ is even iff $x$ is even.

If $\pi(0)$ is even we find that $a_0$ must also be even as $p(0) = a_0$.

If $\pi(1)$ is also even we find that $\sum_i a_i$ must be even as $p(1) = \sum_i a_i$.

Rivest's criterion tells us that $\Delta_1$ and $\Delta_2$ are even, thus $\sum_{i\geq2}a_i$ is even.

But this leads to an impossibility. $a_0$ and $\sum_{i\geq2}a_i$ are even, but $a_1$ must be odd due to Rivest's criterion, thus $p(1) = \sum_i a_i$ can't be even.

  • $\begingroup$ This is clever! I didn't think of that. I am hoping that there are criteria that more characterizing, so the speak. $\endgroup$ – user340082710 Aug 10 at 2:29

This answer is partial.

Fix any natural $k$. Let $S_k$ be the group of all permutations of the set $[2^k]$. A permutation $\pi\in S_k$ is representable, if there exists a polynomial $p\in \Bbb Z[x]$ which represents $\pi$, that is $p(x)\equiv \pi(x)\pmod {2^k}$ for each $x\in [2^k]$. Let $G_k$ be a set of all representable permutations of $S_k$. Let $\pi,\sigma\in G_k$ be permutations represented by polynomials $p,q\in \Bbb Z[x]$, respectively. Then $p(q(x))\equiv \pi(\sigma(x))\pmod {2^k}$ for each $x\in [2^k]$, thus $\pi\sigma\in G_k$. Therefore $G_k$ is a semigroup of a finite group $S_k$, so it is a group.

Put $G^0_k=\{\pi\in G_k:\pi(0)=0\}$. Let $\pi_1\in G_k$ be a permutation of $[2^k]$ such that $\pi_1(x)\equiv x+1\pmod {2^k}$ for each $x\in [2^k]$ and $C$ be a cyclic group of order $2^k$ generated by the map $\pi$. Since for each permutation $\pi\in G_k$ we have $\pi_1^{-\pi(0)}\pi(0)=0$, we have $\pi_1^{-\pi(0)}\pi\in G^0_k$, $G_k=CG^0_k$, so it suffices to describe the group $G^0_k$.

For each natural $l\le k$ put $X_l=\{0,2^l, 2\cdot 2^l,\dots, 2^k-2^l\}\subset [2^k]$. Let $\pi\in G^0_k$ be any permutation. It is easy to check that $\pi(X_l)\subset X_l$ for each $l$. Since $\pi$ is a bijection, we have $\pi(X_l)=X_l$ for each $l$.


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.