On the graph of a function over a prime field whose small powers have bounded degree

Abstract. Let f be a function from a finite field Fp with a prime number p of elements, to Fp. In this article we consider those functions f(X) for which there is a positive integer n> 2 p − 1 − 114 with the property that f(X)i, when considered as an element of Fp[X]/(Xp −X), has degree at most p − 2 − n+ i, for all i = 1,..., n. We prove that every line is incident with at most t − 1 points of the graph of f, or at least n + 4 − t points, where t is a positive integer satisfying n> (p − 1)/t + t − 3 if n is even and n> (p − 3)/t + t − 2 if n is odd. With the additional hypothesis that there are t − 1 lines that are incident with at least t points of the graph of f, we prove that the graph of f is contained in these t − 1 lines. We conjecture that the graph of f is contained in an algebraic curve of degree t − 1 and prove the conjecture for t = 2 and t = 3. These results apply to functions that determine less than p−2√p − 1+ 114 directions. In particular, the proof of the conjecture for t = 2 and t = 3 gives new proofs of the result of Lovász and Schrijver [7] and the result in [5] respectively, which classify all functions which determine at most 2(p − 1)/3 directions. 1