Last week, we Leeds mathematicians were treated to a talk by Professor Green Professor Green with the delightfully elementary title of Points and Lines. It reported on joint work of Ben Green and Terence Tao. Here I’m going to talk about the background to their work. As always, any errors are mine.
The idea is that we will be presented with some points, specifically a finite collection of points in the plane. We want to predict the answer to questions of the form: how many lines are there through exactly (n) many of these points? We want to do this while knowing as little as possible about the details of what we’ll be given. Actually, on a first pass, these questions are pretty trivial:
- There are guaranteed to be infinitely many lines through zero points since when you’re positioning a line, a finite set of points is very easy to miss.
- Similarly, there will be infinitely many lines which hit exactly one point, since once you’ve decided which to hit, you can easily tweak that line to miss the rest.
- Must there be any lines which hit exactly two points? Not necessarily. If all the points lie on a single straight line (and if there are more than two of them), then any line either goes through 0, 1, or all of them.
- Arranging the points around a circle illustrates that there also need not be any lines which hit exactly 3 points. The same argument works for n= 4,5,6…
So far, so straightforward: we can predict the answer exactly for (n=0,1) and not at all otherwise. But let’s think again: in the case of (n=3), there’s obviously nothing special about a circle. There are numerous other curves which would do just as well: a parabola, hyperbola, squircle, catenary, … all of these and many others share the property than any straight line hits them at most twice.
However, for the case (n=2), there is something undeniably special about demanding that all our points lie along a single straight line. So the question arises: is this configuration the only obstacle? Must it be the case that either all the points lie along a line, or we will be able to find a line hitting exactly two of them? This problem was first posed, so far as we know, by J.J. Sylvester in the back pages of the Educational Times in 1893, under the unassuming title of mathematical question 11851. (The Royal Society’s Sylvester Medal is depicted above, of which Ben Green is the most recent winner, for another famous result of his jointly with Tao.)
The question was later re-asked by Paul Erdős and then solved in 1940 by Tibor Gallai, who established that the answer was yes: if a set of points do not all lie on a line, then there must be some line through exactly two of them.
A later proof by Leroy Kelly is, as Ben put it, a `classic of mathematics’ and actually induced an audible gasp from the audience. So let’s see it:
We assume that our points don’t all lie along a single line. That means we can definitely find two of them which lie on a line L, along with some other point X lying off L, as shown. In fact, there are likely to be numerous such configurations; we choose the one where the perpendicular distance from X to L is the least possible.
The claim is then that L contains only those two points. Suppose not. Then there must be two points A & B both lying on L and on the same side of the perpendicular line XL. Now, let M = XA. This line also contains two points (obviously), but the distance from B to M is less than that from X to L, which is a contradiction. QED
Clever, right? Anyway, for reasons unexplained, lines which pass through exactly two of our specified collection of points are known as ordinary lines. The Sylvester-Gallai theorem above therefore says that (so long as our points are not colinear) an ordinary line will always exist. But the next question is: how many must there be? In most cases there will be lots: if you try this for a random scattering of (m) points, then in all likelihood, whenever you draw a line through two points it will miss all the others. Thus there are around (frac{1}{2}m^2) ordinary lines.
But it is not hard to come up with sets with fewer. For instance, take (m-1) points all lying along a line, and add in one extra point (X) off it. Then the only ordinary lines are those which connect (X) to another point, giving (m-1) many.
A cunning construction by Károly Böröczky brings this down even further: a set of (m) points with only (frac{1}{2}m) many ordinary lines.[1]
Now we come to the theorem of Green and Tao. In their paper, they have shown that Böröczky’s examples are as good as it gets. For large enough values of (m), they prove that every non-colinear set of (m) points must have at least (frac{1}{2}m) many ordinary lines.
How large is `large enough’? The bound they establish is in the vicinity (10^{10^{10}}), but the true answer may be as low as 14. For smaller sets, it is possible to do better. The left-hand picture here shows a set of 7 points with only 3 ordinary lines.
And how is it proved? Well, I’m not going to go into details, but the key step is the unexpected (to me) connection of the property `has few ordinary lines’ with the property `can be covered with a single cubic curve’.
[1] For the cognoscenti: it achieves this by moving the action to the real projective plane, arranging (m) points symmetrically around the circle, and placing another (m) on the line at infinity at positions corresponding to the directions determined pairs of points from the first set. Then the only ordinary lines are the (m) many tangents to the circle at points. Finally, since no-one mentioned anything about lines at infinity being permitted, the whole set-up needs to be transported back to the plain old Euclidean plane, which can be achieved via a projective transformation. This however will distort the circle into an ellipse. See page 11 of their paper for a picture. )