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

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:

1. (2,3)
2. (2,4)
3. (1,3)
4. (1,4)
5. (3,4)
6. (1,2)
7. (1,2,4,3)
8. (1,2,3,4)
9. (1,3,4,2)
10. (1,3,2,4)
11. (1,4,3,2)
12. (1,4,2,3)

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

1. 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$.
2. $q=3$ does not satisfy the hypothesis of Wells' result, but it satisfies the conclusion.
3. $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.