Dickson polynomial

In mathematics, the Dickson polynomials, denoted Template:Math, form a polynomial sequence introduced by Template:Harvs. They were rediscovered by Template:Harvtxt 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 Template:Math, they give many examples of permutation polynomials; polynomials acting as permutations of finite fields.

Definition

First kind

For integer Template:Math and Template:Mvar in a commutative ring Template:Mvar with identity (often chosen to be the finite field Template:Math) the Dickson polynomials (of the first kind) over Template:Mvar are given by

$D_n(x,\alpha )=\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }\frac{n}{n-i}(\genfrac{}{}{0ex}{}{n-i}{i})(-\alpha {)}^i{x}^{n-2i}.$

The first few Dickson polynomials are

$\begin{array}{cc}{D}_1(x,\alpha )& =x\\ D_2(x,\alpha )& =x^2-2\alpha \\ D_3(x,\alpha )& =x^3-3x\alpha \\ D_4(x,\alpha )& =x^4-4x^2\alpha +2{\alpha }^2\\ D_5(x,\alpha )& =x^5-5x^3\alpha +5x{\alpha }^2.\end{array}$

They may also be generated by the recurrence relation for Template:Math,

$D_n(x,\alpha )=x{D}_{n-1}(x,\alpha )-\alpha D_{n-2}(x,\alpha ),$

with the initial conditions Template:Math and Template:Math.

The coefficients are given at several places in the OEIS with minute differences for the first two terms.

Second kind

The Dickson polynomials of the second kind, Template:Math, are defined by

$E_n(x,\alpha )=\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{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

$\begin{array}{cc}{E}_0(x,\alpha )& =1\\ E_1(x,\alpha )& =x\\ E_2(x,\alpha )& =x^2-\alpha \\ E_3(x,\alpha )& =x^3-2x\alpha \\ E_4(x,\alpha )& =x^4-3x^2\alpha +{\alpha }^2.\end{array}$

They may also be generated by the recurrence relation for Template:Math,

$E_n(x,\alpha )=x{E}_{n-1}(x,\alpha )-\alpha E_{n-2}(x,\alpha ),$

with the initial conditions Template:Math and Template:Math.

The coefficients are also given in the OEIS.

Properties

The Template:Math are the unique monic polynomials satisfying the functional equation

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

where Template:Math and Template:Math.

They also satisfy a composition rule,

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

The Template:Math also satisfy a functional equation

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

for Template:Math, Template:Math, with Template:Math and Template:Math.

The Dickson polynomial Template:Math is a solution of the ordinary differential equation

$(x^2-4\alpha )y^{″}+x{y}^{\prime }-n^{2}y=0,$

and the Dickson polynomial Template:Math is a solution of the differential equation

$(x^2-4\alpha )y^{″}+3x{y}^{\prime }-n(n+2)y=0.$

Their ordinary generating functions are

$\begin{array}{cc}\sum _n{D}_n(x,\alpha )z^n& =\frac{2-xz}{1-xz+\alpha z^2}\\ \sum _n{E}_n(x,\alpha )z^n& =\frac{1}{1-xz+\alpha z^2}.\end{array}$

Links to other polynomials

By the recurrence relation above, Dickson polynomials are Lucas sequences. Specifically, for Template:Math, the Dickson polynomials of the first kind are Fibonacci polynomials, and Dickson polynomials of the second kind are Lucas polynomials.

By the composition rule above, when α is idempotent, composition of Dickson polynomials of the first kind is commutative.

• The Dickson polynomials with parameter Template:Math give monomials.

$D_n(x,0)=x^n.$

• The Dickson polynomials with parameter Template:Math are related to Chebyshev polynomials Template:Math of the first kind by

$D_n(2x,1)=2T_n(x).$

• Since the Dickson polynomial Template:Math can be defined over rings with additional idempotents, Template:Math is often not related to a Chebyshev polynomial.

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 Template:Math (considered as a function of Template:Math with α fixed) is a permutation polynomial for the field with Template:Math elements if and only if Template:Math is coprime to Template:Math.

Template:Harvtxt 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 Template:Harvtxt, and subsequently Template:Harvtxt gave a simpler proof along the lines of an argument due to Schur.

Further, Template:Harvtxt proved that any permutation polynomial over the finite field Template:Math whose degree is simultaneously coprime to Template:Math and less than Template:Math 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 Template:Mathth kind. Specifically, for Template:Math with Template:Math for some prime Template:Mvar and any integers Template:Math and Template:Math, the Template:Mvarth Dickson polynomial of the Template:Mathth kind over Template:Math, denoted by Template:Math, is defined by

$D_{0,k}(x,\alpha )=2-k$

and

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

Template:Math and Template:Math, showing that this definition unifies and generalizes the original polynomials of Dickson.

The significant properties of the Dickson polynomials also generalize:

• Recurrence relation: For Template:Math,

$D_{n,k}(x,\alpha )=x{D}_{n-1,k}(x,\alpha )-\alpha D_{n-2,k}(x,\alpha ),$

with the initial conditions Template:Math and Template:Math.

• Functional equation:

$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 Template:Math, Template:Math.

• Generating function:

$\sum _{n=0}^{\mathrm{\infty }}{D}_{n,k}(x,\alpha )z^n=\frac{2-k+(k-1)xz}{1-xz+\alpha z^2}.$

References

• Template:Citation
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Springer
• Template:Citation
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal