# Permutation polynomial > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Permutation_polynomial > Markdown URL: https://mediated.wiki/source/Permutation_polynomial.md > Source: https://en.wikipedia.org/wiki/Permutation_polynomial > Source revision: 1340784573 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) In [mathematics](/source/Mathematics), a **permutation polynomial** (for a given [ring](/source/Ring_(mathematics))) is a [polynomial](/source/Polynomial) that acts as a [permutation](/source/Permutation) of the elements of the ring, i.e. the map x \mapsto g(x) is a [bijection](/source/Bijection). In case the ring is a [finite field](/source/Finite_field), the [Dickson polynomials](/source/Dickson_polynomials), which are closely related to the [Chebyshev polynomials](/source/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**/*n***Z**, such polynomials have also been studied and applied in the [interleaver](/source/Interleaver) component of [error detection and correction](/source/Error_detection_and_correction) algorithms.[2][3] ## Single variable permutation polynomials over finite fields Let **F***q* = GF(*q*) be the finite field of [characteristic](/source/Characteristic_(field_theory)) p, that is, the field having q elements where *q* = *p**e* for some prime p. A polynomial f with coefficients in **F***q* (symbolically written as *f* ∈ **F***q*[*x*]) is a *permutation polynomial* of **F***q* if the function from **F***q* to itself defined by c \mapsto f(c) is a permutation of **F***q*.[4] Due to the finiteness of **F***q*, this definition can be expressed in several equivalent ways:[5] - the function c \mapsto f(c) is *onto* ([surjective](/source/Surjective_function)); - the function c \mapsto f(c) is *one-to-one* ([injective](/source/Injective_function)); - *f*(*x*) = *a* has a solution in **F***q* for each a in **F***q*; - *f*(*x*) = *a* has a *unique* solution in **F***q* for each a in **F***q*. A characterization of which polynomials are permutation polynomials is given by (*[Hermite](/source/Hermite)'s Criterion*)[6][7] *f* ∈ **F***q*[*x*] is a permutation polynomial of **F***q* [if and only if](/source/If_and_only_if) the following two conditions hold: 1. f has exactly one root in **F***q*; 1. for each integer t with 1 ≤ *t* ≤ *q* − 2 and t \not \equiv 0 \!\pmod p, the reduction of *f*(*x*)*t* mod (*x**q* − *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](/source/Monic_polynomial), *g*(0) = 0 and (provided the characteristic p does not divide the degree n of the polynomial) the coefficient of *x**n*−1 is 0. There are many open questions concerning permutation polynomials defined over finite fields.[8][9] ### Small degree Hermite's criterion is computationally intensive and can be difficult to use in making theoretical conclusions. However, [Dickson](/source/Leonard_Eugene_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 any q x^2 q \equiv 0\! \pmod 2 x^3 q \not \equiv 1 \! \pmod 3 x^3 - ax (a not a square) q \equiv 0 \! \pmod 3 x^4 \pm 3x q = 7 x^4 + a_1 x^2 + a_2 x (if its only root in Fq is 0) q \equiv 0 \! \pmod 2 x^5 q \not \equiv 1 \! \pmod 5 x^5 - ax (a not a fourth power) q \equiv 0 \! \pmod 5 x^5 + ax \,(a^2 = 2) q = 9 x^5 \pm 2x^2 q = 7 x^5 + ax^3 \pm x^2 + 3a^2 x (a not a square) q = 7 x^5 + ax^3 + 5^{-1} a^2 x (a arbitrary) q \equiv \pm 2 \! \pmod 5 x^5 + ax^3 + 3a^2 x (a not a square) q = 13 x^5 - 2ax^3 + a^2x (a not a square) 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 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] - *x**n* permutes GF(*q*) if and only if n and *q* − 1 are [coprime](/source/Coprime_integers) (notationally, (*n*, *q* − 1) = 1).[13] - If a is in GF(*q*) and *n* ≥ 1 then the [Dickson polynomial](/source/Dickson_polynomial) (of the first kind) *D**n*(*x*,*a*) is defined by 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](/source/Recursive_relation) 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 *a* ≠ 0 and *n* > 1 then *D**n*(*x*, *a*) permutes GF(*q*) if and only if (*n*, *q*2 − 1) = 1.[14] If *a* = 0 then *D**n*(*x*, 0) = *x**n* and the previous result holds. - If GF(*q**r*) is an [extension](/source/Field_extension) of GF(*q*) of degree r, then the [linearized polynomial](/source/Linearised_polynomial) L(x) = \sum_{s=0}^{r-1} \alpha_s x^{q^s}, with α*s* in GF(*q**r*), is a [linear operator](/source/Linear_operator) on GF(*q**r*) over GF(*q*). A linearized polynomial *L*(*x*) permutes GF(*q**r*) if and only if 0 is the only root of *L*(*x*) in GF(*q**r*).[13] This condition can be expressed algebraically as[15] \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(*q**r*) form a [group](/source/Group_(mathematics)) under the operation of composition modulo x^{q^r} - x, which is known as the Betti-Mathieu group, isomorphic to the [general linear group](/source/General_linear_group) GL(*r*, **F***q*).[15] - If *g*(*x*) is in the polynomial ring **F***q*[*x*] and *g*(*x**s*) has no nonzero root in GF(*q*) when s divides *q* − 1, and *r* > 1 is relatively prime (coprime) to *q* − 1, then *x**r*(*g*(*x**s*))(*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} + ax where m divides *q* − 1, and x^r \left(x^d - a\right)^{\left(p^n - 1\right)/d} where d divides *p**n* − 1. ### Exceptional polynomials An **exceptional polynomial** over GF(*q*) is a polynomial in **F***q*[*x*] which is a permutation polynomial on GF(*q**m*) for infinitely many m.[16] A permutation polynomial over GF(*q*) of degree at most *q*1/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 Main article: [Oval (projective plane)](/source/Oval_(projective_plane)) In [finite geometry](/source/Finite_geometry) coordinate descriptions of certain point sets can provide examples of permutation polynomials of higher degree. In particular, the points forming an [oval](/source/Oval_(projective_plane)) in a finite [projective plane](/source/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](/source/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](/source/Polynomial_time).[19] ## Permutation polynomials in several variables over finite fields A polynomial f \in \mathbb{F}_q[x_1,\ldots,x_n] is a **permutation polynomial in n variables over** \mathbb{F}_q if the equation f(x_1,\ldots,x_n) = \alpha has exactly q^{n-1} solutions in \mathbb{F}_q^n for each \alpha \in \mathbb{F}_q.[20] ## Quadratic permutation polynomials (QPP) over finite rings For the [finite ring](/source/Finite_ring) **Z**/*n***Z** one can construct quadratic permutation polynomials. Actually it is possible if and only if *n* is divisible by *p*2 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](/source/Interleaver) component of [turbo codes](/source/Turbo_codes) in [3GPP Long Term Evolution](/source/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 Consider g(x) = 2x^2+x for the ring **Z**/4**Z**. One sees: g(0) = 0; g(1) = 3; g(2) = 2; g(3) = 1, so the polynomial defines the permutation \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**/*8***Z**. One sees: g(0) = 0; g(1) = 3; g(2) = 2; g(3) = 5; g(4) = 4; g(5) = 7; g(6) = 6; g(7) = 1, so the polynomial defines the permutation \begin{pmatrix} 0 &1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 &3 & 2 & 5 & 4 & 7 & 6 & 1 \end{pmatrix} . ### Rings Z/*pk*Z Consider g(x) = ax^2+bx+c for the ring **Z**/*pk***Z**. **Lemma:** for *k*=1 (i.e. **Z**/*p***Z**) 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**/*pk***Z**) such polynomial defines a permutation if and only if a \equiv 0 \pmod p and b \not \equiv 0 \pmod p. ### Rings Z/*n*Z Consider 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+ \sum_{0 < i \leq M} a_i x^i defines a permutation for the ring **Z**/*n***Z** if and only if all the polynomials 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, 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} \dots p_l^{k_l}, assume that *k*1 >1. Consider ax^2+bx, such that a= 0 \bmod p_1, but a\ne 0 \bmod p_1^{k_1}; assume that a = 0 \bmod p_i^{k_i}, *i* > 1. And assume that b\ne 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} and 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](/source/Prime_number) we should use the lemma discussed previously to see that it defines the permutation. For example, consider **Z**/12**Z** and polynomial 6x^2+x. It defines a permutation \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 A polynomial *g*(*x*) for the ring **Z**/*pk***Z** is a permutation polynomial if and only if it permutes the [finite field](/source/Finite_field) **Z**/*p***Z** and g'(x) \ne 0 \bmod p for all *x* in **Z**/*pk***Z**, where *g*′(*x*) is the [formal derivative](/source/Formal_derivative) of *g*(*x*).[22] ## Schur's conjecture Let *K* be an [algebraic number field](/source/Algebraic_number_field) with *R* the [ring of integers](/source/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](/source/Prime_ideal) *P*, then *f* is the composition of Dickson polynomials, degree-one polynomials, and polynomials of the form *x**k*. In fact, [Schur](/source/Issai_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 1. Li, Chengqing & Lu, Xiaoxiong (2025). "The graph structure of Chebyshev permutation polynomials over ring Z_{p^k}". *IEEE Transactions on Information Theory*. **71**: 1419–1433. [doi:10.1109/TIT.2024.3522095](https://doi.org/10.1109/TIT.2024.3522095) 1. Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". *IEEE Transactions on Information Theory*. **53** (6): 2116–2132. [arXiv:cs/0601048](https://arxiv.org/abs/cs/0601048). [doi:10.1109/TIT.2007.896870](https://doi.org/10.1109/TIT.2007.896870) 1. Takeshita, Oscar (2005). "A New Construction for [LDPC Codes](/source/Low-density_parity-check_code) using Permutation Polynomials over Integer Rings". [arXiv:cs/0506091](https://arxiv.org/abs/cs/0506091) 1. Mullen & Panario 2013, p. 215 1. Lidl & Niederreiter 1997, p. 348 1. Lidl & Niederreiter 1997, p. 349 1. Mullen & Panario 2013, p. 216 1. Lidl & Mullen (1988) 1. Lidl & Mullen (1993) 1. Dickson 1958, pg. 63 1. Mullen & Panario 2013, p. 217 1. Lidl & Mullen 1988, p. 244 1. Lidl & Niederreiter 1997, p. 351 1. Lidl & Niederreiter 1997, p. 356 1. Lidl & Niederreiter 1997, p. 362 1. Mullen & Panario 2013, p. 236 1. Mullen & Panario 2013, p. 238 1. Mullen & Panario 2013, p. 239 1. Kayal, Neeraj (2005). "Recognizing permutation functions in polynomial time". *Electronic Colloquium on Computational Complexity* 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](https://doi.org/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](https://doi.org/10.1007/BF01202000). MR 1190826. 1. Mullen & Panario 2013, p. 230 1. [3GPP TS 36.212](http://www.3gpp.org/ftp/Specs/html-info/36212.htm) 1. Sun, Jing & Takeshita, Oscar (2005). "Interleaver for Turbo Codes Using Permutation Polynomials Over Integer Rings". *IEEE Transactions on Information Theory*. **51** (1): 102. 1. Fried, M. (1970). "On a conjecture of Schur". *Michigan Math. J.* 1. Turnwald, G. (1995). "On Schur's conjecture". *J. Austral. Math. Soc.*. **58** (3): 312–357. [doi:10.1017/S1446788700038349](https://doi.org/10.1017/S1446788700038349) 1. 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](https://doi.org/10.1006/ffta.1996.0170) ## References - 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](https://doi.org/10.2307/2323626). [JSTOR 2323626](https://www.jstor.org/stable/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](https://doi.org/10.2307/2324822). [JSTOR 2324822](https://www.jstor.org/stable/2324822) - Lidl, Rudolf & Niederreiter, Harald (1997). [*Finite fields*](https://archive.org/details/finitefields0000lidl_a8r3). Vol. 20. Encyclopedia of Mathematics and Its Applications. 2nd ed. [Cambridge University Press](/source/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](https://doi.org/10.1016/j.ffa.2012.12.003) --- Adapted from the Wikipedia article [Permutation polynomial](https://en.wikipedia.org/wiki/Permutation_polynomial) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Permutation_polynomial?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.