Permutation polynomial

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 ↦ g ( x ) {\displaystyle 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. [1] 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/nZ, such polynomials have also been studied and applied in the interleaver component of error detection and correction algorithms.[2][3]

## Single variable permutation polynomials over finite fields

[edit]

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 f ∈ Fq[x]) is a permutation polynomial of Fq if the function from Fq to itself defined by  c ↦ f ( c ) {\displaystyle c\mapsto f(c)} is a permutation of Fq.[4]

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

* the function  c ↦ f ( c ) {\displaystyle c\mapsto f(c)} is onto (surjective);
* the function  c ↦ f ( c ) {\displaystyle c\mapsto f(c)} is one-to-one (injective);
* f(x) = a has a solution in Fq for each a in Fq;
* f(x) = a has a unique solution in Fq for each a in Fq.

A characterization of which polynomials are permutation polynomials is given by

(Hermite's Criterion)[6][7] f ∈ Fq[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 ≤ t ≤ q − 2 and  t ≢ 0 ( mod p ) {\displaystyle t\not \equiv 0\\!{\pmod {p}}} , the reduction of f(x)t mod (xq − x) has degree ≤ q − 2.

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

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

### Small degree

[edit]

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:[10][7]

Normalized Permutation Polynomial of Fq | q

|

x {\displaystyle x} | any  q {\displaystyle q}
x 2 {\displaystyle x^{2}} |  q ≡ 0 ( mod 2 ) {\displaystyle q\equiv 0\\!{\pmod {2}}}
x 3 {\displaystyle x^{3}} |  q ≢ 1 ( mod 3 ) {\displaystyle q\not \equiv 1\\!{\pmod {3}}}
x 3 − a x {\displaystyle x^{3}-ax} ( a {\displaystyle a} not a square) |  q ≡ 0 ( mod 3 ) {\displaystyle q\equiv 0\\!{\pmod {3}}}
x 4 ± 3 x {\displaystyle x^{4}\pm 3x} |  q = 7 {\displaystyle q=7}
x 4 + a 1 x 2 + a 2 x {\displaystyle x^{4}+a_{1}x^{2}+a_{2}x} (if its only root in Fq is 0) |  q ≡ 0 ( mod 2 ) {\displaystyle q\equiv 0\\!{\pmod {2}}}
x 5 {\displaystyle x^{5}} |  q ≢ 1 ( mod 5 ) {\displaystyle q\not \equiv 1\\!{\pmod {5}}}
x 5 − a x {\displaystyle x^{5}-ax} ( a {\displaystyle a} not a fourth power) |  q ≡ 0 ( mod 5 ) {\displaystyle q\equiv 0\\!{\pmod {5}}}
x 5 + a x ( a 2 = 2 ) {\displaystyle x^{5}+ax\,(a^{2}=2)} |  q = 9 {\displaystyle q=9}
x 5 ± 2 x 2 {\displaystyle x^{5}\pm 2x^{2}} |  q = 7 {\displaystyle q=7}
x 5 + a x 3 ± x 2 + 3 a 2 x {\displaystyle x^{5}+ax^{3}\pm x^{2}+3a^{2}x} ( a {\displaystyle a} not a square) |  q = 7 {\displaystyle q=7}
x 5 + a x 3 + 5 − 1 a 2 x {\displaystyle x^{5}+ax^{3}+5^{-1}a^{2}x} ( a {\displaystyle a} arbitrary) |  q ≡ ± 2 ( mod 5 ) {\displaystyle q\equiv \pm 2\\!{\pmod {5}}}
x 5 + a x 3 + 3 a 2 x {\displaystyle x^{5}+ax^{3}+3a^{2}x} ( a {\displaystyle a} not a square) |  q = 13 {\displaystyle q=13}
x 5 − 2 a x 3 + a 2 x {\displaystyle x^{5}-2ax^{3}+a^{2}x} ( a {\displaystyle a} not a square) |  q ≡ 0 ( mod 5 ) {\displaystyle q\equiv 0\\!{\pmod {5}}}

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

### Some classes of permutation polynomials

[edit]

Beyond the above examples, the following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.[12]

* xn permutes GF(q) if and only if n and q − 1 are coprime (notationally, (n, q − 1) = 1).[13]
* If a is in GF(q) and n ≥ 1 then the Dickson polynomial (of the first kind) Dn(x,a) is defined by  D n ( x , a ) = ∑ j = 0 ⌊ n / 2 ⌋ n n − j ( n − j j ) ( − a ) j x n − 2 j . {\displaystyle D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.}

These can also be obtained from the recursion D n ( x , a ) = x D n − 1 ( x , a ) − a D n − 2 ( x , a ) , {\displaystyle D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),} with the initial conditions  D 0 ( x , a ) = 2 {\displaystyle D_{0}(x,a)=2} and  D 1 ( x , a ) = x {\displaystyle D_{1}(x,a)=x} . The first few Dickson polynomials are:

* D 2 ( x , a ) = x 2 − 2 a {\displaystyle D_{2}(x,a)=x^{2}-2a}
* D 3 ( x , a ) = x 3 − 3 a x {\displaystyle D_{3}(x,a)=x^{3}-3ax}
* D 4 ( x , a ) = x 4 − 4 a x 2 + 2 a 2 {\displaystyle D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}}
* D 5 ( x , a ) = x 5 − 5 a x 3 + 5 a 2 x . {\displaystyle D_{5}(x,a)=x^{5}-5ax^{3}+5a^{2}x.}

If a ≠ 0 and n > 1 then Dn(x, a) permutes GF(q) if and only if (n, q2 − 1) = 1.[14] If a = 0 then Dn(x, 0) = xn and the previous result holds.

* If GF(qr) is an extension of GF(q) of degree r, then the linearized polynomial L ( x ) = ∑ s = 0 r − 1 α s x q s , {\displaystyle L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},} with αs in GF(qr), is a linear operator on GF(qr) over GF(q). A linearized polynomial L(x) permutes GF(qr) if and only if 0 is the only root of L(x) in GF(qr).[13] This condition can be expressed algebraically as[15] det ( α i − j q j ) ≠ 0 ( i , j = 0 , 1 , … , r − 1 ) . {\displaystyle \det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).}

The linearized polynomials that are permutation polynomials over GF(qr) form a group under the operation of composition modulo  x q r − x {\displaystyle x^{q^{r}}-x} , which is known as the Betti-Mathieu group, isomorphic to the general linear group GL(r, Fq).[15]

* If g(x) is in the polynomial ring Fq[x] and g(xs) has no nonzero root in GF(q) when s divides q − 1, and r > 1 is relatively prime (coprime) to q − 1, then xr(g(xs))(q \- 1)/s permutes GF(q).[7]
* 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 + a x {\displaystyle x^{(q+m-1)/m}+ax} where m divides q − 1, and  x r ( x d − a ) ( p n − 1 ) / d {\displaystyle x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}} where d divides pn − 1.

### Exceptional polynomials

[edit]

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

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

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

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.[18] (See Schur's conjecture below).

## Geometric examples

[edit]

Main article: 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, 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

[edit]

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

## Permutation polynomials in several variables over finite fields

[edit]

A polynomial  f ∈ F q [ x 1 , … , x n ] {\displaystyle f\in \mathbb {F} _{q}[x_{1},\ldots ,x_{n}]} is a permutation polynomial in n variables over F q {\displaystyle \mathbb {F} _{q}} if the equation  f ( x 1 , … , x n ) = α {\displaystyle f(x_{1},\ldots ,x_{n})=\alpha } has exactly  q n − 1 {\displaystyle q^{n-1}} solutions in  F q n {\displaystyle \mathbb {F} _{q}^{n}} for each  α ∈ F q {\displaystyle \alpha \in \mathbb {F} _{q}} .[20]

## Quadratic permutation polynomials (QPP) over finite rings

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

### Simple examples

[edit]

Consider  g ( x ) = 2 x 2 + x {\displaystyle g(x)=2x^{2}+x} for the ring Z/4Z. One sees:  g ( 0 ) = 0 {\displaystyle g(0)=0} ; g ( 1 ) = 3 {\displaystyle g(1)=3} ; g ( 2 ) = 2 {\displaystyle g(2)=2} ; g ( 3 ) = 1 {\displaystyle g(3)=1} , so the polynomial defines the permutation  ( 0 1 2 3 0 3 2 1 ) . {\displaystyle {\begin{pmatrix}0&1&2&3\\\0&3&2&1\end{pmatrix}}.}

Consider the same polynomial  g ( x ) = 2 x 2 + x {\displaystyle g(x)=2x^{2}+x} for the other ring Z/8Z. One sees:  g ( 0 ) = 0 {\displaystyle g(0)=0} ; g ( 1 ) = 3 {\displaystyle g(1)=3} ; g ( 2 ) = 2 {\displaystyle g(2)=2} ; g ( 3 ) = 5 {\displaystyle g(3)=5} ; g ( 4 ) = 4 {\displaystyle g(4)=4} ; g ( 5 ) = 7 {\displaystyle g(5)=7} ; g ( 6 ) = 6 {\displaystyle g(6)=6} ; g ( 7 ) = 1 {\displaystyle g(7)=1} , so the polynomial defines the permutation  ( 0 1 2 3 4 5 6 7 0 3 2 5 4 7 6 1 ) . {\displaystyle {\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 ) = a x 2 + b x + c {\displaystyle 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, p>2 (Z/pkZ) such polynomial defines a permutation if and only if  a ≡ 0 ( mod p ) {\displaystyle a\equiv 0{\pmod {p}}} and  b ≢ 0 ( mod p ) {\displaystyle b\not \equiv 0{\pmod {p}}} .

### Rings Z/nZ

[edit]

Consider  n = p 1 k 1 p 2 k 2 . . . p l k l {\displaystyle 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 + ∑ 0 < i ≤ M a i x i {\textstyle g(x)=a_{0}+\sum _{0<i\leq 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 + ∑ 0 < i ≤ M a i , p t x i {\textstyle g_{p_{t}}(x)=a_{0,p_{t}}+\sum _{0<i\leq M}a_{i,p_{t}}x^{i}} defines the permutations for all rings  Z / p t k t Z {\displaystyle Z/p_{t}^{k_{t}}Z} , where  a j , p t {\displaystyle a_{j,p_{t}}} are remainders of  a j {\displaystyle a_{j}} modulo  p t k t {\displaystyle 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 {\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}} , assume that k1 >1\.

Consider  a x 2 + b x {\displaystyle ax^{2}+bx} , such that  a = 0 mod p 1 {\displaystyle a=0{\bmod {p}}_{1}} , but  a ≠ 0 mod p 1 k 1 {\displaystyle a\neq 0{\bmod {p}}_{1}^{k_{1}}} ; assume that  a = 0 mod p i k i {\displaystyle a=0{\bmod {p}}_{i}^{k_{i}}} , i > 1\. And assume that  b ≠ 0 mod p i {\displaystyle b\neq 0{\bmod {p}}_{i}} for all i = 1, ..., l. (For example, one can take  a = p 1 p 2 k 2 . . . p l k l {\displaystyle a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}} and  b = 1 {\displaystyle 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  6 x 2 + x {\displaystyle 6x^{2}+x} . It defines a permutation  ( 0 1 2 3 4 5 6 7 8 ⋯ 0 7 2 9 4 11 6 1 8 ⋯ ) . {\begin{pmatrix}0&1&2&3&4&5&6&7&8&\cdots \\\0&7&2&9&4&11&6&1&8&\cdots \end{pmatrix}}.

## Higher degree polynomials over finite rings

[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 ) ≠ 0 mod p {\displaystyle g'(x)\neq 0{\bmod {p}}} for all x in Z/pkZ, where g′(x) is the formal derivative of g(x).[22]

## 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,[23] who gave a flawed proof of a false version of the result. Correct proofs have been given by Turnwald[24] and Müller.[25]

## Notes

[edit]

1. ^ Li, Chengqing; Lu, Xiaoxiong (2025). "The graph structure of Chebyshev permutation polynomials over ring  Z p k {\displaystyle Z_{p^{k}}} ". IEEE Transactions on Information Theory. 71: 1419–1433\. doi:10.1109/TIT.2024.3522095.
2. ^ Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". IEEE Transactions on Information Theory. 53 (6): 2116–2132\. arXiv:cs/0601048. doi:10.1109/TIT.2007.896870.
3. ^ Takeshita, Oscar (2005). "A New Construction for LDPC Codes using Permutation Polynomials over Integer Rings". arXiv:cs/0506091.
4. ^ Mullen & Panario 2013, p. 215
5. ^ Lidl & Niederreiter 1997, p. 348
6. ^ Lidl & Niederreiter 1997, p. 349
7. ^ a b c Mullen & Panario 2013, p. 216
8. ^ Lidl & Mullen (1988)
9. ^ Lidl & Mullen (1993)
10. ^ Dickson 1958, pg. 63
11. ^ Mullen & Panario 2013, p. 217
12. ^ Lidl & Mullen 1988, p. 244
13. ^ a b Lidl & Niederreiter 1997, p. 351
14. ^ Lidl & Niederreiter 1997, p. 356
15. ^ a b Lidl & Niederreiter 1997, p. 362
16. ^ Mullen & Panario 2013, p. 236
17. ^ a b Mullen & Panario 2013, p. 238
18. ^ Mullen & Panario 2013, p. 239
19. ^ 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.
20. ^ Mullen & Panario 2013, p. 230
21. ^ 3GPP TS 36.212
22. ^ Sun, Jing; Takeshita, Oscar (2005). "Interleaver for Turbo Codes Using Permutation Polynomials Over Integer Rings". IEEE Transactions on Information Theory. 51 (1): 102.
23. ^ Fried, M. (1970). "On a conjecture of Schur". Michigan Math. J.: 41–55.
24. ^ Turnwald, G. (1995). "On Schur's conjecture". J. Austral. Math. Soc. 58 (3): 312–357\. doi:10.1017/S1446788700038349.
25. ^ Müller, P. (1997). "A Weil-bound free proof of Schur's conjecture". Finite Fields and Their Applications. 3: 25–32\. doi:10.1006/ffta.1996.0170.

## 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. JSTOR 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. JSTOR 2324822.
* Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields. Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069. Chapter 7.
* Mullen, Gary L.; Panario, Daniel (2013). Handbook of Finite Fields. CRC Press. ISBN 978-1-4398-7378-6. Chapter 8.
* Shallue, C.J.; Wanless, I.M. (March 2013). "Permutation polynomials and orthomorphism polynomials of degree six". Finite Fields and Their Applications. 20: 84–92\. doi:10.1016/j.ffa.2012.12.003.