10
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ If one of blocking points is $(0,0,0)$ and others are $(a_i,b_i,c_i)$, we may consider a polynomial $f(x,y,z)=\prod(1+xa_i+yb_i+zc_i)$, which has non-zero value at $(0,0,0)$, and has root of multiplicity at least $2q-1$ at each other point - by 2-dimensional case. What are lower bounds for degrees of such polynomials? $\endgroup$ – Fedor Petrov Jan 28 '16 at 0:56
  • $\begingroup$ $(2q-2)(q-1) + 3(q-1) = 2q^2 - 1$ by Ball and Serra's punctured combinatorial nullstellensatz with multiplicity: link.springer.com/article/10.1007%2Fs00493-009-2509-z. Thus giving another proof of Douglas Zare's lower bound given below. (Nice catch. I should have thought about this before) $\endgroup$ – Anurag Jan 28 '16 at 1:10
  • $\begingroup$ Does equality occur? $\endgroup$ – Fedor Petrov Jan 28 '16 at 1:18
  • $\begingroup$ No, not always. The bounds obtained by this result, for example on multiple blocking sets, can be improved for many cases. Also, the value of $s(3)$ violates this bound. $\endgroup$ – Anurag Jan 28 '16 at 1:21
  • $\begingroup$ But it is another question, examples here may a priori have no relation to blocking sets problem. $\endgroup$ – Fedor Petrov Jan 28 '16 at 1:24
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks. This is how I understand the second part: all lines contained in the hyperplanes $H_1, \dots, H_q$ are blocked once you have chosen a pair of intersecting lines in each of them. And every transverse which doesn't contain $P$ is blocked by $H_1 \setminus \{P\}$. Any transverse through $P$ other than the line $\ell$ intersects every $H_i$ ($i > 2$) in a point $R_i$ other than $Q_i = \ell \cap H_i$ and the line $Q_iR_i$ is parallel to one of the $q+1$ lines through $P$ in $H_1$. So, we ensure that for each line through $P$ in $H_1$, we take a parallel line through $Q_i$ in $H_i$. $\endgroup$ – Anurag Jan 27 '16 at 22:51
  • $\begingroup$ I would like to add that a friend of mine is running a computation which has shown that $s(4) = 34 < 36$ (in case you are wondering about the sharpness of this bound $s(q) \leq 3q^2 - 3q$). He'll hopefully post more values he has computed by tomorrow. By interpolating from $s(2), s(3), s(4)$ we could make a bold (and probably wrong) conjecture that $s(q) = (5q^2 - 3q)/2$ ... But may be one can try constructing examples of size $(5q^2 - 3q)/2$ to show $s(q) \leq (5q^2 - 3q)/2$. $\endgroup$ – Anurag Jan 27 '16 at 22:57
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Hence $\lim \inf s(q)/q^2=2$? Is $\lim \sup s(q)/q^2 = 2$? Or $3$? $\endgroup$ – Will Sawin Feb 1 '16 at 2:57
  • $\begingroup$ Yes, lim inf is equal to $2$. I can't say what the lim sup is going to be. The lower bounds for double blocking sets in the case of non-square $q$ are not sharp. In particular, the working conjecture (unless there has been some very recent progress on this) seems to be that for prime $p$ a double blocking set in $PG(2,p)$ has size at least $3p$. Thus, for prime $p$ we probably can't improve $s(p) \leq 3p^2 - 3p$ using double blocking sets. $\endgroup$ – Anurag Feb 1 '16 at 3:53
  • $\begingroup$ It is interesting. Are there examples of estimates which are proved to be much better in the case $q$ square resp. to $q$ prime? $\endgroup$ – Fedor Petrov Feb 4 '16 at 11:41
  • $\begingroup$ @FedorPetrov: I don't think I understand your question. Are you looking for improvements of the upper bound in the case of q prime? $\endgroup$ – Anurag Feb 4 '16 at 15:25
  • 1
    $\begingroup$ I mean, that I have never seen the following phenomenon: "asymptotics for $q$ squares and $q$ primes is different." This question is a candidate, but maybe there are known examples? $\endgroup$ – Fedor Petrov Feb 4 '16 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.