The fewest points that meet every line

The curve that no three points in line define asked for the largest set of points in a finite plane with no three on a line — a set that meets every line at most twice — and found the conics in odd order and the hyperovals in even. This essay asks the opposite question. What is the smallest set of points that meets every line at least once?

Put that way it is too easy. In a projective plane any two lines meet, so a single line already meets every other line, and with $q + 1$ points it is as small as a set meeting every line can be: through any point outside the set pass $q + 1$ lines, and each of them needs a point of the set of its own. The interesting question forbids the cheap answer. A blocking set is a set of points that meets every line and contains no line entirely. Such sets exist in almost every finite plane, and they are expensive: a line costs $q + 1$ points, and a blocking set that is not a line costs at least $q + \sqrt q + 1$.

Seven points in a plane of twenty-one #

The figure draws the projective plane over the field of four elements — its sixteen affine points as a grid, labelled by the field’s elements $0, 1, \omega, \omega^2$, and its five points at infinity, one for each direction of parallel lines, in a row above. It has 21 lines, each with five points. A line blocks every line, with five points. The large dots are seven points that meet every one of the 21 lines and contain none of them, and they are the fewest possible: an exhaustive search tried every way of choosing six points that meets every line and found that each one contains a whole line.

The seven points are not arbitrary. They form a Baer subplane: a copy of the seven-point Fano plane sitting inside the larger plane, its seven lines being seven of the big plane’s lines, each meeting the subplane in exactly three points. Every other line of the big plane — fourteen of them — meets the subplane in exactly one point. That is the whole mechanism. Each of the subplane’s own lines is met three times, and every other line is met once, so every line is met and no line is used up.

Aart Bruen proved in 1970 that no blocking set can do better: in a plane of order $q$ a nontrivial blocking set has at least $q + \sqrt q + 1$ points, and when $q$ is a square the bound is met by a Baer subplane of order $\sqrt q$ and only by one. For $q = 4$ that is $4 + 2 + 1 = 7$.

Why a blocking set cannot be small #

Bruen’s argument is a count, and it is short enough to give in outline. Let $B$ be a blocking set of size $q + k$ containing no line. Take a line $\ell$ that meets $B$ in as many points as any line does, say $n$ points, with $n \le q$ since $\ell$ is not inside $B$. Through a point $P$ of $\ell$ not in $B$ pass $q$ other lines, and each must meet $B$ somewhere off $\ell$; those meetings are distinct points, since two lines through $P$ meet only at $P$. So $B$ has at least $q$ points off $\ell$, and with the $n$ on it, $q + k \ge q + n$, so every line meets $B$ in at most $k$ points.

Now count pairs. Every line meets $B$ at least once and at most $k$ times, and summing over the $q^2 + q + 1$ lines the number of points and the number of pairs of points of $B$ on each line, a short calculation with those two constraints — the variance of the line intersections cannot be negative — forces $k \ge \sqrt q + 1$. Equality requires every line to meet $B$ in exactly 1 or $\sqrt q + 1$ points, which is exactly what a Baer subplane does: the fourteen lines and the seven lines in the hero figure.

Prime orders cost more #

When $q$ is prime there are no subplanes at all — a subplane would need a subfield — and the bound $q + \sqrt q + 1$ is not a whole number to aim at. In the plane of order 5, Bruen’s bound says at least $5 + 2.24 + 1 = 8.24$, so at least 9. The search confirms it: every set of 7 and of 8 points that meets every line contains one, and the first set of 9 it finds is drawn in the figure. Of its 31 lines, three meet it in four points, four in three, six in two and eighteen in one.

The three lines meeting it four times are the sides of a projective triangle. Take three lines forming a triangle, and on each side choose the vertices and every other point between them — $(q + 1)/2$ points per side, $3(q + 1)/2$ in all. A line that dodges the chosen points on two sides could slip through a gap on the third, and the arithmetic of the field forbids it: by Menelaus’s theorem, which holds over any field, a line cuts the three sides at points whose coordinates multiply to a fixed value, and choosing the alternate points by whether their coordinate is a square makes that product impossible for three gaps at once. Aart Blokhuis proved in 1994 that in a plane of prime order nothing smaller exists: a blocking set containing no line has at least $3(q + 1)/2$ points, and the projective triangle meets the bound. His proof is algebraic — it writes the blocking set as a polynomial over the field, using Rédei’s theory of polynomials with many missing coefficients — and it closed a question that Bruen’s counting had left open since 1970.

Sizes against the bounds #

The search settles five planes. In the seven-point plane of order 2 there is no blocking set at all without a line, and the reason can be checked by hand. A set meeting every line leaves out some points, and any line made entirely of left-out points is a line it misses. If it leaves out two points, the five lines through either of them account for all the lines touching them, and the other two lines lie wholly inside the set. If it leaves out three points not on a line, those three touch six of the seven lines, and the seventh lies inside the set. If the three left out are a line, the set misses that line. Three points that meet every line must themselves be a line, and fewer cannot meet all seven. Every case ends with a whole line inside the set or a line missed, and the search confirms it in eighteen branches. In order 3 the minimum is 6, in order 4 it is 7, in order 5 it is 9, and in order 7 it is 12. Every one sits on the better of the two bounds: Blokhuis’s $3(q + 1)/2$ for the primes 3, 5 and 7, and Bruen’s $q + \sqrt q + 1$ for the square 4, where it is the larger of the two. At every prime Bruen’s bound is strictly weaker — 8.24 against 9 at order 5, 10.65 against 12 at order 7 — and the gap is what Blokhuis’s theorem was needed for.

The bounds are about what is forced; they do not by themselves say that smaller sets are impossible to find. That is the search’s work, and its cost is the next figure.

Ruling out the smaller sets #

The search is a branch-and-bound over sets of a fixed size. It picks a line not yet met — the one with the fewest points still allowed — and branches on its points, each branch forbidding the points the earlier branches tried, so that every candidate set is reached exactly once. It never adds a point that would complete a line. And it abandons a branch as soon as the lines still unmet outnumber what the remaining points could reach, since each point lies on only $q + 1$ lines.

The work grows steeply with the order. Ruling out five points in the plane of order 3 takes 274 branches; ruling out six in order 4 takes 3,125; ruling out eight in order 5, 120,503. In the plane of order 7, with 57 points, ruling out sets of nine, ten and eleven points takes half a million, seven and a half million and seventy-one million branches, almost eighty million in all. Order 8, with 73 points, or order 11, with 133, would take vastly more, and the theorems are what reach them. The search confirms the theorems where it can; the theorems cover every order at once.

The minimum sizes also bear on a question the essays on finite planes have asked before: which orders a plane can have. A projective plane of order $q$ is the same thing as a complete set of orthogonal Latin squares of order $q$, and the orders a plane cannot have — six, ten, and those ruled out by Bruck and Ryser — were excluded by counting arguments of exactly Bruen’s kind, a sum of squares that cannot be negative. Blocking sets give one more invariant to compute in any plane anybody constructs, and in the search for exotic planes of small order they have been used as fingerprints: two planes with different numbers of minimum blocking sets cannot be the same plane.

How many minimum sets, and how many shapes #

The same search, told to keep going rather than stop at the first success, counts every minimum blocking set. To save work it counts those through one fixed point and multiplies by the number of points over the set’s size, which is exact because the plane’s symmetries move any point to any other. The counts are 234 in the plane of order 3, 360 in order 4, 15,500 in order 5 and 130,340 in order 7.

Set beside the symmetries of each plane — the invertible $3 \times 3$ matrices over the field, up to multiplication by a constant — the counts say something about shape. In order 4 the plane has 60,480 such symmetries and 360 Baer subplanes, and $60{,}480/360 = 168$, the number of symmetries of the Fano plane itself: every minimum blocking set is a Baer subplane, all of them alike, each fixed by the symmetries of the small plane it copies. In orders 3 and 5 the ratio is 24, consistent with every minimum set being a projective triangle, each fixed by 24 symmetries. In order 7 the ratio is 43.2, not a whole number, and so the minimum sets of order 7 cannot all be images of one shape: more than one configuration of 12 points meets every line with none to spare. The projective triangle is one; describing the others is a classification problem the count raises and does not answer.

Random blocking sets are larger #

How special are the smallest ones? The last figure builds 2,000 blocking sets at random in the plane of order 7: add random points that complete no line until every line is met, then remove any point all of whose lines are met at least twice, until every point is needed. Each result is minimal — no point can be dropped — but not necessarily minimum. Most have 14 points; a few have 16 or 17; 27 of the 2,000 reach 12, and none go below it, as the search guarantees. The smallest blocking sets are rare, rigid configurations, and a greedy process stumbles on them about one time in seventy-five.

That rarity is typical of extremal objects in finite geometry. The largest sets with no three in line were forced to be conics; the smallest sets meeting every line are forced, in the cases the search reaches, to be subplanes or triangles or a short list of relatives. In both directions the extreme is algebraic structure, and the typical set is not.

Where blocking sets are used #

Blocking sets are the finite-geometry form of a hitting set — a set of elements meeting every member of a family — and they turn up wherever a family of lines must each be touched. In coding theory, a blocking set in a projective space gives a linear code whose minimum distance is controlled by how the set meets hyperplanes, and minimal blocking sets correspond to minimal codewords. In the design of experiments and of secret-sharing schemes, a set of participants that meets every “line” of a geometric access structure is exactly a blocking set. And the polynomial method that Blokhuis used has a famous relative: Robert Jamison, and independently Andries Brouwer and Alexander Schrijver, proved in 1977–78 that blocking every line of the affine plane of order $q$ takes at least $2q - 1$ points, by an argument with polynomials over the field so short that it became the model for the finite-field Kakeya problem a generation later.

Every statement here also has a dual, because a projective plane looks the same with points and lines exchanged. A set of lines that passes through every point and does not consist of all the lines through one point — a dual blocking set — needs exactly as many lines as a blocking set needs points: seven in the plane of order 4, nine in order 5, twelve in order 7. The trivial cover, all the lines through one point, costs $q + 1$; refusing it costs the same half again. In that form the question is about covering a finite world with straight cuts, and the Baer subplane becomes seven lines of the plane of order 4 that pass through every one of its 21 points, three lines through seven of them and one through each of the rest.

What the search shows and assumes #

The planes are built from field arithmetic and checked: every line has $q + 1$ points. The minimum sizes are exact for the five orders searched, because the search is exhaustive and each of its candidate sets is reached once, by construction. The counts are exact too, under the assumption — true for these planes, whose symmetries move any point to any other — that every point lies in the same number of minimum blocking sets. The random sets show what a greedy process finds, and nothing more.

All five planes are the planes built from fields. The plane of order 9 that no field built has its own blocking sets, and Bruen’s bound, which is a pure count, holds there too; Blokhuis’s, which uses the field’s polynomials, need not, and order 9 is not prime in any case. The search does not reach it.

Still open: the second smallest, and the planes no field builds #

Above the minimum the picture is far less complete. the sizes of minimal blocking sets between the minimum and much larger values are not fully understood: which sizes occur, and with what structure, is known for small primes by computation and in ranges by theorems, with gaps between. For square orders, sets just above the Baer subplane are classified by results of Blokhuis, Storme, Szőnyi and others; for orders that are prime powers but not squares, such as 8 and 32, the exact minimum is known only in some cases. And in the planes that are not built from fields, the polynomial method does not apply at all, and it is not known in general how small a blocking set can be there, or whether every such plane even has one of size near its Bruen bound.

Expensive, and forced to be structured #

A set of points meeting every line of a finite plane and containing none needs at least $q + \sqrt{q} + 1$ points, and in a plane of prime order at least $3(q + 1)/2$ — 7 in the plane of order 4, 9 in order 5, 12 in order 7 — and exhaustive search confirms each value, ruling out every smaller set at a cost of up to seventy-one million branches. The smallest sets are a copy of the seven-point plane, meeting each line once or three times, or a projective triangle of alternate points on three lines; they are counted exactly, they are rare among random minimal sets, and in order 7 they come in more than one shape. A line meets every line for $q + 1$ points; refusing to use a line costs a half again.