Lacunary Polynomials over Finite Fields Course notes

Javier Herranz

Abstract

This is a summary of the course Lacunary Polynomials over Finite Fields, given by Simeon Ball, from the University of London, in March 5-8, 2002, at the Universitat Politècnica de Catalunya (Barcelona). Explanations of Dr. Ball have been complemented with some results of [3] and [4].

1 Introduction

The object of the talks was to give an introduction to lacunary polynomials over finite fields and show some applications to the problem of determining the number of slopes defined by the graph of a function on a finite field and to the size of minimum blocking sets in projective planes.

The notes are organised as follows. Section 2 is an introduction to lacunary polynomials, fully reducible polynomials with a gap between its degree and second degree, together with main results on the size of this gap. In Section 3, application of these results to obtain bounds on the number of slopes of the graph of a function defined on a finite field. Section 4 deals with an application to bound the size of a minimal blocking set in a projective plane. Finally, Section 5 includes some recent results on the above two problems together with open problems and conjectures.

2 Lacunary Polynomials

Definition 2.1. Let K be a (commutative) field. A polynomial f ∈ K[X] is said to be fully reducible if f factors completely into linear factors over K[X]; in other words, K is a splitting field for f.

We denote by f^{∘} the degree of f, and by f^{∘∘} its second degree, that is, the degree of f(x) − c_{f^{∘}}X^{f^{∘}}, were c_{f^{∘}} is the leading coefficient of f.

Definition 2.2. We say a polynomial f is a lacunary polynomial if it is fully reducible and f^{∘∘} < f^{∘} − 1.

For example, any polynomial in ℂ[X] is fully reducible. In ℝ[X], if a polynomial f is lacunary, then f^{∘} − f^{∘∘} ≤ 2 or f(X) = cX^{f^{∘}}. We are interested in K = GF (q), the finite field with q elements. So q = p^{h} for some prime p and some integer h. Let us see some examples in this case.

Example 2.1. f(X) = X^{q} − X = ∏_{a∈GF (q)}(X − a). In this case, f^{∘∘} = 1.

Example 2.2. If q is even, we can define the polynomial

T r_{q→2}(X) := X + X^{2} + X^{4} + … + X^{q/2},

which satisfies T r(X) divides (X^{q} + X), since

(T r(X)_{q→2})^{2} + T r(X)_{q→2} = X^{q} + X,

and thus the polynomial is fully reducible. Here f^{∘∘} = f^{∘}/2.

Lacunary polynomials were introduced by Rédei in [11]. The main results in this section (basically Theorems 2.1 and 2.2) are due to him. Before stating the first theorem, let us consider a polynomial

f(X) = a_{0} + a_{1}X + … + a_{n}X^{n} = ∑_{i=0}^{n} a_{i}X^{i} ∈ GF (q)[X].

If we define

f′(X) = ∑_{i=0}^{n} ia_{i}X^{i−1},

then we have

f′ = 0 ⟺ f ∈ GF (q)[X^{p}].

Definition 2.3. We say that a is a k-fold root of f if (X − a)^{k}|f(X).

If a is a k-fold root of f, then it is clear that a is a (k − 1)-fold root of f′. Furthermore, if p|k, then a is also a k-fold root of f′; indeed, if f(X) = (X − a)^{k}g(X), then

f′(X) = (X − a)^{k}g′(X) + g(X)k(X − a)^{k−1} = (X − a)^{k}g′(X),

because k = 0 in GF (q)[X].

Theorem 2.1. Let f(X) = X^{p} +g(X) , with g^{∘} = f^{∘∘} < p, be fully reducible in GF (p)[X], p a prime. Then either g is constant, or g = −X, or g^{∘} ≥ (p + 1)/2.

Proof. We note first that f′ = g′. Let us now write f(X) = r(X)s(X), where s(X) contains all the linear factors of f exactly once. So r(X) contains all the repeated factors of f. Now

\begin{matrix}s(X)|f − (X^{p} − X) = X + g \\ r(X)|f′ = g′ \end{matrix} \} ⟹ f(X) = r(X)s(X) | (X + g)g′ (1)

We consider 3 cases:

(a) If g′ = 0, then \begin{matrix}g ∈ K[X^{p}] \\ g^{∘} < p \end{matrix} \} ⟹ g is constant.

(b) If g′ ≠ 0 and X + g ≠ 0 (i.e., g ≠ −X), then comparison of degrees in the divisibility relation (1) gives:

p ≤ g^{∘} − 1 + g^{∘} ⟹ g^{∘} ≥ \frac{p + 1}{2}

(c) Finally, if g′ ≠ 0 and X + g = 0, then g = −X.

When g^{∘} = (p + 1)/2 holds, we can be more precise about the structure of f. The divisibility relation (1) is actually an equality (up to scalars), that is,

X^{p} + g = c(X + g)g′,

where c is a scalar and g(X) = ∑_{i=0}^{(p+1)/2} g_{i}X^{i} with α = g_{\frac{p+1}{2}} ≠ 0. If we replace X by X + a, then f changes to f(X + a) = X^{p} + a + g(X + a), which has the same lacunarity type, but has coefficient of X^{\frac{p−1}{2}} equal to zero if we choose a = −2g_{\frac{p−1}{2}} /g_{\frac{p+1}{2}} . So we can assume without loss of generality that g_{\frac{p−1}{2}} = 0.

We now have

X^{p} + ∑_{i=0}^{\frac{p+1}{2}} g_{i}X^{i} = c(X + ∑_{i=0}^{\frac{p+1}{2}} g_{i}X^{i})(∑_{i=0}^{\frac{p+1}{2}} ig_{i}X^{i−1})

Let k < (p−1)/2 be the largest index for which β = g_{k} ≠ 0. Assume that k > 1; then equating the coefficients of X^{k+ \frac{p−1}{2}} we obtain: 0 = c(αβ)(k + \frac{p−1}{2}). Since c ≠ 0 and α ≠ 0 and k < (p + 1)/2, then we would have β = 0, a contradiction. So k = 1 and

g(X) = αX^{\frac{p+1}{2}} + βX + γ .

By comparing the coefficients of X^{\frac{p−1}{2}} in the two sides of the equality X^{p} + g = c(X + g)g′ we obtain γ = 0. Hence, if g^{∘} = (p + 1)/2, then up to a linear transformation

f(X) = X^{p} + αX^{\frac{p+1}{2}} + βX.

Theorem 2.2. Let f = X^{q}+g(X) be fully reducible in GF (q)[X], where q = p^{h}, and let e be such that f ∈ GF (q)[X^{p^{e}}] \ GF (q)[X^{p^{e+1}}]. Then

(i) p^{e} = q and f = (X + c)^{q} = X^{q} + c, for some c ∈ GF (q), or

(ii) g = −X and f = X^{q} − X, or

(iii) g^{∘} ≥ p^{e}⌈\frac{q/p^{e}+1}{p^{e}+1}⌉.

Proof. Write f = f_{1}^{p^{e}}, so f_{1} = X^{q/p^{e}} + g_{1}, with g = g_{1}^{p^{e}}. Again we write f_{1} = r(X)s(X), where s contains linear factors of f_{1} exactly once, and r contains the repeated linear factors.

Note that, excluding the case in which g = c is a constant and hence e = h (giving (i)), we have g′_{1} ≠ 0, because otherwise we would have g ∈ GF (q)[X^{p^{e+1}}] and so f ∈ GF (q)[X^{p^{e+1}}], which is not the case.

Now we have

\begin{matrix}s(X)|f − (X^{q} − X) = X + g \\ r(X)|f′_{1} = g′_{1} ≠ 0 \end{matrix} \} ⟹ f_{1}|(X + g)g′_{1}  (2)

Either X + g = 0, i.e. g = −X, giving (ii), or f_{1}^{∘} ≤ g^{∘} + g_{1}^{∘} − 1; the last case implies q/p^{e} ≤ g^{∘} + g^{∘}/p^{e} − 1, and so

q/p^{e} + 1 ≤ (\frac{p^{e} + 1}{p^{e}})g^{∘}.

Since g^{∘}/p^{e} is an integer, we have that ⌈\frac{q/p^{e}+1}{p^{e}+1}⌉ ≤ g^{∘}/p^{e} and finally

g^{∘} ≥ p^{e}⌈\frac{q/p^{e} + 1}{p^{e} + 1}⌉

As in Theorem 2.1, if there is equality in Theorem 2.2 (iii) then the divisibility relation (4) becames an equality (up to scalaras), that is,

f_{1} = X^{q/p^{e}} + g_{1} = c(X + g)g′_{1} = c(X + g_{1}^{p^{e}})g′_{1},

for some scalar c. If we denote t = p^{e} and replace g_{1} by g, what can we say about the equation X^{q/t} + g = (X + g^{t})g′ ? Let’s look at the case g′ = 1.

Lemma 2.1. If X^{q/t} + g = X + g^{t} where q = p^{h} and t = p^{e}, then X^{q/t} + g = T r_{q→t}(X) = X + X^{t} + … + X^{q/t} and GF (t) is a subfield of GF (q), i.e. e|h.

Proof. First note that g^{∘} = q/t^{2}. Write g = ∑_{i=0}^{q/t^{2}} g_{i}X^{i} and, equating coefficients, we obtain that g_{1} = 1, g_{k} = 0, for 1 < k < t, g_{t} = 1, and so on. That is, all non-zero coefficients are coefficients of terms of order t^{i}. However, g_{q/t^{2}} = 1 ≠ 0, so there exists some positive integer i such that q/t^{2} = t^{i}. Then, q = t^{i+2} ⇒ p^{h} = p^{e(i+2)} ⇒ e|h.

A general result in this direction is given in the following result whose proof can be found in Lemma 3.2 of [3].

Lemma 2.2. Let X^{q/t} + g = (X + g^{t})g′, where t = p^{e} > 1. Then, either g′ is constant, or

(1) for some i > 0, g′ ∈ GF (q)[X^{t^{i}}]\GF (q)[X^{t^{i+1}}], and

(2) \frac{q(t−1)}{t^{i+2}} ≤ (g′)^{∘} ≤ \frac{(t−1)(q−t^{i+1})}{t^{i+2}−t}, and

(3) g′ = ητ^{t−1}, for some polynomials η ∈ GF (q)[X^{t^{i+1}}] and τ ∈ GF (q)[X^{t^{i}}].

3 Number of Slopes of the Graph of a Function Defined on a Finite Field

Let f be a function f : GF (q) → GF (q). We want to find answers to the question: how few directions can be determined by a function f? Or in other words, how small can the set D be, where

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

Let us look at a couple of examples.

Example 3.1. If q is a square and f(X) = X^{\sqrt{q}}, then we have

\frac{f(x) − f(y)}{x − y} = \frac{x^{\sqrt{q}} − y^{\sqrt{q}}}{x − y} = \frac{(x − y)^{\sqrt{q}}}{x − y} = (x − y)^{\sqrt{q}−1},

and so D = \{z^{\sqrt{q}−1} | z ∈ GF (q)^{∗}\}. Since (z^{\sqrt{q}−1})^{\sqrt{q}+1} = z^{q−1} = 1, we have that the elements in D are the solutions of the equation X^{\sqrt{q}+1} = 1 (roots of the unity), so we can conclude that |D| = \sqrt{q} + 1.

Example 3.2. If q is even and f(X) = T r_{q→2}(X) = X +X^{2} +X^{4} +…+X^{q/2}, we have that f(X) divides X^{q} + X, since f^{2} + f = X^{q} + X has q/2 different roots, and that f(x) + f(y) = f(x + y). Then:

\frac{f(x) − f(y)}{x − y} = \frac{T r_{q→2}(x + y)}{x + y}.

So we can write

D = \{\frac{T r(z)}{z} | z ∈ GF (q)^{∗}\} = \{0\} ∪ \{\frac{T r(z)}{z} | T r(z) ≠ 0\}.

But now, if we put u = f(x) = T r_{q→2}(x) = x + x^{2} + x^{4} + … + x^{q/2}, then u^{2} = x^{2} + x^{4} + … + x^{q/2} + x^{q} = x^{2} + x^{4} + … + x^{q/2} + x = u. We have u^{2} = u, and so u ∈ GF (2) = {0, 1}. Hence we can write

D = \{0\} ∪ \{\frac{1}{z} | T r(z) ≠ 0\}.

Since the equation T r(z) = 0 has q/2 different solutions, the number of elements z such that T r(z) ≠ 0 is also q/2, and so we have that |D| = q/2 + 1.

We want to find bounds for the value N = |D|, in the case of any function f.

Theorem 3.1. (Rédei) Let f be a function f : GF (q) → GF (q) with q = p^{h}, and U = {(x, f(x)) | x ∈ GF (q)}. Let e be the largest integer such that each line (between two points of U) is incident with a multiple of p^{e} points of U. Then either

1. e = 0 and (q + 3)/2 ≤ N;

2. e > 0 and

p^{e}⌈\frac{q/p^{e} + 1}{p^{e} + 1}⌉ + 1 ≤ N ≤ (q − 1)/(p^{e} − 1);

3. f is linear, e = h and N = 1.

Proof. Consider the following polynomial in two variables:

R(X, Y) = ∏_{x∈GF (q)}(X + xY − f(x))

Let c ∈ GF (q) and suppose that two of the linear factors in R(X, c) are the same. That is, there exist x, y ∈ GF (q) such that x ≠ y and X + xc − f(x) = X + yc − f(y). Then c = \frac{f(x)−f(y)}{x−y} ∈ D.

On the other hand, if c ∉ D, then all linear factors of R(X, c) are different, and so R(X, c) = X^{q} − X. We now write

R(X, Y) = ∑_{j=0}^{q} h_{j}(Y)X^{q−j}

where h_{j} is a polynomial in Y of degree at most j (because the total degree of R(X, Y) is q). In fact h_{j}^{∘} ≤ j − 1, for 1 ≤ j ≤ q − 2, since the coefficient of Y^{j} in h_{j}(Y) is the coefficient of X^{q−j} in

∏_{x∈GF (q)}(X + xY) = X^{q} + XY^{q−1}.

Choose c ∉ D. Then, h_{j}(c) = 0 for 1 ≤ j ≤ q − 1. Since h_{j}^{∘} ≤ j − 1 for 1 ≤ j ≤ q − 2 and there exist q − N = |GF (q) \ D| different values of c such that h_{j}(c) = 0 we can conclude that h_{j} ≡ 0 when j − 1 < q − N. Hence,

R(X, Y) = X^{q} + h_{q−N+1}(Y)X^{N−1} + ( lower order terms in X).

Now choose c ∈ D. We have R(X, c) = X^{q} + g(X), where g^{∘} ≤ N − 1.

If g(X) = −X, then R(X, c) = X^{q} − X ⇒ c ∉ D, a contradiction. So we have g(X) ≠ −X. Put now f(X) = R(X, c), and use Theorem 2.2. The required condition on the value e in Theorem 2.2 is implied by the geometric condition that is imposed on e in the current theorem. Statement (ii) of Theorem 2.2 does not hold, because g(X) ≠ −X. Possibility (i) means that R(X, c) = (X + α)^{q}. But R(X, c) = ∏_{x∈GF (q)}(X + xc − f(x)), so we conclude that xc − f(x) = α, for all x ∈ GF (q). Thus, f(X) = cX − α is a linear function, and it is easy to see that then N = 1, giving statement (3) of this theorem.

Possibility (iii) gives us

N − 1 ≥ g^{∘} ≥ p^{e}⌈\frac{q/p^{e} + 1}{p^{e} + 1}⌉.

Note that, if e = 0, then we have N − 1 ≥ g^{∘} ≥ \frac{q+1}{2}, and so N ≥ \frac{q+3}{2}, giving us statement (1) of the theorem.

This theorem was subsequently improved to the following theorem in [3], with the exception of the cases p^{e} = 2 and 3. A proof of the following theorem which includes the cases p^{e} = 2 and 3 can be found in [1].

Theorem 3.2. ^{1} Let f be a function f : GF (q) → GF (q) with q = p^{h}, and U = {(x, f(x)) | x ∈ GF (q)}. Let e be the largest integer such that each line (between two points of U) is incident with a multiple of p^{e} points of U. Then all the following statements hold;

1. e = 0 and (q + 3)/2 ≤ N;

2. e > 0, e|h and q/p^{e} + 1 ≤ N ≤ (q − 1)/(p^{e} − 1);

3. f is linear, e = h and N = 1.

Moreover if p^{e} > 2 then the graph of f is GF (p^{e})-linear.

Note that for many values c (those such that c ∉ D), we have that f(X)−cX is a permutation polynomial. That is, f(X) − cX : GF (q) → GF (q) is a permutation (bijective function) of the elements of GF (q).

4 Blocking Sets

We start this section by explaining the basic notions of affine and projective planes. The affine plane over a finite field GF (q) is defined as a set of points P = {(x, y) | x, y ∈ GF (q)}, and a set of lines, which are defined as subsets of points that are solutions of linear equations. We denote these lines as

ℓ_{c,d} := {(x, y) | y = cx + d}.

1Lecturer’s note: It was my original intention to give a proof of the bounds in this theorem following the lacunary polynomial approach in [3]. However this turned out to be too time consuming. Fortunately I discovered a simpler proof using Hasse derivatives but only after the course had finished. This is the proof that appears in [1]. It should be possible to give a sketch that proof as well in any future course.

Furthermore, there are vertical lines ℓ_{e} := {(e, y) | y ∈ GF (q)}. Each line contains q different points of P. There are in all q^{2} points and q^{2} + q lines. We denote this affine plane as AG(2, q).

To complete this to the projective plane P G(2, q) we must add points (c), where (c) is incident with all lines with direction c, i.e. ℓ_{c,d} for all d ∈ GF (q). We must add also a point (∞) incident with all vertical lines ℓ_{e}, and the line ℓ_{∞} = {(c) | c ∈ GF (q)} ∪ {(∞)}. Now the number of points |P| is equal to the number of lines |L| which is equal to q^{2} + q + 1, and each line contains q + 1 points. Moreover, the following properties are satisfied:

(P1) any two points are incident with a unique line,

(P2) any two lines are incident with a unique point,

(P3) there is a set of four points no three of which are collinear (in other words, there exists a quadrangle).

Any incident structure satisfying (P1), (P2) and (P3) is called a projective plane.

Definition 4.1. The order of a projective plane is the number of points on a line minus one. For example, the order of P G(2, q) is q.

If q is a prime power, then as we have seen there exist projective planes of order q. It is not known whether there exist projective planes of non-prime power order.

Definition 4.2. A blocking set B in a projective plane Π is a set of points such that every line in Π is incident with some point in B.

Example 4.1. Let B be the set of points on a line. Then |B| = q + 1, and it is trivial to see that B is a blocking set.

Example 4.2. If D is the set of directions determined by a function f, as defined in Section 2, then

B = {(x, f(x)) | x ∈ GF (q)} ∪ {(c) | c ∈ D}

is a blocking set of q + N points. Indeed, if a line l of the affine plane AG(2, q) is not incident with B_{1} = {(x, f(x)) | x ∈ GF (q)} then one of the q − 1 parallel lines to l must meet B_{1} in at least two points and therefore its direction c is a point in B.

Definition 4.3. A minimal blocking set is a blocking set that contains no proper subset that is a blocking set.

Proposition 4.1. Let B be a blocking set with |B| = q + k such that B does not contain any line. Then every line is incident with at most k points of B.

Proof. Assume that there exists a line ℓ incident with k + 1 points of B. Let P be a point of this line ℓ that is not in B (P exists because B does not contain any line). Now we know that there are q + 1 different lines incident with P, and that any of these lines must be also incident with a (different) point of B. So we have that line ℓ is incident with k + 1 different points of B, and each of the q other lines is incident with a different point of B. Therefore, |B| ≥ k + 1 + q, a contradiction.

Note that if there is a line ℓ such that |ℓ ∩ B| = k, then |B| ≥ q + k.

Definition 4.4. If B is a minimal and non-trivial (it does not contain any line) blocking set of size q + k such that there is a line incident with k points of B, then B is called a Rédei blocking set.

Any Rédei blocking set can be constructed from the graph of a function.

Example 4.3. Let q be odd and B the Rédei blocking set associated to the function f(x) = x^{\frac{q+1}{2}} , that is,

B = \{(x, x^{\frac{q+1}{2}} ) | x ∈ GF (q)\} ∪ \{(±1)\} ∪ \{(\frac{1 + x}{1 − x}) | x not an square\}.

Then |B| = q + 2 + (q − 1)/2 = 3(q + 1)/2.

Example 4.4. GF (q_{1}) a subfield of GF (q). Define B = {(x, T r_{q→q_{1}}(x)) | x ∈ GF (q)} ∪ {(c) / c ∈ D}.

Then |B| = q + q/q_{1} + 1 (applying some techniques similar to those in Example 3.2). Note that if q is a square, taking q_{1} = \sqrt{q}, we obtain |B| = q + \sqrt{q} + 1.

Theorem 4.1. (Bruen [5]) If B is a blocking set, not containing a line, in a projective plane of order q, then |B| ≥ q + \sqrt{q} + 1.

Proof. If there is a line incident with more than \sqrt{q} + 1 points of B, then Proposition 4.1 is enough. Otherwise, we can write |B| = q + k + 1 (we want to see k ≥ \sqrt{q}), and let τ_{i} = |\{lines incident with exactly i points of B\}|. Then we have:

∑_{i=0}^{k+1} τ_{i} = q^{2} + q + 1  (3)

∑_{i=0}^{k+1}(k + 1 − i)(i − 1)τ_{i} ≥ 0  (4)

Inequality 4 holds because all terms of the sum are greater or equal to 0 (note that τ_{0} = 0, by the definition of a blocking set).

Now we consider pairs (P, ℓ) such that P ∈ B is incident with line ℓ, and count these pairs in two different ways, obtaining

|B|(q + 1) = ∑_{i=0}^{k+1} iτ_{i}  (5)

Finally, if we count in two different ways the number of triples (P, Q, ℓ) such that P, Q ∈ B, P ≠ Q and P, Q incident with line ℓ, we obtain

|B|(|B| − 1) = ∑_{i=0}^{k+1} i(i − 1)τ_{i}  (6)

Then, combining equations (3), (4), (5) and (6), it is easy to deduce that k ≥ \sqrt{q}.

Theorem 4.2. (Blokhuis [2]) Let p be a prime and B a blocking set in P G(2, p) not containing a line. Then |B| ≥ \frac{3(p+1)}{2}.

Proof. Let |B| = p + k + 1. We can assume that ℓ_{∞} is a tangent of B and that the point of B incident with ℓ_{∞} is the point (∞). Then B\ℓ_{∞} ⊂ AG(2, p) and |B\ℓ_{∞}| = p+k. Now the p^{2} lines defined by Y = −yX −x, where x, y ∈ GF (p), are the p^{2} lines not incident with (∞). We define

R(X, Y) = ∏_{(a,b)∈B\ℓ_{∞}}(X + aY + b)

Now, for all x, y ∈ GF (p), there exists a point (a, b) ∈ B\ℓ_{∞} such that the line Y = −yX − x is incident with point (a, b). That is, b = −ya − x and so x + ay + b = 0, which implies R(x, y) = 0. So R(X, Y) ∈ GF (p)[X, Y] and R(x, y) = 0 for all (x, y) ∈ GF (p)^{2}. This implies that there exist G, H ∈ GF (p)[X, Y] such that

R(X, Y) = (X^{p} − X)G(X, Y) + (Y^{p} − Y)H(X, Y).

Note that G^{∘} = k and H^{∘} ≤ k. Now we consider R̄(X, Y) = ∏(X + aY) = X^{p}Ḡ + Y^{p}H̄, where Ḡ, H̄, R̄ are the homogeneous parts of G, H, R of highest degree. If we put Y = 1, we obtain ∏(X + a) = X^{p}g + h = f, with f(X) = R̄(X, 1), g = Ḡ(X, 1) and h = H̄(X, 1). Note again that g^{∘} = k and h^{∘} ≤ k, and f is fully reducible over GF (p).

We split up f = rs, where s(X) contains all the linear factors of f exactly once, and r(X) the repeated linear factors. Now s divides X^{p} − X and f and so s divides f − (X^{p} − X)g = Xg + h. The polynomial r divides f and f′ and hence divides f′g − g′f = h′g − g′h. Therefore

f | (Xg + h)(h′g − g′h).

Now Xg ≠ h since g^{∘} = k ≥ h^{∘}.

If h′g − g′h ≠ 0 then comparing degrees in this divisibility implies p + k ≤ k + 1 + 2k − 2. Note that the coefficients of the term of degree 2k − 1 in h′g and g′h are the same and so the degree of h′g − g′h is at most 2k − 2. Hence k ≥ (p + 1)/2 and |B| ≥ 3(p + 1)/2.

If h′g − g′h = 0 then (gh^{p−1})′ = 0. Let m be the largest common factor of g and h, (g, h) = m and write g = mg_{1} and h = mh_{1} so that (g_{1}, h_{1}) = 1. Then (g_{1}h_{1}^{p−1})′ = 0 and so g_{1}h_{1}^{p−1} is a p-th power and since h_{1} and g_{1} have no common factors they are p-th powers themselves. If g_{1}^{∘} or h_{1}^{∘} are not zero then they are at least p and we have that k ≥ p and |B| ≥ 2p + 1. If not, then g_{1} and h_{1} are both constant and

f = m(X^{p}g_{1} + h_{1}) = m(Xg_{1} + h_{1})^{p}.

Let a = h_{1}/g_{1} ∈ GF (p). Then X + a occurs p times as a factor of f and by the definition of f this implies that the blocking set has p points incident with the line X = a. Hence either B contains this line or |B| ≥ 2p + 1.

5 Recent Results on the Number of Directions and Blocking Sets

Summing up the results that we have seen until now, any non-linear function f : GF (q) → GF (q), with q prime, determines at least \frac{q+3}{2} directions. And the bound is tight, since the function f(X) = X^{\frac{q+1}{2}} determines exactly \frac{q+3}{2} directions.

Theorem 5.1. (Lovász and Schrijver [7]) Any function that determines \frac{q+3}{2} directions, where q is prime, is affinely equivalent to X^{\frac{q+1}{2}} .

Proof. (idea) We define, for a function f determining \frac{q+3}{2} directions,

F (X, Y) = ∏_{x∈GF (q)}(X + xY − f(x))

Then, for c ∈ D, we have R(X, c) = X^{q} + g(X), where g^{∘} = \frac{q+1}{2}. But as a corollary of Theorem 2.1, we showed that any fully reducible lacunary polynomial of the form X^{q} +g(X), with g^{∘} = \frac{q+1}{2}, is equivalent, up to transformations X ↦ X + a, to X^{q} ± 2X^{\frac{q+1}{2}} + 1 or to X^{q} ± X^{\frac{q+1}{2}} .

With some algebraic work we get that f is affinely equivalent to X^{\frac{q+1}{2}} .

Before returning to blocking sets, we state a “number theory” theorem:

Theorem 5.2. (Kneser’s theorem[9]) Let G be an Abelian group, and let A, B be finite non-empty subsets of G. Denote by A + B = {a + b | a ∈ A, b ∈ B}, and let H = {g ∈ G | g + A + B = A + B}.

Then H is a subgroup of G, and if |A + B| < |A| + |B|, then |A + B| = |A + H| + |B + H| − |H|.

Now we consider GF (q)^{∗} = {1, ε, ε^{2}, …, ε^{q−2}}, where ε is a primitive element of GF (q). GF (q)^{∗} is an Abelian group (with multiplication).

Let U be a minimal blocking set contained in 3 non-concurrent lines. We can choose these lines to be the x-axis ℓ_{x}, the y-axis ℓ_{y} and ℓ_{∞}. If U does not contain a line, then the points (0, 0), (0) and (∞) belong to U. We define the following sets:

A = {a | (0, ε^{a}) ∉ U} W_{A} = {(0, ε^{a}) | a ∈ A}
B = {b | (ε^{−b}, 0) ∉ U} W_{B} = {(ε^{−b}, 0) | b ∈ B}

Then W_{A} = ℓ_{y}\U and W_{B} = ℓ_{x}\U.

The direction of a line joining a point of W_{A} and a point of W_{B} is \frac{ε^{a}}{ε^{−b}} = ε^{a+b}, for some a ∈ A, b ∈ B. Hence if we have c ∈ A + B the point (c) must be in the blocking set U. Now we define the sets:

W_{C} = {(ε^{g}) | g ∉ A + B} C = {c | (ε^{c}) ∈ W_{C}}

Then by the minimality of U we have that U = (ℓ_{∞}∪ℓ_{x}∪ℓ_{y})\(W_{A}∪W_{B}∪W_{C}) and |U| = 3q − |A| − |B| − |C|, where |C| = |W_{C}| = |GF (q)^{∗}| − |A + B| = q − 1 − |A + B|, so |U| = 2q + 1 − |A| − |B| + |A + B|.

If |A + B| ≥ |A| + |B|, then |U| ≥ 2q + 1 (very large!).

Otherwise, replace A by A + H and B by B + H, where H is defined as in Theorem 5.2 (then U possibly becomes smaller, but U is minimal). Then we have |U| = 2q+1−|A+H|−|B+H|−|A+B| (remember that A+B+H = A+B). We can apply Theorem 5.2 and conclude that |U| = 2q + 1 − |H|, where H is a subgroup of GF (q)^{∗} (and so, |H| = d, for some d|q − 1). This result was proved by Szőnyi:

Theorem 5.3. (Szőnyi [12]) Every minimal blocking set U of size less than 2q + 1 contained in 3 non-concurrent lines satisfies |U| = 2q + 1 − d, for some d|q − 1.

Note that the above also constructs a minimal blocking set of size 2q + 1 − d contained in the union of three lines, for all d|q − 1; take H to be a subgroup of GF (q)^{∗} and A = B = H, so that C = GF (q)^{∗} \ H and |U| = 3 + 2(q − 1 − |H|) + |H|.

Theorem 5.4. (Gács [6]) If f : GF (q) → GF (q), with q prime, determines more than \frac{q+3}{2} directions, then it determines at least ⌈\frac{2(q−1)}{3}⌉ + 1 directions.

This bound is almost tight, there are examples for q = 1 mod 3, of functions that determine \frac{2q+1}{3} + 1 directions.

Proof. (idea) It is complicated but the idea is to show that functions determining less than ⌈\frac{2(q−1)}{3}⌉+1 directions are affinely equivalent to a function f satisfying f^{2}(X) = (aX + b)^{2}, for some a, b ∈ GF (q).

Then one sees that the graph {(x, f(x)) | x ∈ GF (q)} is contained in the union of two lines (f(x) − ax − b)(f(x) + ax + b) = 0.

Then we can construct a blocking set by adding the determined directions on ℓ_{∞}. This blocking set is contained in the union of three lines and the result follows by applying Theorem 5.3.

Let us return to blocking sets. The following theorem summarizes some known bounds on the cardinality of blocking sets.

Theorem 5.5. If B is a blocking set of P G(2, q) not containing a line. Then one of the following statements hold:

(i) q is prime and |B| ≥ \frac{3(q+1)}{2}.

(ii) q is a square and |B| ≥ q + \sqrt{q} + 1.

(iii) q = p^{2d+1} and |B| ≥ q + \sqrt{pq} + 2.

All examples we have seen where |B| ≤ \frac{3(q+1)}{2} have been of Rédei type, i.e. |B| = q + k, where there exists a line incident with k points of B. But there exist many other blocking sets of size less than \frac{3(q+1)}{2}. These come from the following construction proposed by Lunardon [8] and Polito and Polverino [10].

Let V be a vector space of dimension 3 over GF (q). P G(2, q) is the pointline incidence structure where: points are the subspaces of V of dimension 1, and lines are the subspaces of V of dimension 2. If q = p^{t}, for some prime p and some integer t, we have that V can be viewed as a vector space of dimension 3t over GF (q).

Let P be the set of points of P G(2, q). Then P ∈ P corresponds to a tdimensional subspace P̄ of this vector space, and ∀P, Q ∈ P, we have P̄ ∩ Q̄ = \{\underline{O}\}.

Lines of P G(2, q) are 2t-dimensional subspaces of V spanned by two points of P G(2, q). Let U be a (t + 1)-dimensional subspace, and define

B_{U} = \{P ∈ P / P̄ ∩ U ≠ \{\underline{0}\}\}

Then B_{U} is a blocking set that satisfies:

|B_{U}| ≤ \frac{p^{t+1} − 1}{p − 1} = p^{t} + p^{t−1} + … + 1 = q + \frac{p^{t} − 1}{p − 1} = q + \frac{q − 1}{p − 1}

It was shown by Polito and Polverino in [10] that if t ≥ 4 it is possible to choose U so that B_{U} is not of Rédei type.

Conjecture 5.1. All blocking sets of size less than \frac{3(q+1)}{2} come from this construction of Polito, Polverino and Lunardon.

Theorem 5.6. (Szőnyi [13]) If a minimal blocking set B satisfies |B| < \frac{3(q+1)}{2} and q = p^{h} with p ≥ 5, then every line is incident with 1 mod p points of B.

This is Theorem 5.5 in Section 5 of [4] and the proof can be found there.

References

[1] S. Ball, The number of directions determined by a function over a finite

field, http://www.maths.qmw.ac.uk/~simeon/listofpapers.html

[2] A. Blokhuis, On the size of a blocking set in P G(2, p), Combinatorica, 14 (1), (1994), 111–114.

[3] 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 on a finite field, J. Combin. Theory Ser. A, 86, 187–196 (1999).

[4] A. Blokhuis and S. Ball, Polynomials in finite geometry, Methods of Discrete Mathematics, Quaderni di mathematica, Napoli, 5, 71–101 (1999).

[5] A.A. Bruen, Blocking sets in finite projective planes, SIAM J. Appl. Math., 21, (1971), 380–392.

[6] A. Gács, On a generalization of Rédei’s theorem, Combinatorica, to appear.

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

[8] G. Lunardon, Normal spreads, Geom. Dedicata, 75, (1999), 245–261.

[9] M. B. Nathanson, Additive Number Theory. Inverse problems and the geometry of sumsets, Springer-Verlag, 1996.

[10] P. Polito and O. Polverino, On small blocking sets, Combinatorica, 18, (1998), 133–137.

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

[12] T. Szőnyi, Combinatorial problems for Abelian groups arising from geometry, Periodica Polytechnica, 19 (1991), 91–100.

[13] T. Szőnyi, Blocking Sets in Desarguesian Affine and Projective Planes, Finite Fields Appl., 3, (1997), 187–202.