# Permutations on $[2^k]$ And the Existance of Permutation Polynomials

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.

• This is clever! I didn't think of that. I am hoping that there are criteria that more characterizing, so the speak. Commented Aug 10, 2019 at 2:29

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$$.