ON THE NUMBER OF DIRECTIONS DETERMINED BY A PAIR OF FUNCTIONS OVER A PRIME FIELD

SIMEON BALL, ANDRÁS GÁCS, AND PETER SZIKLAI

Abstract. A three-dimensional analogue of the classical direction problem is proposed and an asymptotically sharp bound for the number of directions determined by a nonplanar set in AG(3, p), p prime, is proved. Using the terminology of permutation polynomials the main result states that if there are more than (2⌈\frac{p−1}{6}⌉ + 1)(p + 2⌈\frac{p−1}{6}⌉)/2 ≈ 2p^{2}/9 pairs (a, b) ∈ 𝔽_{p}^{2} with the property that f(x)+ag(x)+bx is a permutation polynomial, then there exist elements c, d, e ∈ 𝔽_{p} with the property that f(x) = cg(x) + dx + e.

1. Introduction

Let q = p^{h} denote a prime power and consider a set U = {(a_{i}, b_{i}) : i = 1, …, q} of q points in the affine plane AG(2, q). The classical direction problem looks for the size of the direction set of U, defined as

D = \{\frac{a_{i} − a_{j}}{b_{i} − b_{j}} : i ≠ j\} ⊆ 𝔽_{q} ∪ \{∞\}.

In the last twenty years or so this problem has received a lot of attention mainly due to its connections with a variety of fields, for example, blocking sets in PG(2, q) [4], permutation polynomials over a finite field [7] and the factorisation of abelian groups [8].

Based on the initial work of Rédei [8] in 1970, the problem was completely solved, whenever the number of directions is at most \frac{q+1}{2}, by Ball, Blokhuis, Brouwer, Storme and Szőnyi [4] and [1] (for small characteristics and a shorter proof). The theorem also characterises the sets of points that have a small number of directions.

The most natural way to formulate an analogous problem for higher dimensions is to take a set U of q^{n−1} points in AG(n, q) and define D to be the set of determined directions, that is, the set of infinite points which are collinear with two points of U. As in the planar case the non-determined directions are those infinite points through which every line contains exactly 1 point of U. This problem was studied in [2], [3] and [10].

In this paper we propose another analogue for the three-dimensional case. This analogue can be formulated for any dimension, but the problem turns out to be significantly harder in three dimensions that this is enough to occupy us here. Apart from trivially applying the results for two and three dimensions, the higher dimensional cases would appear to be, for the moment, inaccessible.

Date: 24 July 2007.

This work was carried out in part under the “Hungarian-Spanish Intergovernmental S and T cooperation programme”. The first author also acknowledges the support of the Ramon y Cajal programme and the project MTM2005-08990-C02-01 of the Spanish Ministry of Science and Education and the project 2005SGR00256 of the Catalan Research Council. The second and third authors were supported by OTKA grants T 043758, T 049662 and F 043772, TÉT grant E-16/04 and Bolyai scholarship.

Let U be a set of q points in AG(3, q) and say that an infinite line l is not determined, if every affine plane through l has exactly one point in common with U.

Before stating the main result of the present paper, we reformulate the aforementioned problems in terms of functions over finite fields. Consider first the planar case. Whenever the size of D is less than q + 1 one can apply an affine transformation so that the image of U is the graph of a function. Therefore we can assume that U = {(x, f(x)) : x ∈ 𝔽_{q}} and

D = \{\frac{f(y) − f(x)}{y − x} | x, y ∈ 𝔽_{q}, x ≠ y\}.

An element c is not in D if and only if x → f(x) − cx is bijective map from 𝔽_{q} to itself. A polynomial which induces a bijective map on 𝔽_{q} is often called a permutation polynomial. Note that over a finite field any function can be written as a polynomial.

Let M(f) be the number of elements of 𝔽_{q} that are not elements of D.

The first analogue to the direction problem in higher dimensions mentioned before, in this terminology, considers the graph of a function from 𝔽_{q}^{n} to itself.

The analogue which we will consider in this paper, in this terminology, considers the graph of a pair of functions f and g over 𝔽_{q}. A line not determined by the graph {(x, f(x), g(x)) | x ∈ 𝔽_{q}} corresponds to a pair (c, d) for which f(x) + cg(x) + dx is a permutation polynomial. We will denote the number of these pairs by M(f, g).

From now on we will only consider the q = p prime case and use the permutation polynomial terminology.

In [8] Rédei and Megyesi proved that if q = p prime and M(f) ≥ (p − 1)/2, then f(x) = cx + d for some c, d ∈ 𝔽_{p}. In other words, the set U is a line.

This result can be used to prove that the only way to factorise the elementary abelian group with p^{2} elements is to use a coset. This was Rédei’s motivation to look at the direction problem for 𝔽_{p}. For more applications of this result to other combinatorial problems, see [7].

In [8] Megyesi provided an example with M(f) = d − 1, for each divisor d of p − 1, which, when d = (p−1)/2, shows this bound to be best possible. Namely, let H be a multiplicative subgroup of 𝔽_{p}, let χ_{H} be the characteristic function of H and let f(x) = χ_{H}(x)x. If d ≠ 1, p − 1 then M(f) = d − 1.

In [7] Lovász and Schrijver proved that if M(f) = (p − 1)/2 then f is affinely equivalent to the example of Megyesi.

In [5] it is proved that if M(f) ≥ 2⌈\frac{p−1}{6}⌉ + 1, then (f(x) − (cx + d))(f(x) − (bx + e)) = 0 for some b, c, d, e ∈ 𝔽_{p}; in other words, the graph of f is contained in the union of two lines.

In [11] Szőnyi proved that if the graph of f is contained in the union of two lines and M(f) ≥ 2, then the graph of f is affinely equivalent to a generalised example of Megyesi detailed above. In the generalised Megyesi example H can be replaced by a union of cosets of a multiplicative subgroup of 𝔽_{p}. In the generalised example the value of M(f) is again d − 1 for some divisor d of p − 1.

Thus, the above results imply that, either M(f) ≤ 2⌈\frac{p−1}{6}⌉, f is affinely equivalent to x^{\frac{p+1}{2}} or f is linear.

In [12] Wan, Mullen and Shiue obtain upper bounds on M(f) in terms of the degree of the polynomial f.

In this article we shall prove that if there are more than (2⌈\frac{p−1}{6}⌉+1)(p+2⌈\frac{p−1}{6}⌉)/2 ≈ 2p^{2}/9 pairs (c, d) ∈ 𝔽_{p}^{2} with the property that x ↦ f(x) + cg(x) + dx is a permutation of 𝔽_{p} then there are elements a, b, e ∈ 𝔽_{p} such that f(x) + ag(x) + bx + e = 0, for all x ∈ 𝔽_{p}; in other words the graph of (f, g), {(x, f(x), g(x)) | x ∈ 𝔽_{p}}, is contained in a plane. At the end of the paper we construct an example showing that for p congruent to 1 modulo 3 this is asymptotically sharp.

2. A slight improvement on [5]

For a polynomial f over 𝔽_{p}, p prime, define

I(f) = min{k + l | ∑_{x∈𝔽_{p}} x^{k}f(x)^{l} ≠ 0}.

In [5] it was proved that if M(f) > (p − 1)/4 and I(f) ≥ 2⌈\frac{p−1}{6}⌉ + 2 then the graph of f is contained in the union of two lines.

Let

π_{k}(Y) = ∑_{x∈𝔽_{p}}(f(x) + xY)^{k}.

It’s a simple matter to check, see [6, Lemma 7.3], that if x ↦ f(x) + ax is a permutation then π_{k}(a) = 0 for all 0 < k < p − 1. Since the polynomial π_{k}(Y) has degree at most k − 1 (the coefficient of Y^{k} is ∑_{x∈𝔽_{p}} x^{k} = 0) it is identically zero for all 0 ≤ k−1 < M(f), unless M(f) = p − 1 in which case f is linear. Hence if f is not linear then I(f) − 1 ≥ M(f).

Thus in [5] it was proved that if M(f) ≥ 2⌈\frac{p−1}{6}⌉ + 1, then the graph of f is contained in the union of two lines.

To be able to prove the main result of this article we need something a little stronger than [5]. We use the same method and essentially follow the proof there but we have to modify the first part of the proof (Lemma 4.1), we manage to avoid the step involving Lemma 4.2, Step 1 and Step 2 are the same, we use a slightly different subspace to be able to reduce Step 3 and Step 4 a little and Step 5 we use in the same way.

In this section we shall prove the following theorem.

Theorem 2.1. If M(f) ≥ (p−1)/6 and I(f) ≥ 2⌈\frac{p−1}{6}⌉+2 then the graph of f is contained in the union of two lines.

The values I(f) and M(f) are invariant under affine transformations and inversion. Replacing f by its inverse is the transformation which switches coordinates, in other words if we switch coordinates then the graph of f, {(x, f(x)) | x ∈ 𝔽_{p}}, becomes the graph of f^{−1}. Let E(f) denote the set of all polynomials that can be obtained from f by applying affine transformations and inversions.

Let (f^{i})^{∘} be the degree of the polynomial f^{i} modulo x^{p} − x. Unless stated otherwise all equations are to be read modulo x^{p} − x.

Note that for any polynomial g of degree less than p the sum

− ∑_{x∈𝔽_{p}} g(x)

is equal to the coefficient of x^{p−1} of g.

Lemma 2.2. If 3 ≤ f^{∘} ≤ (p − 1)/2 then I(f) ≤ (p + 1)/3.

Proof. Write p − 1 = af^{∘} + b with 0 ≤ b < f^{∘}. The degree of f(x)^{a}x^{b} is p − 1, so we have I(f) ≤ a + b.

If f^{∘} = 3 then a + b ≤ (p − 2)/3 + 1 = (p + 1)/3.

If (p + 1)/3 ≤ f^{∘} ≤ (p − 1)/2 then a + b = 2 + p − 1 − 2f^{∘} ≤ (p + 1)/3.

If (p + 1)/4 ≤ f^{∘} ≤ (p − 1)/3 then a + b = 3 + p − 1 − 3f^{∘} ≤ 3 + p − 1 − 3(p + 1)/4 = (p + 1)/4 + 1 ≤ (p + 1)/3 for p ≥ 11.

If 4 ≤ f^{∘} ≤ (p+1)/4 then a+b ≤ (p−b−1)/f^{∘}+b ≤ p/f^{∘}+(bf^{∘}−b−1)/f^{∘} ≤ p/f^{∘}+f^{∘}−2. This is at most (p+1)/3 if and only if the quadratic inequality 3(f^{∘})^{2} −(p+7)f^{∘} +3p ≤ 0 is satisfied. For p ≥ 20, the inequality is satisfied for both f^{∘} = 4 and f^{∘} = (p + 1)/4, so it holds for all values between 4 and (p + 1)/4. For p < 20 a case by case analysis suffices to show that a + b ≤ (p + 1)/3. □

Note that for f^{∘} = 2 we have I(f) = (p − 1)/2 and M(f) = 0 and for f^{∘} = 1 we have I(f) = p − 1 and M(f) = p − 1.

Lemma 2.3. If f^{∘} = (p + 1)/2 then either I(f) ≤ (p + 5)/4 or f is affinely equivalent to x^{\frac{p+1}{2}} .

Proof. After applying a suitable affine transformation we can suppose that f(x) = x^{\frac{p+1}{2}} + g(x) where g^{∘} ≤ (p − 3)/2.

If g^{∘} ≤ 1 then by applying another linear transformation we can subtract g from f and hence f is affinely equivalent to x^{\frac{p+1}{2}} .

Suppose g^{∘} ≥ 2. Write (p − 3)/2 = ag^{∘} + b with 0 ≤ b < g^{∘} and consider the polynomial

f(x)^{a+1}x^{b} = ∑_{i=0}^{a+1} \binom{a + 1}{i}x^{i \frac{p+1}{2} +b}g(x)^{a+1−i}.

We claim that the only term in the sum that has a term of degree x^{p−1} (modulo x^{p} − x) is g(x)^{a}x^{\frac{p+1}{2} +b}. Let r(x) = g(x)^{a+1−i}x^{i \frac{p+1}{2} +b} (modulo x^{p}−x), a typical term in the sum (note that all the binomial coefficients are non-zero). If i is even then r(x) = g(x)^{a+1−i}x^{b+i}, which has degree (a + 1 − i)g^{∘} + b + i = (p − 3)/2 + g^{∘} − (g^{∘} − 1)i < p − 1. If i ≠ 1 is odd then r(x) = g(x)^{a+1−i}x^{\frac{p−1}{2} +i+b}, which has degree (a + 1 − i)g^{∘} + (p − 1)/2 + i + b = p − 2 + g^{∘} − (g^{∘} − 1)i < p − 1.

Hence f(x)^{a+1}x^{b} has degree p − 1 which implies I(f) ≤ a + 1 + b.

Finally, note that a + b ≤ (p − 3)/(2g^{∘}) + g^{∘} − 1, which is at most (p + 1)/4 if 2 ≤ g^{∘} ≤ (p − 3)/4. If g^{∘} > (p − 3)/4 then a = 1 and b = (p − 3)/2 − g^{∘} < (p − 3)/4 and so a + b < (p + 1)/4. □

Let s = ⌈(p − 1)/6⌉.

We will assume from now on that I(f) ≥ 2s + 2. By the definition of I(f) the sum

∑_{x∈𝔽_{p}} x^{k}f(x)

has no term of degree x^{p−1}, for all k = 0, 1, …, 2s, and therefore the degree of f is at most p − 2s − 2. By Lemma 2.2 and Lemma 2.3 the degree of f is at least (p + 3)/2.

Lemma 2.4. There is polynomial in h ∈ E(f) with one of the following properties. Either

(i) for all i such that 1 ≤ i ≤ 2s, (h^{i})^{∘} ≤ h^{∘} + i − 1 and (h^{2})^{∘} = h^{∘} + 1, or (ii) for all i such that 1 ≤ i ≤ 2s, (h^{i})^{∘} ≤ (h^{2})^{∘} + i − 2 and (h^{3})^{∘} = (h^{2})^{∘} + 1,

and h has no root in 𝔽_{p}.

Proof. Let

d(f) = max{(f^{i})^{∘} − i | 1 ≤ i ≤ 2s}

and let d = d(f_{1}) be maximal over all polynomials in E(f). The fact that f^{∘} ≥ (p + 3)/2 implies that d ≥ (p + 1)/2.

Let π(Y) = π_{p−1−d}(Y). The coefficient of Y^{p−1−d−j} in π(Y) is \binom{p−1−d}{j} ∑_{x∈𝔽_{p}} x^{p−1−d−j}f^{j} which, by the definition of d, is non-zero for at least one j where 1 ≤ j ≤ 2s. Hence π(Y) ≢ 0.

If for all a such that f(x) + ax is a permutation polynomial we have π(a) = π′(a) = π′′(a) = 0 then (Y − a)^{3} divides π(Y) and since M(f) ≥ (p − 1)/6 the degree of π, π^{∘} = p − 1 − d ≥ 3M(f) ≥ (p − 1)/2 which isn’t the case.

Since 0 < p − 1 − d < p − 1 we have already seen that π(a) = 0, so either π′(a) ≠ 0 or π′′(a) ≠ 0 for some a.

Let f_{2} be the inverse of the function f(x) + ax.

If

0 ≠ π′(a) = −(d + 1) ∑_{x∈𝔽_{p}} x(f + ax)^{p−2−d}

then ∑_{z∈𝔽_{p}} f_{2}(z)z^{p−2−d} ≠ 0 and so f_{2}^{∘} ≥ d + 1. By the maximality of d, f_{2}^{∘} = d + 1 and so (f_{2}^{i})^{∘} − i ≤ f_{2}^{∘} − 1. If (f_{2}^{2})^{∘} ≤ f_{2}^{∘} then let f_{3} = f_{2} + cx where c is chosen so that (f_{3}^{2})^{∘} ≥ f_{3}^{∘} + 1 and f_{3} is not a permutation polynomial. Note that f_{3}^{2} = f_{2}^{2} + 2cxf_{2} + c^{2}x^{2}.

If

0 ≠ π′′(a) = (d + 1)(d + 2) ∑_{x∈𝔽_{p}} x^{2}(f + ax)^{p−3−d}

then ∑_{z∈𝔽_{p}}(f_{2}(z))^{2}z^{p−3−d} ≠ 0 and so (f_{2}^{2})^{∘} ≥ d+2. By the maximality of d, (f_{2}^{2})^{∘} = d+2 and so (f_{2}^{i})^{∘} − i ≤ (f_{2}^{2})^{∘} − 2. If (f_{2}^{3})^{∘} ≤ (f_{2}^{2})^{∘} then let f_{3} = f_{2} + cx where c is chosen so that (f_{3}^{3})^{∘} ≥ (f_{3}^{2})^{∘} + 1 and f_{3} is not a permutation polynomial.

Finally, let e be an element not in the image of f_{3} and let f_{4} = f_{3} − e. Then f_{4} has no root in 𝔽_{p}. □

The dimension of a subspace of a finite dimensional vector space of polynomials is equal to the number of degrees occurring amongst the elements of a subspace. This is easily seen if we take the canonical basis {1, x, x^{2}, …, x^{t}}. The matrix whose rows form a basis for the subspace can be reduced to a matrix in row echelon form whose rows span the same subspace and correspond to polynomials of different degrees.

Lemma 2.5. There is a polynomial in h ∈ E(f) for which there exist polynomials F, G and H, where H^{∘} − 2 = F^{∘} − 1 = G^{∘} = r ≤ s − 2, (F, G) = 1 and

F h + Gh^{2} = H.

Note that this implies that h satisfies the conditions of Lemma 2.4 (i).

Proof. Let h be a polynomial satisfying the conditions of Lemma 2.4. Since I(h) ≥ 2s + 2 we have (h^{i})^{∘} ≤ p − 2s − 3 + i.

Define subspaces of the vector space of polynomials of maximum degree p − 1

ψ_{j} = {F h + Gh^{2} | F^{∘} ≤ j, G^{∘} ≤ j − 1},

where j ≤ s − 1. If there are polynomials F and G such that F h + Gh^{2} = 0 then since h has no root F + Gh = 0 which is impossible since (hG)^{∘} is at least 3s and at most 5s − 3 < p − 1. Thus the dimension of ψ_{j} is 2j + 1.

Since I(h) ≥ 2s + 1 and 2(j + 1) ≤ 2s, the sum over 𝔽_{p} of the evaluation of the product of any two elements of ψ_{j} is zero, hence the sum of the degrees of any two elements of ψ_{s−1} is not equal to p − 1. The maximum degree of any element of ψ_{s−1} is p − s − 3 and so only half of the degrees in the interval [s + 2, …, p − 1 − (s + 2)] can occur. But dimψ_{s−1} = 2s − 1 > (p − 1 − (s + 2) − (s + 1))/2 and so there is an element H of degree at most s + 1 in ψ_{s−1}.

Let H be of minimal degree, so (F, G) = 1.

If h satisfies case (i) of Lemma 2.4 then (h^{2})^{∘} = h^{∘} + 1 and r = G^{∘} = F^{∘} − 1. Moreover F h^{2} + Gh^{3} = Hh and (h^{3})^{∘} ≤ h^{∘} + 2 implies H^{∘} ≤ r + 2.

If h satisfies case (ii) of Lemma 2.4 then (h^{3})^{∘} = (h^{2})^{∘} + 1 ≥ h^{∘} + 2 and (h^{4})^{∘} ≤ (h^{2})^{∘} + 2. Let F^{∘} = r + 1 and so G^{∘} ≤ r. The equation F h^{3} + Gh^{4} = Hh^{2} implies H^{∘} ≤ r + 2. If G^{∘} ≤ r − 1 then F h^{2} + Gh^{3} = Hh implies r + 2 + h^{∘} ≥ H^{∘} + h^{∘} = r + 1 + (h^{2})^{∘} and so (h^{2})^{∘} = h^{∘} + 1. But then F h + Gh^{2} = H implies G^{∘} = r.

Either way we have r = G^{∘} = F^{∘} − 1 ≥ H^{∘} − 2.

Let h_{1} = h + ax and F_{1} = F − 2axG, G_{1} = G and H_{1} = H − a^{2}x^{2}G + axF. Then F_{1}h_{1} +G_{1}h_{1}^{2} = H_{1} and we can choose a so that H_{1} has degree r +2. Now when we look at ψ_{r+1} for h_{1} we find F_{1}, G_{1} and H_{1} as required. Note that (F, G) = 1 implies (F_{1}, G_{1}) = 1.

□ We wish to prove r = 0. So let us assume r ≥ 1 and define i to be such that (i−2)r +1 ≤ s < (i − 1)r + 1 for r ≥ 2 and i = s for r = 1. Note that r ≤ s − 2 implies i ≥ 3 and that s + r − 1 ≤ 2s − i if i = 3 or i = s and also if both i ≥ 4 and r ≥ 2, since r ≤ (s − 1)/2 and i ≤ (s − 1)/2.

Lemma 2.6. There is a polynomial h ∈ E(f) and a polynomial G, where G^{∘} = r ≤ s − 2, such that for all j = 2, …, i, there is an F_{j} and an H_{j} with the property that (F_{j}, G) = 1,

F_{j}h + G^{j−1}h^{j} = H_{j},

F_{j}^{∘} ≤ (j − 1)(r + 1), H_{j}^{∘} ≤ (j − 1)r + j and H_{i}^{∘} = (i − 1)r + i.

Proof. Let h_{1} satisfy the conditions of Lemma 2.5. We start by proving that there is an h ∈ E(f) for which (h^{i−1})^{∘} ≥ h^{∘} + i − 2.

If (h_{1}^{i−1})^{∘} ≤ h_{1}^{∘} +i−3 then let h = h_{1} +ax. Choose a so that h^{i−1} = ∑_{j=0}^{i−1} \binom{i−1}{j}(ax)^{i−j−1}h_{1}^{j} has degree at least h^{∘} + i − 2 while at the same time the degree of F − 2axG is r + 1 and the degree of H − a^{2}x^{2}G + axF is r + 2.

We will prove the lemma by induction. Lemma 2.5 implies that for j = 2 we can take F_{2} = F and H_{2} = H.

Define F_{j} = −(F_{j−1}F + H_{j−1}G) and H_{j} = −HF_{j−1}. It can be checked by induction, multiplying by Gh and using Gh^{2} = H − F h, that

F_{j}h + G^{j−1}h^{j} = H_{j}.

The degrees satisfy F_{j}^{∘} ≤ (j − 1)(r + 1) and H_{j}^{∘} ≤ (j − 1)r + j and (F_{j}, G) = 1, since (F, G) = 1 by Lemma 2.5 and (F_{j−1}, G) = 1 by induction.

Now (h^{i−1})^{∘} ≥ h^{∘} + i − 2 and the equation F_{i−1}h + G^{i−2}h^{i−1} = H_{i−1} implies that F_{i−1}^{∘} ≥ (i−2)(r+1) and so F_{i−1}^{∘} = (i−2)(r+1). Finally H_{i} = −HF_{i−1} implies H_{i}^{∘} = (i−1)r+i. □

Let h satisfy the conditions of Lemma 2.6. Note that this implies that h satisfies the conditions of Lemma 2.5 and Lemma 2.4 (i). Define

ϕ_{j} = {Ah + Bh^{i} | A^{∘} ≤ j, B^{∘} ≤ j + 1 − i}.

Note that H_{i} ∈ ϕ_{(i−1)r+i−1} and that (i − 1)r + i − 1 ≤ s + r + i − 2 ≤ 2s − 1.

Lemma 2.7. For j ≤ 2s − 1 all polynomials of ϕ_{j} have degree at least H_{i}^{∘} and those of degree at most p − 2 − h^{∘} are multiples of H_{i}.

Proof. If Ah + Bh^{i} = 0 then, since h has no root in 𝔽_{p}, A + Bh^{i−1} = 0. The degree of Bh^{i−1} is at most p − 4 and at least (p + 3)/2 and so A = B = 0. Thus the dimension of ϕ_{j} is 2j + 3 − i.

Suppose that ϕ_{j} contains a polynomial C of degree n but no polynomial of degree n + 1. Then ϕ_{j+1} contains a polynomial of degree n + 1, xC for example, and a polynomial of degree one more than the maximum degree of an element of ϕ_{j}. However dimϕ_{j+1} = dimϕ_{j} + 2, so n is unique. Moreover, the polynomials of degree n + 1 in ϕ_{j+1} are multiples of a polynomial of degree n in ϕ_{j}.

Since j ≤ 2s − 1, ϕ_{j} contains no element of degree p − 1 − h^{∘}. Now H_{i} ∈ ϕ_{(i−1)r+i−1} and is a polynomial of degree less than p − 1 − h^{∘}. It is not a multiple of any polynomial in ϕ_{j} for j < (i − 1)r + i − 1, since if it were there would be a non-constant polynomial K and polynomials A and B with the property that (KA)h + (KB)h^{i} ∈ ϕ_{(i−1)r+i−1}, with (KA)^{∘} ≤ (i − 1)r + i − 1 and (KB)^{∘} ≤ (i − 1)r, which would be a constant multiple of H_{i}. This is not possible since (F_{i}, G) = 1. Thus all polynomials in ϕ_{j} of degree at most p − 2 − h^{∘} are multiples of H_{i} and in particular have degree at least H_{i}^{∘}.

□

The following lemma contradicts the previous one which implies that our assumption that r ≥ 1 was incorrect.

Lemma 2.8. There is a non-zero polynomial of degree less than H_{i}^{∘} in ϕ_{j} for some j ≤ 2s − 2.

Proof. Suppose r ≥ 2 and so i ≤ s. Let

Δ = {Ah + B_{2}h^{2} + … + B_{i−1}h^{i−1} + Ch^{i} | A^{∘} ≤ s − 1, B_{j}^{∘} ≤ r − 1, C^{∘} ≤ s − i}.

Since I(h) ≥ 2s + 1 the sum of the degrees of any two elements of Δ is not equal to p − 1. The maximum degree of any element of Δ is p−s−3 and so only half of the degrees in the interval [s+2, …, p−1−(s+2)] can occur, in other words at most ⌊(p−4−2s)/2⌋ ≤ 2s−2 of the degrees in this interval occur. If dimΔ = (i−2)r+2s−i+1 then there is a polynomial

E = Ah + B_{2}h^{2} + … + B_{i−1}h^{i−1} + Ch^{i}

in Δ of degree at most s + 2 − ((i − 2)r + 2s − i + 1 − (2s − 2)) = s − (i − 2)r + i − 1. If dimΔ < (i − 2)r + 2s − i + 1 then E = 0 ∈ Δ non-trivially. Either way there is a polynomial E ∈ Δ with not all A, B_{j}, C zero where E^{∘} ≤ s − (i − 2)r + i − 1.

Substituting G^{j−1}h^{j} = H_{j} − hF_{j} we have

G^{i−2}E = G^{i−2}Ah + CG^{i−2}h^{i} + ∑_{j=2}^{i−1} B_{j}G^{i−1−j}(H_{j} − hF_{j})

and rearranging

G^{i−2}E − ∑_{j=2}^{i−1} B_{j}G^{i−1−j}H_{j} = (G^{i−2}A − ∑_{j=2}^{i−1} B_{j}F_{j}G^{i−1−j})h + CG^{i−2}h^{i}.

Checking the degrees on the right-hand side we see that the left-hand side is a polynomial in ϕ_{j} for some j ≤ 2s − 2.

The degree of the left-hand side is at most max{s + i − 1, ir − r + i − 2} which is less than H_{i}^{∘} = (i − 1)r + i.

If r = 1 then take i = s and define Δ as above. There is a polynomial E in Δ of degree at most s + 1 and the degree of G^{i−2}E is at most 2s − 1 which is the degree of H_{s}. If we have equality then by Lemma 2.7 the polynomial

(G^{s−2}A − ∑_{j=2}^{s−1} B_{j}F_{j}G^{s−1−j})h + CG^{s−2}h^{s}

is a constant multiple of F_{s}h+G^{s−1}h^{s} which implies CG^{s−2} is a constant multiple of G^{s−1} which it is not since one has degree s − 2 and the other s − 1.

□

We can now prove Theorem 2.1.

Proof. By the previous lemmas there exists polynomials h ∈ E(f) and F of degree 1 and H of degree 2 such that h^{2}+F h = H. Thus (h+F/2)^{2} = H +F^{2}/4. All values of H +F^{2}/4 are squares and so H + F^{2}/4 = (ax + b)^{2}. Hence (h + F/2 − ax − b)(h + F/2 + ax + b) = 0 and the graph of h (and so the graph of f too) is contained in the union of two lines. □

3. Linear combinations of three permutation polynomials

In this section we will need the following theorem which can de deduced from [9, Theorem 0.1].

Theorem 3.1. Let π(Y, Z) be an absolutely irreducible polynomial of degree d with coefficients in 𝔽_{p} such that 1 < d < p. The number of solutions N to the equation π(y, z) = 0 in 𝔽_{p}^{2} satisfies

N ≤ d(d + p − 1)/2.

Let M(f, g) be the number of pairs (a, b) ∈ 𝔽_{p}^{2} for which f(x)+ag(x)+bx is a permutation polynomial. Let

I(f, g) = min{k + l + m | ∑_{x∈𝔽_{p}} x^{k}f(x)^{l}g(x)^{m} ≠ 0}.

Recall s = ⌈\frac{p−1}{6}⌉. Before we prove the main result of this section we need the following lemma

Lemma 3.2. If M(f, g) > (2s + 1)(p + 2s)/2 then I(f, g) ≥ 2s + 2 or there are elements c, d, e ∈ 𝔽_{p} such that f(x) + cg(x) + dx + e = 0 for all x ∈ 𝔽_{p}.

Proof. Let π_{k}(Y, Z) = ∑_{x∈𝔽_{p}}(f(x) + g(x)Y + xZ)^{k}.

By [6, Lemma 7.3], if f(x) + ag(x) + bx is a permutation polynomial then π_{k}(a, b) = 0 for all 0 < k < p − 1. Write

π_{k} = ∏ σ_{j}(Y, Z),

where each σ_{j} is absolutely irreducible. Then ∑ σ_{j}^{∘} = π_{k}^{∘} ≤ k.

Let N_{j} be the number of solutions of σ_{j}(a, b) = 0 in 𝔽_{p} for which f(x) + ag(x) + bx is a permutation polynomial.

If λσ_{j} ∈ 𝔽_{p}[Y, Z], for some λ in an extension of 𝔽_{p}, and σ_{j}^{∘} ≥ 2 then by Theorem 3.1 N_{j} ≤ σ_{j}^{∘}(p + σ_{j}^{∘} − 1)/2.

Suppose σ_{j}^{∘} = 1 and there are at least (p + 1)/2 pairs (a, b) for which σ_{j}(a, b) = 0 and f(x) + ag(x) + bx is a permutation polynomial. Let σ_{j} = αY + βZ + γ. If α ≠ 0 then there are (p + 1)/2 elements b ∈ 𝔽_{p} with the property that αf(x) − (βb + γ)g(x) + bαx = αf(x) − γg(x) + b(αx − β) is a permutation polynomial. By Rédei and Megyesi’s theorem mentioned in the introduction, this implies that αf(x) − γg(x) is linear and hence there are elements c, d, e ∈ 𝔽_{p} such that f(x) + cg(x) + dx + e = 0 for all x ∈ 𝔽_{p}. If α = 0 then there are (p + 1)/2 elements a ∈ 𝔽_{p} with the property that βf(x) − γx + aβg(x) is a permutation polynomial. The set of p points {(βf(x) − γx, βg(x)) | x ∈ 𝔽_{p}} may not be the graph of a function but it is a set of p points that does not determine at least (p+1)/2 directions. Thus it is affinely equivalent to a graph of a function that does not determine at least (p − 1)/2 directions and so by Rédei and Megyesi’s theorem, it is a line. Hence, there are elements c, d and e with the property that c(βf(x) − γx) + dβg(x) + e = 0 for all x ∈ 𝔽_{p}. Thus, either there are elements c, d, e ∈ 𝔽_{p} such that f(x) + cg(x) + dx + e = 0 for all x ∈ 𝔽_{p} or N_{j} ≤ (p − 1)/2.

Suppose λσ_{j} ∉ 𝔽_{p}[Y, Z] for any λ in any extension of 𝔽_{p}. The polynomials σ_{j} = ∑ α_{nm}Y^{n}Z^{m} and σ̂_{j} = ∑ α_{nm}^{p}Y^{n}Z^{m} have at most (σ_{j}^{∘})^{2} zeros in common by Bezout’s theorem. However if (y, z) ∈ 𝔽_{p}^{2} and σ_{j}(y, z) = 0 then σ̂_{j}(y, z) = 0. Hence

N_{j} ≤ (σ_{j}^{∘})^{2} ≤ σ_{j}^{∘}(p + σ_{j}^{∘} − 1)/2,

whenever σ_{j}^{∘} ≤ (p − 1)/2.

Thus if π_{k} ≢ 0 and k ≤ (p − 1)/2 then N(π_{k}), the number of solutions of π_{k}(y, z) = 0 in 𝔽_{p} for which f(x) + ag(x) + bx is a permutation polynomial, satisfies

N(π_{k}) ≤ ∑ N_{j} ≤ ∑ σ_{j}^{∘}(p + σ_{j}^{∘} − 1)/2 ≤ k(p − 1)/2 + \frac{1}{2} ∑(σ_{j}^{∘})^{2}

≤ k(p − 1)/2 + \frac{1}{2}(∑ σ_{j}^{∘})^{2} = (k(p − 1) + k^{2})/2.

By hypothesis π_{k} ≡ 0 or

(2s + 1)(p + 2s)/2 < N_{k} ≤ (k(p − 1) + k^{2})/2,

which gives k ≥ 2s + 2. Now

π_{k}(Y, Z) = ∑_{l=0}^{k} ∑_{m=0}^{k−l} \binom{k}{l}\binom{k − l}{m} (∑_{x∈𝔽_{p}} x^{k−l−m}f(x)^{l}g(x)^{m}) Y^{m}Z^{k−l−m},

and so I(f, g) ≥ 2s + 2.

□

Theorem 3.3. If M(f, g) > (2s + 1)(p + 2s)/2 then there are elements c, d, e ∈ 𝔽_{p} such that f(x) + cg(x) + dx + e = 0.

Proof. If p = 3 and M(f, g) > (2s + 1)(p + 2s)/2 = 15/2 then there is a c such that f(x)+cg(x)+bx is a permutation polynomial for all b ∈ 𝔽_{p}, which can only occur if there is a constant e such that f(x) + cg(x) + e = 0.

So suppose p ≥ 5 and that there are no elements c, d, e ∈ 𝔽_{p} with the property that f(x) + cg(x) + dx + e = 0.

Clearly I(f + ag) ≥ I(f, g) for all a ∈ 𝔽_{p} and I(f, g) ≥ 2s + 2 by Lemma 3.2.

There is an a_{1} ∈ 𝔽_{p} with the property that

M(f + a_{1}g) ≥ M(f, g)/p ≥ (p − 1)/6.

By Theorem 2.1 there are constants c, d, c′, d′ ∈ 𝔽_{p} with the property that

(f + a_{1}g + cx + d)(f + a_{1}g + c′x + d′) = 0

so the graph of (f, g), the set of points {(x, f(x), g(x)) | x ∈ 𝔽_{p}}, is contained in the union of two planes.

By Rédei and Megyesi’s theorem, since we have assumed that the graph of f + a_{1}g is not a line, M(f + a_{1}g) ≤ (p − 1)/2 and so there is an a_{2} ≠ a_{1} with the property that

M(f + a_{2}g) ≥ (M(f, g) − (p − 1)/2)/(p − 1) ≥ (p − 1)/6.

Thus the graph of (f, g) is contained in the union of two other planes, different from the ones before. The intersection of the two planes with the two planes is four lines and so the graph of (f, g) is contained in the union of four lines.

Similarly, since (M(f, g)−(p−1))/(p−2) ≥ (p−1)/6 and (M(f, g)−3(p−1)/2)/(p−3) ≥ (p − 1)/6, there is an a_{3} and an a_{4} with that property that M(f + a_{3}g) ≥ (p − 1)/6 and M(f + a_{4}g) ≥ (p − 1)/6 and so the graph of (f, g) is contained in two other distinct pairs of planes. The four lines span three different pairs of planes and so the graph of (f, g) is contained in the union of two lines and hence a plane, which is a contradiction. □

There is an example when q is an odd prime (power) congruent to 1 modulo 3 with M(f, g) = 2(q − 1)^{2}/9 − 1 where the graph of (f, g) is not contained in a plane, which shows that the bound is the right order of magnitude.

Let E = {e ∈ 𝔽_{q} | e^{(q−1)/3} = 1}∪{0}. Then the set S = {(e, 0, 0), (0, e, 0), (0, 0, e) | e ∈ E} is a set of q points. If π, the plane defined by

X_{1} + aX_{2} + bX_{3} = c,

is incident with (e, 0, 0) for some e ∈ E then c ∈ E. Likewise if it is incident with (0, e, 0) for some e ∈ E then a/c ∈ E and if it is incident with (0, 0, e) for some e ∈ E then b/c ∈ E.

If π is incident with two points of S then either a ∈ E, b ∈ E or a/b ∈ E. Thus if a, b and a/b are not elements of E then π and all the planes parallel to π are incident with exactly one point of S. There are 2(q − 1)^{2}/9 such sets of parallel lines.

If we make a change of coordinates so that {X_{1} = x | x ∈ 𝔽_{q}} is one such set of parallel planes then there are functions f and g for which S = {(x, f(x), g(x)) | x ∈ 𝔽_{q}}. Each other set of parallel lines with the above property corresponds to a pair (a, b) such that f(x)+ag(x)+bx is a permutation polynomial. Thus M(f, g) = 2(q −1)^{2}/9−1. Explicitly the functions f and g can be defined by f(x) = χ_{H}(x)x and g(x) = χ_{ϵH}(x)x, where χ_{H} is the characteristic function of H = {t^{3} | t ∈ 𝔽_{p}} and ϵ is a primitive third root of unity.

4. Acknowledgements

We are grateful to Tamas Szőnyi for some valuable discussions and to Vsevolod Lev for his help in making the article accessible to a wider audience.

References

[1] S. Ball, The number of directions determined by a function over a finite field, J. Combin. Theory Ser. A, 104 (2003) 341–350.

[2] S. Ball, On the graph of a function in many variables over a finite field, Des. Codes Cryptogr., to appear.

[3] S. Ball and M. Lavrauw, On the graph of a function in two variables over a finite field, J. Algebraic Combin., 23 (2006) 243–253.

[4] A. Blokhuis, S. Ball, A. E. Brouwer, L. Storme and T. Szőnyi, On the number of slopes of the graph of a function defined over a finite field, J. Combin. Theory Ser. A, 86 (1999) 187–196.

[5] A. Gács, On a generalization of Rédei’s theorem, Combinatorica, 23 (2003) 585–598.

[6] R. Lidl and H. Niederreiter, Finite Fields, Second Edition, Cambridge University Press, 1997.

[7] L. Lovász and A. Schrijver, Remarks on a theorem of Rédei, Studia Scient. Math. Hungar. 16 (1981) 449–454.

[8] L. Rédei, Lückenhafte Polynome über endlichen Körpen, Birkhäuser-Verlag, Basel, 1970. (English translation: Lacunary Polynomials over finite fields, North-Holland, Amsterdam, 1973.)

[9] K-O. Stöhr and J. F. Voloch, Weierstrass points and curves over finite fields, Proc. London Math. Soc., 52 (1986) 1–19.

[10] L. Storme and P. Sziklai, Linear point sets and Rédei type k-blocking sets in PG(n, q), J. Algebraic Combin., 14 (2001) 221–228.

[11] T. Szőnyi, Combinatorial problems for Abelian groups arising from geometry, Periodica Polytechnica, 19 (1991) 197–212.

[12] D. Wan, G. L. Mullen and P. J.-S. Shiue, The number of permutation polynomials of the form f(x) + c(x) over a finite field, Proc. Edinburgh Math. Soc, 38 (1995) 133–149.

Simeon Ball

Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Jordi Girona 1-3, Mòdul C3, Campus Nord, 08034 Barcelona, Spain

simeon@mat.upc.es

András Gács and Peter Sziklai

Eötvös University Budapest, Pázmány P. sétány 1/c, Budapest, Hungary H-1117

gacs@cs.elte.hu, sziklai@cs.elte.hu