Points necessary to intersect all lines in finite projective geometry

Question

I'm reading about finite geometries, projective and affine.

I wonder what the smallest set of points is, given a geometry $PG(d,q)$, that intersects all lines. (or hyperplanes.) For example in the Fano plane, it looks like three points are enough.

I'm still not quite used to thinking about geometries like this, so I wonder if anybody has a hint for how I might approach the problem?

Edit: It's clear that $q+1$ points are enough, since you can use that to cover an entire line, and all lines intersect in some point. However, it's not as clear to me that you can't do with less points.

Update: For AG(d,q), this paper says that we need exactly $d(q-1)+1$ points to intersect all hyperplanes.

Answer 1

In the book of Kiss-Szőnyi: Véges geometriák (Finite geometries in Hungarian) the Lemma 6.22 says that

In a projective plane of order $q$ any set of points which meets all the lines is of size at least $q+1$. If the size is precisely $q+1$, then they form a line of the projective plane.

I hope this helps you.

Answer 2

The theorem Stefan mentions is quite easy to prove:

Let $P$ be a projective plane of order $q$ and assume that $x_1,\ldots,x_q$ are $q$ points of $P$ intersecting with every line. The point $x_1$ lies on exactly $q+1$ lines (as does every point of $P$). Since any two points of $P$ are joined by one line, every point $x_2,\ldots,x_q$ can contribute at most $q$ "new" lines to the set of lines covered by the given points, i.e. we have $$q^2+q+1 < (q+1) + (q-1)*q = q^2 + 1,$$ a contradiction.

Similarly, if $x_1,\ldots,x_{q+1}$ are $q+1$ points intersecting with every line, let $s_i$ be the number of lines through $x_i$ not already covered by an $x_j$ with $j<i$. Then $$\begin{align}s_1&=q+1\\ s_2&=q\\ s_k&\le q\;\text{ (for $k\ge3$),} \end{align}$$ so in total we have $$\begin{align}q^2+q+1&=\sum_{i=1}^{q+1}s_i \\ &\le (q+1) + q*q\\ &=q^2+q+1.\end{align}$$ This forces $s_k=q$ for all $k\ge2$, i.e. all points $x_2,\ldots,x_{q+1}$ have the same line in common with $x_1$, i.e. they form exactly one line of $P$.

Answer 3

The sets you are looking at are called blocking sets with respect to lines, knowing that should help find some relevant literature on the topic. They have mostly been studied in projective planes, but also in affine planes and, to some extent, higher dimensional finite geometries.

The biggest problem is, what is the size of the smallest blocking set that does not contain a line?

This paper is the best reference for blocking sets in affine spaces that I can find; it is On intersection sizes in Desarguesian affine spaces, by Simeon Ball. http://www.sciencedirect.com/science/article/pii/S0195669800903500

I've only looked it over briefly, it may refer to blocking sets with respect to hyperplanes instead of lines (a line is a hyperplane in a plane).