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\mapstog(x)
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.[1] [2]
Let be the finite field of characteristic, that is, the field having elements where for some prime . A polynomial with coefficients in (symbolically written as) is a permutation polynomial of if the function from to itself defined by
c\mapstof(c)
Due to the finiteness of, this definition can be expressed in several equivalent ways:
c\mapstof(c)
c\mapstof(c)
A characterization of which polynomials are permutation polynomials is given by
(Hermite's Criterion) is a permutation polynomial of if and only if the following two conditions hold:
t\not\equiv0\pmodp
If is a permutation polynomial defined over the finite field, then so is for all and in . The permutation polynomial is in normalized form if and are chosen so that is monic, and (provided the characteristic does not divide the degree of the polynomial) the coefficient of is 0.
There are many open questions concerning permutation polynomials defined over finite fields.
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 | ||
---|---|---|
x | any q | |
x2 | q\equiv0\pmod2 | |
x3 | q\not\equiv1\pmod3 | |
x3-ax a | q\equiv0\pmod3 | |
x4\pm3x | q=7 | |
x4+a1x2+a2x | q\equiv0\pmod2 | |
x5 | q\not\equiv1\pmod5 | |
x5-ax a | q\equiv0\pmod5 | |
x5+ax(a2=2) | q=9 | |
x5\pm2x2 | q=7 | |
x5+ax3\pmx2+3a2x a | q=7 | |
x5+ax3+5-1a2x a | q\equiv\pm2\pmod5 | |
x5+ax3+3a2x a | q=13 | |
x5-2ax3+a2x a | q\equiv0\pmod5 |
A list of all monic permutation polynomials of degree six in normalized form can be found in .
Beyond the above examples, the following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.
These can also be obtained from the recursionwith the initial conditions
D0(x,a)=2
D1(x,a)=x
D2(x,a)=x2-2a
D3(x,a)=x3-3ax
D4(x,a)=x4-4ax2+2a2
D5(x,a)=x5-5ax3+5a2x.
If and then permutes GF(q) if and only if . If then and the previous result holds.
The linearized polynomials that are permutation polynomials over form a group under the operation of composition modulo
qr | |
x |
-x
An exceptional polynomial over is a polynomial in which is a permutation polynomial on for infinitely many .
A permutation polynomial over of degree at most is exceptional over .
Every permutation of is induced by an exceptional polynomial.
If a polynomial with integer coefficients (i.e., in) is a permutation polynomial over for infinitely many primes, then it is the composition of linear and Dickson polynomials. (See Schur's conjecture below).
See main article: Oval (projective plane).
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, with 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 .
The problem of testing whether a given polynomial over a finite field is a permutation polynomial can be solved in polynomial time.[3]
A polynomial
f\inFq[x1,\ldots,xn]
Fq
f(x1,\ldots,xn)=\alpha
qn-1
n | |
F | |
q |
\alpha\inFq
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 [4] e.g. page 14 in version 8.8.0).
Consider
g(x)=2x2+x
Consider the same polynomial
g(x)=2x2+x
Consider
g(x)=ax2+bx+c
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/pkZ) such polynomial defines a permutation if and only if
a\equiv0\pmodp
b\not\equiv0\pmodp
Consider
k1 | |
n=p | |
1 |
k2 | |
p | |
2 |
kl | |
...p | |
l |
Lemma: any polynomial defines a permutation for the ring Z/nZ if and only if all the polynomials defines the permutations for all rings
kt | |
Z/p | |
t |
Z
a | |
j,pt |
aj
kt | |
p | |
t |
As a corollary one can construct plenty quadratic permutation polynomials using the following simple construction. Consider
n=
k1 | |
p | |
1 |
k2 | |
p | |
2 |
...
kl | |
p | |
l |
Consider
ax2+bx
a=0\bmodp1
a\ne0\bmod
k1 | |
p | |
1 |
a=0\bmod
ki | |
p | |
i |
b\ne0\bmodpi
a=p1
k2 | |
p | |
2 |
kl | |
...p | |
l |
b=1
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.
For example, consider and polynomial
6x2+x