Namespaces
Variants
Actions

Difference between revisions of "Dickson polynomial"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (AUTOMATIC EDIT (latexlist): Replaced 88 formulas out of 88 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
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
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<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>
+
Out of 88 formulas, 88 were replaced by TEX code.-->
  
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" />.
+
{{TEX|semi-auto}}{{TEX|done}}
 +
The Dickson polynomial of the first kind of degree $n$ with parameter $a$ is defined by
 +
 
 +
\begin{equation*} D_ { n } ( x , a ) = \sum _ { i = 0 } ^ { \lfloor n / 2 \rfloor } \frac { n } { n - i } \left( \begin{array} { c } { n - i } \\ { i } \end{array} \right) ( - a ) ^ { i } x ^ { n - 2 i }, \end{equation*}
 +
 
 +
where $\lfloor n / 2 \rfloor$ denotes the largest integer $\leq n / 2$.
  
 
They satisfy the following recurrence:
 
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>
+
\begin{equation*} D _ { n } ( x , a ) = x D _ { n - 1 } ( x , a ) - a D _ { n - 2 } ( x , a ) , \quad n \geq 2, \end{equation*}
  
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
+
where the two initial polynomials are $D _ { 0 } ( x , a ) = 2$ and $D _ { 1 } ( x , a ) = x$. 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>
+
\begin{equation*} D _ { n } ( x , a ) = \left( \frac { x + \sqrt { x ^ { 2 } - 4 a } } { 2 } \right) ^ { n } + \left( \frac { x - \sqrt { x ^ { 2 } - 4 a } } { 2 } \right) ^ { n }. \end{equation*}
  
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
+
There is a functional equation, so that if $x$ can be written as $x = u + a / u$ for some $u$, 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>
+
\begin{equation*} D _ { n } ( x , a ) = u ^ { n } + \frac { a ^ { n } } { u ^ { n } }. \end{equation*}
  
 
The generating function is:
 
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>
+
\begin{equation*} \sum _ { n = 0 } ^ { \infty } D _ { n } ( x , a ) z ^ { n } = \frac { 2 - x z } { 1 - x z + a z ^ { 2 } }. \end{equation*}
  
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
+
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 $D _ { n } ( x , a )$ 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>
+
\begin{equation*} ( x ^ { 2 } - 4 a ) y ^ { \prime \prime } + x y ^ { \prime } - n ^ { 2 } y = 0. \end{equation*}
  
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" />,
+
Dickson polynomials $D _ { n } ( x , a )$ are not unrelated to a well-studied class of polynomials. Consider the classical Chebyshev polynomials $T _ { n } ( x )$, defined for each integer $n \geq 0$ by $T _ { n } ( x ) = \operatorname { cos } ( n \operatorname { arccos } x )$. Over the complex numbers, if $u = e ^ { i \alpha }$ so that $x = u + 1 / u = 2 \operatorname { cos } \alpha$,
  
<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>
+
\begin{equation*} D _ { n } ( x , 1 ) = u ^ { n } + u ^ { - n } = e ^ { i n \alpha } + e ^ { - i n \alpha } = \end{equation*}
  
<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>
+
\begin{equation*} = 2 \operatorname { cos } ( n \alpha ) = 2 T _ { n } ( \operatorname { cos } \alpha ) = 2 T _ { n } \left( \frac { x } { 2 } \right). \end{equation*}
  
 
Hence Dickson polynomials are related to the classical Chebyshev polynomials, and in fact some authors use the latter terminology.
 
Hence Dickson polynomials are related to the classical Chebyshev polynomials, and in fact some authors use the latter terminology.
Line 38: Line 46:
 
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 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" />:
+
Dickson polynomials play a fundamental role in the theory of permutation polynomials over finite fields. For $q$ a prime power, let $\mathbf{F} _ { q }$ denote the [[Finite field|finite field]] containing $q$ elements. A [[Polynomial|polynomial]] with coefficients in $\mathbf{F} _ { q }$ is a permutation polynomial if it induces a one-to-one mapping on the field $\mathbf{F} _ { q }$. It is known from [[#References|[a11]]], p. 356, that for $a \neq 0 \in{\bf F}_ { q }$, the Dickson polynomial $D _ { n } ( x , a )$ is a permutation polynomial on $\mathbf{F} _ { q }$ if and only if the [[Greatest common divisor|greatest common divisor]] of $n$ and $q ^ { 2 } - 1$ equals $1$:
  
<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>
+
\begin{equation*} ( n , q ^ { 2 } - 1 ) = 1. \end{equation*}
  
(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.
+
(When $a = 0$, $D _ { n } ( x , 0 ) = x ^ { n }$ induces a permutation on $\mathbf{F} _ { q }$ if and only $( n , q - 1 ) = 1$.) S.D. Cohen [[#References|[a3]]] has shown that if $p$ is a large prime number compared to the degree of a polynomial, then the permutation polynomial $f$ 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.
+
The real importance of Dickson polynomials in the theory of permutations comes from the Schur conjecture. If $p$ is an odd prime number, reduce an integral polynomial $f ( x )$ modulo $p$, i.e. reduce the integer coefficients modulo the prime number $p$, so that one may view $f$ as a function $f : \mathbf{F} _ { p } \rightarrow \mathbf{F} _ { p }$, where $\mathbf{F} _ { p }$ denotes the field of integers modulo $p$. Using the [[Dirichlet theorem|Dirichlet theorem]] on prime numbers in an arithmetic progression, it is easy to see that the polynomial $x ^ { n }$ permutes the field $\mathbf{F} _ { p }$ for infinitely many prime numbers $p$ if and only if $( n , 2 ) = 1$. Similarly, for a non-zero integer $a$, the Dickson polynomial $D _ { n } ( x , a )$ permutes the field $\mathbf{F} _ { p }$ for infinitely many prime numbers $p$ if and only if $( n , 6 ) = 1$, see [[#References|[a10]]], p. 75. In 1923, I. Schur conjectured in [[#References|[a16]]] that there are no other integral polynomials that permute the field $\mathbf{F} _ { p }$ for infinitely many prime numbers $p$ other than compositions of power polynomials $x ^ { n }$, Dickson polynomials $D _ { n } ( x , a )$, and linear polynomials $a x + b$ (here, $a$ and $b$ 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
+
Given a polynomial $f$ over $\mathbf{F} _ { q }$, define the value set $V _ { f }$ of $f$ by $V _ { f } = \{ f ( a ) : a \in {\bf F} _ { q } \}$. Since a polynomial of degree $n$ over a field can have at most $n$ 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>
+
\begin{equation*} \lfloor \frac { q - 1 } { n } \rfloor + 1 \leq | V _ { f } | \leq q. \end{equation*}
  
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.
+
Polynomials which achieve the above lower bound are called minimal value-set polynomials, see [[#References|[a12]]]. As noted in [[#References|[a7]]], polynomials of degree $n$ 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]]].
+
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 $\{ x ^ { n } \}$ and $\{ D _ { N } ( x , 1 ) \}$, see [[#References|[a10]]], p. 13. Dickson polynomials provide a class of polynomials, one of each degree $n \geq 1$, 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.
 
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.
Line 60: Line 68:
 
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.
 
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
+
As with the classical Chebyshev polynomials, Dickson polynomials of the second kind have also been studied. These polynomials of degree $n$ with parameter $a$ 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>
+
\begin{equation*} E _ { n } ( x , a ) = \sum _ { i = 0 } ^ { | n / 2 | } \left( \begin{array} { c } { n - i } \\ { i } \end{array} \right) ( - a ) ^ { i } x ^ { n - 2 i }. \end{equation*}
  
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.
+
Dickson polynomials of the second kind satisfy the same recurrence as those of the first kind, except that the initial polynomial $E _ { 0 } ( x , a ) = 1$. 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.
+
Contrary to the many known properties of the Dickson polynomials $D _ { n } ( x , a )$ 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 matrix|circulant determinant]]s is given in [[#References|[a10]]], Sect. 7.8.
 
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 matrix|circulant determinant]]s 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.
+
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 $\mathbf{Z} _ { n }$ of integers modulo $n$ as well as for the Galois ring $\operatorname{GR} ( p ^ { r } , s )$ (a degree $s$ [[Galois extension|Galois extension]] of ${\bf Z} _ { p ^ r}$), infinite algebraic extensions of finite fields, and matrix rings, see [[#References|[a10]]], Chaps. 4; 5.
  
 
====References====
 
====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>
+
<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>

Latest revision as of 16:45, 1 July 2020

The Dickson polynomial of the first kind of degree $n$ with parameter $a$ is defined by

\begin{equation*} D_ { n } ( x , a ) = \sum _ { i = 0 } ^ { \lfloor n / 2 \rfloor } \frac { n } { n - i } \left( \begin{array} { c } { n - i } \\ { i } \end{array} \right) ( - a ) ^ { i } x ^ { n - 2 i }, \end{equation*}

where $\lfloor n / 2 \rfloor$ denotes the largest integer $\leq n / 2$.

They satisfy the following recurrence:

\begin{equation*} D _ { n } ( x , a ) = x D _ { n - 1 } ( x , a ) - a D _ { n - 2 } ( x , a ) , \quad n \geq 2, \end{equation*}

where the two initial polynomials are $D _ { 0 } ( x , a ) = 2$ and $D _ { 1 } ( x , a ) = x$. A second closed form is given by

\begin{equation*} D _ { n } ( x , a ) = \left( \frac { x + \sqrt { x ^ { 2 } - 4 a } } { 2 } \right) ^ { n } + \left( \frac { x - \sqrt { x ^ { 2 } - 4 a } } { 2 } \right) ^ { n }. \end{equation*}

There is a functional equation, so that if $x$ can be written as $x = u + a / u$ for some $u$, then

\begin{equation*} D _ { n } ( x , a ) = u ^ { n } + \frac { a ^ { n } } { u ^ { n } }. \end{equation*}

The generating function is:

\begin{equation*} \sum _ { n = 0 } ^ { \infty } D _ { n } ( x , a ) z ^ { n } = \frac { 2 - x z } { 1 - x z + a z ^ { 2 } }. \end{equation*}

Dickson polynomials satisfy a second-order differential equation which corresponds to the well-known differential equation for the classical Chebyshev polynomials. In particular, the polynomial $D _ { n } ( x , a )$ satisfies

\begin{equation*} ( x ^ { 2 } - 4 a ) y ^ { \prime \prime } + x y ^ { \prime } - n ^ { 2 } y = 0. \end{equation*}

Dickson polynomials $D _ { n } ( x , a )$ are not unrelated to a well-studied class of polynomials. Consider the classical Chebyshev polynomials $T _ { n } ( x )$, defined for each integer $n \geq 0$ by $T _ { n } ( x ) = \operatorname { cos } ( n \operatorname { arccos } x )$. Over the complex numbers, if $u = e ^ { i \alpha }$ so that $x = u + 1 / u = 2 \operatorname { cos } \alpha$,

\begin{equation*} D _ { n } ( x , 1 ) = u ^ { n } + u ^ { - n } = e ^ { i n \alpha } + e ^ { - i n \alpha } = \end{equation*}

\begin{equation*} = 2 \operatorname { cos } ( n \alpha ) = 2 T _ { n } ( \operatorname { cos } \alpha ) = 2 T _ { n } \left( \frac { x } { 2 } \right). \end{equation*}

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 [a4]. In 1923, I. Schur [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 [a10] for a survey of algebraic and number-theoretic properties as well as applications of Dickson polynomials; see also [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 $q$ a prime power, let $\mathbf{F} _ { q }$ denote the finite field containing $q$ elements. A polynomial with coefficients in $\mathbf{F} _ { q }$ is a permutation polynomial if it induces a one-to-one mapping on the field $\mathbf{F} _ { q }$. It is known from [a11], p. 356, that for $a \neq 0 \in{\bf F}_ { q }$, the Dickson polynomial $D _ { n } ( x , a )$ is a permutation polynomial on $\mathbf{F} _ { q }$ if and only if the greatest common divisor of $n$ and $q ^ { 2 } - 1$ equals $1$:

\begin{equation*} ( n , q ^ { 2 } - 1 ) = 1. \end{equation*}

(When $a = 0$, $D _ { n } ( x , 0 ) = x ^ { n }$ induces a permutation on $\mathbf{F} _ { q }$ if and only $( n , q - 1 ) = 1$.) S.D. Cohen [a3] has shown that if $p$ is a large prime number compared to the degree of a polynomial, then the permutation polynomial $f$ essentially comes from a Dickson polynomial. See [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 $p$ is an odd prime number, reduce an integral polynomial $f ( x )$ modulo $p$, i.e. reduce the integer coefficients modulo the prime number $p$, so that one may view $f$ as a function $f : \mathbf{F} _ { p } \rightarrow \mathbf{F} _ { p }$, where $\mathbf{F} _ { p }$ denotes the field of integers modulo $p$. Using the Dirichlet theorem on prime numbers in an arithmetic progression, it is easy to see that the polynomial $x ^ { n }$ permutes the field $\mathbf{F} _ { p }$ for infinitely many prime numbers $p$ if and only if $( n , 2 ) = 1$. Similarly, for a non-zero integer $a$, the Dickson polynomial $D _ { n } ( x , a )$ permutes the field $\mathbf{F} _ { p }$ for infinitely many prime numbers $p$ if and only if $( n , 6 ) = 1$, see [a10], p. 75. In 1923, I. Schur conjectured in [a16] that there are no other integral polynomials that permute the field $\mathbf{F} _ { p }$ for infinitely many prime numbers $p$ other than compositions of power polynomials $x ^ { n }$, Dickson polynomials $D _ { n } ( x , a )$, and linear polynomials $a x + b$ (here, $a$ and $b$ may be rational numbers). The first proof of this conjecture was given by M. Fried [a5]. More recently, in [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 [a13] G.L. Mullen proved a matrix analogue of Schur's conjecture.

Given a polynomial $f$ over $\mathbf{F} _ { q }$, define the value set $V _ { f }$ of $f$ by $V _ { f } = \{ f ( a ) : a \in {\bf F} _ { q } \}$. Since a polynomial of degree $n$ over a field can have at most $n$ roots, one has

\begin{equation*} \lfloor \frac { q - 1 } { n } \rfloor + 1 \leq | V _ { f } | \leq q. \end{equation*}

Polynomials which achieve the above lower bound are called minimal value-set polynomials, see [a12]. As noted in [a7], polynomials of degree $n$ with value sets of small cardinality (less than twice the minimum) come from Dickson polynomials. As indicated in [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 $\{ x ^ { n } \}$ and $\{ D _ { N } ( x , 1 ) \}$, see [a10], p. 13. Dickson polynomials provide a class of polynomials, one of each degree $n \geq 1$, which can be solved by radicals; see [a18].

The construction of irreducible polynomials over finite fields (cf. also Irreducible polynomial) is an important problem and in [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 [a6] for polynomial bases and [a1] and [a15] for completely normal bases. Connections between optimal normal bases and Dickson polynomials are discussed in [a10], Sect. 7.5.

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

A combinatorial application of Dickson polynomials is developed in [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). See [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 $n$ with parameter $a$ may be defined by

\begin{equation*} E _ { n } ( x , a ) = \sum _ { i = 0 } ^ { | n / 2 | } \left( \begin{array} { c } { n - i } \\ { i } \end{array} \right) ( - a ) ^ { i } x ^ { n - 2 i }. \end{equation*}

Dickson polynomials of the second kind satisfy the same recurrence as those of the first kind, except that the initial polynomial $E _ { 0 } ( x , a ) = 1$. See [a10], Chap. 2, for other basic properties of these polynomials.

Contrary to the many known properties of the Dickson polynomials $D _ { n } ( x , a )$ of the first kind, as indicated in [a10], very few properties of Dickson polynomials of the second kind are known (1998); see, for example, [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 [a10], Sects. 2.4, 3.5, and 4.3. A connection of Dickson polynomials in several variables to circulant determinants is given in [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 $\mathbf{Z} _ { n }$ of integers modulo $n$ as well as for the Galois ring $\operatorname{GR} ( p ^ { r } , s )$ (a degree $s$ Galois extension of ${\bf Z} _ { p ^ r}$), infinite algebraic extensions of finite fields, and matrix rings, see [a10], Chaps. 4; 5.

References

[a1] D. Blessenohl, K. Johnsen, "Eine Verschärfung des Satzes von der Normalbasis" J. Algebra , 103 (1986) pp. 141–159
[a2] 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
[a3] S.D. Cohen, "Proof of a conjecture of Chowla and Zassenhaus on permutation polynomials" Canad. Math. Bull. , 33 (1990) pp. 230–234
[a4] 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
[a5] M. Fried, "On a conjecture of Schur" Michigan Math. J. , 17 (1970) pp. 41–55
[a6] S. Gao, G.L. Mullen, "Dickson polynomials and irreducible polynomials over finite fields" J. Number Th. , 49 (1994) pp. 118–132
[a7] J. Gomez-Calderon, D.J. Madden, "Polynomials with small value sets over finite fields" J. Number Th. , 28 (1988) pp. 167–188
[a8] L.C. Hsu, G.L. Mullen, P.J.-S. Shiue, "Dickson–Stirling numbers" Proc. Edinburgh Math. Soc. , 40 (1997) pp. 409–423
[a9] R. Lidl, G.L. Mullen, "The world's most interesting class of integral polynomials" Preprint (1999)
[a10] R. Lidl, G.L. Mullen, G. Turnwald, "Dickson Polynomials" , Pitman Monogr. Surveys Pure Appl. Math. , 65 , Longman (1993)
[a11] R. Lidl, H. Niederreiter, "Finite fields" , Encycl. Math. Appl. , 20 , Cambridge Univ. Press (1997)
[a12] W.H. Mills, "Polynomials with minimal value sets" Pacific J. Math. , 14 (1964) pp. 225–241
[a13] 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
[a14] K.V.H. Parshall, "A study in group theory: Leonard Eugene Dickson's "Linear Groups" " Math. Intelligencer , 13 : 1 (1991) pp. 7–11
[a15] 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
[a16] 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
[a17] G. Turnwald, "On Schur's conjecture" J. Austral. Math. Soc. Ser. A , 58 (1995) pp. 312–357
[a18] K.S. Williams, "A generalization of Cardan's solution of the cubic" Math. Gaz. , 46 (1962) pp. 221–223
How to Cite This Entry:
Dickson polynomial. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dickson_polynomial&oldid=49965
This article was adapted from an original article by Gary L. Mullen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article