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

Let ff be a function from a finite field FpFp with a prime number pp of elements, to FpFp. In this article we consider those functions f(X)f(X) for which there is a positive integer n>2p−1−114 with the property that f(X)if(X)i, when considered as an element of Fp[X]/(Xp−X)Fp[X]/(Xp−X), has degree at most p−2−n+ip−2−n+i, for all i=1,…,ni=1,…,n. We prove that every line is incident with at most t−1t−1 points of the graph of ff, or at least n+4−tn+4−t points, where tt is a positive integer satisfying n>(p−1)/t+t−3n>(p−1)/t+t−3 if nn is even and n>(p−3)/t+t−2n>(p−3)/t+t−2 if nn is odd. With the additional hypothesis that there are t−1t−1 lines that are incident with at least tt points of the graph of ff, we prove that the graph of ff is contained in these t−1t−1 lines. We conjecture that the graph of ff is contained in an algebraic curve of degree t−1t−1 and prove the conjecture for t=2t=2 and t=3t=3. These results apply to functions that determine less than p−2p−1+114 directions. In particular, the proof of the conjecture for t=2t=2 and t=3t=3 gives new proofs of the result of Lovász and Schrijver [L. Lovász, A. Schrijver, Remarks on a theorem of Rédei, Studia Sci. Math. Hungar. 16 (1981) 449–454] and the result in [A. Gács, On a generalization of Rédei’s theorem, Combinatorica 23 (2003) 585–598] respectively, which classify all functions which determine at most 2(p−1)/32(p−1)/3 directions.