Polynomials with small value set over finite fields (Q1096675)

Let \(K_ q\) denote the finite field with \(q=p^ r\) elements. Let f(x) be a monic polynomial of degree \(d\) with coefficients in \(K_ q\). Let C(f) denote the number of distinct values of f(x) as x ranges over \(K_ q\). The authors give a complete list of polynomials such that \(d<q^{1/4}\), \(GCD(q,d)=1\) and \(C(f)<2q/d\). The result is obtained [following the work of the reviewer, Can. Math. Bull. 10, 585-594 (1967; Zbl 0185.103)] by using the connection between the size of C(f) and the factorization of f(x)-f(y) in the ring \(K_ q[x,y]\).