zbMATH — the first resource for mathematics

On the number of values taken by a polynomial over a finite field. (English) Zbl 0693.12014
Let \(f=f(x)\) be a (monic) polynomial in x of degree n with coefficients in the finite field \({\mathbb{F}}_ q\) with q elements, and let r(f) denote the number of distinct values of f(x) for \(x\in {\mathbb{F}}_ q\). We have then q/n\(\leq r(f)\leq q\). In 1955 the reviewer proved that if the polynomial \(f^*(u,v)=(f(u)-f(v))/(u-v)\) is absolutely irreducible, then \(r(f)\geq q/2+O(q^{1/2})\), and B. J. Birch and H. P. F. Swinnerton-Dyer found in 1959 the precise result \[ r(f)=q(\sum^{n}_{j=1}\frac{(- 1)^{j-1}}{j!})+O(q^{1/2}), \] on condition that the Galois group of \(f(x)=y\) over \({\bar {\mathbb{F}}}_ q(y)\) is the full symmetric group. In this paper the author gives lower bounds for r(f), valid for f “general”, which improve on the above bounds in several cases. Thus, if q is prime and \(q^{1/4}<n-1<q\) and if \(f^*(u,v)\) is absolutely irreducible, then one has \[ r(f)\geq \frac{1}{4}(\frac{q}{n-1})^{4/3}, \] and, if the characteristic of \({\mathbb{F}}_ q\) is not 2 and if \(f'\) has \(n-1>0\) distinct roots and f is injective on the roots of \(f'\), then \[ r(f)\geq \frac{2q^ 2}{(n+1)q+(n-1)(n-2)}. \]
Reviewer: S.Uchiyama

11T06 Polynomials over finite fields
11T55 Arithmetic theory of polynomial rings over finite fields
Full Text: DOI EuDML