# Points necessary to intersect all lines in finite projective geometry

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.

• What is $PG(d,q)$? Nov 6, 2015 at 19:27
• If $V(d+1,q)$ is the vector space of rank $d+1$ over $GF(q)$, then then projective space $PG(d,q)$ is the geometry where points, lines etc. are the subspaces of $V(d+1,q)$ of rank $1,2,...$. (From www-ma4.upc.es/~simeon/IFG.pdf) Nov 9, 2015 at 10:28

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

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.

• That sounds like a great book :-) I don't suppose it's available in English? Nov 13, 2015 at 16:06
• Is the proof complicated? Does it also say something about affine geometries? Nov 13, 2015 at 16:54

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

• This is a generalization of the result I put, which is great! Thank you very much! Dec 18, 2015 at 16:06