Dickson polynomial

In mathematics, the Dickson polynomials, denoted D_n(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 α in a commutative ring R with identity (often chosen to be the finite field F_q = GF(q)) the Dickson polynomials (of the first kind) over R are given by

[math]\displaystyle{ 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} \,. }[/math]

The first few Dickson polynomials are

[math]\displaystyle{ \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} }[/math]

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

[math]\displaystyle{ D_n(x,\alpha) = xD_{n-1}(x,\alpha)-\alpha D_{n-2}(x,\alpha) \,, }[/math]

with the initial conditions D₀(x,α) = 2 and D₁(x,α) = x.

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, E_n(x,α), are defined by

[math]\displaystyle{ E_n(x,\alpha)=\sum_{i=0}^{\left\lfloor \frac{n}{2} \right\rfloor}\binom{n-i}{i} (-\alpha)^i x^{n-2i}. }[/math]

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

[math]\displaystyle{ \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} }[/math]

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

[math]\displaystyle{ E_n(x,\alpha) = xE_{n-1}(x,\alpha)-\alpha E_{n-2}(x,\alpha) \,, }[/math]

with the initial conditions E₀(x,α) = 1 and E₁(x,α) = x.

The coefficients are also given in the OEIS.

Properties

The D_n are the unique monic polynomials satisfying the functional equation

[math]\displaystyle{ D_n\left(u + \frac{\alpha}{u},\alpha\right) = u^n + \left(\frac{\alpha}{u}\right)^n, }[/math]

where α ∈ F_q and u ≠ 0 ∈ F_q².

They also satisfy a composition rule,

[math]\displaystyle{ D_{mn}(x,\alpha) = D_m\bigl(D_n(x,\alpha),\alpha^n\bigr) \,= D_n\bigl(D_m(x,\alpha),\alpha^m\bigr) \, . }[/math]

The E_n also satisfy a functional equation

[math]\displaystyle{ E_n\left(y + \frac{\alpha}{y}, \alpha\right) = \frac{y^{n+1} - \left(\frac{\alpha}{y}\right)^{n+1}}{y - \frac{\alpha}{y}} \,, }[/math]

for y ≠ 0, y² ≠ α, with α ∈ F_q and y ∈ F_q².

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

[math]\displaystyle{ \left(x^2-4\alpha\right)y'' + xy' - n^2y=0 \,, }[/math]

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

[math]\displaystyle{ \left(x^2-4\alpha\right)y'' + 3xy' - n(n+2)y=0 \,. }[/math]

Their ordinary generating functions are

[math]\displaystyle{ \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} }[/math]

Links to other polynomials

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

[math]\displaystyle{ D_n(x,0) = x^n \, . }[/math]

• The Dickson polynomials with parameter α = 1 are related to Chebyshev polynomials T_n(x) = cos (n arccos x) of the first kind by

[math]\displaystyle{ D_n(2x, 1) = 2T_n(x) \,. }[/math]

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

(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 (Turnwald 1995), and subsequently (Müller 1997) gave a simpler proof along the lines of an argument due to Schur.

Further, (Müller 1997) proved that any permutation polynomial over the finite field F_q whose degree is simultaneously coprime to q and less than q^1/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. Specifically, for α ≠ 0 ∈ F_q with q = p^e for some prime p and any integers n ≥ 0 and 0 ≤ k < p, the nth Dickson polynomial of the (k + 1)th kind over F_q, denoted by D_n,k(x,α), is defined by

[math]\displaystyle{ D_{0,k}(x,\alpha) = 2 - k }[/math]

and

[math]\displaystyle{ 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} \,. }[/math]

D_n,0(x,α) = D_n(x,α) and D_n,1(x,α) = E_n(x,α), 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,

[math]\displaystyle{ D_{n,k}(x,\alpha) = xD_{n-1,k}(x,\alpha)-\alpha D_{n-2,k}(x,\alpha)\,, }[/math]

with the initial conditions D_0,k(x,α) = 2 − k and D_1,k(x,α) = x.

• Functional equation:

[math]\displaystyle{ 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} \,, }[/math]

where y ≠ 0, y² ≠ α.

• Generating function:

[math]\displaystyle{ \sum_{n=0}^{\infty} D_{n,k}(x,\alpha)z^n = \frac{2 - k + (k-1)xz}{1 - xz + \alpha z^2} \,. }[/math]

References

• Brewer, B. W. (1961), "On certain character sums", Transactions of the American Mathematical Society 99 (2): 241–245, doi:10.2307/1993392, ISSN 0002-9947 
• Dickson, L. E. (1897). "The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group I,II". Ann. of Math. (The Annals of Mathematics) 11 (1/6): 65–120; 161–183. doi:10.2307/1967217. ISSN 0003-486X. 
• Fried, Michael (1970). "On a conjecture of Schur". Michigan Math. J. 17: 41–55. doi:10.1307/mmj/1029000374. ISSN 0026-2285. http://projecteuclid.org/euclid.mmj/1029000374. 
• Lidl, R.; Mullen, G. L.; Turnwald, G. (1993). Dickson polynomials. Pitman Monographs and Surveys in Pure and Applied Mathematics. 65. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York. ISBN 978-0-582-09119-1. 
• Lidl, Rudolf; Niederreiter, Harald (1983). Finite fields. Encyclopedia of Mathematics and Its Applications. 20 (1st ed.). Addison-Wesley. ISBN 978-0-201-13519-0. https://archive.org/details/finitefields0000lidl. 
• Hazewinkel, Michiel, ed. (2001), "Dickson polynomials", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=D/d120140 
• Mullen, Gary L.; Panario, Daniel (2013), Handbook of Finite Fields, CRC Press, ISBN 978-1-4398-7378-6 
• Müller, Peter (1997). "A Weil-bound free proof of Schur's conjecture". Finite Fields and Their Applications 3: 25–32. doi:10.1006/ffta.1996.0170. 
• Rassias, Thermistocles M.; Srivastava, H.M.; Yanushauskas, A. (1991). Topics in Polynomials of One and Several Variables and Their Applications: A Legacy of P.L.Chebyshev. World Scientific. pp. 371–395. ISBN 978-981-02-0614-7. 
• Turnwald, Gerhard (1995). "On Schur's conjecture". J. Austral. Math. Soc. Ser. A 58 (3): 312–357. doi:10.1017/S1446788700038349. http://journals.cambridge.org./action/displayFulltext?type=1&pdftype=1&fid=4986396&jid=JAZ&volumeId=58&issueId=&aid=4986388. 
• Young, Paul Thomas (2002). "On modified Dickson polynomials". Fibonacci Quarterly 40 (1): 33–40. http://www.fq.math.ca/Scanned/40-1/young.pdf. 
• Bayad, Abdelmejid; Cangul, Ismail Naci (2012). "The minimal polynomial 2 cos(pi/q) and Dickson polynomials". Appl. Math. Comp. 218: 7014-7022. doi:10.1016/j.amc.2011.12.044.