Blocking sets in three dimensional finite affine spaces

Question

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

Edit 1: After Douglas Zare's answer below we have $s(q) \geq 2q^2 - 1$ for all $q$ and $s(q) \leq 3q^2 - 3q$ for $q \geq 3$. Can this be improved further?

I have also found two references that prove this lower bound of $2q^2 - 1$, Proposition 4.1 in Nuclei of pointsets in $PG(n,q)$ (1997) and Theorem 3.1 in On Nuclei and Blocking Sets in Desarguesian Spaces (1999). In fact, Sziklai has mentioned the same argument as Douglas Zare after his proof of Proposition 4.1. Their proofs are generalisations of the polynomial technique introduced by Blokhuis in On nuclei and affine blocking sets (1994).

Answer 1

Here is a slightly better lower bound. If there are fewer than $2q^2$ points then there is some line that hits the set at most once. Consider the $q+1$ planes containing a line containing one point. There must be at least $2q-2$ other points in each of those planes to meet all lines in the plane, for a total of $1+(q+1)(2q-2) = 2q^2-1$ points. So, $2q^2-1 \le s(q)$. This is sharp for $q=2$.

---

Here is a very slightly better upper bound: $s(q) \le 3q^2-3q$ for $q\ge 3$. This is sharp for $q=3$. Consider parallel hyperplanes $H_1,...,H_q$ and a transverse line $\ell$ intersecting $H_1$ at the point $P$. Consider the $q+1$ lines through $P$ contained in $H_1$. Together with $\ell$, these span $q+1$ planes $K_1,...,K_{q+1}$. Choose $q-1$ pairs $\{K_{i,1},K_{i,2}\}$ so that every plane is chosen at least once, which is possible when $2q-2 \ge q+1,$ or $q \ge 3$.

Include $H_1 \setminus \{P\}$. Include two lines through $\ell \cap H_i$: $H_i \cap K_{i,1}$ and $H_i \cap K_{i,2}$.

This has one fewer point than three hyperplanes intersecting at a point, and it meets all lines. So, for $q \ge 3, s(q) \le 3q^2-3q$.

Answer 2

Here is an improvement of the upper bound which I found in ``The polynomial method in Galois geometries'' by Simeon Ball. See page number 4.

The known constructions are somewhat crude. For example, let $S$ be a set of points of $AG(3,q)$ with the property that every line is incident with a point of $S$. For $q$ square, the smallest known example has size roughly $2q^2 + 2q\sqrt{q}$ and is constructed using a double blocking set of $PG(2,q)$ at infinity and forming a cone with a vertex point of the affine space.

Let's work out the details. A double blocking set in $PG(2,q)$ is a set of points that intersects every line in at least two points. Let $AG(3,q)$ be embedded in $PG(3,q)$ via a hyperplane at infinity $H_\infty \cong PG(2,q)$. Now let $B$ be a double blocking set in $H_\infty$. Pick any affine point $a$ and let $S$ be the affine part of the union of all lines connecting $a$ to a point of $B$ (the so-called cone). Now let $\ell$ be any line of $AG(3,q)$. The plane $H$ spanned by $a$ and $\ell$ intersects $H_\infty$ in a line $\ell_{\infty}$. The line $\ell_{\infty}$ contains at least two points $b_1, b_2$ of $B$. Since $a, b_1, b_2$ are in $H$ the lines $\ell_1 = ab_1$ and $\ell_2 = ab_2$ are contained in $H$. In the affine part of $H$ there is a unique line through $a$ and parallel to $\ell$. Thus $\ell$ intersects at least one of these lines non-trivially in their affine part, which is contained in $S$. This proves that $S$ is a blocking set in $AG(3,q)$.

The size of $S$ is equal to $1 + (q-1)|B|$. Therefore, we can take $B$ to be as small as possible to get small blocking sets in $AG(3,q)$. Three non-concurrent lines in $PG(2,q)$ form a double blocking set of size $3q$. But this gives us the old bound of $s(q) \leq 3q^2 - 3q + 1$. When $q$ is a square we can take a union of two disjoint Baer subplanes (each one of them forms a blocking set in $PG(2,q)$, which gives us $$|S| = 1 + (q - 1)(2q + 2\sqrt{q} + 2) = 2q^2 + 2q\sqrt{q} - 2\sqrt{q} - 1.$$ Sadly, we can't do any better than this as shown by Blokhuis and Ball in ``On the size of a double blocking set in $PG(2,q)$'' for $q > 16$ . For non-square $q = p^{2d + 1} > 3$, there is lower bound of $2q + p^d \lceil(p^{d+1} + 1)/(p^d + 1)\rceil + 2$ on the size of a double blocking set, but it is not always sharp. There is further discussion for smaller planes in the paper, but that doesn't help us much in our problem and so we have $$s(q) \leq 2q^2 + 2q\sqrt{q} - q - 2\sqrt{q}$$ for $q$ square, which is strictly better than the previous bound of $3q^2 - 3q$ for all $q \geq 9$.