On sets defining few ordinary lines

Ben Green and I have just uploaded to the arXiv our new paper “On sets defining few ordinary lines“, submitted to Discrete and Computational Geometry. This paper asymptotically solves two old questions concerning finite configurations of points in the plane . Given a set of points in the plane, define an ordinary line to be a line containing exactly two points of . The classical Sylvester-Gallai theorem, first posed as a problem by Sylvester in 1893, asserts that as long as the points of are not all collinear, defines at least one ordinary line:

It is then natural to pose the question of what is the minimal number of ordinary lines that a set of non-collinear points can generate. In 1940, Melchior gave an elegant proof of the Sylvester-Gallai theorem based on projective duality and Euler’s formula , showing that at least three ordinary lines must be created; in 1951, Motzkin showed that there must be ordinary lines. Previously to this paper, the best lower bound was by Csima and Sawyer, who in 1993 showed that there are at least ordinary lines. In the converse direction, if is even, then by considering equally spaced points on a circle, and points on the line at infinity in equally spaced directions, one can find a configuration of points that define just ordinary lines.

As first observed by Böröczky, variants of this example also give few ordinary lines for odd , though not quite as few as ; more precisely, when one can find a configuration with ordinary lines, and when one can find a configuration with ordinary lines. Our first main result is that these configurations are best possible for sufficiently large :

Theorem 1 (Dirac-Motzkin conjecture) If is sufficiently large, then any set of non-collinear points in the plane will define at least ordinary lines. Furthermore, if is odd, at least ordinary lines must be created.

The Dirac-Motzkin conjecture asserts that the first part of this theorem in fact holds for all , not just for sufficiently large ; in principle, our theorem reduces that conjecture to a finite verification, although our bound for “sufficiently large” is far too poor to actually make this feasible (it is of double exponential type). (There are two known configurations for which one has ordinary lines, one with (discovered by Kelly and Moser), and one with (discovered by Crowe and McKee).)

Our second main result concerns not the ordinary lines, but rather the -rich lines of an -point set – a line that meets exactly three points of that set. A simple double counting argument (counting pairs of distinct points in the set in two different ways) shows that there are at most

-rich lines. On the other hand, on an elliptic curve, three distinct points P,Q,R on that curve are collinear precisely when they sum to zero with respect to the group law on that curve. Thus (as observed first by Sylvester in 1868), any finite subgroup of an elliptic curve (of which one can produce numerous examples, as elliptic curves in have the group structure of either or ) can provide examples of -point sets with a large number of -rich lines (, to be precise). One can also shift such a finite subgroup by a third root of unity and obtain a similar example with only one fewer -rich line. Sylvester then formally posed the question of determining whether this was best possible.

This problem was known as the Orchard planting problem, and was given a more poetic formulation as such by Jackson in 1821 (nearly fifty years prior to Sylvester!):

Our second main result answers this problem affirmatively in the large case:

Theorem 2 (Orchard planting problem) If is sufficiently large, then any set of points in the plane will determine at most -rich lines.

Again, our threshold for “sufficiently large” for this is extremely large (though slightly less large than in the previous theorem), and so a full solution of the problem, while in principle reduced to a finitary computation, remains infeasible at present.

Our results also classify the extremisers (and near extremisers) for both of these problems; basically, the known examples mentioned previously are (up to projective transformation) the only extremisers when is sufficiently large.

Our proof strategy follows the “inverse theorem method” from additive combinatorics. Namely, rather than try to prove direct theorems such as lower bounds on the number of ordinary lines, or upper bounds on the number of -rich lines, we instead try to prove inverse theorems (also known as structure theorems), in which one attempts a structural classification of all configurations with very few ordinary lines (or very many -rich lines). In principle, once one has a sufficiently explicit structural description of these sets, one simply has to compute the precise number of ordinary lines or -rich lines in each configuration in the list provided by that structural description in order to obtain results such as the two theorems above.

Note from double counting that sets with many -rich lines will necessarily have few ordinary lines. Indeed, if we let denote the set of lines that meet exactly points of an -point configuration, so that is the number of -rich lines and is the number of ordinary lines, then we have the double counting identity

which among other things implies that any counterexample to the orchard problem can have at most ordinary lines. In particular, any structural theorem that lets us understand configurations with ordinary lines will, in principle, allow us to obtain results such as the above two theorems.

As it turns out, we do eventually obtain a structure theorem that is strong enough to achieve these aims, but it is difficult to prove this theorem directly. Instead we proceed more iteratively, beginning with a “cheap” structure theorem that is relatively easy to prove but provides only a partial amount of control on the configurations with ordinary lines. One then builds upon that theorem with additional arguments to obtain an “intermediate” structure theorem that gives better control, then a “weak” structure theorem that gives even more control, a “strong” structure theorem that gives yet more control, and then finally a “very strong” structure theorem that gives an almost complete description of the configurations (but only in the asymptotic regime when is very large). It turns out that the “weak” theorem is enough for the orchard planting problem, and the “strong” version is enough for the Dirac-Motzkin conjecture. (So the “very strong” structure theorem ends up being unnecessary for the two applications given, but may be of interest for other applications.) Note that the stronger theorems do not completely supercede the weaker ones, because the quantitative bounds in the theorems get progressively worse as the control gets stronger.

Before we state these structure theorems, note that all the examples mentioned previously of sets with few ordinary lines involved cubic curves: either irreducible examples such as elliptic curves, or reducible examples such as the union of a circle (or more generally, a conic section) and a line. (We also allow singular cubic curves, such as the union of a conic section and a tangent line, or a singular irreducible curve such as .) This turns out to be no coincidence; cubic curves happen to be very good at providing many -rich lines (and thus, few ordinary lines), and conversely it turns out that they are essentially the only way to produce such lines. This can already be evidenced by our cheap structure theorem:

Theorem 3 (Cheap structure theorem) Let be a configuration of points with at most ordinary lines for some . Then can be covered by at most cubic curves.

This theorem is already a non-trivial amount of control on sets with few ordinary lines, but because the result does not specify the nature of these curves, and how they interact with each other, it does not seem to be directly useful for applications. The intermediate structure theorem given below gives a more precise amount of control on these curves (essentially guaranteeing that all but at most one of the curve components are lines):

Theorem 4 (Intermediate structure theorem) Let be a configuration of points with at most ordinary lines for some . Then one of the following is true:

1. lies on the union of an irreducible cubic curve and an additional points.
2. lies on the union of an irreducible conic section and an additional lines, with of the points on in either of the two components.
3. lies on the union of lines and an additional points.

By some additional arguments (including a very nice argument supplied to us by Luke Alexander Betts, an undergraduate at Cambridge, which replaces a much more complicated (and weaker) argument we originally had for this paper), one can cut down the number of lines in the above theorem to just one, giving a more useful structure theorem, at least when is large:

Theorem 5 (Weak structure theorem) Let be a configuration of points with at most ordinary lines for some . Assume that for some sufficiently large absolute constant . Then one of the following is true:

1. lies on the union of an irreducible cubic curve and an additional points.
2. lies on the union of an irreducible conic section, a line, and an additional points, with of the points on in either of the first two components.
3. lies on the union of a single line and an additional points.

As mentioned earlier, this theorem is already strong enough to resolve the orchard planting problem for large . The presence of the double exponential here is extremely annoying, and is the main reason why the final thresholds for “sufficiently large” in our results are excessively large, but our methods seem to be unable to eliminate these exponentials from our bounds (though they can fortunately be confined to a lower bound for , keeping the other bounds in the theorem polynomial in ).

For the Dirac-Motzkin conjecture one needs more precise control on the portion of on the various low-degree curves indicated. This is given by the following result:

Theorem 6 (Strong structure theorem) Let be a configuration of points with at most ordinary lines for some . Assume that for some sufficiently large absolute constant . Then, after adding or deleting points from if necessary (modifying appropriately), and then applying a projective transformation, one of the following is true:

1. is a finite subgroup of an elliptic curve (EDIT: as pointed out in comments, one also needs to allow for finite subgroups of acnodal singular cubic curves), possibly shifted by a third root of unity.
2. is the Borozcky example mentioned previously (the union of equally spaced points on the circle, and points on the line at infinity).
3. lies on a single line.

By applying a final “cleanup” we can replace the in the above theorem with the optimal , which is our “very strong” structure theorem. But the strong structure theorem is already sufficient to establish the Dirac-Motzkin conjecture for large .

There are many tools that go into proving these theorems, some of which are extremely classical (with at least one going back to the ancient Greeks), and others being more recent. I will discuss some (not all) of these tools below the fold, and more specifically:

1. Melchior’s argument, based on projective duality and Euler’s formula, initially used to prove the Sylvester-Gallai theorem;
2. Chasles’ version of the Cayley-Bacharach theorem, which can convert dual triangular grids (produced by Melchior’s argument) into cubic curves that meet many points of the original configuration );
3. Menelaus’s theorem, which is useful for producing ordinary lines when the point configuration lies on a few non-concurrent lines, particularly when combined with a sum-product estimate of Elekes, Nathanson, and Ruzsa;
4. Betts’ argument, that produces ordinary lines when the point configuration lies on a few concurrent lines;
5. A result of Poonen and Rubinstein that any point not on the origin or unit circle can lie on at most seven chords connecting roots of unity; this, together with a variant for elliptic curves, gives the very strong structure theorem, and is also (a strong version of) what is needed to finish off the Dirac-Motzkin and orchard planting problems from the structure theorems given above.

There are also a number of more standard tools from arithmetic combinatorics (e.g. a version of the Balog-Szemeredi-Gowers lemma) which are needed to tie things together at various junctures, but I won’t say more about these methods here as they are (by now) relatively routine.