View source for Dickson polynomial

The Dickson polynomial of the first kind of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201401.png" /> with parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201402.png" /> is defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201403.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201404.png" /> denotes the largest integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201405.png" />.

They satisfy the following recurrence:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201406.png" /></td> </tr></table>

where the two initial polynomials are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201407.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201408.png" />. A second closed form is given by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d1201409.png" /></td> </tr></table>

There is a functional equation, so that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014010.png" /> can be written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014011.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014012.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014013.png" /></td> </tr></table>

The generating function is:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014014.png" /></td> </tr></table>

Dickson polynomials satisfy a second-order differential equation which corresponds to the well-known differential equation for the classical [[Chebyshev polynomials|Chebyshev polynomials]]. In particular, the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014015.png" /> satisfies

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014016.png" /></td> </tr></table>

Dickson polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014017.png" /> are not unrelated to a well-studied class of polynomials. Consider the classical Chebyshev polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014018.png" />, defined for each integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014019.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014020.png" />. Over the complex numbers, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014021.png" /> so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014022.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014023.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014024.png" /></td> </tr></table>

Hence Dickson polynomials are related to the classical Chebyshev polynomials, and in fact some authors use the latter terminology.

L.E. Dickson was the first to seriously study various algebraic and number-theoretic properties of these polynomials. In particular, he studied these polynomials as part of his Ph.D. thesis at the University of Chicago in 1896; see also [[#References|[a4]]]. In 1923, I. Schur [[#References|[a16]]] suggested that these polynomials be named in honour of Dickson.

==Properties and applications.==
Dickson polynomials have various properties and applications in a variety of areas. Rather than trying to provide too many details here, only a few of these properties and applications are given below; see the various references for additional details. See [[#References|[a10]]] for a survey of algebraic and number-theoretic properties as well as applications of Dickson polynomials; see also [[#References|[a9]]] for a brief discussion of some of these properties.

Dickson polynomials play a fundamental role in the theory of permutation polynomials over finite fields. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014025.png" /> a prime power, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014026.png" /> denote the [[Finite field|finite field]] containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014027.png" /> elements. A [[Polynomial|polynomial]] with coefficients in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014028.png" /> is a permutation polynomial if it induces a one-to-one mapping on the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014029.png" />. It is known from [[#References|[a11]]], p. 356, that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014030.png" />, the Dickson polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014031.png" /> is a permutation polynomial on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014032.png" /> if and only if the [[Greatest common divisor|greatest common divisor]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014034.png" /> equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014035.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014036.png" /></td> </tr></table>

(When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014038.png" /> induces a permutation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014039.png" /> if and only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014040.png" />.) S.D. Cohen [[#References|[a3]]] has shown that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014041.png" /> is a large prime number compared to the degree of a polynomial, then the permutation polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014042.png" /> essentially comes from a Dickson polynomial. See [[#References|[a14]]] for a discussion of Dickson's work related to permutations (which Dickson called substitution quantics) and his work related to linear groups.

The real importance of Dickson polynomials in the theory of permutations comes from the Schur conjecture. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014043.png" /> is an odd prime number, reduce an integral polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014044.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014045.png" />, i.e. reduce the integer coefficients modulo the prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014046.png" />, so that one may view <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014047.png" /> as a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014048.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014049.png" /> denotes the field of integers modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014050.png" />. Using the [[Dirichlet theorem|Dirichlet theorem]] on prime numbers in an arithmetic progression, it is easy to see that the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014051.png" /> permutes the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014052.png" /> for infinitely many prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014053.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014054.png" />. Similarly, for a non-zero integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014055.png" />, the Dickson polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014056.png" /> permutes the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014057.png" /> for infinitely many prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014058.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014059.png" />, see [[#References|[a10]]], p. 75. In 1923, I. Schur conjectured in [[#References|[a16]]] that there are no other integral polynomials that permute the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014060.png" /> for infinitely many prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014061.png" /> other than compositions of power polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014062.png" />, Dickson polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014063.png" />, and linear polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014064.png" /> (here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014065.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014066.png" /> may be rational numbers). The first proof of this conjecture was given by M. Fried [[#References|[a5]]]. More recently, in [[#References|[a17]]] G. Turnwald proved this using only elementary (i.e., without complex analysis) arguments but the proof is still not easy. No truly easy proof is known (1998). In [[#References|[a13]]] G.L. Mullen proved a matrix analogue of Schur's conjecture.

Given a polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014067.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014068.png" />, define the value set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014069.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014070.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014071.png" />. Since a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014072.png" /> over a field can have at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014073.png" /> roots, one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014074.png" /></td> </tr></table>

Polynomials which achieve the above lower bound are called minimal value-set polynomials, see [[#References|[a12]]]. As noted in [[#References|[a7]]], polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014075.png" /> with value sets of small cardinality (less than twice the minimum) come from Dickson polynomials. As indicated in [[#References|[a2]]], Dickson polynomials provide one of the few classes of polynomials over finite fields whose value sets have been determined.

If the polynomials (one of each degree) of a class, called a permutable chain of polynomials, over an integral domain commute under composition, then this class must essentially come from the two classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014076.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014077.png" />, see [[#References|[a10]]], p. 13. Dickson polynomials provide a class of polynomials, one of each degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014078.png" />, which can be solved by radicals; see [[#References|[a18]]].

The construction of irreducible polynomials over finite fields (cf. also [[Irreducible polynomial|Irreducible polynomial]]) is an important problem and in [[#References|[a6]]] it is shown how Dickson polynomials can be effectively used in this regard. For computational work involving finite fields it is useful to have various kinds of bases for extension fields. In this regard, Dickson polynomials again play important roles; see [[#References|[a6]]] for polynomial bases and [[#References|[a1]]] and [[#References|[a15]]] for completely normal bases. Connections between optimal normal bases and Dickson polynomials are discussed in [[#References|[a10]]], Sect. 7.5.

Various applications of Dickson polynomials are discussed in [[#References|[a10]]], Chap. 7. These applications include [[Cryptology|cryptology]] for the secure transmission of information, pseudo-primality testing (cf. also [[Pseudo-prime|Pseudo-prime]]; [[Probabilistic primality test|Probabilistic primality test]]), complete mappings useful in the construction of sets of mutually orthogonal Latin squares (cf. also [[Latin square|Latin square]]), and character sums related to Dickson polynomials (cf. also [[Weyl sum|Weyl sum]]).

A combinatorial application of Dickson polynomials is developed in [[#References|[a8]]], where a study is made of Dickson–Stirling numbers. These generalize the well-studied Stirling numbers of the first and second kinds (cf. [[Combinatorial analysis|Combinatorial analysis]]). See [[#References|[a10]]], Sect. 7.7, for a construction of complete sets of mutually orthogonal Latin squares of prime power orders using Dickson polynomials.

As with the classical Chebyshev polynomials, Dickson polynomials of the second kind have also been studied. These polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014079.png" /> with parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014080.png" /> may be defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014081.png" /></td> </tr></table>

Dickson polynomials of the second kind satisfy the same recurrence as those of the first kind, except that the initial polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014082.png" />. See [[#References|[a10]]], Chap. 2, for other basic properties of these polynomials.

Contrary to the many known properties of the Dickson polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014083.png" /> of the first kind, as indicated in [[#References|[a10]]], very few properties of Dickson polynomials of the second kind are known (1998); see, for example, [[#References|[a10]]], p. 76, as this comment relates to permutations.

Dickson polynomials in several variables have been considered by a number of authors. For a brief survey see [[#References|[a10]]], Sects. 2.4, 3.5, and 4.3. A connection of Dickson polynomials in several variables to circulant determinants is given in [[#References|[a10]]], Sect. 7.8.

Dickson polynomials have been studied over a number of algebraic settings in addition to finite fields. In particular, various properties of Dickson polynomials have been obtained for the ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014084.png" /> of integers modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014085.png" /> as well as for the Galois ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014086.png" /> (a degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014087.png" /> [[Galois extension|Galois extension]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120140/d12014088.png" />), infinite algebraic extensions of finite fields, and matrix rings, see [[#References|[a10]]], Chaps. 4; 5.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Blessenohl,   K. Johnsen,   "Eine Verschärfung des Satzes von der Normalbasis"  ''J. Algebra'' , '''103'''  (1986)  pp. 141–159</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.-S. Chou,   J. Gomez-Calderon,   G.L. Mullen,   "Value sets of Dickson polynomials over finite fields"  ''J. Number Th.'' , '''30'''  (1988)  pp. 334–344</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S.D. Cohen,   "Proof of a conjecture of Chowla and Zassenhaus on permutation polynomials"  ''Canad. Math. Bull.'' , '''33'''  (1990)  pp. 230–234</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  L.E. Dickson,   "The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group"  ''Ann. of Math.'' , '''11'''  (1897)  pp. 65–120; 161–183</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Fried,   "On a conjecture of Schur"  ''Michigan Math. J.'' , '''17'''  (1970)  pp. 41–55</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  S. Gao,   G.L. Mullen,   "Dickson polynomials and irreducible polynomials over finite fields"  ''J. Number Th.'' , '''49'''  (1994)  pp. 118–132</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J. Gomez-Calderon,   D.J. Madden,   "Polynomials with small value sets over finite fields"  ''J. Number Th.'' , '''28'''  (1988)  pp. 167–188</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  L.C. Hsu,   G.L. Mullen,   P.J.-S. Shiue,   "Dickson–Stirling numbers"  ''Proc. Edinburgh Math. Soc.'' , '''40'''  (1997)  pp. 409–423</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R. Lidl,   G.L. Mullen,   "The world's most interesting class of integral polynomials"  ''Preprint''  (1999)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  R. Lidl,   G.L. Mullen,   G. Turnwald,   "Dickson Polynomials" , ''Pitman Monogr. Surveys Pure Appl. Math.'' , '''65''' , Longman  (1993)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  R. Lidl,   H. Niederreiter,   "Finite fields" , ''Encycl. Math. Appl.'' , '''20''' , Cambridge Univ. Press  (1997)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  W.H. Mills,   "Polynomials with minimal value sets"  ''Pacific J. Math.'' , '''14'''  (1964)  pp. 225–241</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  G.L. Mullen,   "Permutation polynomials: A matrix analogue of Schur's conjecture and a survey of recent results"  ''Finite Fields Appl.'' , '''1'''  (1995)  pp. 242–258</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  K.V.H. Parshall,   "A study in group theory: Leonard Eugene Dickson's  "Linear Groups" "  ''Math. Intelligencer'' , '''13''' :  1  (1991)  pp. 7–11</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  A. Scheerhorn,   "Dickson polynomials and completely normal elements over finite fields"  D. Gollmann (ed.) , ''Applications of Finite Fields'' , ''IMA Conf. Proc. Ser.'' , Oxford Univ. Press  (1996)  pp. 47–55</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  I. Schur,   "Über den Zusammenhang zwischen einem Problem der Zahlentheorie und einem Satz über algebraische Funktionen"  ''Sitzungsber. Preuss. Akad. Wiss. Berlin''  (1923)  pp. 123–134</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  G. Turnwald,   "On Schur's conjecture"  ''J. Austral. Math. Soc. Ser. A'' , '''58'''  (1995)  pp. 312–357</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  K.S. Williams,   "A generalization of Cardan's solution of the cubic"  ''Math. Gaz.'' , '''46'''  (1962)  pp. 221–223</TD></TR></table>