Dickson polynomial

Definition

First kind

For integer n 0 and α in a commutative ring R with identity (often chosen to be the finite field ) the Dickson polynomials (of the first kind) over R are given by

:D_n(x,\alpha)=\sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor}\frac{n}{n-i} \binom{n-i}{i} (-\alpha)^i x^{n-2i} ,.

The first few Dickson polynomials are

:\begin{align} 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{align}

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

:D_n(x,\alpha) = xD_{n-1}(x,\alpha)-\alpha D_{n-2}(x,\alpha) ,, with the initial conditions and .

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, En(x,α), are defined by :E_n(x,\alpha)=\sum_{i=0}^{\left\lfloor \frac{n}{2} \right\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

:\begin{align} 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{align}

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

:E_n(x,\alpha) = xE_{n-1}(x,\alpha)-\alpha E_{n-2}(x,\alpha) ,, with the initial conditions and .

The coefficients are also given in the OEIS.

Properties

The Dn are the unique monic polynomials satisfying the functional equation

:D_n\left(u + \frac{\alpha}{u},\alpha\right) = u^n + \left(\frac{\alpha}{u}\right)^n, where α ∈ Fq and u ≠ 0 ∈ Fq2.

They also satisfy a composition rule, :D_{mn}(x,\alpha) = D_m\bigl(D_n(x,\alpha),\alpha^n\bigr) ,= D_n\bigl(D_m(x,\alpha),\alpha^m\bigr) , .

The En also satisfy a functional equation :E_n\left(y + \frac{\alpha}{y}, \alpha\right) = \frac{y^{n+1} - \left(\frac{\alpha}{y}\right)^{n+1}}{y - \frac{\alpha}{y}} ,, for y ≠ 0, y2 ≠ α, with α ∈ Fq and y ∈ Fq2.

The Dickson polynomial is a solution of the ordinary differential equation :\left(x^2-4\alpha\right)y'' + xy' - n^2y=0 ,, and the Dickson polynomial is a solution of the differential equation :\left(x^2-4\alpha\right)y'' + 3xy' - n(n+2)y=0 ,. Their ordinary generating functions are :\begin{align} \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{align}

Links to other polynomials

By the recurrence relation above, Dickson polynomials are Lucas sequences. Specifically, for , 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 give monomials.

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

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

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

• Since the Dickson polynomial Dn(x,α) can be defined over rings with additional idempotents, Dn(x,α) 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 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.

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

Further, proved that any permutation polynomial over the finite field Fq whose degree is simultaneously coprime to q and less than q 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. Specifically, for α ≠ 0 ∈ Fq with for some prime p and any integers n ≥ 0 and 0 ≤ k q, denoted by D**n,k(x,α), is defined by :D_{0,k}(x,\alpha) = 2 - k and :D_{n,k}(x,\alpha)=\sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor}\frac{n - ki}{n-i}\binom{n-i}{i} (-\alpha)^i x^{n-2i} ,.

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

The significant properties of the Dickson polynomials also generalize:

• Recurrence relation: For n ≥ 2,

D_{n,k}\left(y + \alpha y^{-1}, \alpha\right) = \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 y ≠ 0, y2 ≠ α.

• Generating function: ::\sum_{n=0}^{\infty} D_{n,k}(x,\alpha)z^n = \frac{2 - k + (k-1)xz}{1 - xz + \alpha z^2} ,.

Notes

References

• {{Cite book
• {{cite journal|first1=Paul Thomas|last1=Young

References

1. {{harvnb. Lidl. Niederreiter. 1983
2. "see OEIS A132460".
3. "see OEIS A213234".
4. "see OEIS A113279".
5. "see OEIS A034807, this one without signs but with a lot of references".
6. "see OEIS A115139".
7. "see OEIS A011973, this one again without signs but with a lot of references".
8. {{harvnb. Mullen. Panario. 2013
9. {{harvnb. Lidl. Niederreiter. 1983
10. (2012). "Dickson polynomials over finite fields". Finite Fields and Their Applications.
11. {{harvnb. Mullen. Panario. 2013
12. {{harvnb. Mullen. Panario. 2013