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 ↦ g ( x ) {\displaystyle 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 Fq = GF(q) be the finite field of characteristic p, that is, the field having q elements where q = pe for some prime p. A polynomial f with coefficients in Fq (symbolically written as f ∈ Fq[x]) is a permutation polynomial of Fq if the function from Fq to itself defined by c ↦ f ( c ) {\displaystyle c\mapsto f(c)} is a permutation of Fq. Due to the finiteness of Fq, this definition can be expressed in several equivalent ways:
the function c ↦ f ( c ) {\displaystyle c\mapsto f(c)} is onto (surjective); the function c ↦ f ( c ) {\displaystyle c\mapsto f(c)} is one-to-one (injective); f(x) = a has a solution in Fq for each a in Fq; f(x) = a has a unique solution in Fq for each a in Fq. A characterization of which polynomials are permutation polynomials is given by (Hermite's Criterion) f ∈ Fq[x] is a permutation polynomial of Fq if and only if the following two conditions hold:
f has exactly one root in Fq; for each integer t with 1 ≤ t ≤ q − 2 and t ≢ 0 ( mod p ) {\displaystyle t\not \equiv 0\!{\pmod {p}}} , the reduction of f(x)t mod (xq − x) has degree ≤ q − 2. If f(x) is a permutation polynomial defined over the finite field GF(q), then so is g(x) = a f(x + b) + c for all a ≠ 0, b and c in GF(q). The permutation polynomial g(x) is in normalized form if a, b and c are chosen so that g(x) is monic, g(0) = 0 and (provided the characteristic p does not divide the degree n of the polynomial) the coefficient of xn−1 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:
A list of all monic permutation polynomials of degree six in normalized form can be found in Shallue & Wanless (2013).
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.
xn permutes GF(q) if and only if n and q − 1 are coprime (notationally, (n, q − 1) = 1). If a is in GF(q) and n ≥ 1 then the Dickson polynomial (of the first kind) Dn(x,a) is defined by D n ( x , a ) = ∑ j = 0 ⌊ n / 2 ⌋ n n − j ( n − j j ) ( − a ) j x n − 2 j . {\displaystyle D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {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 ) , {\displaystyle D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),}
with the initial conditions D 0 ( x , a ) = 2 {\displaystyle D_{0}(x,a)=2} and D 1 ( x , a ) = x {\displaystyle D_{1}(x,a)=x} . The first few Dickson polynomials are:
D 2 ( x , a ) = x 2 − 2 a {\displaystyle D_{2}(x,a)=x^{2}-2a}
D 3 ( x , a ) = x 3 − 3 a x {\displaystyle D_{3}(x,a)=x^{3}-3ax}
… excerpt ends here. Continue reading the full article.
