Degrees of some permutation polynomials

Let $\F_q$ be a finite field. For any function $f:\F_q\to \F_q$, there exists a polynomial $p\in \F_q[x]$ such that $f(a) = p(a)$ for all $a\in \F_q$. In other words, every function from a finite field to itself can be represented by a polynomial.

In particular, every permutation of $\F_q$ can be represented by a polynomial. This isn’t true for other finite rings, a fact which is the topic of one of my papers. At any rate, polynomials that represent permutations are called permutation polynomials.

It’s not easy to determine which polynomials are permutation polynomials. The exception is for the finite field $\F_2$, and more generally $\Z/2^w$. Then this case Ronald Rivest gave a straightforward criterion for whether a polynomial is a permutation polynomial.

However, there is a classical result that says any permutation may be represented uniquely by a polynomial whose degree is at most $q-2$. Here is an example noted by Charles Wells. Let $a,b\in\F_q$ be two distinct elements. The polynomial
$$f(x) = x + (a-b)(x-a)^{q-1} + (b-a)(x-b)^{q-1}$$
represents the transposition of $a$ and $b$. I suggest that you verify this by direct substitution, using the identity $c^{q-1} =1$ whenever $c\not=0$, which in turn follows from Fermat’s little theorem.
More »

All set endomorphisms of a finite field are polynomial

Posted by Jason Polak on 03. October 2017 · Write a comment · Categories: elementary · Tags: , ,

Let $F$ be a finite field. Did you know that given any function $\varphi:F\to F$, there exists a polynomial $p\in F[x]$ such that $\varphi(a) = p(a)$ for all $a\in F$? It’s not hard to produce such the required polynomial:
$$p(x) = \sum_{a\in F} \left( \varphi(a)\prod_{b\not= a}(x – b)\prod_{b\not=a}(a-b)^{-1} \prod \right)$$
This works because every nonzero element of $F$ is not a zerodivisor.

The same cannot be said of infinite fields. If $F$ is infinite, then there are functions $\varphi:F\to F$ that cannot be represented as polynomials. That’s because the cardinality of $F[x]$ is the same as that of $F$ when $F$ is infinite. However, the number of functions $F\to F$ is greater than the cardinality of $F$. Therefore, there simply aren’t enough polynomials.

But, one does not have to go to infinite fields. For any prime $q$, there are functions $\Z/q^2\to \Z/q^2$ that cannot be represented as a polynomial. This is true because if $\varphi$ is a polynomial function, then $\varphi(x + q)\equiv \varphi(x)$ modulo $q$. Therefore, any of the $q^{q-2}$ functions $\varphi:\Z/q^2\to\Z/q^2$ satisfying $\varphi(0) = 0$ and $\varphi(q) = 1$ cannot be represented by polynomial.