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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

1
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 2010 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 2010 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 2010 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)$?] – unknown (google) May 17 2010 at 14:25

2
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 2010 at 14:36

## 3 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 30, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.912738025188446, "perplexity_flag": "head"}