$\newcommand{\F}{{\mathbb F}}$ Let $q$ be an odd prime power. A blocking set in the affine plane $\F_q^2$ is a set blocking (meeting) every line.

A union of two non-parallel lines is a blocking set of size $2q-1$, and it is well-known that this is the smallest possible size of a blocking set in $\F_q^2$. A very simple proof goes as follows. Suppose that $B\subset\F_q^2$ is a blocking set. Translating $B$ appropriately, we can assume that $0\in B$, and we let then $B_0:=B\setminus\{0\}$. The new set $B_0$ blocks every line not passing through the origin; that is, every line of the form $ax+by=1$ with $a,b\in\F_q$ not equal to $0$ simultaneously. As a result, the polynomial $$ P(x,y):=\prod_{(a,b)\in B_0}(ax+by-1) $$ vanishes at every point of $\F_q^2$ with the exception of the origin. Now, if we had $|B_0|<2p-2$, then $P(x,y)$ would be a linear combination of monomials of the form $x^my^n$ with $\min\{m,n\}<p-1$, while for every such monomial, $$ \sum_{x,y\in\F_q} x^my^n=0; $$ this would lead to $$ \sum_{x,y\in\F_q}P(x,y)=0, $$ a contradiction.

Suppose now that $B\subset\F_q^2$ blocks every line with the possible exception of at most one line in every direction. What is the smallest possible size of such an "almost blocking" set?

If $B\subset\F_q^2$ is almost blocking, then pairing in an arbitrary way the non-blocked lines and adding to $B$ the intersection points of these pairs of lines we get a "usual" blocking set; since we had to add at most $(q+1)/2$ points, this gives $$ |B| \ge (2q-1)-\frac{q+1}2 = \frac32(q-1). $$ On the other hand, it is not difficult to construct almost blocking sets $B\subset \F_q^2$ with $$ |B| < 2q-\sqrt q. $$

Is the smallest possible size of an almost blocking set "essentially $\frac32\,q$" or "essentially $2q$" (or neither)?


Your Answer

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

Browse other questions tagged or ask your own question.