Value sets of Dickson polynomials over finite fields (Q581593): Difference between revisions

Let f(x) be a polynomial over \({\mathbb F}_ q\), the finite field of \(q=p^ n\) elements. Let \(V_ f=\{f(x)|\) \(x\in {\mathbb F}_ q\}\) denote the value set of f(x) and \(| V_ f|\) denote the cardinality of \(V_ f\). It is easy to see that \(| V_ f| \geq [(q-1)/d]+1\), where \([\;]\) denotes the greatest integer function. If equality holds here, \(f(x)\) is called a ``minimal value set polynomial''. Such polynomials over finite fields have been previously studied by \textit{L. Carlitz}, \textit{D. J. Lewis}, \textit{W. H. Mills} and \textit{E. G. Straus} [Mathematika 8, 121--130 (1961; Zbl 0106.01105)] and \textit{W. H. Mills} [Pac. J. Math. 14, 225--241 (1964; Zbl 0126.03004)]. Recently, \textit{J. Gomez-Calderón} and \textit{D. J. Madden} [J. Number Theory 28, No. 2, 167--188 (1988; Zbl 0634.12014)] have considered polynomials with small, but not minimal, value sets; in particular, polynomials with \(| V_ f| \leq 2\{[q-1)/d]+1\}\). Also \textit{J. Gomez-Calderón} [Mathematika 35, No. 1, 144--148 (1988; Zbl 0691.12004)] has recently proved that if \(3\leq d<p\) and \(| V_ f| \leq [(q- 1)/d]+(2(q-1)/d^ 2)-1\), then \(| V_ f| =[(q-1)/d]+1\), i.e., \(f(x)\) is a minimal value set polynomial. At the other extreme, if \(f(x)\) is a permutation polynomial over \({\mathbb F}_ q\), then \(f(x)\) has a value set of maximum possible cardinality, i.e., \(| V_ f| =q\). \textit{R. Lidl} and \textit{H. Niederreiter} [Finite fields. Cambridge: Cambridge Univ. Press (1983; Zbl 0554.12010)] have given a comprehensive survey of the many papers written on permutation polynomials over finite fields. It is easy to show that for the power polynomials \(f(x)=x^ d\), \(| V_ f|\) depends only upon \((d,q-1)\), the g.c.d. of \(d\) and \(q-1\). More specifically, if \((d,q-1)=\delta\), then \(f(x)=x^ d\) has \(| V_ f| =(q-1)/\delta +1\). Thus, if \(d\) divides \(q-1\), then \(x^ d\) is a minimal value set polynomial while, if \((d,q-1)=1\), then \(x^ d\) is a permutation polynomial on \({\mathbb F}_ q.\) For \(a\in {\mathbb F}_ q\) and \(d\geq 1\) an integer, a Dickson polynomial of degree d over \({\mathbb F}_ q\) is defined by \[ (1)\quad g_ d(x,a)=\sum^{[d/2]}_{t=0}(d/(d-1))\left( \begin{matrix} d-t\\ t\end{matrix} \right)(-a)^ tx^{d-2t}. \] Since \(g_ d(x,0)=x^ d\), the Dickson polynomial \(g_ d(x,a)\) may be viewed as a generalization of the power polynomial \(x^ d\) over \({\mathbb F}_ q\). Hence, it is not unreasonable to hope that Dickson polynomials may also have value sets whose cardinalities depend only upon \(d\) and \(q\). In the present paper, the authors define the cardinalities of the value sets for all Dickson polynomials with \(a\in \mathbb F^*_ q\) and \(d\geq 1\). They also show that if \((d,q^ 2- 1)=\delta\), then \(g_ d(x,a)\) and \(g_{\delta}(x,a)\) have value sets with the same cardinality. As a corollary, they also obtain a new proof of the well-known result that, if \(a\in \mathbb F^*_ q\), then \(g_ d(x,a)\) is a permutation polynomial on \(\mathbb F_ q\) if and only if \((d,q^ 2-1)=1\). From the formula obtained for the cardinality of the value set of \(g_ d(x,a)\) it is clear that the Dickson polynomials, like the power polynomials \(x^ d\), take on both small and large value sets.