Value sets of polynomials over finite fields
HTML articles powered by AMS MathViewer
- by Da Qing Wan, Peter Jau-Shyong Shiue and Ching Shyang Chen PDF
- Proc. Amer. Math. Soc. 119 (1993), 711-717 Request permission
Abstract:
Let ${{\mathbf {F}}_q}$ be the finite field of $q$ elements, and let ${V_f}$ be the number of values taken by a polynomial $f(x)$ over ${{\mathbf {F}}_q}$. We establish a lower bound and an upper bound of ${V_f}$ in terms of certain invariants of $f(x)$. These bounds improve and generalize some of the previously known bounds of ${V_f}$. In particular, the classical Hermite-Dickson criterion is improved. Our bounds also give a new proof of a recent theorem of Evans, Greene, and Niederreiter. Finally, we give some examples which show that our bounds are sharp.References
- L. Carlitz, D. J. Lewis, W. H. Mills, and E. G. Straus, Polynomials over finite fields with minimal value sets, Mathematika 8 (1961), 121β130. MR 139606, DOI 10.1112/S0025579300002230
- Wun Seng Chou, Javier Gomez-Calderon, and Gary L. Mullen, Value sets of Dickson polynomials over finite fields, J. Number Theory 30 (1988), no.Β 3, 334β344. MR 966096, DOI 10.1016/0022-314X(88)90006-6
- Ronald J. Evans, John Greene, and Harald Niederreiter, Linearized polynomials and permutation polynomials of finite fields, Michigan Math. J. 39 (1992), no.Β 3, 405β413. MR 1182496, DOI 10.1307/mmj/1029004595
- Javier Gomez-Calderon, A note on polynomials with minimal value set over finite fields, Mathematika 35 (1988), no.Β 1, 144β148. MR 962743, DOI 10.1112/S0025579300006355
- Javier Gomez-Calderon and Daniel J. Madden, Polynomials with small value set over finite fields, J. Number Theory 28 (1988), no.Β 2, 167β188. MR 927658, DOI 10.1016/0022-314X(88)90064-9
- V. A. Kurbatov and N. G. Starkov, The analytic representation of permutations, Sverdlovsk. Gos. Ped. Inst. UΔen. Zap. 31 (1965), 151β158 (Russian). MR 0215817
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- W. H. Mills, Polynomials with minimal value sets, Pacific J. Math. 14 (1964), 225β241. MR 159813
- Gary L. Mullen, Permutation polynomials over finite fields, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp.Β 131β151. MR 1199828 L. J. Rogers, Note on functions proper to represent a substitution of a prime number of letters, Messenger Math. 21 (1981), 44-47.
- Da Qing Wan, A $p$-adic lifting lemma and its applications to permutation polynomials, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp.Β 209β216. MR 1199834
- Da Qing Wan and Rudolf Lidl, Permutation polynomials of the form $x^rf(x^{(q-1)/d})$ and their group structure, Monatsh. Math. 112 (1991), no.Β 2, 149β163. MR 1126814, DOI 10.1007/BF01525801
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 119 (1993), 711-717
- MSC: Primary 11T06; Secondary 11T55
- DOI: https://doi.org/10.1090/S0002-9939-1993-1155603-2
- MathSciNet review: 1155603