Skip to main content
2 of 3
added some improvements
Anurag
  • 1.2k
  • 1
  • 20
  • 29

Blocking sets in three dimensional finite affine spaces

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 improvement 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?

Anurag
  • 1.2k
  • 1
  • 20
  • 29