When does the underlying map of a polynomial induce a permutation on $\mathbb{Z}/p\mathbb{Z}$?

Question

For example, the underlying function of the polynomial $$f(x)=4x^2-3x^7$$ induces a permutation on $\mathbb{Z}/11\mathbb{Z}$, though I only know the proof by "brutal force" (is there a cleverer proof?).

In general, is there a criterion determining if a polynomial $f(x)$ induces a permutation on $\mathbb{Z}/p\mathbb{Z}$?

Edit: I am not even sure if it matters whether $p$ is prime or not but I will tag this question "finite fields" for now. Does it matter?

Answer 1

Such polynomials are called permutation polynomials. There is a lot of literature on this, a starting point can be the Wikipedia article.

For a finite field $F_q$, one does not have to check all possible values. There is a polynomial-time algorithm known to check whether a given rational function (hence in particular polynomial) induces a permutation, see e.g. Recognizing permutation functions in polynomial time, Neeraj Kayal.

Answer 2

Wikipedia has the answer:

Let $\mathbb F_q$ be a finite field of characteristic $p$. Then $f \in \mathbb F_q[x]$ is a permutation polynomial iff $f$ has exactly one root in $\mathbb F_q$ and for each integer $t$ with $1 \le t \le q-2$ and $t\not\equiv 0 \bmod p$, the degree of $f(x)^t \bmod (x^q-x)$ is at most $q-2$.

This is known as Hermite's criterion.

See also these surveys:

• Permutation polynomials over finite fields — A survey of recent advances (2015)

• Permutation polynomials of finite fields (2012)