The busiest point in a set

The line with only two points on it proved the Sylvester–Gallai theorem: a finite set of points in the plane, not all on one line, always has a line through exactly two of them. At least as many lines as points proved the de Bruijn–Erdős theorem, that such a set determines at least as many connecting lines as it has points. Both are statements about the lines. This essay asks a question about the points.

Through each point of the set pass some of the connecting lines — one for each direction in which it sees another point, with points that line up behind each other sharing a line. A point with no other point in line with it lies on $n - 1$ lines, the most possible. A point in the middle of a long row lies on fewer. Gabriel Dirac asked in 1951 how small the busiest point’s count can be made: must some point lie on many connecting lines?

The configuration that sets the target #

Dirac’s guess was a half. The reason is the configuration on the left of the hero figure. Put half the points on one line and half on another, arranged so that the two lines’ crossing point is not one of them and no point of one line is in line with two points of the other except along its own line. A point on the first line sees each point of the second line in a different direction, and sees all the points of its own line in one direction. It lies on $n/2 + 1$ lines, and every point is in the same position. No point is busier than $n/2 + 1$.

So no theorem can say “some point lies on more than about half the lines”, and Dirac conjectured that half is right: that every set of $n$ points not all on a line has a point on at least $n/2$ connecting lines, give or take a constant. Sets in which no point lies on more than $n/2$ lines exist — the search below finds two — so half is the target exactly, and the conjecture is usually stated as $n/2 - c$ for a fixed $c$, a form that tolerates whatever small exceptions the exact value might have.

How busy different sets are #

The question has an easy answer for most sets, and the interest is concentrated in a few.

Points in general position — no three on a line, here points on a parabola — make every point as busy as possible: each lies on $n - 1$ lines, and the share tends to one. Square grids are less extreme. In a $k \times k$ grid many points hide behind each other along rows, columns and diagonals, and the busiest point lies on about 61 per cent of the $n - 1$ lines it could see; the share settles near $0.61$ by the time the grid is five by five. The two-line configuration is the only one of the three that approaches a half. Random sets behave like general position: points with random real coordinates have no three on a line with probability one, and a random set of points on a fine grid has few collinear triples, so its busiest point is on nearly $n - 1$ lines. Quiet sets are rare and have to be built. That is the usual shape of an extremal problem in this subject — the typical configuration is nowhere near the extreme, and the extreme is a delicate arrangement that a random search over coordinates would almost never find — and it is why the search below works on a grid, where coincidences of direction are common enough to exploit.

Why grids settle near $0.61$ is a pleasant aside. From a corner of a large grid, the directions to the other points correspond to lattice points that are visible — not hidden behind a nearer point on the same line — and a lattice point $(a, b)$ is visible from the origin exactly when $a$ and $b$ have no common factor. The share of such points is $6/\pi^2 \approx 0.608$, the chance that two random whole numbers are coprime. The busiest point of a grid is not quite a corner, but its count is governed by the same arithmetic.

The two-line construction is best when the split is even. A point on the smaller line sees every point of the larger line along a different line, so the busiest point lies on one more line than the larger side has points, and the even split minimises the larger side. The figure checks the formula for every split of twenty points. Adding a third line does not help: points on three lines see more distinct directions, because a point on one line sees the points of two other lines, not one.

A square root, in four lines #

Before any deep theorem, an elementary argument already shows that some point is moderately busy, and it is worth seeing because it shows where the difficulty lies. Take any point $p$ of the set, and suppose it lies on $d$ connecting lines. Every other point is on one of them, so by more things than boxes one of these lines, call it $\ell$, carries at least $(n - 1)/d$ points besides $p$. The set is not all on one line, so some point $q$ lies off $\ell$. From $q$, the points of $\ell$ lie in different directions — two of them in the same direction would put $q$ on $\ell$ — so $q$ lies on at least $(n-1)/d$ lines.

Either $p$ is on at least $\sqrt{n - 1}$ lines, or $\ell$ has more than $\sqrt{n-1}$ points and $q$ is on at least that many lines. Some point is on at least $\sqrt{n - 1}$ connecting lines. For fourteen points that is $3.6$ against the two-line configuration’s $8$; for a million points it is a thousand against half a million. The argument is tight for neither, and the reason is visible in it: it uses one point and one line, and a set that keeps every point quiet must keep all of them quiet at once. Getting from $\sqrt n$ to a constant fraction of $n$ requires counting over all points and all lines together, which is what the incidence theorems do.

Counting every point against every line #

The global count starts from an identity. Count the pairs (point, connecting line through it) in two ways. By points, it is the sum of every point’s number of lines. By lines, it is the sum over lines of how many points each holds. So the average number of lines through a point is

$$\frac{1}{n} \sum_{\ell} |\ell|,$$

the total size of all the lines divided by the number of points. A set with many lines, each holding at least two points, has a high average and therefore a busy point; a set with few lines must have long ones, and a long line makes every point off it busy, as in the argument above. Three ordinary lines from a count used a count of the same double-counting kind, Melchior’s inequality, to find ordinary lines; here the count is pointed at the busiest point instead.

Beck’s dichotomy is the quantitative version of “many lines or a long line”, and the difficulty of Dirac’s conjecture is that the extremal configuration sits exactly on the border: the two-line set has two long lines, each with half the points, and about $n^2/4$ short lines between them. It has a constant fraction on one line and a constant times $n^2$ lines at once. A proof of the half has to handle sets that are partly like that and partly not, and the incidence theorems lose constants precisely in that mixed regime.

What has been proved #

The first theorem in the direction of Dirac’s conjecture came thirty years after it, and it came from a different problem. József Beck and, independently, Endre Szemerédi and William Trotter proved in 1983 a dichotomy that at least as many lines as points described: a set of $n$ points either has a constant fraction of them on a single line, or determines a constant times $n^2$ connecting lines. Either way some point is on many lines. In the first case, a point off the big line sees each point of it in a different direction. In the second, $n^2$ lines through $n$ points means some point is on about $n$ of them, since each line passes through at least two points and so the total count of point-line memberships is at least twice the number of lines.

That gives “some point lies on at least $n/C$ lines” for a constant $C$, which in the original argument was very large. The constant was brought down in stages, and in 2017 Zeye Han proved that some point lies on at least $n/3 + 1$ lines — the weak Dirac conjecture, so called because Paul Erdős had proposed it as a weaker target than Dirac’s, asking only for some fixed fraction of $n$. Between the proved third and the conjectured half lies the whole open question.

A search on a small grid #

What does a small set that tries hard to keep every point quiet look like? A local search answers that within limits.

The search starts from random sets of $n$ points on an $8 \times 8$ grid and moves one point at a time to an unused grid point, keeping the move whenever it does not make the busiest point busier, with twelve random starts of 1,500 moves for each size. For every $n$ from 5 to 19 the best set it finds has a point on at least $n/2$ lines; for $n = 6$ and $n = 8$ it finds sets reaching exactly $n/2$, slightly better than the two-line construction’s $n/2 + 1$, and for larger $n$ it does a point or two worse than two lines. Nothing it finds comes near the proved $n/3$.

The evidence is weak in a precise way. An $8 \times 8$ grid holds only so many long lines, and the configurations that come closest to Dirac’s bound for larger $n$ may need coordinates the grid does not offer; a local search can also get stuck. What the search shows is the shape that quiet configurations take.

They put many of their points on a few common lines. That is the mechanism: points on a common line share one connecting line among all of them, so packing points into rows reduces every point’s count, while any point off the rows sees each row point in a new direction. The most economical arrangement is the one that puts nearly all points into rows while making each point see as few rows head-on as possible, and two rows is the extreme.

Where the square root is the truth #

The square-root argument is weak in the real plane, but it is not a weak argument: there are planes in which it is exactly right. In the projective plane over the field with $q$ elements there are $n = q^2 + q + 1$ points, every line holds $q + 1$ of them, and every point lies on $q + 1$ lines, which is about $\sqrt n$. Take all its points as the set. They are not all on one line, and no point lies on more than $q + 1$ connecting lines — the square-root bound, attained. Seven points, seven lines drew the smallest case, the Fano plane with $q = 2$: seven points, each on three lines, against a real-plane conjecture that would ask for three and a half.

So Dirac’s conjecture, like the Sylvester–Gallai theorem itself, is a statement about the real plane that fails over finite fields, and fails badly. Every proof of it must use something the real plane has and finite planes lack — order, or the fact that two real lines meet at most once in a way that respects betweenness — and that is exactly what the Szemerédi–Trotter theorem encodes: its incidence bound is false over finite fields, where the projective plane has far more incidences than the real bound allows. The weakness of the elementary argument and the strength of the incidence theorems are the same fact seen from two sides: the elementary argument would work in any plane, so it can do no better than the finite planes permit.

Inside a single grid #

The grid also shows how unequal the points of one set can be.

The centre of a $7 \times 7$ grid lies on 16 lines, the fewest of any of its points, because every row, column and diagonal through it is long and hides many points behind others. The corners lie on 25. The busiest points, with 30 lines, sit one step in from each corner, where the long lines through the point are fewer and many directions reach exactly one other point. A point’s count is the number of directions in which it sees anything, and the centre of a symmetric set is where the most points line up.

Two conjectures by one Dirac #

Gabriel Dirac’s name is on another threshold of one half. Half the neighbours forces a tour proved his theorem of 1952, a year after this conjecture: a graph in which every vertex is joined to at least half of the others has a tour through every vertex. The two statements are about different objects, a graph’s edges and a point set’s lines, and the half arises differently — in the graph theorem as the point at which two neighbourhoods must overlap, in the point set as the share a point on one of two lines sees. But both are the kind of question Dirac favoured: a local count, made at one vertex or one point, that would force a global structure if it is large enough, with the extremal example built from two halves.

The difference in their fates is instructive. The graph theorem has a half-page proof. The point-set conjecture has resisted seventy years, and the reason lies in the geometry: a graph can be built with any pattern of edges, so its extremal examples are easy to understand, while a point set’s lines are constrained by the plane, and the theorems that control them — Szemerédi–Trotter above all — are deep.

Counted exactly, searched locally #

Every count in the figures is exact: a point’s lines are counted as the distinct reduced directions to the other points, computed in whole numbers. The families are checked at every size drawn, and the two-line formula is checked for every split of twenty points. The search is the soft part. It finds configurations; it cannot show that better ones do not exist, either on its grid or off it.

Nor do the figures show the proofs. The step from Beck’s dichotomy to “a constant fraction of $n$” is short, but the dichotomy itself rests on the Szemerédi–Trotter bound on incidences between points and lines, and Han’s improvement to a third uses a careful count of how points distribute among lines of different sizes. Neither is a picture.

Still open: from a third to a half #

The strong Dirac conjecture — some point on at least $n/2 - c$ lines, for a fixed $c$ — is open. The gap between $n/3$ and $n/2$ is not a gap of small cases: for every large $n$ the truth is somewhere in it, and neither the constructions nor the proofs have moved into the middle. The structure theory of Ben Green and Terence Tao, which settled the count of ordinary lines for large $n$ in the fewest ordinary lines a polygon allows, applies to sets with few ordinary lines, and a set in which every point is on few lines need not be such a set, so it does not obviously help.

The two-line configuration also invites a structural guess, stated by several authors in varying forms: that every set in which every point lies on fewer than about $n/2 + c$ lines has most of its points on two lines. If true, it would explain why the search’s best configurations look the way they do, and it would imply the conjecture. Nothing like it is proved, and rows of three, planted on a cubic is a reminder of how much structure can hide in configurations that look unstructured: the orchard problem’s best sets turned out to live on cubic curves, which nobody would have guessed from the first examples.