Degrees of a polynomial $p$ such that $x\mapsto p(x)$ is one-to-one 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$?
 A: I only saw this a decade late, but just to record answers to these questions in case someone else comes across this post in the future:

*

*The only degree-3 examples are as follows, up to composing on both sides with degree-$1$ polynomials: $x^3$ with $q\not\equiv 1\pmod{3}$, and $x^3-cx$ with $3\mid q$ and $c$ a nonsquare in $\mathbb F_q$.  This was proved by Dickson in his 1896 Ph.D. thesis The analytic representations of substitutions on a power of a prime number of letters with a discussion of the linear group.


*Yes, the degrees are generically quite high.  As in the statement of the question, we could start with any of the $q!$ permutations $\pi$ of $\mathbb F_q$, and use Lagrange interpolation to produce a unique polynomial $f_\pi(x)$ of degree at most $q-1$ which acts on $\mathbb F_q$ as $\pi$.  If $q>2$ then $f_\pi(x)$ cannot actually have degree $q-1$, for instance because $f_\pi(x)=\sum_{\alpha\in\mathbb F_q} \pi(\alpha)\cdot\bigl(1-(x-\alpha)^{q-1}\bigr)$ and visibly the coefficient of $x^{q-1}$ is $-\sum_{\alpha\in\mathbb F_q}\pi(\alpha)$, which equals $-\sum_{\alpha\in\mathbb F_q} \alpha$ since $\pi$ is a permutation, and finally this last summation equals $0$ when $q>2$.  However, most choices of $\pi$ do yield polynomials $f_\pi(x)$ of degree very close to $q$.  Specifically, Konyagin and Pappalardi proved in 2002 (Enumerating permutation polynomials over finite fields by degree) that the number $N$ of permutation polynomials of degree less than $q-2$ satisfies
$$\lvert N-(q-1)!\rvert\le\sqrt{2e/\pi}q^{q/2}.$$
So roughly $(q-1)/q$ of the $q!$ permutations $\pi$ yield permutation polynomials $f_\pi(x)$ having degree $q-2$, and roughly $1/q$ of the $\pi$'s yield lower-degree $f_\pi$'s.  Note that this is what one would naïvely expect if the coefficient of $x^{q-2}$ in $f_\pi(x)$ were randomly distributed among elements of $\mathbb F_q$.  In a 2006 followup paper (Enumerating permutation polynomials over finite fields by degree II), Konyagin and Pappalardi extended their result to degrees $q-3$, $q-4$, ..., $0.96017q$, yielding the answers one would have naïvely expected.


*It is known that if a permutation polynomial $f(x)\in\mathbb F_q[x]$ has degree $n$, where $n\le q^{1/4}$, then $f(x)$ has the very unusual property that there are infinitely many $k$ for which $f(x)$ permutes $\mathbb F_{q^k}$ (see Rem. 8.4.20 of this paper).  Polynomials with the latter property are called "exceptional".  I interpret this $n\le q^{1/4}$ result as suggesting that, since exceptionality seems very unlikely to ever happen "at random", therefore any permutation polynomial of degree at most $q^{1/4}$ should have a good causal reason for existing.  There are partial classification results for exceptional polynomials: for instance, it is known that the exceptional polynomials with degree coprime to $q$ are precisely the compositions of degree-one polynomials, $x^r$ with $\gcd(r,q^2-q)=1$, and degree-$r$ Dickson polynomials with $\gcd(r,q^3-q)=1$ (Dickson polynomials are defined by the functional equation $f(x+a/x)=x^r+(a/x)^r$ for some $a\in\mathbb F_q^*$; in characteristic not $2$ they are quadratic twists of Chebyshev polynomials) -- this was shown in a hard-to-find 1975 paper by Klyachko (Monodromy groups of polynomial mappings, in Russian, pp. 82-91 of vol. 6 of "Studies in Number Theory", Izdat. Saratov. Univ., Saratov, 1975), and also in the appendix of a 1997 paper by Müller
(A Weil-bound free proof of Schur's conjecture).
More generally, any exceptional polynomial of degree at least $2$ can be written as the composition of indecomposable exceptional polynomials, meaning polynomials which cannot be written as compositions of lower-degree polynomials in $\mathbb F_q[x]$.  There are only a few known families of indecomposable exceptional polynomials, and it is known that any as-yet-unknown example would have degree $p^k$ where $k\ge 4$ and $p:=\operatorname{char}(\mathbb F_q)$; but it is not expected that there actually exist any as-yet-unknown examples.
The known examples are listed in my brief survey paper
Exceptional polynomials.


*It is unknown whether the bound $n\le q^{1/4}$ in item 3 can be improved substantially.  This is especially interesting when $q$ is a prime $p$, where it is unknown whether every permutation polynomial over $\mathbb F_p$ of degree less than $p/(2\log p)$ must be exceptional, and hence (by Klyachko's result mentioned in item 3) must be a composition of degree-one polynomials, polynomials of the form $x^r$, and Dickson polynomials.  (The bound $p/(2\log p)$ is natural to consider because that is roughly the value at which naïve heuristics would predict that at random there would not exist any permutation polynomials with degree below that bound.)  When $q$ is a square, there are various constructions of non-exceptional permutation polynomials over $\mathbb F_q$ of degree roughly $\sqrt{q}$.  For some infinite classes of $q$'s, there are constructions of non-exceptional permutation polynomials of degree roughly $\sqrt[3]{q}$.  But to date there is no known example of a non-exceptional permutation polynomial over $\mathbb F_q$ of degree less than $\sqrt[3]{q}$, for any $q$.


*Roland Bacher mentioned in a comment that the affine bijections and the power permutations $x^n$ probably generate all permutations of $\mathbb F_q$.  That is true — in fact, Carlitz showed in 1953 that if $q>2$ then all permutations are generated by the permutations of the form $ax+b$ and $x^{q-2}$ (Permutations in a finite field).  But I don't think this says much about degrees of permutation polynomials, since compositions of several copies of $ax+b$ and $x^{q-2}$ typically have huge degree with loads of terms, and it's hard to control the degrees of the polynomials you'll get by reducing these gigantic polynomials mod $x^q-x$.
A: If $q$ is a prime, not dividing $p^2-1$, then $q$-th Dickson's polynomial will permute the field of $p$ elements. 
A: 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 — 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
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.
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. Israel J. Math. 82 (1993), no. 1-3, 157–225.
A: For permutation polynomials, you can also look into the relevant part of "Finite fields", by Rudolf Lidl and Harald Niederreiter, CUP.
