Given a finite field $K$, what are the possible degrees of a polynomial $p\in K[x]$ such that $x\longmapsto p(x)$ is one-to-one?


Such a polynomial has clearly not degree $0$ and it cannot be of degree two except for
$x\longmapsto (\alpha(x))^2$ for $\alpha$ an affine bijection of a field of characteristic $2$.


Are there many examples of degree $3$ (except for the stupid $x\longmapsto (\alpha(x))^3$
with $\alpha$ an affine bijection of a field of characteristic $3$)?


I guess that the degrees of such polynomials (except for affine bijections and their
composition with the Frobenius map)
are generically fairly high (the interpolation polynomial for a "random" permutation
of a finite field with $q$ elements should typically be of degree $q-1$).


What can for instance be said on the smallest degree $>1$ of a non-affine polynomial
inducing a bijection of $\mathbb Z/p\mathbb Z$?



Degrees of a polynomial $p$ such that $x\mapsto p(x)$ is one-to-one
Such things are referred to as ‘permutation polynomials’ and if you do a search, you'll find a whole menagerie of non-stupid classes which is constantly expanding. One simple result going back to Dickson provides something converse to damiano's [observation](https://mathoverflow.net/questions/25008/given-a-finite-field-k-what-are-the-possible-degrees-of-a-polynomial-p-in-k#comment52602_25008) — there are no (non-linear) permutation polynomials of degree dividing $q-1$.


Something backing up your guess that the degrees are 'generically' fairly high is a conjecture of Carlitz:
Fix even degree $n$, then the cardinality $q$ (with $q$ odd) of a field having a degree $n$ permutation polynomial is bounded from above.


This has been proved in cases for $n$ up to 14 by Dickson, Hayes and then Daqing Wan in [*On a conjecture of Carlitz*](https://doi.org/10.1017/S1446788700029657)
J. Austral. Math. Soc. Ser. A 43 (1987), no. 3, 375–384
but as far as I can tell, the general case is completely open.


Edit: a quick search provides more:


S. Cohen [*Permutation polynomials and primitive permutation groups.*](https://doi.org/10.1007/BF01246737)
Arch. Math. (Basel) 57 (1991), no. 5, 417–423


proves the above conjecture for $n\leq 1000$ and for n begin 2 times an odd prime.
And in fact the whole conjecture is implied by the result proved by Fried, Saxl and Guralnick in


[*Schur covers and Carlitz's conjecture.*](https://doi.org/10.1007/BF02808112) Israel J. Math. 82 (1993), no. 1-3, 157–225.


