Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 1, 43-53.

On the Smallest Minimal Blocking Sets in Projective Space Generating the Whole Space

Martin Bokler Klaus Metsch

Mathematisches Institut, Universität Giessen Arndtstr. 2, D-35392 Giessen e-mail: Klaus.Metsch@math.uni-giessen.de

Abstract. It was conjectured that the smallest minimal point sets of PG(2s, q), q a square, that meet every s-subspace and that generate the whole space are Baer subgeometries PG(2s, \sqrt{q}). This was shown in 1971 by Bruen for s = 1, and by Metsch and Storme [5] for s = 2. Our main interest in this paper is to prepare a possible proof of this conjecture by proving a strong theorem on line-blocking sets in projective spaces (see Theorem 1.1). We apply this theorem to prove the conjecture in the case s = 3. The general case will be handled in a forthcoming paper by the first author.

1. Introduction

Let PG(n, q) be the projective space of dimension n over the finite field GF(q).

A t-blocking set B in PG(n, q), with n ≥ t + 1, is a set B of points such that any (n − t)- dimensional subspace intersects B. A 1-blocking set in PG(2, q) is simply called a blocking set. A t-blocking set is called minimal, if none of its proper subsets is also a t-blocking set.

The smallest t-blocking sets have been characterized by Bose and Burton [1]. They proved that the smallest t-blocking sets in PG(n, q) are subspaces of dimension t. An old result of Bruen [2] states that the second smallest minimal blocking set in the plane PG(2, \sqrt{q}), q a square, is (the point set of) a Baer subplane PG(2, \sqrt{q}). For further results we need the notion of a cone.

Let V and U be skew subspaces of a projective space, and let S be a non-empty subset of U. The cone with vertex V and base S is the point-set that is the union of the subspaces

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2002 Heldermann Verlag

44 M. Bokler, K. Metsch: On the Smallest Minimal Blocking Sets in …

⟨V, P ⟩ with points P ∈ S. In this paper S will typically be a Baer subspace PG(s, \sqrt{q}), and then we speak of a cone with vertex V over a Baer subspace PG(s, \sqrt{q}). If V is a point (or line), we speak of a point-cone (or a line-cone). We allow the degenerate situation, when V is empty; then the cone with vertex V and base S is simply the set S. When S consists of a single point, then the cone is a subspace of dimension dim(V) + 1.

Heim [4] proved that the second smallest minimal t-blocking sets in PG(n, q) are cones with a (t − 2)-dimensional vertex and with base a second smallest minimal 1-blocking set in a plane. For q square, this is, by the above mentioned result of Bruen [2], a cone with (t − 2)-dimensional vertex and with base a Baer subplane PG(2, \sqrt{q}) in a plane. For t = 1 and q a square, this was proved earlier by Bruen [3].

A property of a t-blocking set in a projective space PG(n, q) is that it is also a t-blocking set in all projective spaces PG(n′, q) of higher dimension n′ > n. Therefore it is quite natural to look for t-blocking sets that generate a space, because all others are t-blocking sets in projective spaces of smaller dimension.

Examples for minimal blocking sets in PG(n, q), q a square, are easy to find. For each integer i with 0 ≤ i ≤ min{t, n − t}, the cone with a (t − 1 − i)-dimensional vertex and a base a Baer subspace PG(2i, \sqrt{q}) is an example for a minimal t-blocking set of PG(n, q). (For i = 0, this is a subspace of dimension t.) While i is growing the cardinality of the example gets larger. If n > 2t, none of these examples generates the space. If n ≤ 2t, then only the example with i = n − t generates the space.

In particular when n = 2t, then PG(2t, \sqrt{q}) is a minimal t-blocking set of PG(n, q) that generates the space. For n ≥ 2t, we conjecture that the above examples are the first t + 1 smallest minimal t-blocking sets. This conjecture is known to be true in the cases t = 1 [3] and t = 2 [5]. The following first result of this paper makes it likely that the conjecture can be proved in general (for q ≠ 4, 9).

Theorem 1.1. Consider the projective space PG(n, q), n ≥ 2, q ≥ 16 a square. Suppose that B is a set of at most

\frac{q^{n} − 1}{q − 1} + \sqrt{q} \frac{q^{n−1} − 1}{q − 1}

points that meets every line. Then B contains either a hyperplane, or a cone over a PG(2, \sqrt{q}) with a vertex of dimension n − 3.

The strategy to use this result for proving the conjecture is as follows. First notice that each of the t + 1 examples B for a t-blocking sets in PG(n, q), n ≥ 2t, satisfies |B| ≤ \frac{q^{t+1}−1}{q−1} + \sqrt{q} \frac{q^{t}−1}{q−1}. On the other hand, suppose that B is a blocking set of PG(2n, q) satisfying this inequality. Then a counting argument shows that B misses many subspaces R of dimension n − t − 2. In the quotient geometry PG(n, q)/R = PG(t + 1, q), the set B becomes a set that meets all lines. Then Theorem 1.1 gives structural information on B. This information, for various subspaces R, seems to be sufficient to prove the conjecture. We demonstrate this in the case t = 3 by proving the following theorem. The general case is more complicated and will be handled in a forthcoming paper by the first author.

Theorem 1.2. The four smallest minimal point-sets of PG(6, q), q a square, q ≥ 16, that meet every plane are a subspace of dimension three, a cone with a line-vertex over a PG(2,\sqrt{q}), a cone with a point-vertex over a PG(4, \sqrt{q}), and a PG(6, \sqrt{q}).

The starting point of the present configurations was the conjecture that PG(2t, \sqrt{q}) is the smallest t-blocking set of PG(2t, q) that is generating PG(2t, q). This conjecture is weaker than the above one. Theorem 1.2 clearly proves it for t = 3.

Corollary 1.3. The smallest minimal point-set of PG(6, q), q a square, q ≥ 16, that generates the space and that meet every plane is a PG(6, \sqrt{q}).

2. An improved bound on line blocking sets of projective spaces

Throughout this paper, q will denote a prime power that is a square. For i ≥ −1, we put

Θ_{i} := \frac{q^{i+1} − 1}{q − 1}.

Then Θ_{i} is the number of points in a projective space of order q and dimension i.

This section is devoted to the proof of Theorem 1.1. Throughout this section, B denotes a point set of PG(n, q) meeting every line of PG(n, q) and satisfying

|B| ≤ Θ_{n−1} + \sqrt{q}Θ_{n−2}.  (1)

A line that meets B in a unique point is called a tangent of B. In order to prove the theorem, we may assume that B is minimal, that is, every point of B lies on a tangent of B. The proof is by induction on n. The case n = 2 of the theorem is well-known; it is due to Bruen [2]. The case n = 3 has been handled in [5] (also only for q ≥ 16). We assume from now on that n ≥ 4 and that the theorem is true for all smaller values of n. We also assume that B contains no hyperplane and show that B contains a cone as described in the theorem.

A subspace of codimension two is called a coline, a subspace of codimension three a coplane. A subspace is called a B-space, if it is contained in B; we also speak of B-lines, B-planes and so on.

Since we quite often find cones over a Baer subplane with a vertex of dimension n − 4, we shall simply call these cones in this section and emphasis this by using italic style: cone.

Lemma 2.1. Let H be a hyperplane.

(a) |H ∩ B| ≤ Θ_{n−2}(\sqrt{q} + 1).

(b) If |H ∩ B| ≤ Θ_{n−2} + Θ_{n−3}\sqrt{q}, then H ∩ B contains a cone or coline.

(c) H ∩ B contains at most \sqrt{q} + 2 colines.

Proof. Part (b) is the induction hypothesis. Part (a) can be seen as follows. If H is a hyperplane, then H is not completely contained in B. If P is a point of H that is not in B, then each of the q^{n−1} lines l with l ∩ H = P meets B in a point outside of B. Hence at most |B| − q^{n−1} points of B lie in H.

In order to prove (c) first notice that the union of c + 1 colines that are contained in a hyperplane cover at least

Θ_{n−2} + cq^{n−2} − \binom{c}{2}q^{n−3}

points. For c = \sqrt{q} + 2, this number is larger than the one in (a). □

Lemma 2.2. A B-coline meets at most q + 2\sqrt{q} − 1 other B-colines in a coplane.

Proof. Suppose that U is a B-coline. Let H_{i}, i = 0, …, q, be the hyperplanes on U and suppose that H_{i} contains c_{i} colines different from U that are contained in B. As in the proof of the preceding lemma, we see that H_{i} \U meets B in at least c_{i}q^{n−2} −\binom{c_{i}}{2}q^{n−3} points. Thus

Θ_{n−2} + ∑_{i=0}^{q} (c_{i}q^{n−2} − \binom{c_{i}}{2}q^{n−3}) ≤ |B|.

Put c = ∑ c_{i}. As c_{i} ≤ \sqrt{q} + 1 for all i (Lemma 2.1 (c)), we have ∑ \binom{c_{i}}{2} ≤ c\sqrt{q}/2. Thus cq^{n−3}(q − \sqrt{q}/2) ≤ |B| − Θ_{n−2}. Using (1) it follows that c < q + 2\sqrt{q}. □

Lemma 2.3. Suppose P is a point of B. Then there exist a coline S and a hyperplane H such that |H ∩ B| ≤ Θ_{n−2} + \sqrt{q}Θ_{n−3} and such that one of the following two statements holds.

(a) P ∈ S and S ⊆ H ∩ B.

(b) |S ∩ B| ≤ Θ_{n−3} + \sqrt{q}Θ_{n−4} and there exists a B-coplane E with P ∈ E ⊆ S ⊆ H.

Proof. Consider a tangent t on P. We count incident pairs (X, H) of points X and hyperplanes H satisfying P ≠ X ∈ H and t ⊆ H. Every point X of B \ {P } lies in Θ_{n−3} such pairs. Thus (|B| − 1)Θ_{n−3} = ∑(|H ∩ B| − 1) were the sum runs over the Θ_{n−2} hyperplanes H containing t. Using (1), it follows that there exists a hyperplane H on t satisfying |H ∩ B| < Θ_{n−2} + \sqrt{q}Θ_{n−3} + 1.

By Lemma 2.1 the set H ∩ B contains either a coline C or a cone C. In both cases C meets every line of H. As t is a tangent of B, it follows that P ∈ C. If C is a coline we are done. Suppose therefore that C is a cone, which has a (n − 4)-subspace as a vertex and a PG(2, \sqrt{q}) as a base. The cone has Θ_{n−2} + \sqrt{q}q^{n−3} points, so apart from the points of C there are at most \sqrt{q}Θ_{n−4} further points in H ∩ B.

The largest subspaces contained in the cone have dimension n − 3 and cover the cone. Let E be a coplane containing P and contained in C. Then H has q − \sqrt{q} colines S that meet C in E. Any of these will meet B in at most Θ_{n−3} + \sqrt{q}Θ_{n−4} points. □

Lemma 2.4. There exists a hyperplane H such that |H ∩ B| ≤ Θ_{n−2} + \sqrt{q}Θ_{n−3} and such that H ∩ B contains a cone.

Proof. Assume that this is not true. Then Lemma 2.1 shows that every hyperplane H satisfying |H ∩ B| ≤ Θ_{n−2} + \sqrt{q}Θ_{n−3} contains a B-coline.

Lemma 2.3 shows that there exists a hyperplane H with at most Θ_{n−2} + \sqrt{q}Θ_{n−3} points in B. Then H contains a B-coline T. Put |H ∩ B| = Θ_{n−2} + c. Then 0 ≤ c ≤ \sqrt{q}Θ_{n−3}. Consider a coplane S of T. Counting |H ∩ B| using the colines of H on S, we see that S lies in a coline T′ of H with T′ ≠ T and |T′ ∩ B| ≤ Θ_{n−3} + c/q. Counting |B| using the hyperplanes on T′ we see that T′ lies in a hyperplane H′ ≠ H satisfying

|H′ ∩ B| ≤ |T′ ∩ B| + \frac{|B| − |H ∩ B|}{q} ≤ Θ_{n−3} + \frac{c}{q} + \frac{1}{q}(q^{n−1} + \sqrt{q}Θ_{n−2} − c).

Then |H′ ∩B| ≤ Θ_{n−2} +\sqrt{q}Θ_{n−3}, so H′ ∩B contains a B-coline T_{S}. As |T′ ∩B| ≤ Θ_{n−3} +c/q and c ≤ \sqrt{q}Θ_{n−3}, then S is the only coplane of T′ contained in B. Thus T_{S} ∩ T′ = S. As T_{S} ∩ T ⊆ H′ ∩ H = T′, we obtain T_{S} ∩ T = S.

Thus, every coplane S of T gives rise to a B-coline T_{S} satisfying T_{S} ∩ T = S. As T has Θ_{n−2} coplanes, it follows that T meets at least that many B-colines in a coplane. This contradicts Lemma 2.2. □

Lemma 2.5. Every point of B lies on a B-coline.

Proof. Assume the point P of B does not lie on a B-coline. Then Lemma 2.3 shows that there exists a coplane E and a coline S with P ∈ E ⊆ S ∩ B and |S ∩ B| ≤ Θ_{n−3} + \sqrt{q}Θ_{n−4}. Now we shall derive a contradiction in several steps.

(a) Suppose H is a hyperplane on S satisfying |H ∩ B| ≤ Θ_{n−2} + \sqrt{q}Θ_{n−3}. Then H ∩ B contains a cone C satisfying C ∩ S = E.

Lemma 2.1 shows that H ∩ B contains a coline or a cone. Assume that H ∩ B contains a coline T. The assumption in the beginning of the proof implies that E is not contained in T. Thus T ∩ S and E are different coplanes of S. Therefore |S ∩ B| ≥ q^{n−3} + Θ_{n−3}, a contradiction.

Hence H ∩ B contains a cone C, which has a subspace V of dimension n − 4 as a vertex and a PG(2, \sqrt{q}) has a base. We have |C| = Θ_{n−2} +\sqrt{q}q^{n−3}. Thus, outside of C there exist at most \sqrt{q}Θ_{n−4} points in H ∩ B, which implies that at least Θ_{n−3} − \sqrt{q}Θ_{n−4} points of E lie in C. This implies that E is contained in C (just check the few possibilities in which a coplane of H can meet the cone C; the largest intersection a coplane can have with C, provided it is not contained in C, is Θ_{n−4} + \sqrt{q}q^{n−4}).

As all coplanes contained in C contain the vertex of C, then V ⊆ E. A coline that contains E and a further point of C meets C in the union of \sqrt{q} + 1 coplanes on V. As S ∩ B is to small to contain that many coplanes on V, it follows that S ∩ C = E.

(b) If H is a hyperplane on S, then |(H \ S) ∩ B| ≥ q^{n−2} + \sqrt{q}q^{n−3} points.

Suppose |(H \ S) ∩ B| ≤ q^{n−2} + \sqrt{q}q^{n−3}. Then |H ∩ B| ≤ Θ_{n−2} + \sqrt{q}Θ_{n−3}. Then (a) shows that H ∩ B contains a cone C with |C ∩ S| = Θ_{n−3}. As cones have Θ_{n−2} + \sqrt{q}q^{n−3} points, it follows that |(H \ S) ∩ B| = q^{n−2} + \sqrt{q}q^{n−3}.

(c) Every hyperplane H on S meets B in at most Θ_{n−2} + \sqrt{q}Θ_{n−3} points.

Apply (b) to the q hyperplanes on S different from H. This shows that H meets B in at most |B| − q(q^{n−2} + \sqrt{q}q^{n−3}) points.

(d) If U is a coline on E, then either |(U \ E) ∩ B| ≤ \sqrt{q}Θ_{n−4} (these will be called small colines) or |(U \ E) ∩ B| ≥ \sqrt{q}q^{n−3} (these will be called big colines).

Let H be a hyperplane containing S and U. By (a) and (c), the set H ∩ B contains a cone C with E ⊆ C. The vertex V of this cone has dimension n − 4 and is contained in E. There are two possibilities how U and C can meet. Either U ∩ C = E, or U ∩ C is the union of \sqrt{q} + 1 subspaces of dimension n − 3 (one of these is E) that mutually meet in V. In the first case |(U \ E) ∩ C| = 0 and in the second case |(U \ E) ∩ C| = \sqrt{q}q^{n−3}.

As C has Θ_{n−2} + \sqrt{q}q^{n−3} points, then (c) shows that H contains apart from the points in C at most \sqrt{q}Θ_{n−4} further points in B. This proves the assertion.

(e) If H is a hyperplane on E containing a small coline, then H contains \sqrt{q} + 1 big and q − \sqrt{q} small colines.

First consider the special case that H contains S. Using the notation of the proof of (d), we see that a coline U of H on E is small if and only if U ∩ C = E. As C is a cone with base a PG(2, \sqrt{q}), we see that this happens for exactly q − \sqrt{q} choices of U.

Now consider the general case that H contains a small coline S′ that might be distinct from S. Since E ⊆ S′, we can repeat the proof of (a), (b), (c), (d) with S′ in place of S. Then the assertion follows as in the special case.

(f) The final contradiction.

Each of the q + 1 hyperplanes on S contains \sqrt{q} + 1 big colines. Thus, the number of big colines is b = (q + 1)(\sqrt{q} + 1).

Consider a big coline U. Let c be the number of hyperplanes on U that contain a small coline and let d be the number of hyperplanes on U that contain no small coline. The c hyperplanes of the first kind each contain exactly \sqrt{q} + 1 big colines, which are U and \sqrt{q} others. The d hyperplanes of the second kind each contain exactly q +1 big colines. It follows that c\sqrt{q} + dq + 1 = b. As c + d = q + 1, then (q + 1 − d)\sqrt{q} + dq + 1 = (q + 1)(\sqrt{q} + 1). This gives (d − 1)(\sqrt{q} − 1) = 1. As q ≠ 4, this is a contradiction. □

Lemma 2.6. The set B contains a cone with a vertex of dimension n − 3 and a PG(2, \sqrt{q}) as a base.

Proof. By Lemma 2.4, there exists a hyperplane H satisfying |H ∩ B| ≤ Θ_{n−2} + \sqrt{q}Θ_{n−3} and such that H ∩ B contains a cone C . The vertex of C is a subspace V of dimension n − 4, the base of the cone is a PG(2, \sqrt{q}). The maximal subspaces contained in C are called the generators of C. There are q + \sqrt{q} + 1 generators. They have dimension n − 3 and contain the vertex V.

As C contains Θ_{n−2} + \sqrt{q}q^{n−3} of the points of H ∩ B, then there exist at most \sqrt{q}Θ_{n−4} points of B in H \ C. This implies that every coplane that is contained in H ∩ B must be one of the generators of C. Hence, if L is a B-coline, then L ∩ H is a coplane and L ∩ H is a generator of the cone C. Therefore the vertex V of the cone is contained in all B-colines.

We shall show that there exists a subspace Z of dimension n − 3 satisfying Z ∩ H = V and such that Z lies in all B-colines. Then the B-colines mutually meet in Z. As each point of a base of the cone C is contained in a B-coplane, it follows then that C contains a cone with vertex Z and a PG(2, \sqrt{q}) as a base. As B is minimal, we will in fact have that B equals this cone.

As every point of B lies on a B-coline (Lemma 2.5), and as each B-coline meets H in a generator of C, we have H ∩B = C. Consider a subspace U of dimension n−2 of H such that V ⊈ U. Then U ∩C is cone with a (n−5)-dimensional subspace as a vertex and a PG(2, \sqrt{q}) as a base. We have |H ∩ B| = |C| = Θ_{n−2} + \sqrt{q}q^{n−3} and |U ∩ B| = |U ∩ C| = Θ_{n−3} + \sqrt{q}q^{n−4}. Let H′ be one of the q hyperplanes with H′ ∩ H = U that has the smallest possible number of points in B. Then

|B| ≥ |H ∩ B| + q(|H′ ∩ B| − |U ∩ B|).

As we know the values of |H ∩ B| and |U ∩ B|, we obtain |H′ ∩ B| < Θ_{n−2} + \sqrt{q}Θ_{n−3} + 1 from (1). As V lies in every B-coline and as H′ does not contain V, then H′ ∩ B does not contain a coline. Then Lemma 2.1 shows that H′ ∩ B contains a cone C′ with a (n − 4)-dimensional vertex V′ and a PG(2, \sqrt{q}) as a base. As for V, we can show that every B-coline contains V′. As V ⊈ H, then V ≠ V′ and hence Z := ⟨V, V′⟩ has dimension at least n − 3. Then dim(Z) = n − 3 and the B-colines mutually meet in Z. This completes the proof. □

3. Blocking planes by points in PG(5, q)

Before we state the main theorem of this section, we need two results. The first one is essential for the proof obtained in this section. The second one, which we formulate as a lemma, might be well-known, but we include a proof anyway.

Result 3.1. [5] Suppose B is a minimal set of points of PG(4, q), q a square and q ≥ 16, that meets every plane. If |B| ≤ q^{2} + q\sqrt{q} + q + \sqrt{q} + 1, then either B is a plane, or the point-cone over a PG(2, \sqrt{q}), or a PG(4, \sqrt{q}).

Lemma 3.2. Consider PG(n, q), n ≥ 2, and a point-set B of PG(n, q). Suppose PG(n, q) induces on B the point-line structure of a projective space PG(m, \sqrt{q}) with m ≥ n (our formulation should imply that a line of PG(n, q) induces at most one line of PG(m, \sqrt{q}), that is a line of PG(n, q) meets B in 0, 1 or \sqrt{q} + 1 points). Then m = n and B is the point-set of a Baer subgeometry.

Proof. First we show that n = m using induction on n. For n = 2, we just have to note that a point of PG(m, \sqrt{q}) with m ≥ 3 lies on more than q + 1 lines. Thus, if n = 2, then m = 2.

Now suppose that n ≥ 3. By the induction hypothesis, a (n − 1)-subspace of PG(m, \sqrt{q}) generates in PG(n, q) a subspace of dimension at least n − 1, and clearly the dimension must be n − 1. Also, no n-subspace of PG(m, \sqrt{q}) can lie in a (n − 1)-subspace of PG(n, q). Therefore, different (n − 1)-subspaces of PG(m, \sqrt{q}) generate in PG(n, q) different (n − 1)- subspaces. Now just notice that for m > n, the number of (n − 1)-subspaces of PG(m, q) is larger than the number of (n − 1)-subspaces of PG(n, q). Thus m = n.

Also B generates PG(n, q). Now it is a standard technique to see that one can choose coordinates in such a way that B consists of the points with coordinates in the subfield F\sqrt{q}. □

The aim of this section is to prove the following theorem.

Theorem 3.3. Suppose B is a set of at most Θ_{3} + \sqrt{q}Θ_{2} points of PG(5, q) and that B meets every plane. Then either B contains a solid, or a line-cone over a PG(2, \sqrt{q}), or a point-cone over a PG(4, \sqrt{q}).

We shall prove this in a series of lemmas. For the rest of this section, we assume that B satisfies the hypotheses of the above theorem. In order to prove the theorem, we can assume that B contains no solid and no line-cone over a PG(2, \sqrt{q}). We can also assume that B is minimal, that is no proper subset of B meets every plane.

Lemma 3.4. If H is a hyperplane, then |H ∩ B| ≤ (\sqrt{q} + 1)Θ_{2}.

Proof. It is not possible that H ∩B meets every line of H, since otherwise Theorem 1.1 would imply that H ∩ B contains a solid or a line-cone over a PG(2, \sqrt{q}). Let l be a line of H with no point in B. Then l lies on q^{3} planes π with π ∩ H = l. As all these meet B, then B contains at least q^{3} points that are not in H. Hence |H ∩ B| ≤ |B| − q^{3} ≤ (\sqrt{q} + 1)Θ_{2}. □

Lemma 3.5. Let R be a point not in B and H a hyperplane not through R. Then the point set B(H, R) := \{RP ∩ H | P ∈ B\} contains a line-cone over a PG(2, \sqrt{q}).

Proof. If l is a line of H, then the plane ⟨P, l⟩ meets B and hence l meets B(H, R). Thus B(H, R) meets all lines of H. As |(H, R)| ≤ |B|, then Theorem 1.1 shows that B(H, R) contains a solid or a line-cone over a PG(2, \sqrt{q}). However, the first case is not possible, because a solid S contained in B(H, R) would give rise to the hyperplane ⟨R, S⟩ with at least Θ_{3} points in B. This is excluded by the previous lemma. □

Lemma 3.6. If R is a point not in B and if B′ is a subset of B, then the number of lines on R that meet B′ is at least |B′| − q\sqrt{q} − \sqrt{q}.

Proof. It suffices to prove this for B′ = B. However, the previous lemma shows that the number of lines of R that meets B is at least as large as the number of points in a line-cone over a PG(2, \sqrt{q}), which is Θ_{3} + \sqrt{q}q^{2}. □

Lemma 3.7. Every point of B lies in a line contained in B.

Proof. Assume this is not true for the point P of B. As B is minimal, then P lies on a plane π with π ∩ B = P.

Consider a solid S on π. Then S ∩ B meets every plane of S. Also S cannot contain a B-line, as a B-line of S would necessarily meet π in P. Therefore |S ∩ B| ≥ q + \sqrt{q} + 1 with equality if and only if S ∩ B is a PG(2, \sqrt{q}) (Theorem 1.1). Hence S \ π contains at least q + \sqrt{q} points of B.

As π lies in Θ_{2} solids, it follows that |B| = Θ_{3} + \sqrt{q}Θ_{2} and that all solids on π meet B in a PG(2\sqrt{q}). Therefore every 4-space on π meets B in (q + 1)(q + \sqrt{q}) + 1 points. Result 3.1 implies now that every 4-space on π either contains a PG(4, \sqrt{q}), or a plane, or a point-cone over a PG(2, \sqrt{q}) as a base. In all three cases, P must lie in this substructure, as π ∩ B = P. But in the last two cases, the substructure is a union of lines, and as we assume that P does not lie on a B-line, then the first case must occur.

Hence each 4-space on π contains a PG(4, \sqrt{q}). As each line of PG(5, q) lies together with π in some 4-space, then each line meets B in 0, 1, or \sqrt{q} + 1 points. Then no point of B lies on a B-line. We can thus repeat our argument and obtain the following: For every plane π with |π ∩ B| = 1, each solid on π meets B in a PG(2, \sqrt{q}) and each 4-space on π meets B in a PG(4, \sqrt{q}).

As every point of B lies in a plane meeting B only in this point, then every plane occurs in a 4-space that meets B in a PG(4, \sqrt{q}). Thus every plane meets B in a point, a Baer subline or a Baer subplane.

This implies quite easily that the structure induced on B is a projective space of order \sqrt{q}. As |B| = Θ_{3} + \sqrt{q}Θ_{2}, then this projective space has dimension six. This contradicts Lemma 3.2. □

The following lemma contains the central argument of the proof. Though it is completely elementary, it is very tricky to find the correct counting argument to obtain a contradiction. The argument was found by the first author while working on his thesis.

Lemma 3.8. Any two B-lines meet.

Proof. Assume that g and h are disjoint lines contained in B. These two lines span a solid S. As B is sufficiently small, we can find a line l that misses S and contains no point of B.

Let P_{i}, i = 0, …, q, be the points of l, and let H_{i} be a hyperplane through S not containing P_{i}. We know that B(H_{i}, P_{i}) contains a line-cone C_{i}, which has Θ_{3} + \sqrt{q}q^{2} points. Suppose that for c of the points P_{i}, one of the lines g and h does not belong to the line-cone C_{i}. Then this line has at most \sqrt{q} + 1 points in C_{i} and therefore the set B(H_{i}, P_{i}) contains at least |C_{i}| + q − \sqrt{q} points. Thus

∑_{i=0}^{q} |B(H_{i}, P_{i})| ≥ (q + 1)(Θ_{3} + q^{2}\sqrt{q}) + c(q − \sqrt{q}).

Now we count this sum in a different way. For this, consider the Θ_{3} planes π on l. If such a plane meets B in d points, then d ≥ 1, and these d points contribute at most dq + 1 to the sum. Thus we obtain |B|q + Θ_{3} as an upper bound for the sum. Compare this with the above lower bound, using |B| ≤ Θ_{3} + \sqrt{q}Θ_{2}, to obtain

(q + 1)(Θ_{3} + q^{2}\sqrt{q}) + c(q − \sqrt{q}) ≤ (q + 1)Θ_{3} + q\sqrt{q}Θ_{2}.

This simplifies to c(\sqrt{q} − 1) ≤ q, that is c ≤ \sqrt{q} + 1.

Now consider one of the points P_{i} for which g and h belong to C_{i}. Then S is a solid that contains two disjoint lines of the line-cone C_{i}. Using the structure of C_{i}, it follows that S meets C_{i} in precisely (\sqrt{q} + 1)q^{2} + q + 1 points. Therefore the hyperplane ⟨S, P ⟩ contains at least this many points from B. As there are q + 1 − c ≥ q − \sqrt{q} choices for P_{i}, it follows that

(q − \sqrt{q})((\sqrt{q} + 1)q^{2} + q + 1) − (q − 1 − \sqrt{q})|S ∩ B| ≤ |B| ≤ Θ_{3} + \sqrt{q}Θ_{2}.

As B contains no solid, then some point of S is not in B. Then Lemma 3.6 implies that |S ∩ B| ≤ q^{2} + q + 1 + \sqrt{q}q + \sqrt{q}. Since q ≥ 9, this gives a contradiction. □

Lemma 3.9. The set B is a cone with point vertex over a PG(4, \sqrt{q}).

Proof. As every two B-lines meet, they all pass through a common point or lie in a common plane. As |B| > q^{2} + q + 1 and as every point of B lies on a B-line, the second case is not possible. Thus all B-lines pass through a common point Q. Then the number of B-lines is c := (|B| − 1)/q ≤ |PG(4, \sqrt{q})|.

Consider a hyperplane H with Q ∉ H. As every point of H ∩ B lies on a B-line, then |H ∩B| ≤ c ≤ |PG(4, \sqrt{q})|. As Q ∉ H, then H ∩B contains no B-line. As H ∩B meets every plane of H, it follows now from Result 3.1 that H ∩ B is a PG(4, \sqrt{q}). Then B contains the cone with vertex Q over this PG(4, \sqrt{q}). As B is minimal, then B contains no points outside this cone. □

4. Blocking solids in PG(6, q)

In this section we shall prove Theorem 1.2. Throughout we assume that B is a set of at most |PG(6, \sqrt{q})| points in PG(6, q) that meets every solid. In order to prove the theorem we may and shall assume that B contains no solid, no cone with line-vertex over a PG(2, \sqrt{q}), and no cone with a point-vertex over a PG(4, \sqrt{q}). We shall show that B is a PG(6, \sqrt{q}).

Lemma 4.1. A hyperplane meets B in at most |PG(5, \sqrt{q})| points.

Proof. Consider a hyperplane H. It is not possible that H ∩ B meets every plane of H, since otherwise Theorem 3.3 would imply that H ∩ B contains one of the structures that we have just excluded. Then, if π is a plane of H missing B, then π lies in q^{3} solids that meet H in π. Hence outside H∩B there exist at least q^{3} points of B. Then |H∩B| ≤ |B|−q^{3} = |PG(5, \sqrt{q})|.

□

Lemma 4.2. Consider a point P ∉ B, a hyperplane H with P ∉ B and the set B(H, P) := {P R ∩ H | R ∈ B} consisting of the projection of B from P onto H. Then B(H, P) is a cone with a point-vertex and a PG(4, \sqrt{q}) as a base.

Proof. As B meets every solid, then the projected set B(H, P) meets every plane of H. Also |B(H, P)| ≤ |B| ≤ |PG(6, \sqrt{q})|. Then Theorem 3.3 shows that B(H, P) contains a solid, or a cone with a line-vertex over a PG(2, \sqrt{q}), or a cone with a point-vertex over a PG(4, \sqrt{q}). The preceding lemma implies that a 4-subspace of H contains at most |PG(5, \sqrt{q})| points of B(H, P). Thus the first two cases are not possible. Hence B(H, P) contains a cone C(H, P) with point-vertex over a PG(4, \sqrt{q}), which has |PG(6, \sqrt{q})| − \sqrt{q} points.

As |B(H, P)| ≤ |B| < Θ_{4}, then some line of H misses B(H, P). Hence, there exists a plane π on P missing B. For each point X in π consider a hyperplane H_{X} not through X. Then we have

∑_{X∈π} |B(H_{X}, X)| ≥ (q^{2} + q + 1)(|PG(6, \sqrt{q})| − \sqrt{q}).

Consider the Θ_{3} solids S on π. If S ∩B contain c points, then c ≥ 1 and the c points of S ∩B contribute at most c(q^{2} + q) + 1 to this sum. Thus we obtain |B|(q^{2} + q) + Θ_{3} as an upper bound for the sum. Comparing the lower with the upper bound using |B| ≤ |PG(6, \sqrt{q})|, we obtain equality. Hence |B| = |PG(6, \sqrt{q})| and B(H, P) = C(H, P). □

Lemma 4.3. (a) Every line meets B in 0, 1, \sqrt{q} + 1 or q + 1 points.

(b) B contains no plane.

(c) Every plane meets B in at most q + \sqrt{q} + 1 points.

(d) B contains no line.

(e) Every plane containing three non-collinear points of B meets B in a PG(2, \sqrt{q}).

Proof. (a) If l is a line, then |B| ≤ |PG(6, \sqrt{q})| implies that l lies in a plane π that has no points of B outside l. Then, if P ∈ π \ l and H is a hyperplane with H ∩ π = l, then l ∩ B = l ∩ B(H, P). As we know the structure of B(H, P), the assertion follows.

(b) If B would contain a plane, then the sets B(H, P) described in the previous lemma would also contain a plane. But this is not true.

(c) Consider a plane π. Then π contains a point P with P ∉ B. Let H be a hyperplane not through P, and project B from P onto H to obtain B(H, P). The previous lemma shows |B(H, P)| = |PG(6, \sqrt{q})| − \sqrt{q} ≥ |B| − \sqrt{q}. As the points of π ∩ B project on at most q + 1 different points, we obtain |π ∩ B| ≤ q + 1 + \sqrt{q}.

(d) Assume that B contains a line l. Let π be a plane on l that contains a further point R of B. By (a), all lines of π on R meet B in at least \sqrt{q} + 1 points. This contradicts (c).

(e) Suppose the plane π has three non-collinear points. We know that |π ∩ B| ≤ q + \sqrt{q} + 1 and that every line that has two points in π ∩ B meets π ∩ B in exactly \sqrt{q} + 1 points. This implies that π ∩ B is a PG(2, \sqrt{q}). □

We are now ready to characterize B and thus complete the proof of Theorem 1.2. We already know that every plane with three non-collinear points in B meets B in a PG(2, \sqrt{q}). This implies that the incidence structure consisting of the points of B and the secants of B satisfies the Axiom of Pasch and thus is a projective space of order \sqrt{q}. As |B| ≤ |PG(6, \sqrt{q})| and |B| ≥ |PG(6, \sqrt{q})| − \sqrt{q} (this follows from Lemma 4.2), then its dimension is six. Thus B induces a PG(6, \sqrt{q}).

References

[1] Bose, R. C.; Burton, R. C.: A characterization of Flat Spaces in a Finite Geometry and the uniqueness of the Hamming and the MacDonald Codes. J. Comb. Th. 1 (1966), 96–104. Zbl 0152.18106

[2] Bruen, A. A.: Blocking sets in finite projective planes. SIAM Journal on Applied Mathematics 21 (1971), 380–392. Zbl 0252.05014

[3] Bruen, A. A.: Blocking sets and skew subspaces of projective space. Canad. J. Math. 32 (1980), 628–630. Zbl 0445.51014

[4] Heim, U.: Proper blocking sets in projective spaces. Discrete Mathematics 174 (1997), 167–176. Zbl 0904.51003

[5] Metsch, K.; Storme, L.: 2-blocking sets in PG(n, q), q square. Beitr. Algebra Geom., submitted.

Received May 10, 2000