Let $n = 2^k$, let $[n] = \{0, \ldots, n-1\}$, and let $f: [n] \to [n]$ denote a function of the form $f(x) := p(x) \mod n$, where $p(x)$ is some polynomial with coefficients in $[n]$. Does $f(x)$ have a well-known name? Moreover, I would like to know a reference that characterizes when $f(x)$ is an odd permutation (i.e. something like $f(x)$ is an odd permutation if and only if something about $p(x)$)? What about the case when we don't require $p(x)$ to be a polynomial, but rather some arbitrary other function?
After some more research, I found the following result (due to Rivest) that characterizes when $f(x)$ is a permutation polynomial: Fix $k \geq 2$. A polynomial $p(x) = a_0 + a_1x + \ldots + a_{d}x^{d}$ with integer coefficients is a permutation polynomial modulo $2^k$ if and only if: (1) $a_1$ is odd, (2) $(a_2 + a_4 + a_6 + \ldots)$ is even, and (3) $(a_3 + a_5 + a_7 + \ldots)$ is even -- See https://people.csail.mit.edu/rivest/pubs/Riv01c.pdf. I am interested in a similar result that characterizes when this permutation is odd.
References would be appreciated!
A partial answer. There does seem to be a pattern:
Being an odd number, the sum of the coefficients is either one more, or one less, than a multiple of four.
Consider the condition $n=2^2$. It seems that the parity of $P$ is determined by whether the sum of the coefficients is one more, or one less, than a multiple of 4.
Similarly, when $n=2^1$, the condition is whether the sum of the coefficients is one more, or one less, than a multiple of 2 (i.e. even or odd). But in fact every permutation polynomial is trivially even in this case: we assume the constant term is 0, so $P(0)=0$. The only way we can have a permutation of $\{0,1\}$ is if $P(1)=1$. Hence if $P$ is a permutation of $\{0,1\}$, then $P$ is the identity on $\{0,1\}$ and hence even.
The pattern apparently doesn't generalize exactly like this for higher $n$, but perhaps we can fashion a similar rule to prove by induction.
Another note: Permutation polynomials $P(x)$ with constant $a_0=0$ correspond to a very special subset of all permutations. Specifically, $P(x)$ always sends even numbers to even numbers and odd numbers to odd numbers— the permutation can be factored into a permutation on odd numbers and a permutation on even numbers. (Proof: if $z$ is even, then $z^k$ and $a_kz^k$ are even for $k>1$, so $P(z)$ is even. If $z$ is odd, then $a_kz^k$ has the same parity as $a_k$, so the parity of $P(z)$ is the parity of $\sum_{k=0}^d a_k$, which is odd because of Rivest's criteria.)
Here is a table for $n=8$. Each row is a permutation polynomial. The coefficients of the polynomial are listed first, in order $[a_0, \ldots, a_d]$. Then the set $[n]$ is listed (it's the same in every row). Then the permutation $P(n)$ is listed. The X and O values indicate (1) whether the permutation is even or odd (first X/O), and (2) whether the sum of the coefficients is one more or one less than a multiple of four (second X/O). The pairs go through periodic patterns of matching/difference, which suggests a slightly more complicated variation may capture the behavior.