Permutation polynomial

In mathematics, a permutation polynomial (for a given ring) is a polynomial that acts as a permutation of the elements of the ring, i.e. the map $x\mapsto g(x)$ is a bijection. In case the ring is a finite field, the Dickson polynomials, which are closely related to the Chebyshev polynomials, provide examples. Over a finite field, every function, so in particular every permutation of the elements of that field, can be written as a polynomial function.

In the case of finite rings Z/nZ, such polynomials have also been studied and applied in the interleaver component of error detection and correction algorithms.

Single variable permutation polynomials over finite fields

Let Template:Math be the finite field of characteristic Template:Mvar, that is, the field having Template:Mvar elements where Template:Math for some prime Template:Mvar. A polynomial Template:Mvar with coefficients in Template:Math (symbolically written as Template:Math) is a permutation polynomial of Template:Math if the function from Template:Math to itself defined by $c\mapsto f(c)$ is a permutation of Template:Math.

Due to the finiteness of Template:Math, this definition can be expressed in several equivalent ways:

• the function $c\mapsto f(c)$ is onto (surjective);
• the function $c\mapsto f(c)$ is one-to-one (injective);
• Template:Math has a solution in Template:Math for each Template:Mvar in Template:Math;
• Template:Math has a unique solution in Template:Math for each Template:Mvar in Template:Math.

A characterization of which polynomials are permutation polynomials is given by

(Hermite's Criterion) Template:Math is a permutation polynomial of Template:Math if and only if the following two conditions hold:

1. Template:Mvar has exactly one root in Template:Math;
2. for each integer Template:Math with Template:Math and $t\equiv ̸0(\mathrm{mod}p)$, the reduction of Template:Math has degree Template:Math.

If Template:Math is a permutation polynomial defined over the finite field Template:Math, then so is Template:Math for all Template:Math and Template:Mvar in Template:Math. The permutation polynomial Template:Math is in normalized form if Template:Math and Template:Mvar are chosen so that Template:Math is monic, Template:Math and (provided the characteristic Template:Mvar does not divide the degree Template:Mvar of the polynomial) the coefficient of Template:Math is 0.

There are many open questions concerning permutation polynomials defined over finite fields.

Small degree

Hermite's criterion is computationally intensive and can be difficult to use in making theoretical conclusions. However, Dickson was able to use it to find all permutation polynomials of degree at most five over all finite fields. These results are:

Normalized Permutation Polynomial of Template:Math	Template:Mvar
$x$	any $q$
$x^2$	$q\equiv 0(\mathrm{mod}2)$
$x^3$	$q\equiv ̸1(\mathrm{mod}3)$
$x^3-ax$ ($a$ not a square)	$q\equiv 0(\mathrm{mod}3)$
$x^4\pm 3x$	$q=7$
$x^4+a_1{x}^2+a_{2}x$ (if its only root in Template:Math is 0)	$q\equiv 0(\mathrm{mod}2)$
$x^5$	$q\equiv ̸1(\mathrm{mod}5)$
$x^5-ax$ ($a$ not a fourth power)	$q\equiv 0(\mathrm{mod}5)$
$x^5+ax(a^2=2)$	$q=9$
$x^5\pm 2x^2$	$q=7$
$x^5+a{x}^3\pm x^2+3a^{2}x$ ($a$ not a square)	$q=7$
$x^5+a{x}^3+5^{-1}{a}^{2}x$ ($a$ arbitrary)	$q\equiv \pm 2(\mathrm{mod}5)$
$x^5+a{x}^3+3a^{2}x$ ($a$ not a square)	$q=13$
$x^5-2a{x}^3+a^{2}x$ ($a$ not a square)	$q\equiv 0(\mathrm{mod}5)$

A list of all monic permutation polynomials of degree six in normalized form can be found in Template:Harvtxt.

Some classes of permutation polynomials

Beyond the above examples, the following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.

• Template:Math permutes Template:Math if and only if Template:Mvar and Template:Math are coprime (notationally, Template:Math).
• If Template:Mvar is in Template:Math and Template:Math then the Dickson polynomial (of the first kind) Template:Math is defined by $$D_n(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }\frac{n}{n-j}(\genfrac{}{}{0ex}{}{n-j}{j})(-a{)}^j{x}^{n-2j}.$$

These can also be obtained from the recursion $$D_n(x,a)=x{D}_{n-1}(x,a)-a{D}_{n-2}(x,a),$$ with the initial conditions $D_0(x,a)=2$ and $D_1(x,a)=x$. The first few Dickson polynomials are:

• $D_2(x,a)=x^2-2a$
• $D_3(x,a)=x^3-3ax$
• $D_4(x,a)=x^4-4a{x}^2+2a^2$
• $D_5(x,a)=x^5-5a{x}^3+5a^{2}x.$

If Template:Math and Template:Math then Template:Math permutes GF(q) if and only if Template:Math. If Template:Math then Template:Math and the previous result holds.

• If Template:Math is an extension of Template:Math of degree Template:Mvar, then the linearized polynomial $$L(x)=\sum _{s=0}^{r-1}{\alpha }_s{x}^{q^s},$$ with Template:Math in Template:Math, is a linear operator on Template:Math over Template:Math. A linearized polynomial Template:Math permutes Template:Math if and only if 0 is the only root of Template:Math in Template:Math. This condition can be expressed algebraically as $$\det \left({\alpha }_{i-j}^{q^j}\right)\ne 0(i,j=0,1,\dots ,r-1).$$

The linearized polynomials that are permutation polynomials over Template:Math form a group under the operation of composition modulo $x^{q^r}-x$, which is known as the Betti-Mathieu group, isomorphic to the general linear group Template:Math.

• If Template:Math is in the polynomial ring Template:Math and Template:Math has no nonzero root in Template:Math when Template:Mvar divides Template:Math, and Template:Math is relatively prime (coprime) to Template:Math, then Template:Math permutes Template:Math.
• Only a few other specific classes of permutation polynomials over Template:Math have been characterized. Two of these, for example, are: $$x^{(q+m-1)/m}+ax$$ where Template:Mvar divides Template:Math, and $$x^r{(x^d-a)}^{(p^n-1)/d}$$ where Template:Mvar divides Template:Math.

Exceptional polynomials

An exceptional polynomial over Template:Math is a polynomial in Template:Math which is a permutation polynomial on Template:Math for infinitely many Template:Mvar.

A permutation polynomial over Template:Math of degree at most Template:Math is exceptional over Template:Math.

Every permutation of Template:Math is induced by an exceptional polynomial.

If a polynomial with integer coefficients (i.e., in Template:Math) is a permutation polynomial over Template:Math for infinitely many primes Template:Mvar, then it is the composition of linear and Dickson polynomials. (See Schur's conjecture below).

Geometric examples

In finite geometry coordinate descriptions of certain point sets can provide examples of permutation polynomials of higher degree. In particular, the points forming an oval in a finite projective plane, Template:Math with Template:Math a power of 2, can be coordinatized in such a way that the relationship between the coordinates is given by an o-polynomial, which is a special type of permutation polynomial over the finite field Template:Math.

Computational complexity

The problem of testing whether a given polynomial over a finite field is a permutation polynomial can be solved in polynomial time.

Permutation polynomials in several variables over finite fields

A polynomial $f\in {𝔽}_q[x_1,\dots ,x_n]$ is a permutation polynomial in Template:Mvar variables over ${𝔽}_q$ if the equation $f(x_1,\dots ,x_n)=\alpha$ has exactly $q^{n-1}$ solutions in ${𝔽}_q^n$ for each $\alpha \in {𝔽}_q$.

Quadratic permutation polynomials (QPP) over finite rings

For the finite ring Z/nZ one can construct quadratic permutation polynomials. Actually it is possible if and only if n is divisible by p² for some prime number p. The construction is surprisingly simple, nevertheless it can produce permutations with certain good properties. That is why it has been used in the interleaver component of turbo codes in 3GPP Long Term Evolution mobile telecommunication standard (see 3GPP technical specification 36.212 e.g. page 14 in version 8.8.0).

Simple examples

Consider $g(x)=2x^2+x$ for the ring Z/4Z. One sees: Template:Nowrap Template:Nowrap Template:Nowrap Template:Nowrap so the polynomial defines the permutation $$\left(\begin{array}{cccc}0& 1& 2& 3\\ 0& 3& 2& 1\end{array}\right).$$

Consider the same polynomial $g(x)=2x^2+x$ for the other ring Z/8Z. One sees: Template:Nowrap Template:Nowrap Template:Nowrap Template:Nowrap Template:Nowrap Template:Nowrap Template:Nowrap Template:Nowrap so the polynomial defines the permutation $$\left(\begin{array}{cccccccc}0& 1& 2& 3& 4& 5& 6& 7\\ 0& 3& 2& 5& 4& 7& 6& 1\end{array}\right).$$

Rings Z/p^kZ

Consider $g(x)=a{x}^2+bx+c$ for the ring Z/p^kZ.

Lemma: for k=1 (i.e. Z/pZ) such polynomial defines a permutation only in the case a=0 and b not equal to zero. So the polynomial is not quadratic, but linear.

Lemma: for k>1, p>2 (Z/p^kZ) such polynomial defines a permutation if and only if $a\equiv 0(\mathrm{mod}p)$ and $b\equiv ̸0(\mathrm{mod}p)$.

Rings Z/nZ

Consider $n=p_1^{k_1}{p}_2^{k_2}...p_l^{k_l}$, where p_t are prime numbers.

Lemma: any polynomial $g(x)=a_0+\sum _{0<i\le M}{a}_i{x}^i$ defines a permutation for the ring Z/nZ if and only if all the polynomials $g_{p_t}(x)=a_{0,p_t}+\sum _{0<i\le M}{a}_{i,p_t}{x}^i$ defines the permutations for all rings $Z/p_t^{k_t}Z$, where $a_{j,p_t}$ are remainders of $a_j$ modulo $p_t^{k_t}$.

As a corollary one can construct plenty quadratic permutation polynomials using the following simple construction. Consider $n=p_1^{k_1}{p}_2^{k_2}\dots p_l^{k_l}$, assume that k₁ >1.

Consider $a{x}^2+bx$, such that $a=0{modp}_1$, but $a\ne 0{modp}_1^{k_1}$; assume that $a=0{modp}_i^{k_i}$, i > 1. And assume that $b\ne 0{modp}_i$ for all Template:Math. (For example, one can take $a=p_1{p}_2^{k_2}...p_l^{k_l}$ and $b=1$). Then such polynomial defines a permutation.

To see this we observe that for all primes p_i, i > 1, the reduction of this quadratic polynomial modulo p_i is actually linear polynomial and hence is permutation by trivial reason. For the first prime number we should use the lemma discussed previously to see that it defines the permutation.

For example, consider Template:Math and polynomial $6x^2+x$. It defines a permutation $\left(\begin{array}{cccccccccc}0& 1& 2& 3& 4& 5& 6& 7& 8& \cdots \\ 0& 7& 2& 9& 4& 11& 6& 1& 8& \cdots \end{array}\right).$

Higher degree polynomials over finite rings

A polynomial g(x) for the ring Z/p^kZ is a permutation polynomial if and only if it permutes the finite field Z/pZ and $g^{\prime }(x)\ne 0modp$ for all x in Z/p^kZ, where g′(x) is the formal derivative of g(x).

Schur's conjecture

Let K be an algebraic number field with R the ring of integers. The term "Schur's conjecture" refers to the assertion that, if a polynomial f defined over K is a permutation polynomial on R/P for infinitely many prime ideals P, then f is the composition of Dickson polynomials, degree-one polynomials, and polynomials of the form x^k. In fact, Schur did not make any conjecture in this direction. The notion that he did is due to Fried, who gave a flawed proof of a false version of the result. Correct proofs have been given by Turnwald and Müller.

References

• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite book Chapter 7.
• Template:Cite book Chapter 8.
• Template:Cite journal