Permutation polynomial
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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 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 \mapsto f(c) is a permutation of . Due to the finiteness of , 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); has a solution in for each in ; has a unique solution in for each in . 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: has exactly one root in ; for each integer with and t \not \equiv 0 \!\pmod p , the reduction of has degree . 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.
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 .
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. permutes if and only if and are coprime (notationally, ). If is in and then the Dickson polynomial (of the first kind) is defined by 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) = xD_{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 - 4ax^2 + 2a^2 D_5(x,a) = x^5 - 5ax^3 + 5a^2 x. If and then permutes GF(q) if and only if . If then and the previous result holds. If is an extension of of degree , then the linearized polynomial L(x) = \sum_{s=0}^{r-1} \alpha_s x^{q^s}, with in , is a linear operator on over . A linearized polynomial permutes if and only if 0 is the only root of in . This condition can be expressed algebraically as \det\left ( \alpha_{i-j}^{q^j} \right ) \neq 0 \quad (i, j= 0,1,\ldots,r-1). The linearized polynomials that are permutation polynomials over 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 . If is in the polynomial ring and has no nonzero root in when divides , and is relatively prime (coprime) to , then permutes . Only a few other specific classes of permutation polynomials over have been characterized. Two of these, for example, are: x^{(q + m - 1)/m} + ax where divides , and x^r \left(x^d - a\right)^{\left(p^n - 1\right)/d} where divides .
Exceptional polynomials
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).
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, 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 .
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 \mathbb{F}_q[x_1,\ldots,x_n] is a permutation polynomial in variables over \mathbb{F}_q if the equation f(x_1,\ldots,x_n) = \alpha has exactly q^{n-1} solutions in \mathbb{F}_q^n for each \alpha \in \mathbb{F}_q . Consider g(x) = 2x^2+x for the ring Z/4Z. One sees: so the polynomial defines the permutation \begin{pmatrix} 0 &1 & 2 & 3 \\ 0 &3 & 2 & 1 \end{pmatrix} . Consider the same polynomial g(x) = 2x^2+x for the other ring Z/8Z. One sees: so the polynomial defines the permutation \begin{pmatrix} 0 &1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 &3 & 2 & 5 & 4 & 7 & 6 & 1 \end{pmatrix} . Consider g(x) = ax^2+bx+c for the ring Z/p k Z. 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 k Z) such polynomial defines a permutation if and only if a \equiv 0 \pmod p and b \not \equiv 0 \pmod p . 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 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 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 >1. Consider ax^2+bx , such that a= 0 \bmod p_1 , but a\ne 0 \bmod p_1^{k_1} ; assume that a = 0 \bmod p_i^{k_i} , i > 1. And assume that b\ne 0 \bmod p_i for all . (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 and polynomial 6x^2+x . It defines a permutation \begin{pmatrix} 0 &1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots \\ 0 &7 & 2 & 9 & 4 & 11 & 6 & 1 & 8 & \cdots \end{pmatrix} .
Higher degree polynomials over finite rings
A polynomial g(x) for the ring Z/p k Z is a permutation polynomial if and only if it permutes the finite field Z/pZ and g'(x) \ne 0 \bmod p for all x in Z/p k Z, 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.
Notes
References
Chapter 7. Chapter 8.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1340784573 under CC BY-SA 4.0; modifications have been made.