Three ordinary lines from a count

The line with only two points on it proved Sylvester’s theorem the way Kelly did in 1948: among all pairs of a point and a connecting line missing it, take the closest, and the line of that pair must hold exactly two points. The argument finds one ordinary line and says nothing about how many there are.

Eberhard Melchior had already done better, in 1941, by an argument of a completely different kind. He proved that every finite set of points in the plane, not all on one line, has at least three ordinary lines — and more than that, an inequality that ties the number of ordinary lines to the number of very rich ones. There is no minimisation in his proof and no distance. It turns the points into lines, counts the pieces of the picture that makes, and applies Euler’s formula.

Points into lines #

The first move is projective duality. Send each point $(a, b)$ to the line $y = ax - b$. Two points on a common line $y = mx + c$ then give two lines that both pass through the point $(m, -c)$ — check: $a$ and $b$ satisfy $b = ma + c$, and the dual line $y = ax - b$ at $x = m$ gives $y = am - b = -c$. So collinear points become concurrent lines, and a connecting line through $k$ of the points becomes a crossing where $k$ of the dual lines meet.

In particular, an ordinary line — exactly two points — becomes a simple crossing, where exactly two lines meet. Sylvester’s question turns into its dual: given finitely many lines, not all through one point, must some point lie on exactly two of them? The first figure shows the translation for the configuration Kelly and Moser singled out, and the three simple crossings are the three ordinary lines the configuration has.

The duality needs one repair to be exact. Two points with the same first coordinate give parallel dual lines, which do not meet in the plane; and a vertical connecting line has no slope to send anywhere. Both problems vanish in the projective plane, the ordinary plane with a line at infinity added, where parallel lines meet at a point on that line. There duality is a perfect exchange of points and lines, and every statement about a configuration of points has a mirror statement about an arrangement of lines. The figures turn each configuration slightly first so that no two dual lines are parallel, which keeps every crossing in view.

A count on the projective plane #

Now count the pieces of the arrangement. The lines cut the projective plane into regions — faces — bounded by segments of lines — edges — that meet at crossings — vertices. Write $t_k$ for the number of crossings where exactly $k$ lines meet, which is the number of connecting lines through exactly $k$ of the original points. Three facts connect the counts.

Each vertex where $k$ lines meet ends $2k$ edges, since each of the $k$ lines passes through and is cut there, and each line is cut into as many edges as it has vertices on it. So the number of edges is

$$E = \sum_k k\,t_k,$$

and the number of vertices is simply $V = \sum_k t_k$.

Each face has at least three sides. A face bounded by only two edges would be a region between two lines that meet twice, and two lines meet only once.

Euler’s formula for the projective plane is $V - E + F = 1$. It is the same formula that says every corner of a polyhedron pays for itself, $V - E + F = 2$, with the $2$ replaced by the projective plane’s own Euler characteristic, which is $1$ — the projective plane being a disc with its boundary glued to itself, a disc sewn to a Möbius band.

Counting edge-sides two ways, every edge borders two faces and every face has at least three edges, so $2E \ge 3F$. Put $F = 1 - V + E$ from Euler’s formula into that:

$$2E \ge 3(1 - V + E) \quad\Longrightarrow\quad E \le 3V - 3.$$

Substituting the two sums:

$$\sum_k k\,t_k \le 3\sum_k t_k - 3 \quad\Longrightarrow\quad \sum_k (3 - k)\,t_k \ge 3.$$

The terms with $k = 2$ are positive, those with $k = 3$ vanish, and those with $k \ge 4$ are negative. Move the negative ones across:

$$t_2 \;\ge\; 3 + \sum_{k \ge 4} (k - 3)\,t_k.$$

That is Melchior’s inequality, and it contains Sylvester’s theorem three times over: there are at least three ordinary lines, and every line carrying four or more points forces extra ordinary lines to pay for it.

Where the count is tight #

The inequality can be checked on any configuration directly, by listing its connecting lines and counting.

Three configurations meet the bound exactly, and each for its own reason. Three points in general position have three ordinary lines and nothing else: the arrangement dual to them is three lines, which cut the projective plane into four triangles and nothing else. The near-pencil — five points on a line and one off it — has one rich line holding five, which the inequality charges two ordinary lines for, and the five lines from the odd point are exactly $3 + 2 = 5$. And the Kelly–Moser configuration has three ordinary lines and six lines of three, which the inequality does not charge for at all.

Equality in the derivation needs every face of the dual arrangement to be a triangle. That is a strong condition on an arrangement, and it explains why so few configurations are tight: most arrangements have some four-sided or larger faces, and each one leaves slack. The rows of random points in the table exceed the bound by eight or more, which is typical — a scattered configuration has many ordinary lines, and Melchior’s inequality is a statement about the rare configurations that try hard to avoid them.

Every small configuration, checked #

The derivation is a proof and needs no checking, but a finite census makes it concrete and shows where the extreme configurations lie.

The census confirms the inequality on every one of the 36,686 configurations and shows the shape of the slack. The bulk of configurations sit well above the bound; the ones that meet it exactly are few and structured — near-pencils, triangles, and configurations built from the triangle-with-medians pattern that Kelly and Moser found. A grid is a hospitable place for collinearity, with many lines of three and four points, and even so the bound is almost never tight.

The three tight configurations in the table illustrate a point about what the inequality measures. It does not bound the ordinary lines below by a function of the number of points; three points and the Kelly–Moser seven both have three ordinary lines. What it bounds is the excess of ordinary lines over rich ones, and a configuration can only have few ordinary lines if it has no lines of four or more — which is exactly why the configurations with the fewest ordinary lines, as the next step shows, are built entirely from lines of two and three points, plus one very rich line placed where it costs nothing.

Arrangements in which every region is a triangle #

The equality case of the count deserves its own look, because it leads somewhere unexpected. Melchior’s inequality is tight exactly when every face of the dual arrangement is a triangle, and arrangements with that property are called simplicial. Classifying them is an old problem and a hard one.

Three infinite families are known. One is the near-pencil and its dual: many lines through one point, crossed by one more line. The other two come from symmetry. Take a regular polygon with $m$ sides and draw its $m$ lines of mirror symmetry; they all pass through the centre and cut the plane into $2m$ triangular wedges — in the projective plane, $m$ triangles doubled up. Add the $m$ lines that extend the polygon’s sides, and the arrangement is still simplicial; for suitable $m$, adding the line at infinity as well keeps it so. The mirror lines alone are the arrangement a kaleidoscope draws, and their triangles are the regions the polygon’s symmetry group permutes, every one a copy of every other.

Beyond the three families, Branko Grünbaum’s catalogue lists about ninety sporadic simplicial arrangements, found over half a century, many of them from the reflection symmetries of the regular solids projected onto a plane. Whether the list is complete is not known. Nobody has a proof that the sporadic examples stop, and new ones have occasionally been found after the catalogue was thought finished.

The connection to ordinary lines is direct. The dual of a simplicial arrangement is a configuration of points meeting Melchior’s bound with equality — as few ordinary lines as its rich lines allow — and the polygon-based families dualise to configurations built from a regular polygon and points at infinity. Those are exactly the configurations that, for large numbers of points, minimise the number of ordinary lines outright. The kaleidoscope and the extremal configuration are the same object seen from the two sides of the duality.

Why the argument needs the real plane #

The derivation used the real projective plane at one point that is easy to miss: faces. A line in the real plane separates it — cutting along a line leaves regions with boundaries — and the arrangement divides the plane into polygons that can be counted. That is a topological fact about real lines, which are one-dimensional.

Over the complex numbers a line is a real surface of dimension two, the projective plane is four-dimensional, and a line no longer cuts anything into faces. The argument does not merely fail to go through; its conclusion fails. The Hesse configuration — nine points of inflection of a complex cubic curve, lying three at a time on twelve lines — has no ordinary line at all, so over the complex numbers the minimum is zero and there is nothing for Euler’s formula to produce. Kelly’s minimisation fails over the complex numbers for a parallel reason, since distance and “closest” need the order of the real line.

This is a sharper statement than “the proof uses the real numbers”. Both known elementary proofs of Sylvester’s theorem use a property of the real plane that the complex plane lacks — an order in one case, separation in the other — and the Hesse configuration shows that some such property is unavoidable. Over a finite field it fails even more dramatically: in the Fano plane every connecting line of the seven points holds three of them, and there are no ordinary lines at all.

What survives over the complex numbers #

Losing the conclusion over the complex numbers does not mean losing everything, and what survives is instructive. In 1983 Friedrich Hirzebruch proved an inequality for arrangements of complex lines that plays the part Melchior’s plays for real ones. For an arrangement of $n$ complex lines in which no point lies on all, or all but one or two, of the lines,

$$t_2 + \tfrac34\,t_3 \;\ge\; n + \sum_{k \ge 5} (k - 4)\,t_k.$$

The difference from Melchior’s inequality is the $t_3$ term on the left. Over the complex numbers ordinary lines can vanish entirely, but only if lines of three take their place: a complex configuration with no ordinary line must have at least $\tfrac43 n$ lines through exactly three points. The Hesse configuration is exactly such a case — nine points and twelve lines of three — and it meets Hirzebruch’s inequality with equality: $\tfrac34 \times 12 = 9$, the number of points.

Hirzebruch’s proof is nothing like Melchior’s. It builds a complex surface branched over the arrangement and applies an inequality between the surface’s topological invariants, a piece of algebraic geometry far from counting faces. That two such different arguments give such similar-looking inequalities — each pricing rich lines against poor ones, each with a constant that the geometry fixes — suggests that the real statement and the complex one are shadows of one fact about how lines can crowd together, and that is how the subject now regards them.

A count stronger than a minimum #

Melchior’s proof and Kelly’s reach overlapping conclusions by opposite routes, and each has an advantage the other lacks.

Kelly’s minimisation is local and geometric: it finds a specific ordinary line, the one nearest to some point, and it generalises to arguments about near-collinear configurations where distances matter. Melchior’s count is global and combinatorial: it never locates an ordinary line, but it proves there are at least three and prices every rich line in ordinary ones. The count is what later work built on. Kelly and Moser in 1958 sharpened the same kind of argument to a lower bound of $3n/7$, which is exact for the seven-point configuration above; Csima and Sawyer in 1993 improved it to $6n/13$ for every $n$ except seven; and the counting tradition culminated in Green and Tao’s 2013 proof that, for large $n$, the true minimum is $n/2$.

The dual arrangement also connects this subject to a large one. Arrangements of lines, and of hyperplanes in higher dimensions, are studied for their own sake, and the numbers $t_k$ — how many crossings of each multiplicity — are their basic invariants. A lemma about crossings of arrangements is often a theorem about collinear points in disguise, and the passage between them is the duality of the first section.

What the pictures cannot show #

The line at infinity. The dual figures turn each configuration so that no two dual lines are parallel, which keeps every crossing in the finite part of the plane. The count itself lives on the projective plane, where some faces wrap through infinity and join up on the other side, and a finite drawing shows those faces cut in two. The Euler count is correct for the projective plane and would be wrong if applied to the faces visible in the drawing.

That every face has three sides. The inequality’s key step is that no face of an arrangement is bounded by fewer than three edges. The figures show arrangements whose faces are visibly polygons, but a two-sided face would need two lines to meet twice, and it is that fact about lines, not any picture, that rules it out.

The configurations beyond the grid. The census covers subsets of a four-by-four grid, where coordinates are small integers and many lines hold several points. Configurations with irrational coordinates — the regular polygons of the next essay — are not in it, and the tight cases there are of a kind the grid cannot produce.

Still open: which configurations are extremal #

Melchior’s inequality is sharp in the sense that equality occurs, but the configurations where it is sharp are not classified in general, and neither are the configurations that come closest to the true minimum of ordinary lines. Green and Tao’s theorem determines the minimum only for $n$ larger than some very large constant, and describes the extremal configurations as close relatives of those built from a regular polygon and its points at infinity. For small $n$ the minima are known by computer search up to a few dozen points, and several small cases are exceptions to every pattern — seven points with three ordinary lines, thirteen with six.

The configurations that achieve $n/2$, and why a regular polygon with its directions added is exactly the thing to look for, are the next part of this subject: a construction by Károly Böröczky that sat in the literature for decades as the conjectured extreme before Green and Tao proved it was.

One formula, three lines #

Melchior’s argument converts a statement about collinear points into a statement about an arrangement of lines and then counts that arrangement’s pieces. Euler’s formula for the projective plane, with its characteristic of one, and the fact that no region can have fewer than three sides, together force at least three simple crossings — at least three ordinary lines — and force more for every line that is unusually rich.

It is a counting proof of a statement that Kelly proved by extremes, and it gives more than his does. The two proofs share one feature, which is also a limitation: each uses a property the real plane has and other planes lack, and the configurations over other fields with no ordinary lines at all show that some such property was always going to be needed.