The fewest ordinary lines a polygon allows

Melchior’s count guarantees three ordinary lines, and Kelly and Moser improved that to $3n/7$ for $n$ points. Both are lower bounds, statements that no configuration has fewer. The other half of the question is constructions — configurations with as few ordinary lines as possible — and the gap between the best construction and the best bound is where the subject lived for sixty years.

The best constructions are due to Károly Böröczky, and they are built from the most symmetric object available: a regular polygon, together with the points where its parallel chords meet at infinity. They have exactly $n/2$ ordinary lines. In 1951 Gabriel Dirac conjectured that this is the truth for every large $n$, and in 2013 Ben Green and Terence Tao proved him right.

Chords that point in only m directions #

The construction rests on a small fact about regular polygons. A regular $m$-gon has $\binom{m}{2}$ chords, but they point in only $m$ different directions.

Number the corners $0, 1, \dots, m - 1$ round the circle. The chord from corner $i$ to corner $j$ is perpendicular to the direction halfway between them, so its direction depends only on $i + j$ — and only on $i + j$ taken modulo $m$, since going once round the circle turns a direction by a full half-turn and back. There are $m$ possible remainders, so there are exactly $m$ directions, and the chords fall into $m$ families of parallel lines. The figure’s check counts the directions rather than assuming them.

In the projective plane every family of parallel lines meets at a single point at infinity. So the $m$ families supply $m$ points at infinity, one for each remainder, and adding them to the $m$ corners gives $n = 2m$ points. That is Böröczky’s configuration.

Now every chord passes through three of these points: its two corners and the point at infinity of its direction. The line at infinity passes through all $m$ new points. Neither kind of line is ordinary. What is left are the lines joining a corner to a point at infinity other than along one of its chords — and there is exactly one such line per corner.

The ordinary lines are the tangents #

Take corner $i$ and a point at infinity with remainder $s$. The line through them is a chord from $i$ to the corner $j$ with $i + j \equiv s$ — which exists unless $j$ would have to be $i$ itself, that is, unless $s \equiv 2i$. In that one case the line through corner $i$ in direction $2i$ meets no other corner. It is the direction perpendicular to the radius at $i$, so the line is the tangent to the circle at corner $i$, and it holds exactly two points of the configuration: the corner and one point at infinity.

So every configuration of this kind has exactly $m$ ordinary lines, one tangent per corner, and $m = n/2$. The solid lines in every figure here are tangents, and nothing else in these configurations is ordinary.

The pentagon shows the count does not depend on $m$ being even. The chord directions are again five, the tangent at each corner is again the only line from that corner that misses every other corner, and the configuration again has half as many ordinary lines as points. For odd and even polygons alike, the tangent at a corner is parallel to the chord joining that corner’s two neighbours, which is why its point at infinity is already in the configuration and why the tangent picks up no third point.

The octagon makes the proportions visible. Most of the thirty-seven lines are chords carrying three points, drawn faintly; the solid star of tangents is a small minority. As $m$ grows the chords number about $m^2/2$ and the ordinary lines stay at $m$, so the configuration is overwhelmingly made of three-point lines — which is exactly what Melchior’s inequality permits for free, since lines of three are the ones it does not charge for. The single very rich line, the line at infinity, is the one expensive item: it holds $m$ points, so Melchior’s inequality demands $3 + (m - 3) = m$ ordinary lines, and the $m$ tangents pay exactly that. Böröczky’s configurations meet Melchior’s bound with equality, which is the dual of the fact that the kaleidoscope arrangements are simplicial.

Odd numbers of points #

The construction gives $n/2$ ordinary lines for every even $n$. For odd $n$ there is a variant, and it does less well.

Add the centre of the polygon, and the diameters — chords through opposite corners — now hold four points each. The tangents are unaffected. But some of the points at infinity lie in directions no diameter takes, and the line from the centre to each of those is new and ordinary. When $m$ is even, half of the $m$ directions are missed by every diameter, so the count rises from $m$ to $3m/2$. With $n = 2m + 1$ points that is $3(n - 1)/4$ ordinary lines, which for these $n$ is $3\lfloor n/4 \rfloor$.

So odd numbers of points seem to force more ordinary lines than even numbers do, and the truth — proved along with the even case — is that they do: for large odd $n$ the minimum is $3\lfloor n/4 \rfloor$, three quarters where the even case has one half. Parity matters here for a reason that is easy to state and hard to prove: the extremal configurations are all built from a regular polygon, and a centre, which an odd count almost forces, spoils the polygon’s economy.

How rigid the construction is #

The configuration is not merely good; it is fragile in a way that shows why it is good. Move a single corner of the hexagon slightly, off the circle. Every chord through that corner loses its point at infinity — its direction no longer matches the others in its family — and each of those lines becomes ordinary, while the lines through the moved corner and each point at infinity become ordinary too. One small displacement turns a configuration with six ordinary lines into one with well over a dozen.

The economy depends on a great many coincidences holding at once: every chord parallel to $m/2$ or so others, every family meeting at a single point that is also on a common line. A configuration with few ordinary lines has to be mostly made of three-point lines, and three-point lines are coincidences — three points in a line is a condition, not an accident. The regular polygon supplies about $m^2/2$ of them from the single fact that chord directions depend on $i + j$ modulo $m$.

That is also why random configurations have many ordinary lines. Points in general position have no three in a line at all, so every one of the $\binom{n}{2}$ connecting lines is ordinary — a number growing like $n^2$, where the extremal configurations have $n/2$. The distance between the typical and the extremal is the whole range from $n^2/2$ down to $n/2$, and the extremal end is reached only by structure as rigid as a regular polygon’s.

The bounds against the constructions #

For sixty years the constructions sat above the bounds, and the question was which would move.

Two bounds are drawn. Kelly and Moser’s $3n/7$, from 1958, is exact at seven points, where their configuration of a triangle, its midpoints and its centroid has three ordinary lines. Csima and Sawyer’s $6n/13$, from 1993, holds for every $n$ except seven, and is exact at thirteen points, where a configuration found by Crowe and McKee has six. Both are good bounds and both lie below the line $n/2$. For small $n$ the gap is hidden by rounding: a count of lines is a whole number, and Csima and Sawyer’s bound rounded up already equals $n/2$ for every even $n$ up to twenty-four. From twenty-six points on it no longer does — it says at least twelve where the construction has thirteen — and the gap between $6n/13$ and $n/2$ widens without limit.

Dirac and Motzkin conjectured that the constructions were right — that apart from the two exceptions, every configuration of $n$ points has at least $\lfloor n/2 \rfloor$ ordinary lines. The small exceptions are part of the reason the question stayed open. Seven and thirteen show that small configurations can do better than the pattern, so any proof had to explain why the exceptions stop, and no counting argument of Melchior’s kind could see the difference between thirteen points and fifteen.

How Green and Tao closed it #

Green and Tao’s 2013 proof is long and its strategy can be stated in a paragraph. They showed that a configuration with few ordinary lines — fewer than a constant times $n$ — must be close to a configuration lying on a cubic curve: most of its points sit on a curve of degree three, which may be an irreducible cubic, or a conic together with a line, or three lines. Then they classified what happens on each kind of cubic.

The cubic is the natural object for a reason that recurs wherever cubic curves appear. Three points on a cubic curve are collinear exactly when they add to zero in the curve’s own group law, so collinearity on a cubic is arithmetic, and a configuration that wants many three-point lines wants to be a subgroup of that group. The same group law is what makes it possible to count the points of a cubic over a finite field and to find the rational points on one; here it does a third job, turning a question about which points line up into a question about which points add up. A subgroup of order $n$ on a cubic has about $n^2/6$ three-point lines — every pair of its points determines a third that is also in it — and very few lines that miss the subgroup’s structure, which is exactly the profile a configuration with few ordinary lines needs. Böröczky’s configuration is the case where the cubic is a conic — the polygon’s circle — together with a line, the line at infinity: the corners lie on the circle, the new points lie on the line, and the three-point lines are the chords, each joining two corners on the conic to one point on the line.

The classification then shows that the best one can do on each kind of cubic is $n/2$ for even $n$ and $3\lfloor n/4 \rfloor$ for odd, achieved only by Böröczky’s configurations and close relatives. The proof needs $n$ to exceed some large constant, because its first step — few ordinary lines forces near-cubic structure — is quantitative with poor constants. For every $n$ above that constant the Dirac–Motzkin conjecture is a theorem. Below it, the question is settled for small $n$ by computer search and remains open for the ones in between.

The same paper solved the orchard problem — the maximum number of three-point lines — for large $n$, by the same cubic curves run the other way. The configurations that avoid ordinary lines and the configurations that pack in three-point lines are the same configurations, which is why the two problems fell together.

The regular polygon’s other lives #

The regular polygon is carrying a great deal in this construction, and it is worth noticing where else it does.

Its $m$ chord directions are the $m$ reflection axes of the polygon turned through a right angle, and the configuration is the dual of the kaleidoscope arrangement of those axes and the polygon’s side lines — the simplicial arrangements that meet Melchior’s bound exactly. The fact that chords have only $m$ directions is the same fact that gives the polygon’s symmetry group $2m$ elements: every chord direction is fixed by one reflection. And which regular polygons exist as constructions — drawable with straightedge and compass — is a different question with a number-theoretic answer, Gauss’s list of constructible polygons; for ordinary lines any polygon will do, because the configuration only needs the polygon to exist, not to be drawable.

The circle matters too. The tangents are ordinary because a tangent meets the circle once, and every corner lies on the circle. Replace the circle by an ellipse — an affine image of it — and nothing changes, because incidences are preserved by affine maps; replace it by any conic, by a projective map, and nothing changes either. It is the conic, not the regularity as such, that makes chords come in parallel families, and that is precisely the “conic plus a line” in Green and Tao’s classification.

What the pictures cannot show #

Collinearity at infinity. Points at infinity are drawn as pairs of marks on the rim, and a line through one of them is drawn as a line in that direction. The figures are a faithful model of the projective plane only if the reader identifies opposite marks, and the line at infinity — the rim — is not a circle in any sense that matters: it is a line, closed up through infinity.

Exactness. The corners of a regular polygon have irrational coordinates, so collinearity was decided in floating-point arithmetic. The figures check that every triple is either collinear to within $10^{-9}$ or clearly not — at least $10^{-3}$ away — so no decision rests on rounding; but that is a margin, not an exact proof, and the exact statement is the argument about remainders modulo $m$ above.

Which of the many equivalent pictures is drawn. Any projective transformation carries a configuration to one with exactly the same incidences, so each figure here stands for an infinite family: the same points with the line at infinity moved into view as an ordinary line, the circle turned into an ellipse or a hyperbola, the corners no longer looking regular at all. The drawings choose the most symmetric member, in which the counting is easiest to follow, and a reader shown a different member of the family would see no polygon — and exactly the same number of ordinary lines.

The theorem for all large $n$. The bounds figure plots configurations up to twenty-one points, where Green and Tao’s theorem says nothing: its constant is far larger. The dots on the line $n/2$ are constructions; the claim that nothing does better is a theorem about sizes no figure reaches.

Still open: the small and middle cases #

The Dirac–Motzkin conjecture is proved for all sufficiently large $n$, and the constant in “sufficiently large” is astronomically beyond the sizes where computer searches can reach. For $n$ between the two, the conjecture is believed and not proved. The exceptional cases seven and thirteen are known; whether any other exception exists below Green and Tao’s threshold is, strictly, unknown, although nobody expects one.

There are also questions on the other side of the bound. The configurations with almost the fewest ordinary lines are classified by Green and Tao only up to a bounded number of changes; how many configurations of $n$ points have exactly $n/2$ ordinary lines, and whether they are all Böröczky’s up to projective transformation, has partial answers. And in three dimensions and higher, where the analogous questions concern planes through three points, the extremal configurations are much less understood — the symmetric objects that play the polygon’s part are not known to exist in general.

Symmetry as the extremal shape #

The configuration with the fewest ordinary lines is not a clever arrangement found by search. It is the corners of a regular polygon and the directions of its chords, and it has exactly $n/2$ ordinary lines for a reason that fits in one sentence: every line through two of its points is a chord carrying a third, except the tangents, and there is one tangent per corner.

That the most symmetric configuration is also the extremal one is the pattern this subject keeps showing — the densest graph without a square was a finite projective plane, and here the fewest ordinary lines come from a polygon and a line at infinity. Green and Tao’s proof explains why rather than merely confirming it: anything with few ordinary lines must be nearly on a cubic curve, and on the cubic that is a conic plus a line, the polygon is where the economy is greatest.