On sets defining few ordinary hyperplanes

On sets defining few ordinary hyperplanes, Discrete Analysis 2020:4, 34 pp.

The well-known Sylvester-Gallai theorem asserts that if $X$ is a finite set of points in the plane, then either $X$ is contained in a line or there is some ordinary line: that is, a line that contains exactly two points of $X$. A particularly short proof starts by considering the minimum possible distance between a line $L$ that goes through at least two points of $X$ and a point $x$ of $X$ that does not go through that line. If $L$ contains at least three points, then at least two of them, $a,b$, say, are on the same side of the nearest point to $x$. If $a$ is the further of the points from $x$, then the distance from $b$ to the line joining $x$ to $a$ is smaller than the distance from $x$ to $L$. This proof has the unsatisfactory feature that it makes use of the Euclidean distance, whereas the theorem itself is invariant under projective transformations. However, there are other proofs of the theorem that do not have this defect.

It is natural to ask how many ordinary lines there must be. A trivial upper bound of $n-1$ can be obtained by taking $n-1$ points on a line and one point off it. A less obvious example due to Böröczky, which works when $n$ is even, is to take $n/2$ points equally spaced round a circle, regarded as a subset of the projective plane, and another $n/2$ points that lie on a line at infinity and that are determined by the $n/2$ possible directions of lines that go through at least two of the points on the circle. The ordinary lines turn out to be the tangent lines to the circle at the first $n/2$ points. When $n\equiv 1$ mod 4, a similar construction gives an example with $3(n-1)/4$ ordinary lines, and when $n\equiv 3$ mod 4 one can obtain a bound of $3(n-3)/4$.

A remarkable result of Green and Tao [2] shows that for $n$ sufficiently large these bounds are sharp, and that in the case of equality the Böröczky examples are unique up to projective transformations. There are a few exceptional examples that show that the condition that $n$ be sufficiently large cannot be dropped.

They also solve the related orchard problem, which is the following question: given $n$ points in the plane, how many lines can there be that contain precisely three of the points? For sufficiently large $n$ the answer turns out to be $\lfloor n(n-3)/6\rfloor+1$. The extremal examples, due to Sylvester, are subsets of cubic curves and exploit the group law for such curves.

A key step in Green and Tao’s proof is a structure theorem that is very interesting in its own right, which states that if a set of $n$ points gives rise to at most $Kn$ ordinary lines, then it must differ by $O(K)$ points from a set of $n$ points in a line, a Böröczky-type example, or a Sylvester-type example.

The purpose of this paper is to prove $d$-dimensional generalizations of all these results. The case $d=3$ was covered in earlier papers by Simeon Ball [2] and the authors [3], so the new results are for $d\geq 4$. They take $n$ points in real projective $d$-space, make the assumption that any $d$ of them span a hyperplane, and obtain a lower bound of $\binom{n-1}{d-1} - O_d(n^{\lfloor(d-1)/2\rfloor})$ for the number of ordinary hyperplanes that the points define. This lower bound is sharp, and like Green and Tao the authors can compute it exactly for sufficiently large $n$ (depending on $d$).

The condition that any $d$ points span a hyperplane does not show up in the 2-dimensional case, since there all it would be saying is that the points are distinct. In general, however, it makes a very big difference to the problem. For example, in three dimensions it rules out constructions such as a plane with $n-k$ points and at most $Cn$ ordinary lines, and $k$ points that lie outside the plane. It is easy to check that the number of ordinary planes defined by this set is at most $Ckn+k^2n+k^3$, which is much smaller than the quadratic lower bound that the authors obtain in this case.

The paper also obtains best possible bounds for the natural $d$-dimensional analogue of the orchard problem (again with the condition that any $d$ points span a hyperplane), and proves a structural result that is closely analogous to the structural result of Green and Tao in two dimensions. The proofs make use of the results of Green and Tao and also of the results of the authors’ earlier paper.

[1] Simeon Ball, On sets defining few ordinary planes, arXiv:1606.02138
[2] Ben Green and Terence Tao, On sets defining few ordinary lines, arXiv:1208.4714
[3] Aaron Lin and Konrad Swanepoel, Ordinary planes, coplanar quadruples, and space quartics, arXiv:1808.10847