# 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

##### MSC:
 11T06 Polynomials over finite fields 11T55 Arithmetic theory of polynomial rings over finite fields
##### Keywords:
number of values; polynomials over finite fields
Full Text: