Value sets of Dickson polynomials over finite fields (Q581593): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Gary L. Mullen / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: John H. Hodges / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11T06 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4128943 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
polynomials over finite fields | |||
Property / zbMATH Keywords: polynomials over finite fields / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
value set | |||
Property / zbMATH Keywords: value set / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
permutation polynomial | |||
Property / zbMATH Keywords: permutation polynomial / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
power polynomials | |||
Property / zbMATH Keywords: power polynomials / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Dickson polynomial | |||
Property / zbMATH Keywords: Dickson polynomial / rank | |||
Normal rank |
Revision as of 18:56, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Value sets of Dickson polynomials over finite fields |
scientific article |
Statements
Value sets of Dickson polynomials over finite fields (English)
0 references
1988
0 references
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.
0 references
polynomials over finite fields
0 references
value set
0 references
permutation polynomial
0 references
power polynomials
0 references
Dickson polynomial
0 references