In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a permutation polynomial (for a given
ring) is a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
that acts as a
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
of the elements of the ring, i.e. the map
is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
. In case the ring is a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) 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, subtr ...
, the
Dickson polynomials In mathematics, the Dickson polynomials, denoted , form a polynomial sequence introduced by . They were rediscovered by in his study of Brewer sums and have at times, although rarely, been referred to as Brewer polynomials.
Over the complex nu ...
, which are closely related to the
Chebyshev polynomials
The Chebyshev polynomials are two sequences of polynomials related to the trigonometric functions, cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric ...
, 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/''n''Z, such polynomials have also been studied and applied in the
interleaver
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
component of
error detection and correction
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable commu ...
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
is a permutation of .
Due to the finiteness of , this definition can be expressed in several equivalent ways:
* the function
is ''onto'' (
surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element o ...
);
* the function
is ''one-to-one'' (
injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
);
* 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
Charles Hermite () FRS FRSE MIAS (24 December 1822 – 14 January 1901) was a French mathematician who did research concerning number theory, quadratic forms, invariant theory, orthogonal polynomials, elliptic functions, and algebra.
Her ...
'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
, 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
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
(notationally, ).
* If is in and then the
Dickson polynomial In mathematics, the Dickson polynomials, denoted , form a polynomial sequence introduced by . They were rediscovered by in his study of Brewer sums and have at times, although rarely, been referred to as Brewer polynomials.
Over the complex numb ...
(of the first kind) is defined by
These can also be obtained from the
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
with the initial conditions
and
.
The first few Dickson polynomials are:
*
*
*
*
If and then permutes GF(''q'') if and only if . If then and the previous result holds.
* If is an
extension
Extension, extend or extended may refer to:
Mathematics
Logic or set theory
* Axiom of extensionality
* Extensible cardinal
* Extension (model theory)
* Extension (predicate logic), the set of tuples of values that satisfy the predicate
* Ext ...
of of degree , then the
linearized polynomial with in , is a
linear operator
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a Map (mathematics), mapping V \to W between two vect ...
on over . A linearized polynomial permutes if and only if 0 is the only root of in .
This condition can be expressed algebraically as
The linearized polynomials that are permutation polynomials over form a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
under the operation of composition modulo
, which is known as the Betti-Mathieu group, isomorphic to the
general linear group
In mathematics, the general linear group of degree ''n'' is the set of invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, ...
.
* 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:
where divides , and
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
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
coordinate descriptions of certain point sets can provide examples of permutation polynomials of higher degree. In particular, the points forming an
oval
An oval () is a closed curve in a plane which resembles the outline of an egg. The term is not very specific, but in some areas (projective geometry, technical drawing, etc.) it is given a more precise definition, which may include either one ...
in a finite
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
, 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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Permutation polynomials in several variables over finite fields
A polynomial
of ''g''(''x'').
. 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
s ''P'', then ''f'' is the composition of Dickson polynomials, degree-one polynomials, and polynomials of the form ''x''
. In fact,
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.
*
*
*
* Chapter 7.
* Chapter 8.
* {{cite journal, first1=C.J., last1=Shallue, first2=I.M., last2=Wanless, title=Permutation polynomials and orthomorphism polynomials of degree six, journal=Finite Fields and Their Applications, volume=20, date= March 2013, pages=84–92, doi=10.1016/j.ffa.2012.12.003, doi-access=free