In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a permutation polynomial (for a given finite ring

Ring (mathematics)

In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...

) is a polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

 that acts as a permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 of the elements of the ring, i.e. the map is one-to-one. In case the ring is a finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

, they are (under certain assumptions) essentially Dickson polynomials which are closely related to the Chebyshev polynomials

Chebyshev polynomials

In mathematics the Chebyshev polynomials, named after Pafnuty Chebyshev, are a sequence of orthogonal polynomials which are related to de Moivre's formula and which can be defined recursively. One usually distinguishes between Chebyshev polynomials of the first kind which are denoted Tn and...

.

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

Error detection and correction

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels...

 algorithms.

Quadratic permutation polynomials (QPP)

For the finite ring Z/nZ one can construct quadratic
permutation polynomials. Actually it is possible if and only if n is divisible by p² 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

3GPP Long Term Evolution

3GPP Long Term Evolution, usually referred to as LTE, is a standard for wireless communication of high-speed data for mobile phones and data terminals. It is based on the GSM/EDGE and UMTS/HSPA network technologies, increasing the capacity and speed using new modulation techniques...

  mobile telecommunication standard (see 3GPP technical specification 36.212 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

.

Let us consider the same polynomial for the other ring Z/8Z.
One sees: ,
so the polynomial defines the permutation

.

Rings Z/p^kZ

Consider for the ring Z/p^kZ.

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/p^kZ) such polynomial defines a permutation if and only if and .

Rings Z/nZ

Consider , where p_t 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
modula .

As a corollary one can construct plenty quadratic permutation polynomials using the following simple construction.
Consider , assume that k₁ >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 p_i,i>1, the reduction of this quadratic polynomial modula 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 Z/12Z and polynomial .
It defines a permutation

.

Higher degree polynomials

Consider polynomial for the ring Z/p^kZ. In the same way as for quadratic polynomials one can see:

Lemma: if and i>0, then polynomial g(x) defines a permutation for the elements of the ring Z/p^kZ for k>1.

However contrary to the case of the quadratic polynomials the lemma is not if and only if. This can be seen from the following statement.

Lemma: consider finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

 Z/pZ for some prime number p.
The cubic polynomial defines a permutation if and only if for all it is true that , i.e. the Legendre symbol

Legendre symbol

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....

 .

Evaluation of the Legendre symbol

Legendre symbol

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....

 can be achieved with the help of quadratic reciprocity law.

So one can see that the analysis of higher degree polynomials to define a permutation is quite subtle question.

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.