Value sets of polynomials over finite fields
Authors:
Da Qing Wan, Peter JauShyong Shiue and Ching Shyang Chen
Journal:
Proc. Amer. Math. Soc. 119 (1993), 711717
MSC:
Primary 11T06; Secondary 11T55
MathSciNet review:
1155603
Fulltext PDF Free Access
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 HermiteDickson 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
(25 #3038)
 [2]
Wun
Seng Chou, Javier
GomezCalderon, and Gary
L. Mullen, Value sets of Dickson polynomials over finite
fields, J. Number Theory 30 (1988), no. 3,
334–344. MR
966096 (90e:11181), http://dx.doi.org/10.1016/0022314X(88)900066
 [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
(93j:11080), http://dx.doi.org/10.1307/mmj/1029004595
 [4]
Javier
GomezCalderon, A note on polynomials with minimal value set over
finite fields, Mathematika 35 (1988), no. 1,
144–148. MR
962743 (90e:11183), http://dx.doi.org/10.1112/S0025579300006355
 [5]
Javier
GomezCalderon and Daniel
J. Madden, Polynomials with small value set over finite
fields, J. Number Theory 28 (1988), no. 2,
167–188. MR
927658 (89d:11111), http://dx.doi.org/10.1016/0022314X(88)900649
 [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
(35 #6652)
 [7]
Rudolf
Lidl and Harald
Niederreiter, Finite fields, Encyclopedia of Mathematics and
its Applications, vol. 20, AddisonWesley Publishing Company, Advanced
Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. 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]
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
(94d:11097)
 [10]
L. J. Rogers, Note on functions proper to represent a substitution of a prime number of letters, Messenger Math. 21 (1981), 4447.
 [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
(93m:11129)
 [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
(92g:11119), http://dx.doi.org/10.1007/BF01525801
 [1]
 L. Carlitz, D. J. Lewis, W. H. Mills, and E. G. Strauss, Polynomials over finite fields with minimal value sets, Mathematika 8 (1961), 121130. MR 0139606 (25:3038)
 [2]
 W. S. Chou, J. GomezCalderon, and G. L. Mullen, Value sets of Dickson polynomials over finite fields, J. Number Theory 30 (1988), 334344. 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. GomezCalderon, A note on polynomials with minimal value set over finite fields, Mathematika 35 (1988), 144148. MR 962743 (90e:11183)
 [5]
 J. GomezCalderon and D. J. Madden, Polynomials with small value sets over finite fields, J. Number Theory 28 (1988), 167188. 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), 151158. (Russian) MR 0215817 (35:6652)
 [7]
 R. Lidl and H. Niederreiter, Finite fields, AddisonWesley, Reading, MA, 1983. MR 746963 (86c:11106)
 [8]
 W. H. Mills, Polynomials with minimal value sets, Pacific J. Math. 14 (1964), 225241. 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. 131151. 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), 4447.
 [11]
 D. Wan, A 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. 209216. MR 1199834 (93m:11129)
 [12]
 D. Wan and R. Lidl, Permutation polynomials of the form and their group structure, Monatsh Math. 112 (1991), 149163. 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:
http://dx.doi.org/10.1090/S00029939199311556032
PII:
S 00029939(1993)11556032
Article copyright:
© Copyright 1993
American Mathematical Society
