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
In case the ring is a finite field, the Dickson polynomials, which are closely related to the Chebyshev polynomials, provide examples.
[1] 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.
[4] Due to the finiteness of Fq, this definition can be expressed in several equivalent ways:[5] A characterization of which polynomials are permutation polynomials is given by (Hermite's Criterion)[6][7] f ∈ Fq[x] is a permutation polynomial of Fq if and only if the following two conditions hold: 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.
[8][9] 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:[10][7] A list of all monic permutation polynomials of degree six in normalized form can be found in Shallue & Wanless (2013).
[11] Beyond the above examples, the following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.
The first few Dickson polynomials are: If a ≠ 0 and n > 1 then Dn(x, a) permutes GF(q) if and only if (n, q2 − 1) = 1.
[14] If a = 0 then Dn(x, 0) = xn and the previous result holds.
The linearized polynomials that are permutation polynomials over GF(qr) form a group under the operation of composition modulo
[15] An exceptional polynomial over GF(q) is a polynomial in Fq[x] which is a permutation polynomial on GF(qm) for infinitely many m.[16] A permutation polynomial over GF(q) of degree at most q1/4 is exceptional over GF(q).
[17] Every permutation of GF(q) is induced by an exceptional polynomial.
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, PG(2,q) with q 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 GF(q).
[20] For the finite ring Z/nZ one can construct quadratic permutation polynomials.
Actually it is possible if and only if n is divisible by p2 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 [21] e.g. page 14 in version 8.8.0).
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.
Lemma: for k>1, p>2 (Z/pkZ) such polynomial defines a permutation if and only if
defines a permutation for the ring Z/nZ if and only if all the polynomials
To see this we observe that for all primes pi, i > 1, the reduction of this quadratic polynomial modulo pi 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.
[22] Let K be an algebraic number field with R the ring of integers.
In fact, Schur did not make any conjecture in this direction.
The notion that he did is due to Fried,[23] who gave a flawed proof of a false version of the result.
Correct proofs have been given by Turnwald[24] and Müller.