Permutation polynomial

Let {{math|1=F_q = GF(q)}} be the finite field of characteristic {{mvar|p}}, that is, the field having {{mvar|q}} elements where {{math|1=q = p^e}} for some prime {{mvar|p}}. A polynomial {{mvar|f}} with coefficients in {{math|F_q}} (symbolically written as {{math|f ∈ F_q[x]}}) is a permutation polynomial of {{math|F_q}} if the function from {{math|F_q}} to itself defined by $c\; \backslash mapsto\; f(c)$ is a permutation of {{math|F_q}}.{{harvnb|Mullen|Panario|2013|loc=p. 215}}

Due to the finiteness of {{math|F_q}}, this definition can be expressed in several equivalent ways:{{harvnb|Lidl|Niederreiter|1997|loc=p. 348}}

• the function $c\; \backslash mapsto\; f(c)$ is onto (surjective);
• the function $c\; \backslash mapsto\; f(c)$ is one-to-one (injective);
• {{math|1=f(x) = a}} has a solution in {{math|F_q}} for each {{mvar|a}} in {{math|F_q}};
• {{math|1=f(x) = a}} has a unique solution in {{math|F_q}} for each {{mvar|a}} in {{math|F_q}}.

A characterization of which polynomials are permutation polynomials is given by

(Hermite's Criterion){{harvnb|Lidl|Niederreiter|1997|loc= p. 349}}{{harvnb|Mullen|Panario|2013|loc=p. 216}} {{math|f ∈ F_q[x]}} is a permutation polynomial of {{math|F_q}} if and only if the following two conditions hold:

1. {{mvar|f}} has exactly one root in {{math|F_q}};
2. for each integer {{math|t}} with {{math|1 ≤ t ≤ q − 2}} and $t\; \backslash not\; \backslash equiv\; 0\; \backslash !\backslash pmod\; p$, the reduction of {{math|f(x)^t mod (x^q − x)}} has degree {{math|≤ q − 2}}.

If {{math|f(x)}} is a permutation polynomial defined over the finite field {{math|GF(q)}}, then so is {{math|1=g(x) = a f(x + b) + c}} for all {{math|a ≠ 0, b}} and {{mvar|c}} in {{math|GF(q)}}. The permutation polynomial {{math|g(x)}} is in normalized form if {{math|a, b}} and {{mvar|c}} are chosen so that {{math|g(x)}} is monic, {{math|1=g(0) = 0}} and (provided the characteristic {{mvar|p}} does not divide the degree {{mvar|n}} of the polynomial) the coefficient of {{math|1=xⁿ⁻¹}} is 0.

There are many open questions concerning permutation polynomials defined over finite fields.{{harvtxt|Lidl|Mullen|1988}}{{harvtxt|Lidl|Mullen|1993}}

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:{{harvnb|Dickson|1958|loc = pg. 63}}

A list of all monic permutation polynomials of degree six in normalized form can be found in {{harvtxt|Shallue|Wanless|2013}}.{{harvnb|Mullen|Panario|2013|loc=p. 217}}

Beyond the above examples, the following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.{{harvnb|Lidl|Mullen|1988|loc=p. 244}}

• {{math|xⁿ}} permutes {{math|GF(q)}} if and only if {{mvar|n}} and {{math|q − 1}} are coprime (notationally, {{math|1=(n, q − 1) = 1}}).{{harvnb|Lidl|Niederreiter|1997|loc=p. 351}}
• If {{mvar|a}} is in {{math|GF(q)}} and {{math|n ≥ 1}} then the Dickson polynomial (of the first kind) {{math|D_n(x,a)}} is defined by $$D\_n(x,a)=\backslash sum\_\{j=0\}^\{\backslash lfloor\; n/2\backslash rfloor\}\backslash frac\{n\}\{n-j\}\; \backslash 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 {{math|a ≠ 0}} and {{math|n > 1}} then {{math|D_n(x, a)}} permutes GF(q) if and only if {{math|1=(n, q² − 1) = 1}}.{{harvnb|Lidl|Niederreiter|1997|loc=p. 356}} If {{math|1=a = 0}} then {{math|1=D_n(x, 0) = xⁿ}} and the previous result holds.

• If {{math|GF(q^r)}} is an extension of {{math|GF(q)}} of degree {{mvar|r}}, then the linearized polynomial $$L(x)\; =\; \backslash sum\_\{s=0\}^\{r-1\}\; \backslash alpha\_s\; x^\{q^s\},$$ with {{math|α_s}} in {{math|GF(q^r)}}, is a linear operator on {{math|GF(q^r)}} over {{math|GF(q)}}. A linearized polynomial {{math|L(x)}} permutes {{math|GF(q^r)}} if and only if 0 is the only root of {{math|L(x)}} in {{math|GF(q^r)}}. This condition can be expressed algebraically as{{harvnb|Lidl|Niederreiter|1997|loc=p. 362}} $$\backslash det\backslash left\; (\; \backslash alpha\_\{i-j\}^\{q^j\}\; \backslash right\; )\; \backslash neq\; 0\; \backslash quad\; (i,\; j=\; 0,1,\backslash ldots,r-1).$$

The linearized polynomials that are permutation polynomials over {{math|GF(q^r)}} 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 {{math|GL(r, F_q)}}.

• If {{math|g(x)}} is in the polynomial ring {{math|F_q[x]}} and {{math|g(x^s)}} has no nonzero root in {{math|GF(q)}} when {{mvar|s}} divides {{math|q − 1}}, and {{math|r > 1}} is relatively prime (coprime) to {{math|q − 1}}, then {{math|x^r(g(x^s))^{(q - 1)/s}}} permutes {{math|GF(q)}}.
• Only a few other specific classes of permutation polynomials over {{math|GF(q)}} have been characterized. Two of these, for example, are: $$x^\{(q\; +\; m\; -\; 1)/m\}\; +\; ax$$ where {{mvar|m}} divides {{math|q − 1}}, and $$x^r\; \backslash left(x^d\; -\; a\backslash right)^\{\backslash left(p^n\; -\; 1\backslash right)/d\}$$ where {{mvar|d}} divides {{math|pⁿ − 1}}.

An exceptional polynomial over {{math|GF(q)}} is a polynomial in {{math|F_q[x]}} which is a permutation polynomial on {{math|GF(q^m)}} for infinitely many {{mvar|m}}.{{harvnb|Mullen|Panario|2013|loc=p. 236}}

A permutation polynomial over {{math|GF(q)}} of degree at most {{math|q^1/4}} is exceptional over {{math|GF(q)}}.{{harvnb|Mullen|Panario|2013|loc=p. 238}}

Every permutation of {{math|GF(q)}} is induced by an exceptional polynomial.

If a polynomial with integer coefficients (i.e., in {{math|ℤ[x]}}) is a permutation polynomial over {{math|GF(p)}} for infinitely many primes {{mvar|p}}, then it is the composition of linear and Dickson polynomials.{{harvnb|Mullen|Panario|2013|loc=p. 239}} (See Schur's conjecture below).

{{main|Oval (projective plane)}}

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, {{math|PG(2,q)}} with {{math|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 {{math|GF(q)}}.

The problem of testing whether a given polynomial over a finite field is a permutation polynomial can be solved in polynomial time.{{cite journal | year = 2005 | id = {{ECCC|2005|05|008}} | first = Neeraj | last = Kayal | title=Recognizing permutation functions in polynomial time | journal = Electronic Colloquium on Computational Complexity }} For earlier research on this problem, see: {{cite journal

| last1 = Ma | first1 = Keju

| last2 = von zur Gathen | first2 = Joachim | author2-link = Joachim von zur Gathen

| doi = 10.1007/BF01277957

| issue = 1

| journal = Computational Complexity

| mr = 1319494

| pages = 76–97

| title = The computational complexity of recognizing permutation functions

| volume = 5

| year = 1995}} {{cite journal

| last = Shparlinski | first = I. E.

| doi = 10.1007/BF01202000

| issue = 2

| journal = Computational Complexity

| mr = 1190826

| pages = 129–132

| title = A deterministic test for permutation polynomials

| volume = 2

| year = 1992}}

A polynomial $f\; \backslash in\; \backslash mathbb\{F\}\_q[x\_1,\backslash ldots,x\_n]$ is a permutation polynomial in {{mvar|n}} variables over $\backslash mathbb\{F\}\_q$ if the equation $f(x\_1,\backslash ldots,x\_n)\; =\; \backslash alpha$ has exactly $q^\{n-1\}$ solutions in $\backslash mathbb\{F\}\_q^n$ for each $\backslash alpha\; \backslash in\; \backslash mathbb\{F\}\_q$.{{harvnb|Mullen|Panario|2013|loc=p. 230}}

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 mobile telecommunication standard (see 3GPP technical specification 36.212 [http://www.3gpp.org/ftp/Specs/html-info/36212.htm 3GPP TS 36.212] e.g. page 14 in version 8.8.0).

Consider $g(x)\; =\; 2x^2+x$ for the ring Z/4Z.

One sees: {{nowrap|$g(0)\; =\; 0$;}} {{nowrap|$g(1)\; =\; 3$;}} {{nowrap|$g(2)\; =\; 2$;}} {{nowrap|$g(3)\; =\; 1$,}}

so the polynomial defines the permutation

$$\backslash 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: {{nowrap|$g(0)\; =\; 0$;}} {{nowrap|$g(1)\; =\; 3$;}} {{nowrap|$g(2)\; =\; 2$;}} {{nowrap|$g(3)\; =\; 5$;}} {{nowrap|$g(4)\; =\; 4$;}} {{nowrap|$g(5)\; =\; 7$;}} {{nowrap|$g(6)\; =\; 6$;}} {{nowrap|$g(7)\; =\; 1$,}} so the polynomial defines the permutation

$$\backslash 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^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, p>2 (Z/p^kZ) such polynomial defines a permutation if and only if $a\; \backslash equiv\; 0\; \backslash pmod\; p$ and $b\; \backslash not\; \backslash equiv\; 0\; \backslash 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 defines a permutation for the ring Z/nZ if and only if all the polynomials 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\}\; \backslash dots\; p\_l^\{k\_l\}$, assume that k₁ >1.

Consider $ax^2+bx$, such that $a=\; 0\; \backslash bmod\; p\_1$, but $a\backslash ne\; 0\; \backslash bmod\; p\_1^\{k\_1\}$; assume that $a\; =\; 0\; \backslash bmod\; p\_i^\{k\_i\}$, i > 1. And assume that $b\backslash ne\; 0\; \backslash bmod\; p\_i$ for all {{math|1=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 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 {{math|Z/12Z}} and polynomial $6x^2+x$.

It defines a permutation

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,{{cite journal | last=Fried | first=M. | title=On a conjecture of Schur | journal=Michigan Math. J. | year=1970 | pages=41–55 }} who gave a flawed proof of a false version of the result. Correct proofs have been given by Turnwald{{cite journal | last=Turnwald | first=G. | title=On Schur's conjecture | journal=J. Austral. Math. Soc. | year=1995 | volume=58 | issue=3 | pages=312–357 | doi=10.1017/S1446788700038349 }} and Müller.{{cite journal | last=Müller | first=P. | title=A Weil-bound free proof of Schur's conjecture | journal=Finite Fields and Their Applications | year=1997 | volume=3 | pages=25–32 | doi=10.1006/ffta.1996.0170 }}

{{reflist}}

• {{cite book|last=Dickson|first=L. E.|title=Linear Groups with an Exposition of the Galois Field Theory|year=1958|orig-year=1901 | publisher=Dover|location=New York}}
• {{cite journal|last1=Lidl|first1=Rudolf|last2=Mullen| first2=Gary L.|title=When Does a Polynomial over a Finite Field Permute the Elements of the Field?|journal=The American Mathematical Monthly|date=March 1988|volume=95|issue=3|pages=243–246| doi=10.2307/2323626|jstor=2323626 }}
• {{cite journal|last1=Lidl|first1=Rudolf|last2=Mullen| first2=Gary L.|title=When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II|journal=The American Mathematical Monthly|date=January 1993|volume=100|issue=1|pages=71–74| doi=10.2307/2324822|jstor=2324822 }}
• {{cite book | zbl=0866.11069 | last1=Lidl | first1=Rudolf | last2=Niederreiter | first2=Harald | author2-link=Harald Niederreiter | title=Finite fields | edition=2nd | series=Encyclopedia of Mathematics and Its Applications | volume=20 | publisher=Cambridge University Press | year=1997 | isbn=0-521-39231-4 | url-access=registration | url=https://archive.org/details/finitefields0000lidl_a8r3}} Chapter 7.
• {{cite book|first1=Gary L.|last1=Mullen|first2=Daniel|last2=Panario|title=Handbook of Finite Fields|year=2013|publisher=CRC Press|isbn=978-1-4398-7378-6}} 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}}

Category:Polynomials

Category:Permutations