Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Value sets of polynomials over finite fields


Authors: Da Qing Wan, Peter Jau-Shyong Shiue and Ching Shyang Chen
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] L. Carlitz, D. J. Lewis, W. H. Mills, and E. G. Strauss, Polynomials over finite fields with minimal value sets, Mathematika 8 (1961), 121-130. MR 0139606 (25:3038)
  • [2] W. S. Chou, J. Gomez-Calderon, and G. L. Mullen, Value sets of Dickson polynomials over finite fields, J. Number Theory 30 (1988), 334-344. MR 966096 (90e:11181)
  • [3] R. J. Evans, J. Greene, and H. Niederreiter, Linearized polynomials and permutation polynomials of finite fields, Michigan Math. J. (to appear). MR 1182496 (93j:11080)
  • [4] J. Gomez-Calderon, A note on polynomials with minimal value set over finite fields, Mathematika 35 (1988), 144-148. MR 962743 (90e:11183)
  • [5] J. Gomez-Calderon and D. J. Madden, Polynomials with small value sets over finite fields, J. Number Theory 28 (1988), 167-188. MR 927658 (89d:11111)
  • [6] V. A. Kurbatov and N. G. Starkov, The analytic representation of permutations, Sverdlovsk. Gos. Ped. Inst. Ucen. Zat. 31 (1965), 151-158. (Russian) MR 0215817 (35:6652)
  • [7] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, MA, 1983. MR 746963 (86c:11106)
  • [8] W. H. Mills, Polynomials with minimal value sets, Pacific J. Math. 14 (1964), 225-241. MR 0159813 (28:3029)
  • [9] G. L. Mullen, Permutation polynomials over finite fields, Proceedings of the International Conference on Finite Fields, Coding Theory and Advances in Communications and Computing, Lecture Notes in Pure and Appl. Math., vol. 141, Marcel Dekker, New York, 1992, pp. 131-151. MR 1199828 (94d:11097)
  • [10] L. J. Rogers, Note on functions proper to represent a substitution of a prime number of letters, Messenger Math. 21 (1981), 44-47.
  • [11] D. Wan, A $ p$-adic lifting lemma and its applications to permutation polynomials, Proceedings of the International Conference on Finite Fields, Coding Theory and Advances in Communications and Computing, Lecture Notes in Pure and Appl. Math., vol. 141, Marcel Dekker, New York, 1992, pp. 209-216. MR 1199834 (93m:11129)
  • [12] D. Wan and R. Lidl, Permutation polynomials of the form $ {x^r}f({x^{(q - 1)/d}})$ and their group structure, Monatsh Math. 112 (1991), 149-163. MR 1126814 (92g:11119)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 11T06, 11T55

Retrieve articles in all journals with MSC: 11T06, 11T55


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1993-1155603-2
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society