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 be the finite field of elements, and let be the number of values taken by a polynomial over . We establish a lower bound and an upper bound of in terms of certain invariants of . These bounds improve and generalize some of the previously known bounds of . 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.

**[1]**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**0139606**, https://doi.org/10.1112/S0025579300002230**[2]**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**, https://doi.org/10.1016/0022-314X(88)90006-6**[3]**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**, https://doi.org/10.1307/mmj/1029004595**[4]**Javier Gomez-Calderon,*A note on polynomials with minimal value set over finite fields*, Mathematika**35**(1988), no. 1, 144–148. MR**962743**, https://doi.org/10.1112/S0025579300006355**[5]**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**, https://doi.org/10.1016/0022-314X(88)90064-9**[6]**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****[7]**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****[8]**W. H. Mills,*Polynomials with minimal value sets*, Pacific J. Math.**14**(1964), 225–241. MR**0159813****[9]**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****[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]**Da Qing Wan,*A 𝑝-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****[12]**Da Qing Wan and Rudolf Lidl,*Permutation polynomials of the form 𝑥^{𝑟}𝑓(𝑥^{(𝑞-1)/𝑑}) and their group structure*, Monatsh. Math.**112**(1991), no. 2, 149–163. MR**1126814**, https://doi.org/10.1007/BF01525801

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