At least as many lines as points

Scatter $n$ points on a page, not all in one line, and draw every line that passes through two or more of them. How few lines can there be?

Two points always give one line. Three points not in a line give three. Four points can give four — three in a row and one off it — but not three. The pattern that suggests itself is that the number of lines is never smaller than the number of points, and that is a theorem: $n$ points not all on one line determine at least $n$ connecting lines. Nicolaas de Bruijn and Paul Erdős proved it in 1948, in a form that needs no geometry at all, and the geometric form has a proof three lines long that rests entirely on Sylvester’s ordinary line.

What makes the statement worth a figure is not the bound but the equality. Almost every configuration has far more lines than points — a set in general position has $n(n-1)/2$ — and exactly one shape of configuration sits on the floor.

A line of points and one more #

The shape is the near-pencil: $n - 1$ points in a line, and one point off it.

Count its lines. The long line is one. Every line through the odd point meets the long line in exactly one of its $n - 1$ points, so there are $n - 1$ of those and no others: two points of the long line determine the long line itself, and two lines through the odd point cannot share a second point. That is $1 + (n - 1) = n$ lines exactly.

The near-pencil is the configuration that is almost collinear, and the reason it is so economical is that it wastes nothing. Every pair of points on the long line is served by one line between them, which is as efficient as a line can be; every line through the odd point carries only two points, which is as inefficient as a line can be, but there are only $n - 1$ such pairs to serve. The long line absorbs $\binom{n-1}{2}$ pairs in a single stroke. A configuration with fewer lines would need to absorb even more pairs per line, and the theorem says that no arrangement manages it.

It is also a configuration full of ordinary lines — $n - 1$ of the $n$ lines carry exactly two points. That is not a coincidence, and it is the first hint of the proof: the configurations with the fewest lines are the ones where Sylvester’s theorem has the least to find, because it can find ordinary lines everywhere.

One point and one line removed together #

Sylvester’s theorem says that a finite set not all in one line has an ordinary line — a connecting line holding exactly two of the points. Call its two points $P$ and $Q$, and remove $P$.

Two things happen, and the figure checks both of them by recounting from the coordinates.

The line $PQ$ disappears. With $P$ gone it holds only $Q$, and a line through a single point is not a connecting line of anything. So the set loses at least one line — more, if $P$ was on several ordinary lines, as in the seven-point figure, where it was on two.

No new line appears, and no other line is lost unless it was ordinary through $P$. Every connecting line of the smaller set was already a connecting line of the larger one. Every line through $P$ that held three or more points still holds two or more after the removal, so it survives.

So the count drops by at least one:

$$\text{lines}(S) \ \ge\ \text{lines}(S \setminus P) + 1.$$

That is the whole induction step. If the smaller set is not all in one line, then by induction it has at least $n - 1$ lines, and the original set has at least $n$. The figure’s arithmetic is exactly this: seven lines for six points gives at least eight for seven, and the actual count is nine.

Where the induction stops #

The induction has one other case: the $n - 1$ points left behind might all lie in one line. Then there is nothing to apply the induction to — a collinear set has one line, not $n - 1$ — and the argument has to look directly at what the original set was.

If removing $P$ leaves $n - 1$ collinear points, then the original set was those $n - 1$ points in a line together with $P$ off it — a near-pencil — and it has exactly $n$ lines, as counted above. So the base case is not an embarrassment to the argument. It is the equality case, and the induction delivers it along with the bound.

It also delivers more than was asked. Follow the argument for a set that is not a near-pencil. At every stage it removes an end of an ordinary line, and at every stage the drop is at least one; the chain ends either at two points (one line) or at a near-pencil, and a set that never becomes a near-pencil picks up an extra line somewhere. A short case check along these lines is the standard proof that the near-pencil is the only configuration in the real plane with exactly $n$ lines. Nothing in the statement of the theorem suggested that the extremal configuration would be unique; the proof finds it because Sylvester’s theorem forces the removals to be of a specific kind.

A census of every subset of a grid #

A theorem that holds for every finite configuration can be tested on finitely many of them, and the test is worth running because it shows the shape of the distribution rather than only its floor.

Three features of the table are worth reading.

The minimum column never goes below the point count, which is the theorem checked on 39,012 cases. The check is not a proof — the theorem is about every finite set in the plane, and a grid is a special place to take points from — but it is an independent confirmation, computed without ever mentioning Sylvester.

The equality column shows the near-pencil being squeezed out. Three points not in a line are always a near-pencil, so all 516 of them have exactly three lines. At four points, 532 sets meet the bound, and every one of them has three points in a row. At five, 120 sets have four points on a grid line and one off it. At six, a near-pencil would need five points in a row, and a four-by-four grid does not have five; so no six-point subset meets the bound at all, and the fewest lines jumps to eight. The grid’s shape, not the theorem, sets the minimum from there on — which is itself a demonstration that the near-pencil is the only way to reach $n$.

The maximum column is $\binom{n}{2}$: the grid has room for eight points with no three in a line, so the most wasteful configurations it holds are in general position throughout the table.

The same theorem with no plane in it #

De Bruijn and Erdős did not prove the geometric statement. They proved a statement about finite sets that contains it.

Call a collection of subsets of a finite set a linear space if every two points lie in exactly one of the subsets, called lines, and every line has at least two points. Connecting lines of points in the plane are an example: two points determine one line, and two lines share at most one point. So is the Fano plane, whose seven points lie three at a time on seven lines with no geometry anywhere in sight.

De Bruijn–Erdős: a linear space with $n$ points, not all on one line, has at least $n$ lines — and exactly $n$ only if it is a near-pencil or a finite projective plane.

The second equality case is the interesting one, and it is the one the real plane cannot have. The Fano plane has seven points and seven lines and is not a near-pencil. So the combinatorial theorem is sharp in a way the geometric one is not, and the geometric one’s uniqueness comes from exactly the property that makes the Fano plane impossible to draw: a projective plane has no ordinary lines at all, while every finite set in the real plane has one. Sylvester’s theorem is what rules out the second equality case, and that is why the geometric proof above could use it as its only tool.

The combinatorial proof is a count, and a surprisingly delicate one. For a point $p$ and a line $L$ not through it, the number of lines through $p$ is at least the number of points on $L$ — each point of $L$ joins $p$ by a different line. Write $r_p$ for the number of lines through $p$ and $k_L$ for the number of points on $L$; then $r_p \ge k_L$ whenever $p \notin L$. Summing a carefully weighted version of that inequality over all non-incident pairs gives $\text{lines} \ge \text{points}$, with equality forcing $r_p = k_L$ for every such pair — which, followed through, is either a near-pencil or a plane in which every point is on the same number of lines. No step uses coordinates, distances or orientation.

A theorem that was proved twice under one name #

There is a quiet connection here to a theorem about schedules. A design in which every pair of people meets exactly once is a linear space whose lines all have the same size, and Fisher’s inequality says it has at least as many groups as people — at least as many lines as points. So Fisher’s inequality, proved by a determinant in 1940, is the special case of de Bruijn–Erdős in which every line has the same length, and de Bruijn–Erdős, proved by a count in 1948, drops the equal-length condition entirely.

The two proofs do not look alike and do not use each other. Fisher’s is linear algebra: the incidence matrix has full rank, so its columns cannot outnumber its rows. De Bruijn and Erdős’s is a counting argument with no matrix in it. The rank proof generalises, and the generalisation meets de Bruijn–Erdős from the other side: take for each point the set of lines through it, and two such sets share exactly one line, so the Fisher-type inequality for set systems with constant pairwise intersection gives, once more, at least as many lines as points. One inequality, reached by a determinant and by a count and by an ordinary line, with the three proofs using three different properties of the object.

And, as a small historical joke, the same two authors proved an entirely different theorem in 1951, about colouring infinite graphs, which is also called the de Bruijn–Erdős theorem. The two have nothing in common but their authors.

Most sets are nowhere near the floor #

The bound is linear in $n$. Most configurations have a number of lines that grows like $n^2$.

The figure’s families spread out quickly. A five-by-five grid, twenty-five points, has 140 lines; the configurations that minimise ordinary lines are extremely economical in one sense and not at all in this one, because their three-point chords number about $n^2/8$. The near-pencil alone stays on the floor.

That spread is a theorem too, and a much harder one. Beck’s theorem (1983) says that for $n$ points in the plane, either some single line contains a constant fraction of them, or they determine at least a constant times $n^2$ lines. There is no middle ground: a set determines few lines only by being mostly collinear. The near-pencil is the extreme case of the first alternative, and the grid and the polygon configurations sit firmly in the second. Beck’s proof goes through the Szemerédi–Trotter bound on incidences between points and lines, which is the quantitative form of the fact that lines cannot pass through many points of a set without the set being close to collinear.

So the de Bruijn–Erdős theorem is the linear end of a quadratic story, and its equality case is precisely the configuration Beck’s first alternative describes in its most extreme form.

The induction on a set that is not special #

The seven-point configuration of Kelly and Moser was chosen above because it has so few ordinary lines, which makes it the hardest case for an argument that uses them. The grid is a more ordinary place to run the same step.

Here the step is generous. The corner of the three-by-three grid lies on its row, its column and its diagonal, each holding three points, and on two ordinary lines running to the midpoints of the far sides. Removing the corner loses the two ordinary lines, keeps the other three, and leaves a set with eighteen lines where the induction only needed eight. The inequality at each step is almost always slack, and the proof works by never needing it to be tight except at the very end.

That slackness is also why the argument cannot prove anything much stronger. Each removal is guaranteed one lost line and no more, because Sylvester’s theorem guarantees one ordinary line and, in general, no more than a handful; a lower bound of $n$ is what the method can deliver. The bound on ordinary lines that Melchior proved — at least three — does not improve it, since a removed point need not lie on more than one of them.

What the drawings cannot settle #

All of them are finite and most are special. The census takes its points from a four-by-four grid, which is a very structured place, and the other figures draw named configurations. The theorem is about every finite set in the real plane, and the proof is the induction, not the census; what the census adds is independent evidence and a view of which sets sit where.

The equality case is proved in words. The figures show that the near-pencil has $n$ lines and that no grid subset of six or more points reaches the bound. That no configuration anywhere other than a near-pencil reaches it follows from the induction argument, carried out carefully, and the drawings illustrate it rather than establish it.

Collinearity is exact here, and the argument does not depend on that. Every count in the figures is made from whole-number coordinates, where three points are in line exactly when a cross product of integers is zero. The theorem holds for arbitrary real coordinates, where no computation could decide collinearity exactly, and the proof does not care: it uses only the existence of an ordinary line.

Nothing here reaches the complex plane. Over the complex numbers there are configurations with no ordinary line — the nine inflection points of a cubic — so the induction cannot start. The combinatorial theorem still applies to them, since any configuration of points and connecting lines is a linear space, and it says they have at least as many lines as points; the nine inflection points have twelve.

Still open: how many lines a given number of ordinary lines forces #

The two theorems in this subject — at least $n/2$ ordinary lines for large $n$, and at least $n$ lines in all — are each sharp for a single family, Böröczky’s configurations for the first and near-pencils for the second. Those are different families, and between them lies a question that is not settled: for a configuration with $n$ points and only a few ordinary lines, how many lines must it have in total?

Green and Tao’s structure theorem says that a configuration with fewer than a constant times $n$ ordinary lines lies mostly on a cubic curve, so its line count is essentially that of a cubic configuration — about $n^2/6$. What happens in the regime between — configurations with, say, $\sqrt n$ ordinary lines, which are neither near-pencils nor near-cubic — is described only by Beck-type bounds with unspecified constants. The exact trade-off between few ordinary lines and few lines is not known, and it is where the two extremal families would have to be interpolated if anyone knew how.

The combinatorial version has its own open edge. De Bruijn–Erdős says a linear space has at least as many lines as points, with the projective planes as the only non-trivial equality case — and which orders of projective plane exist is itself unknown. Every known plane has prime-power order; the plane of order ten was ruled out only by a massive computer search in 1989, and whether a plane of order twelve exists is open. So the equality case of the combinatorial theorem is, strictly, not classified: its members are known to be exactly the projective planes, and the list of projective planes is not known.

One point that carries the whole count #

The proof uses one fact about the plane — that a finite set not in a line has a line through exactly two of its points — and one operation, removing a point. That the combination yields a sharp bound, with a unique extremal configuration, is the kind of economy the subject keeps rewarding. The near-pencil is the configuration where the odd point out is carrying the whole count: remove it and the set collapses into one line, and put it back and it adds exactly one line for every point it can see.

That reading also explains why the bound is linear rather than quadratic. A point added to a set adds lines only towards the points it does not already share a line with, and in the near-pencil the long line has pre-empted every pair but the $n - 1$ involving the odd point. Every other configuration leaves more pairs unserved by long lines, and pays for each of them with a line of its own. The theorem is, in the end, a statement that no arrangement of points can pre-empt more pairs than a single line of $n - 1$ of them does — and Sylvester’s ordinary line is the certificate, at every stage of the induction, that some pair has escaped.