Polynomials with minimal value sets
William Hobson Mills · Pacific Journal of Mathematics · 1964
Let 3ίΓ be a finite field of characteristic p that contains exactly q elements. Let F(x) be a polynomial over 3ίΓ of degree /, /> 0, and let r + 1 denote the number of distinct values F(τ) as τ ranges over JΓ*. Carlitz, Lewis, Mills, and Straus [1] pointed out that r ^ [(q — 1)//], and raised the question of determining all polynomials for which r = [(q — 1)//]. The cases r = 0 and r = 1 are special cases that do not fit into the general pattern. These are treated in [1], and do not concern us here. Thus we arrive at the statement of our main problem: For what polynomials F(x) do we have ( I) r = [(q- 1)//] 2> 2? Carlitz, Lewis, Mills, and Straus [1] determined all polynomials with / < 2p + 2 for which (I) holds. In the present paper this result is extended—all polynomials with f ^LΛ / q for which (I) holds are determined. These are polynomials of the form F(x) = aLυ + 7, where L is a polynomial that factors into distinct linear factors over 3ίΓ and that has the form L = β + Σ ΦiXpU f i and where v and k are integers such that v \\ (pk — 1) and q is a power of pk. Regardless of the size of / our present methods give a great deal of information about F(x). Furthermore many of the proofs of [1] can be shortened and simplified by using the results of § 1 of the present paper. The results of [1] provide a complete answer for the case q = p. In the present paper the problem is completely solved for the case q = p\\ 1. Preliminaries * Let 3ίΓ be a finite field with q elements and characteristic p. We use Greek letters for elements of 3Γ, and small Latin letters, other than x, for nonnegative integers. We use capital letters for polynomials in one variable over <5(Γ. The poly-