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

• 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. 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$. 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. 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)$?] 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.

• Shortly after the Fried-Guralnick-Saxl result was announced, Lenstra produced a very short and simple proof of the Carlitz conjecture. Lenstra's own beautiful exposition of his proof is in his 1999 MSRI talk msri.org/workshops/131/schedules/25415 However, the much more difficult Fried-Guralnick-Saxl paper also proved a great deal more than just the Carlitz conjecture, and their paper opened up the possibility of determining all permutation polynomials over $\mathbb F_q$ of degree at most $q^{1/4}$, for any $q$. Aug 23 at 20:51

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:

1. 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.

2. 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\frac{x^q-x}{x-\alpha}$$ 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$$, etc., yielding the answers one would have naively expected.

3. 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"uller (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.

4. 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{q}$$. But to date there is no known example of a non-exceptional permutation polynomial over $$\mathbb F_q$$ of degree less than $$\sqrt{q}$$, for any $$q$$.

5. 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$$.

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.

• That book gives an excellent synopsis of pre-1970 content, but there have been so many developments in the past 50 years that nowadays one would want to supplement that reference with something more modern. Aug 23 at 20:39
• @MichaelZieve : agreed. Thanks a lot for your late and very informative answer to the OP's question. Aug 25 at 4:16