Permutation polynomial

Last updated • 9 min readFrom Wikipedia, The Free Encyclopedia

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

Contents

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]

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 fFq[x]) is a permutation polynomial of Fq if the function from Fq to itself defined by is a permutation of Fq. [3]

Due to the finiteness of Fq, this definition can be expressed in several equivalent ways: [4]

A characterization of which polynomials are permutation polynomials is given by

( Hermite's Criterion) [5] [6] fFq[x] is a permutation polynomial of Fq if and only if the following two conditions hold:

  1. f has exactly one root in Fq;
  2. for each integer t with 1 ≤ tq − 2 and , the reduction of f(x)t mod (xqx) has degree q − 2.

If f(x) is a permutation polynomial defined over the finite field GF(q), then so is g(x) = af(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 xn1 is 0.

There are many open questions concerning permutation polynomials defined over finite fields. [7] [8]

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: [9] [6]

Normalized Permutation Polynomial of Fqq
any
( not a square)
(if its only root in Fq is 0)
( not a fourth power)
( not a square)
( arbitrary)
( not a square)
( not a square)

A list of all monic permutation polynomials of degree six in normalized form can be found in Shallue & Wanless (2013). [10]

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. [11]

These can also be obtained from the recursion

with the initial conditions and . 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. [13] 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 , which is known as the Betti-Mathieu group, isomorphic to the general linear group GL(r, Fq). [14]

Exceptional polynomials

An exceptional polynomial over GF(q) is a polynomial in Fq[x] which is a permutation polynomial on GF(qm) for infinitely many m. [15]

A permutation polynomial over GF(q) of degree at most q1/4 is exceptional over GF(q). [16]

Every permutation of GF(q) is induced by an exceptional polynomial. [16]

If a polynomial with integer coefficients (i.e., in ℤ[x]) is a permutation polynomial over GF(p) for infinitely many primes p, then it is the composition of linear and Dickson polynomials. [17] (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, 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).

Computational complexity

The problem of testing whether a given polynomial over a finite field is a permutation polynomial can be solved in polynomial time. [18]

Permutation polynomials in several variables over finite fields

A polynomial is a permutation polynomial in n variables over if the equation has exactly solutions in for each . [19]

Quadratic permutation polynomials (QPP) over finite rings

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

Simple examples

Consider for the ring Z/4Z. One sees: ;;;, so the polynomial defines the permutation

Consider the same polynomial for the other ring Z/8Z. One sees: ;;;;;;;, so the polynomial defines the permutation

Rings Z/pkZ

Consider 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, p>2 (Z/pkZ) such polynomial defines a permutation if and only if and .

Rings Z/nZ

Consider , where pt are prime numbers.

Lemma: any polynomial defines a permutation for the ring Z/nZ if and only if all the polynomials defines the permutations for all rings , where are remainders of modulo .

As a corollary one can construct plenty quadratic permutation polynomials using the following simple construction. Consider , assume that k1 >1.

Consider , such that , but ; assume that , i > 1. And assume that for all i = 1, ..., l. (For example, one can take and ). 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 . It defines a permutation

Higher degree polynomials over finite rings

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 for all x in Z/pkZ, where g(x) is the formal derivative of g(x). [21]

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

Notes

  1. Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". IEEE Transactions on Information Theory. 53: 2116–2132. arXiv: cs/0601048 . doi:10.1109/TIT.2007.896870.
  2. Takeshita, Oscar (2005). "A New Construction for LDPC Codes using Permutation Polynomials over Integer Rings". arXiv: cs/0506091 .
  3. Mullen & Panario 2013 , p. 215
  4. Lidl & Niederreiter 1997 , p. 348
  5. Lidl & Niederreiter 1997 , p. 349
  6. 1 2 3 Mullen & Panario 2013 , p. 216
  7. Lidl & Mullen (1988)
  8. Lidl & Mullen (1993)
  9. Dickson 1958 , pg. 63
  10. Mullen & Panario 2013 , p. 217
  11. Lidl & Mullen 1988 , p. 244
  12. 1 2 Lidl & Niederreiter 1997 , p. 351
  13. Lidl & Niederreiter 1997 , p. 356
  14. 1 2 Lidl & Niederreiter 1997 , p. 362
  15. Mullen & Panario 2013 , p. 236
  16. 1 2 Mullen & Panario 2013 , p. 238
  17. Mullen & Panario 2013 , p. 239
  18. Kayal, Neeraj (2005). "Recognizing permutation functions in polynomial time". Electronic Colloquium on Computational Complexity. ECCC   TR05-008. For earlier research on this problem, see: Ma, Keju; von zur Gathen, Joachim (1995). "The computational complexity of recognizing permutation functions". Computational Complexity. 5 (1): 76–97. doi:10.1007/BF01277957. MR   1319494.Shparlinski, I. E. (1992). "A deterministic test for permutation polynomials". Computational Complexity. 2 (2): 129–132. doi:10.1007/BF01202000. MR   1190826.
  19. Mullen & Panario 2013 , p. 230
  20. 3GPP TS 36.212
  21. Sun, Jing; Takeshita, Oscar (2005). "Interleaver for Turbo Codes Using Permutation Polynomials Over Integer Rings". IEEE Transactions on Information Theory. 51 (1): 102.
  22. Fried, M. (1970). "On a conjecture of Schur". Michigan Math. J.: 41–55.
  23. Turnwald, G. (1995). "On Schur's conjecture". J. Austral. Math. Soc.: 312–357.
  24. Müller, P. (1997). "A Weil-bound free proof of Schur's conjecture". Finite Fields and Their Applications: 25–32.

Related Research Articles

Field (mathematics) Algebraic structure with addition, multiplication and division

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers do. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics.

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod p when p is a prime number.

In mathematics, particularly in algebra, a field extension is a pair of fields such that the operations of E are those of F restricted to E. In this case, F is an extension field of E and E is a subfield of F. For example, under the usual notions of addition and multiplication, the complex numbers are an extension field of the real numbers; the real numbers are a subfield of the complex numbers.

Unitary group Group of unitary matrices

In mathematics, the unitary group of degree n, denoted U(n), is the group of n × n unitary matrices, with the group operation of matrix multiplication. The unitary group is a subgroup of the general linear group GL(n, C). Hyperorthogonal group is an archaic name for the unitary group, especially over finite fields. For the group of unitary matrices with determinant 1, see Special unitary group.

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial x2 − 2 is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as if it is considered as a polynomial with real coefficients. One says that the polynomial x2 − 2 is irreducible over the integers but not over the reals.

Polynomial ring Algebraic structure

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In number theory, the local zeta functionZ(Vs) is defined as

In mathematics, the (field) norm is a particular mapping defined in field theory, which maps elements of a larger field into a subfield.

In mathematics, the field trace is a particular function defined with respect to a finite field extension L/K, which is a K-linear map from L onto K.

In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.

E<sub>7</sub> (mathematics)

In mathematics, E7 is the name of several closely related Lie groups, linear algebraic groups or their Lie algebras e7, all of which have dimension 133; the same notation E7 is used for the corresponding root lattice, which has rank 7. The designation E7 comes from the Cartan–Killing classification of the complex simple Lie algebras, which fall into four infinite series labeled An, Bn, Cn, Dn, and five exceptional cases labeled E6, E7, E8, F4, and G2. The E7 algebra is thus one of the five exceptional cases.

In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

In commutative algebra and field theory, the Frobenius endomorphism is a special endomorphism of commutative rings with prime characteristic p, an important class which includes finite fields. The endomorphism maps every element to its p-th power. In certain contexts it is an automorphism, but this is not true in general.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

In commutative algebra, an element b of a commutative ring B is said to be integral overA, a subring of B, if there are n ≥ 1 and aj in A such that

In mathematics, the Dickson polynomials, denoted Dn(x,α), form a polynomial sequence introduced by L. E. Dickson (1897). They were rediscovered by Brewer (1961) in his study of Brewer sums and have at times, although rarely, been referred to as Brewer polynomials.

In ring theory, a branch of mathematics, a ring R is a polynomial identity ring if there is, for some N > 0, an element P ≠ 0 of the free algebra, ZX1, X2, ..., XN⟩, over the ring of integers in N variables X1, X2, ..., XN such that

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

In mathematics, a linearised polynomial is a polynomial for which the exponents of all the constituent monomials are powers of q and the coefficients come from some extension field of the finite field of order q.

In mathematics, the ring of polynomial functions on a vector space V over a field k gives a coordinate-free analog of a polynomial ring. It is denoted by k[V]. If V is finite dimensional and is viewed as an algebraic variety, then k[V] is precisely the coordinate ring of V.

References