On the number of distinct values of a class of functions over a finite field

Several authors have recently shown that a planar function over a finite field of order q must have at least (q + 1)/2 distinct values. In this note this result is extended by weakening the hypothesis significantly and strengthening the conclusion. We also give an algorithm for determining whether a given bivariate polynomial phi(X, Y) can be written as f(X + Y) - f(X) - f(Y) for some polynomial f. Using the ideas of the algorithm, we then show a Dembowski-Ostrom polynomial is planar over a finite field of order q if and only if it yields exactly (q + 1)/2 distinct values under evaluation; that is, it meets the lower bound of the image size of a planar function. (C) 2010 Elsevier Inc. All rights reserved.