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.