How often points can sit on lines

Points and lines are the most elementary objects in plane geometry, and a surprising number of the essays near this one have to appeal to an estimate about them without stopping to look at it. The busiest point in a set rests on it, at least as many lines as points needs its strength for Beck’s theorem, and the count of pairs one apart uses the same method. This essay looks at it directly.

Fix $n$ points and $m$ lines. Call a point lying on a line an incidence. What is the largest possible number of incidences $I$?

The theorem, due to Endre Szemerédi and William Trotter in 1983, says that

$$I \le C\left((nm)^{2/3} + n + m\right)$$

for an absolute constant $C$. For $n = m$, that is about $n^{4/3}$. And the grid shows that this is the correct order. Its original proof was a heavy cell decomposition. In 1997 László Székely found a proof that is hardly more than a remark, using a theorem about the crossings a graph cannot avoid which has nothing visibly to do with incidences.

Why a grid is good #

Before any bound, here is a very good example, in a form due to György Elekes. Take the points $(x, y)$ with $x$ in $\{0, \dots, k-1\}$ and $y$ in $\{0, \dots, 3k^2 - 1\}$: a thin tall block. Take the lines $y = ax + b$ with slope $a$ in $\{0, \dots, 2k-1\}$ and intercept $b$ in $\{0, \dots, k^2-1\}$. On any such line, each whole number $x$ from $0$ to $k - 1$ gives a whole number $y$ that lies inside the block, so every line passes through exactly $k$ points.

That gives $n = 3k^3$ points and $m = 2k^3$ lines, with $I = 2k^4$ incidences. Since $k$ is about $n^{1/3}$, that is of order $n^{4/3}$. The check at $k = 5$ with brute force finds all 250 lines with $5$ incidences each, and the case drawn in the figure with $k = 4$ has 512 incidences against $(nm)^{2/3} = 845$. There are no tricks here: the idea is that many lines with small rational slopes pass through many points of a lattice.

The ordinary square grid does almost as well, and the lines through it are worth counting exactly. A line through a square grid of size $N$ passes through many points when its slope is a simple fraction, and how many lines have at least $r$ points is an exact count.

For the $18 \times 18$ grid, with $n = 324$, there are 23,926 lines through at least two points, 4,398 through at least three, 718 through at least five, 70 through at least ten and 38 through all eighteen. The last are the rows, the columns and the diagonals in the two directions. The theorem has an equivalent form about such rich lines: for $r$ up to about $\sqrt n$, there are at most about $n^2/r^3$ lines with at least $r$ points. The measured counts divided by that expression lie between 0.63 and 1.13 for $r$ from 3 to 9. So the grid is at the limit of the theorem at every level of richness simultaneously, up to a constant, and this is a stronger claim than a statement about one value of $m$.

From incidences to rich lines #

The two forms of the theorem are one calculation apart, and the rich-line form is usually the one that gets used. Suppose $L_r$ lines each contain at least $r$ of the $n$ points. Those lines alone have at least $rL_r$ incidences, so applying the theorem to them gives

$$r L_r \le C\left((n L_r)^{2/3} + n + L_r\right).$$

For $r$ larger than the constant, the last term can be absorbed on the left. Then either the first term dominates, and $L_r \lesssim n^2/r^3$, or the second does, and $L_r \lesssim n/r$. The second case is the trivial one, of lines with very many points each, of which there can only be a few. The first case is the content. It says that the number of lines with at least $r$ points falls as the cube of $r$, whereas pair-counting says it falls only as the square. Pair-counting gives $L_r \lesssim n^2/r^2$, because each such line accounts for about $r^2$ of the $n^2$ pairs of points, and that is exact in a finite plane. So the real plane makes a rich line rarer than the arithmetic of pairs requires. A line can be rich, but the rich lines cannot then overlap as heavily as the pairs would permit.

What counting pairs gives #

The classical bound uses only the fact that two points determine a line. Count triples: a line and two different points on it. Each pair of points has at most one such line, so the sum over lines of $\binom{r_\ell}{2}$ is at most $\binom{n}{2}$. By the Cauchy–Schwarz inequality, $I$ is at most about $m^{1/2} n + m$. Swapping the roles of points and lines gives the dual bound $n^{1/2} m + n$.

At $n = m$ these bounds give $n^{3/2}$, whereas the truth is $n^{4/3}$. For a million points and a million lines, that is a billion against a hundred million. The difference is a factor of the sixth root of the number of lines.

The reason it is worth writing down the pair-counting bound is what it does elsewhere. It uses exactly one fact about geometry, that two points lie on one line. So it applies in any setting where that fact holds, and it is exact in one of them.

The plane over a finite field #

In the plane built from a finite field, with $q^2 + q + 1$ points and the same number of lines, every line has $q + 1$ points. That gives $I = (q^2 + q + 1)(q + 1)$, about $n^{3/2}$, which matches the pair-counting bound up to a constant. So that bound is sharp as a statement about geometries.

So Szemerédi–Trotter is false over finite fields. The ratio of the actual incidences to its expression rises with $q$, from 0.92 at $q = 3$ to 2.6 at $q = 29$, and it keeps rising without limit, like $q^{1/3}$. This is the point noted in the busiest point in a set: the theorem encodes something about the real numbers, because a real line has a betweenness that a finite line lacks, and the shortest proof uses that order very explicitly.

The order is not the only possible reason, though, and it is worth being careful here. Csaba Tóth proved that the same bound holds over the complex numbers, where a line is a two-dimensional plane with no order along it at all. The proof is far longer. What fails in a finite field is something else as well: a finite field has subfields and a positive characteristic, so a finite plane sits inside it as a perfectly structured set with far too many incidences. In the complex numbers there is no finite subfield to hide in. So order is what makes the proof short, while the absence of finite subfields is what makes the statement true. Over prime fields, which have no proper subfields, there are versions with weaker exponents for small sets, and how good those exponents can be is an active question.

The proof #

Draw a graph, with the $n$ points as its nodes. On each line, join consecutive incident points by an edge. This is the only place where order enters: a real line lets its points be taken in a definite sequence, each point having at most two neighbours on that line.

A line with $r$ points contributes $r - 1$ edges. So the graph has $E = I - m$ edges, ignoring lines with no points. It is drawn in the plane, and its edges can cross only where two of the lines cross, so it has at most $\binom{m}{2} < m^2$ crossings.

Now use the crossing lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton: a graph with $n$ nodes and $E \ge 4n$ edges has at least $E^3/(64n^2)$ crossings in any drawing. If $E$ is less than $4n$, then $I < 4n + m$, and that is the linear term in the theorem. Otherwise,

$$\frac{(I - m)^3}{64 n^2} \le m^2,$$

so $I \le 4(nm)^{2/3} + m$. This is the whole proof.

It is hard to overstate how striking that was when Székely found it. Szemerédi and Trotter’s original proof had a very large constant and elaborate geometry. The crossing lemma itself is proved by applying Euler’s formula to a random sample of the nodes, and the essay on crossings gives that proof. So the chain is: Euler’s formula gives few edges for a planar graph; by sampling, many edges force many crossings; and lines cross at most once, so many incidences would be impossible. A statement about incidences follows from one about planar graphs without any new geometric ideas. And by using the number of crossings on a thrackle as the opposite extreme, one can see exactly what is being used: two lines cross once, no more, and that uniform bound is what the graph inherits.

The argument also generalises at once. For curves in place of lines, if any two curves cross at most $s$ times and any two points lie on at most a bounded number of curves, the same reasoning gives similar bounds with exponents depending on $s$. That is how the best known bound on the number of pairs at unit distance is obtained, by treating unit circles as curves. Curves were much harder before this simple approach existed, and that one proof made a whole family of results short.

Beck’s dichotomy #

Another consequence explains why the theorem turned up in the count of connecting lines. József Beck proved in 1983, at the same moment and by a related method, that a set of $n$ points must either have a large fraction of its points on a single line, or determine a large multiple of $n^2$ connecting lines. There is nothing in between, no set with a moderate maximum on a line and a moderate number of lines.

The derivation is a short calculation in the rich-line form. Sort the $\binom{n}{2}$ pairs of points by how rich the line through them is. A line with about $2^i$ points accounts for about $4^i$ pairs, and there are at most about $n^2/8^i$ such lines when $2^i$ is small against $\sqrt n$, for a total of about $n^2/2^i$ pairs at that scale. Summing over large $i$, the pairs on rich lines add up to a small fraction of all pairs, and the rest must lie on lines with a bounded number of points. Each such line accounts for a bounded number of pairs, so there are a constant times $n^2$ of them, unless the very richest lines, of more than about $\sqrt n$ points, take the rest. Those are few, and a further step shows that one of them must hold a large share of the set. So the same cube in the rich-line count is what forces the dichotomy, and it is a stronger structural statement than either of the two options alone.

A sum and a product #

Here is the corollary that shows how far the method reaches. Paul Erdős and Szemerédi conjectured that a set of numbers cannot have both few sums and few products. If a set $A$ of $n$ numbers is an arithmetic progression, its sumset $A + A$ is small, with about $2n$ values, and its product set $AA$ is large. If it is a geometric progression, the reverse. They conjectured that $\max(|A + A|, |AA|)$ is at least nearly $n^2$. It is an arithmetic question with no mention of geometry.

Elekes’s proof of 1997 is a single application of the theorem. Take the point set $(A + A) \times (AA)$, and take the $n^2$ lines $y = a(x - b)$ for $a, b$ in $A$. Each line contains, for each $c$ in $A$, the point with $x = b + c$ and $y = ac$, both coordinates in the set. So each of the $n^2$ lines contains at least $n$ of the points. The number of incidences is at least $n^3$, and the theorem says

$$n^3 \le C\left(|A + A|\,|AA|\, n^2\right)^{2/3} + \ldots,$$

which gives $|A + A|\,|AA| \ge c\,n^{5/2}$, and therefore one of them is at least about $n^{5/4}$. That is a far-reaching result from a four-line geometry theorem, used as a black box. The best exponents have moved a little further, to about $4/3$ plus a small fraction, using more refined ideas, and they are nowhere near the conjectured 2. The analogue for sums in a finite field, relevant to two sets added modulo a prime, required entirely new ideas by Jean Bourgain, Nets Katz and Terence Tao, since the incidence theorem is unavailable there, and it has become a central tool in additive combinatorics.

Exact numbers at small sizes #

For a square grid of $n$ points, take the $n$ richest lines. For the $12 \times 12$ grid that means 144 lines and a total of 1,024 incidences. The ratio to $n^{4/3}$ in the table is 1.389 at $3 \times 3$, 1.409 at $5 \times 5$, 1.375 at $8 \times 8$ and 1.357 at $12 \times 12$. It looks to be approaching a constant. The best upper bound of this form, due to Pach, Radoš Radoičić, Gábor Tardos and Géza Tóth, has constant about 2.5, and the grid gives a value slightly over half of that. Which of the two is closer to the truth at large $n$ is not known. There may be better arrangements than a square grid for large $n$, and for small $n$ the true extremal arrangements are known to be more irregular, at least for very small sizes, where they are often non-lattice sets.

The numbers also make clear how soon the theorem’s asymptotic form is visible. At $n = 9$, the very small grid already sits on the same ratio to within two per cent. Most bounds of this type start to mean something only for very large sizes, and this one is good at every scale. That helps explain why the structural side of the question has been useful in practice for algorithms in computational geometry, where the number of incidences determines the speed of searching among lines and points.

Counted exactly, and bounded by quotation #

The counts for the grid are exact: all lines through two or more points were enumerated and each was counted. The figures do not, however, compare the grid against any cleverer point sets, so the statement that no arrangement does much better rests on the theorem, whose proof is above, with the crossing lemma cited from its essay. The values for finite fields are exact counts of a simple formula, with the exact number of slanted lines checked by brute force at $q = 3$, 5 and 7.

The constant in the proof’s bound comes from the crossing lemma’s constant of 64, and various improvements to 2.5 are quoted. The conjectured form of the sum-product question and the exponents about it are cited, and Elekes’s argument was given in sketch form with its omitted lower-order terms. The arrangement of seven lines is an illustration and does not test anything.

Still open: the constant and the extremal shape #

What is the best constant $C$ in the bound, and what do the extremal arrangements look like? The upper constant is about 2.5, and the square grids computed here hold at about 1.37, so there is a gap of nearly a factor of two. And all known extremal examples are lattice-like. The inverse question asks whether every near-extremal arrangement must have a large lattice-like piece. Elekes conjectured a structural result of this kind, and it has been difficult. Attempts have shown that near-extremal arrangements must have many lines with many points in common, and that they cannot be too random, but a full description is unavailable, which is not unlike the structural results of Green and Tao for ordinary lines that the fewest ordinary lines a polygon allows discussed.

How close can $\max(|A + A|, |AA|)$ come to $n^2$? Beyond a small improvement over $4/3$, progress has been slow, and any approach based only on Szemerédi–Trotter is known to stall well short of the conjecture. A proof of the sum-product conjecture would require finding some additional way in which addition and multiplication differ.

Order along a line #

In the real plane $n$ points and $m$ lines have about $(nm)^{2/3}$ incidences at most, against about $n\sqrt m$ for pair-counting, and the difference comes from the order along a real line. Draw the incidences as a graph whose edges run between neighbouring points of a line, and then many incidences mean many edges, many edges mean many crossings, and the lines cross each other only once. A grid with small-slope lines reaches this order, and a finite-field plane breaks it, because its lines have no order at all.

The surprising conclusion is about arithmetic. A theorem on points and lines implies that a set of numbers cannot be structured for addition and multiplication at the same time. The two operations are distinct, and it takes a geometric statement about ordered lines to say how distinct they are.