# Dickson polynomial

In mathematics, the Dickson polynomials, denoted Dn(x,α), form a polynomial sequence introduced by L. E. Dickson (1897). They were rediscovered by Brewer (1961) in his study of Brewer sums and have at times, although rarely, been referred to as Brewer polynomials.

Over the complex numbers, Dickson polynomials are essentially equivalent to Chebyshev polynomials with a change of variable, and, in fact, Dickson polynomials are sometimes called Chebyshev polynomials. Dickson polynomials are generally studied over finite fields, where they sometimes may not be equivalent to Chebyshev polynomials. One of the main reasons for interest in them is that for fixed α, they give many examples of permutation polynomials; polynomials acting as permutations of finite fields.

## Definition

### First kind

For integer n > 0 and ${\displaystyle \alpha }$ in a commutative ring R with identity (often chosen to be the finite field Fq = GF(q)) the Dickson polynomials (of the first kind) over R are given by[1]

${\displaystyle D_{n}(x,\alpha )=\sum _{i=0}^{\lfloor n/2\rfloor }{\frac {n}{n-i}}{\binom {n-i}{i}}(-\alpha )^{i}x^{n-2i}.}$

The first few Dickson polynomials are

${\displaystyle D_{1}(x,\alpha )=x\,}$
${\displaystyle D_{2}(x,\alpha )=x^{2}-2\alpha \,}$
${\displaystyle D_{3}(x,\alpha )=x^{3}-3x\alpha \,}$
${\displaystyle D_{4}(x,\alpha )=x^{4}-4x^{2}\alpha +2\alpha ^{2}\,}$
${\displaystyle D_{5}(x,\alpha )=x^{5}-5x^{3}\alpha +5x\alpha ^{2}.\,}$

They may also be generated by the recurrence relation for n ≥ 2,

${\displaystyle D_{n}(x,\alpha )=xD_{n-1}(x,\alpha )-\alpha D_{n-2}(x,\alpha ),}$

with the initial conditions ${\displaystyle D_{0}(x,\alpha )=2}$ and ${\displaystyle D_{1}(x,\alpha )=x}$.

### Second kind

The Dickson polynomials of the second kind, ${\displaystyle E_{n}(x,\alpha )}$, are defined by

${\displaystyle E_{n}(x,\alpha )=\sum _{i=0}^{\lfloor n/2\rfloor }{\binom {n-i}{i}}(-\alpha )^{i}x^{n-2i}.}$

They have not been studied much, and have properties similar to those of Dickson polynomials of the first kind. The first few Dickson polynomials of the second kind are

${\displaystyle E_{0}(x,\alpha )=1\,}$
${\displaystyle E_{1}(x,\alpha )=x\,}$
${\displaystyle E_{2}(x,\alpha )=x^{2}-\alpha \,}$
${\displaystyle E_{3}(x,\alpha )=x^{3}-2x\alpha \,}$
${\displaystyle E_{4}(x,\alpha )=x^{4}-3x^{2}\alpha +\alpha ^{2}.\,}$

They may also be generated by the recurrence relation for n ≥ 2,

${\displaystyle E_{n}(x,\alpha )=xE_{n-1}(x,\alpha )-\alpha E_{n-2}(x,\alpha ),}$

with the initial conditions ${\displaystyle E_{0}(x,\alpha )=1}$ and ${\displaystyle E_{1}(x,\alpha )=x}$.

## Properties

The Dn are the unique monic polynomials satisfying the functional equation

${\displaystyle D_{n}(u+{\frac {\alpha }{u}},\alpha )=u^{n}+\left({\frac {\alpha }{u}}\right)^{n},}$

where ${\displaystyle \alpha \in \mathbb {F} _{q}}$ and ${\displaystyle u\neq 0\in \mathbb {F} _{q^{2}}}$.[2]

They also satisfy a composition rule,[2]

${\displaystyle D_{mn}(x,\alpha )=D_{m}(D_{n}(x,\alpha ),\alpha ^{n})\,.}$

The En also satisfy a functional equation[2]

${\displaystyle E_{n}(y+{\frac {\alpha }{y}},\alpha )={\frac {y^{n+1}-\left({\frac {\alpha }{y}}\right)^{n+1}}{y-{\frac {\alpha }{y}}}},}$

for ${\displaystyle y\neq 0,\pm {\sqrt {\alpha }}}$, with ${\displaystyle \alpha \in \mathbb {F} _{q}}$ and ${\displaystyle y\in \mathbb {F} _{q^{2}}}$.

The Dickson polynomial y = Dn is a solution of the ordinary differential equation

${\displaystyle (x^{2}-4\alpha )y''+xy'-n^{2}y=0\,}$

and the Dickson polynomial y = En is a solution of the differential equation

${\displaystyle (x^{2}-4\alpha )y''+3xy'-n(n+2)y=0.}$

Their ordinary generating functions are

${\displaystyle \sum _{n}D_{n}(x,\alpha )z^{n}={\frac {2-xz}{1-xz+\alpha z^{2}}}\,}$
${\displaystyle \sum _{n}E_{n}(x,\alpha )z^{n}={\frac {1}{1-xz+\alpha z^{2}}}.\,}$

• Dickson polynomials of the first kind over the complex numbers are related to Chebyshev polynomials Tn(x) = cos (n arccos x) of the first kind by[1]
${\displaystyle D_{n}(2x,1)=2T_{n}(x).}$

Using this relation to define Tn over finite fields, this relationship can be extended as follows for odd q. For ${\displaystyle \alpha \neq 0\in \mathbb {F} _{q}}$ and ${\displaystyle \beta \in \mathbb {F} _{q^{2}}}$ with ${\displaystyle \beta ^{2}=\alpha }$,[3]

${\displaystyle D_{n}(x,\alpha )=2\beta ^{n}T_{n}\left({\frac {x}{2\beta }}\right).}$

Similar relations hold between Dickson polynomials of the second kind and the Chebyshev polynomials of the second kind, Un.

Since the Dickson polynomial Dn(x, α) can be defined over rings in which α is not a square, and over rings of characteristic 2, in these cases, Dn(x, α) is often not related to a Chebyshev polynomial.

• The Dickson polynomials with parameter α = −1 are related to the Fibonacci and Lucas polynomials.
• The Dickson polynomials with parameter α = 0 give monomials:
${\displaystyle D_{n}(x,0)=x^{n}\,.}$

## Permutation polynomials and Dickson polynomials

A permutation polynomial (for a given finite field) is one that acts as a permutation of the elements of the finite field.

The Dickson polynomial Dn(x, α) (considered as a function of x with α fixed) is a permutation polynomial for the field with q elements if and only if n is coprime to q2−1.[3]

M. Fried (1970) proved that any integral polynomial that is a permutation polynomial for infinitely many prime fields is a composition of Dickson polynomials and linear polynomials (with rational coefficients). This assertion has become known as Schur's conjecture, although in fact Schur did not make this conjecture. Since Fried's paper contained numerous errors, a corrected account was given by G. Turnwald (1995), and subsequently P. Müller (1997) gave a simpler proof along the lines of an argument due to Schur.

Further, P. Müller (1997) proved that any permutation polynomial over the finite field Fq whose degree is simultaneously coprime to q−1 and less than q1/4 must be a composition of Dickson polynomials and linear polynomials.

## Generalization

Dickson polynomials of both kinds over finite fields can be thought of as initial members of a sequence of generalized Dickson polynomials referred to as Dickson polynomials of the (k + 1)-th kind.[4] Specifically, for ${\displaystyle \alpha \in \mathbb {F} _{q}}$ with ${\displaystyle q=p^{e}}$ for some prime p and any integers ${\displaystyle n\geq 0}$ and ${\displaystyle 0\leq k, the n-th Dickson polynomial of the (k + 1)-th kind over ${\displaystyle \mathbb {F} _{q}}$, denoted by ${\displaystyle D_{n,k}(x,\alpha )}$, is defined by,[5] ${\displaystyle D_{0,k}(x,\alpha )=2-k}$ and

${\displaystyle D_{n,k}(x,\alpha )=\sum _{i=0}^{\lfloor n/2\rfloor }{\frac {n-ki}{n-i}}{\binom {n-i}{i}}(-\alpha )^{i}x^{n-2i}.}$

${\displaystyle D_{n,0}(x,\alpha )=D_{n}(x,\alpha )}$ and ${\displaystyle D_{n,1}(x,\alpha )=E_{n}(x,\alpha )}$, showing that this definition unifies and generalizes the original polynomials of Dickson.

The significant properties of the Dickson polynomials also generalize:[6]

• Recurrence relation: For ${\displaystyle n\geq 2}$,
${\displaystyle D_{n,k}(x,\alpha )=xD_{n-1,k}(x,\alpha )-\alpha D_{n-2,k}(x,\alpha ),}$
with the initial conditions ${\displaystyle D_{0,k}(x,\alpha )=2-k}$ and ${\displaystyle D_{1,k}(x,\alpha )=x}$.
• Functional equation:
${\displaystyle D_{n,k}(y+\alpha y^{-1},\alpha )={\frac {y^{2n}+k\alpha y^{2n-2}+\cdots +k{\alpha }^{n-1}y^{2}+{\alpha }^{n}}{y^{n}}}={\frac {y^{2n}+{\alpha }^{n}}{y^{n}}}+\left({\frac {k\alpha }{y^{n}}}\right){\frac {y^{2n}-{\alpha }^{n-1}y^{2}}{y^{2}-\alpha }},}$
where ${\displaystyle y\neq 0,\pm {\sqrt {\alpha }}.}$
• Generating function:
${\displaystyle \sum _{n=0}^{\infty }D_{n,k}(x,\alpha )z^{n}={\frac {2-k+(k-1)xz}{1-xz+\alpha z^{2}}}.}$

## Notes

1. ^ a b Lidl & Niederreiter 1983, p. 355
2. ^ a b c Mullen & Panario 2013, p. 283
3. ^ a b Lidl & Niederreitter 1983, p. 356
4. ^ Wang, Q.; Yucas, J.L. (2012), "Dickson polynomials over finite fields", Finite Fields and their Applications, 18: 814–831
5. ^ Mullen & Panario 2013, p. 287
6. ^ Mullen & Panario 2013, p. 288