Permutation polynomial

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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. There are some situations in which these are essentially the only permutation polynomials over finite fields.

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]

Quadratic permutation polynomials (QPP)[edit]

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 [3] e.g. page 14 in version 8.8.0).

Simple examples[edit]

Consider  g(x) = 2x^2+x for the ring Z/4Z. One sees:  g(0) = 0;~ g(1) = 3;~ g(2) = 2;~ g(3) = 1  , so the polynomial defines the permutation

\begin{pmatrix}
0 &1 & 2 & 3 \\
0 &3 & 2 & 1\end{pmatrix} .

Let us consider the same polynomial  g(x) = 2x^2+x for the other ring Z/8Z. One sees:  g(0) = 0;~ g(1) = 3;~ g(2) = 2;~ g(3) = 5;~ g(4) = 4;~ g(5) = 7; ~ g(6) = 6; ~ g(7) = 1; , 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} .

Rings Z/pkZ[edit]

Consider  g(x) = ax^2+bx+c for the ring Z/pkZ.

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 ( Z/pkZ) such polynomial defines a permutation if and only if a = 0~ mod~ p and b \ne 0~ mod~ p.

Rings Z/nZ[edit]

Consider n=p_1^{k_1}p_2^{k_2}...p_l^{k_l}, where pt 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}...p_l^{k_l}, assume that k1 >1.

Consider ax^2+bx, such that  a= 0~ mod~ p_1, but  a\ne 0~ mod~ p_1^{k_1}; assume that  a= 0~ mod~ p_i^{k_i},i>1. And assume that b\ne 0~ mod~ p_i for all i=1...l. (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 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 Z/12Z and polynomial 6x^2+x. It defines a permutation

\begin{pmatrix}
0 &1 & 2 & 3 & 4 & 5  & 6 & 7 & 8 & ... \\
0 &7 & 2 & 9 & 4 & 11 & 6 & 1 & 8 &  ... \end{pmatrix} .

Higher degree polynomials[edit]

A polynomial g(x) for the ring Z/pkZ is a permutation polynomial if and only if it permutes the finite field Z/pZ and g'(x) \ne 0~ mod~ p for all x in Z/pkZ, where g′(x) is the formal derivative of g(x).[4]

Lemma: consider the finite field Z/pZ for some prime number p. The cubic polynomial  g(x) = ax^3+bx defines a permutation if and only if for all y \in Z/pZ it is true that  y^2\ne -b/a , i.e. the Legendre symbol 
\left(\frac{-b/a}{p}\right)=-1.
.

Evaluation of the Legendre symbol can be achieved with the help of quadratic reciprocity law.

Finite fields[edit]

There are many open questions concerning permutation polynomials defined over finite fields (see Lidl & Mullen (1988) and Lidl & Mullen (1993)).

If f(x) is a permutation polynomial defined over the finite field GF(q), where q = pe for some prime p, then so is g(x) = a f(x + b) + c for all a ≠ 0, b and c in GF(q). We say that 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.

The following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.[5]

  • Dickson (1958, pg. 63) lists all normalized permutation polynomials of degree at most 5.
  • xk permutes GF(q) if and only if (k, q - 1) = 1.
  • If a is in GF(q) then the Dickson polynomial gk(x,a) permutes GF(q) if and only if (k, q2 - 1) = 1.
  • If GF(qr) is an extension of GF(q) of degree r, then the linearised polynomial
L(x) = \Sigma_{s=0}^{r-1} \alpha_s x^{q^s},
with αs in GF(qr) is a linear operator on GF(qr) over GF(q) and it permutes GF(qr) if and only if
 \rm{det}\left ( \alpha_{i-j}^{q^j} \right ) \neq 0 \quad (i, j= 0,1,\ldots,r-1).
  • If r > 1 is relatively prime to q - 1, s divides q - 1 and g(xs) has no nonzero root in GF(q) where g(x) is in the polynomial ring GF(q)[x], then xr(g(xs))(q - 1)/s permutes GF(q).
  • Only a few other specific classes of permutation polynomials over GF(q) have been characterized. Two of these, for example, are:
 x^{(q + m - 1)/m} + ax
where m divides q - 1, and
 x^r(x^d - a)^{(p^n - 1)/d}
where d divides pn - 1.

Geometric examples[edit]

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).

Schur's conjecture[edit]

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 xk. In fact, Schur did not make any conjecture in this direction. The notion that he did is due to Fried,[6] who gave a flawed proof of a false version of the result. Correct proofs have been given by Turnwald [7] and Müller.[8]

Notes[edit]

  1. ^ Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". arXiv:cs/0601048.
  2. ^ Takeshita, Oscar (2005). "A New Construction for LDPC Codes using Permutation Polynomials over Integer Rings". arXiv:cs/0506091.
  3. ^ 3GPP TS 36.212
  4. ^ Sun, Jing; Takeshita, Oscar (2005). "Interleaver for Turbo Codes Using Permutation Polynomials Over Integer Rings". IEEE transactions on information theory 51 (1): 102
  5. ^ Lidl & Mullen 1988, pg. 244
  6. ^ Fried, M. (1970). "On a conjecture of Schur". Michigan Math. J.: 41–55. 
  7. ^ Turnwald, G. (1995). "On Schur's conjecture". J. Austral. Math. Soc.: 312–357. 
  8. ^ Müller, P. (1997). "A Weil-bound free proof of Schur's conjecture". Finite Fields Appl.: 25–32. 

References[edit]

  • Dickson, L. E. (1958) [1901]. Linear Groups with an Exposition of the Galois Field Theory. New York: Dover. 
  • Lidl, Rudolf; Mullen, Gary L. (March 1988). "When Does a Polynomial over a Finite Field Permute the Elements of the Field?". The American Mathematical Monthly 95 (3): 243–246. doi:10.2307/2323626. 
  • Lidl, Rudolf; Mullen, Gary L. (January 1993). "When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II". The American Mathematical Monthly 100 (1): 71–74. doi:10.2307/2324822. 

Further reading[edit]