# 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$?

-
If n is coprime to q-1, then every element of K admits an n-th root in K, so that the polynomial $x^n$ is one-to-one. – damiano May 17 '10 at 13:44
Nice observation. So let us also remove the class of "stupid" examples obtained by composing (perhaps several times) affine bijections and powers coprime to $p-1$. – Roland Bacher May 17 '10 at 13:56
The group of affine bijections and the group $(\mathbb Z/(q-1)\mathbb Z)^*$ (acting as powers) generate probably the complete symmetric group of all permutations of all elements in the field. This, if true, yields almost an answer. – Roland Bacher May 17 '10 at 14:03
There seem to be some discussion on the subject of permutation polynomials in Ch. 7 of Lidl-Niederreiter‏ (books.google.com/…). [I hope I understood the question correctly. In the title shouldn’t $x\mapsto f(x)$ really be $c\mapsto f(c)$?] – user2734 May 17 '10 at 14:25
I would start with the work of Mike Zieve, who's thinking very actively about permutation polynomials. See e.g. front.math.ucdavis.edu/0810.2830 – JSE May 17 '10 at 14:36

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.

-

If $q$ is a prime, not dividing $p^2-1$, then $q$-th Dickson's polynomial will permute the field of $p$ elements.

-

For permutation polynomials, you can also look into the relevant part of "Finite fields", by Rudolf Lidl and Harald Niederreiter, CUP.

-