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.

Wait, this is a polynomial of degree $q-1$ isn’t it? Where’s the promised degree at most $q-2$ polynomial? Well, if you look carefully you can rewrite it as

$$f(x) = x + (a-b)[ (x-a)^{q-1} – (x-b)^{q-1}].$$

Now it’s more apparent that upon expanding, the $x^{q-1}$ terms cancel. You should also check that the $x^{q-2}$ coefficient is nonzero. Therefore, the degree of this transposition polynomial is actually $q-2$.

Wells also proved that if $q\equiv 2\pmod{3}$, then every three cycle can be represented by a polynomial of degree $q-2$. But what if the requirement $q\equiv{2}\pmod{3}$ is not satisfied? Can we find a $q$ and a three cycle in $\F_q$ that is not represented by a polynomial of degree $q-2$? Counterexample time!

The first $q$ that comes to mind is $q = 3$. The only three cycles are $(0 1 2)$ and $(0 2 1)$. Of course, in this case, both actually can be represented by polynomials of degree $q – 2 = 1$. They are $x+1$ and $x+2$ respectively.

The next smallest $q$ is $q = 4$. In this case, there are eight three cycles. Can all of them be represented by polynomials of degree $q -2 = 2$? Actually, none of them can. Can you prove it? In fact, using the labeling $[0,1,x,1+x]\to [1,2,3,4]$, the permutations that can be represented by quadratic polynomials in $\F_4$ are exactly the following:

- (2,3)
- (2,4)
- (1,3)
- (1,4)
- (3,4)
- (1,2)
- (1,2,4,3)
- (1,2,3,4)
- (1,3,4,2)
- (1,3,2,4)
- (1,4,3,2)
- (1,4,2,3)

As expected by Wells’ result, we have all the transpositions. But we also get all the four-cycles! To recap:

- Wells proved that if $q\equiv 2\pmod{3}$, then every three cycle permutation of $\F_q$ can be represented by a polynomial of degree $q-2$.
- $q=3$ does not satisfy the hypothesis of Wells’ result, but it satisfies the conclusion.
- $q=4$ does not satisfy the hypothesis of Wells’ result, and it does
*not*satisfy the conclusion since no three cycle permutation of $\F_4$ can be represented by a quadratic polynomial.