Dickson polynomial

In mathematics, the Dickson polynomials (or Brewer polynomials), denoted Dn(x,α), form a polynomial sequence introduced by L. E. Dickson (1897) and rediscovered by Brewer (1961) in his study of Brewer sums.

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 mainly studied over finite fields, when they are not 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

D0(x,α) = 2, and for n > 0 Dickson polynomials (of the first kind) are given by

D_n(x,\alpha)=\sum_{p=0}^{\lfloor n/2\rfloor}\frac{n}{n-p} \binom{n-p}{p} (-\alpha)^p x^{n-2p}.

The first few Dickson polynomials are

D_0(x,\alpha) = 2 \,
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. \,

The Dickson polynomials of the second kind En are defined by

E_n(x,\alpha)=\sum_{p=0}^{\lfloor n/2\rfloor}\binom{n-p}{p} (-\alpha)^p x^{n-2p}.

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

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. \,

Properties

The Dn satisfy the identities

D_n(u + \alpha/u,\alpha) = u^n + (\alpha/u)^n \, ;
D_{mn}(x,\alpha) = D_m(D_n(x,\alpha),\alpha^n) \, .

For n≥2 the Dickson polynomials satisfy the recurrence relation

D_n(x,\alpha) = xD_{n-1}(x,\alpha)-\alpha D_{n-2}(x,\alpha) \,
E_n(x,\alpha) = xE_{n-1}(x,\alpha)-\alpha E_{n-2}(x,\alpha). \,

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

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

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

(x^2-4\alpha)y'' + 3xy' - n(n+2)y=0. \,

Their ordinary generating functions are

\sum_nD_n(x,\alpha)z^n = \frac{2-xz}{1-xz+\alpha z^2} \,
\sum_nE_n(x,\alpha)z^n = \frac{1}{1-xz+\alpha z^2}. \,

Links to other polynomials

D_n(2xa,a^2)= 2a^{n}T_n(x) \,
E_n(2xa,a^2)= a^{n}U_n(x). \,

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

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.[1]

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.

References

  1. ↑ Lidl & Niederreiter (1997) p.356
This article is issued from Wikipedia - version of the Wednesday, February 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.