Value sets of polynomials over finite fields

Wan, Da Qing; Shiue, Peter Jau-Shyong; Chen, Ching Shyang

doi:10.1090/S0002-9939-1993-1155603-2

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

Note on functions proper to represent a substitution of a prime number of letters

21

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