Residue sums of Dickson polynomials over finite fields

Abstract

Given a polynomial with integral coefficients, one can inquire about the possible residues it can take in its image modulo a prime $p$. The sum over the distinct residues can sometimes be computed independent of the prime $p$; for example, Gauss showed that the sum over quadratic residues vanishes modulo a prime. In this paper we provide a closed form for the sum over distinct residues in the image of Dickson polynomials of arbitrary degree over finite fields of odd characteristic, and prove a complete characterization of the size of the image set. Our result provides the first non-trivial classification of such a sum for a family of polynomials of unbounded degree.

Major revisions: we now treat the more general case of Dickson polynomials over finite fields of odd characteristic instead of Lucas polynomials modulo a prime. 19 pages, comments welcome!