Blocking Sets and Covers, variations of the Kakeya problem

Aart Blokhuis
Technische Universiteit Eindhoven

The fi nite fi eld Kakeya problem asks for the (minimal) number of points covered by a set of lines in AG(n, q), the n-dimensional affine space over the fi eld with q elements. It was essentially solved in a beautiful paper by Dvir, who proved the conjecture that the order of magnitude is q^n. The case n=2 was settled earlier. Here the precise lower bounds are known. For q even the lines can be taken `in general position' (folkore), for q odd one takes q lines in general position, and adds a suitable line in the last direction (with Mazzocca). Together with De Boeck, Mazzocca and Storme we determined the second smallest Kakeya set in the even case. A second variation we studied with Seva Lev. Fix n and k. We color the points of AG(n, 2), Red and Green, in such a way that for every point P there is a k-dimensional subspace containing it that is completely green, with the
possible exception of the point P itself. How many red points can there be? Equivalently, how many green points must there be. The dual problem of covering a set of points in the plane by lines, is to block a set of lines by points. Here the basic, but trivial result is that q + 1 points suffice to block all lines of the projective plane PG(2, q). For the afine plane the case is much more interesting and non-trivial. By a famous result of Jamison, Brouwer, Schrijver, we need at least 2q-1 points. With a relatively large group of people we recently looked at this problem for the set of points and blocks (secants) of the classical unital. This is a set of q3 + 1 points in PG(2, q^2), such that every line intersects it in q + 1 or 1 point.
It is well known that the points of PG(2, q^2) can be partitioned into q^2-q+1 Baer subplanes (PG(2, q)). The union of any t disjoint Baer subplanes forms a two-intersection set with intersection numbers t; q + t. With some luck I will also be able to say something interesting about the following problem: How many points are needed to cover the long secants (so the q + t-secants) of such a union.

Back to Workshop IV: Finding Algebraic Structures in Extremal Combinatorial Configurations