This is the first in a new series of posts, in which I will survey the constructions leading to the best known lower bounds for the various incidence problems. Although recently many improved upper bounds for incidence problems were proven, not much progress was made concerning the lower bounds.
We begin with the case of point-line incidences in the plane. This is of course the matching lower bound for the famous Szemerédi–Trotter Theorem.
Theorem 1 (Szemerédi and Trotter). The maximum number of incidences between a set of points and a set of lines, both in , is
Notice that the linear terms dominate this bound when either or . Since a point-line configuration with incidences is easy to construct, we focus on obtaining incidences when .
Today the “common” construction for the planar point-line incidence bound is by Elekes. Elekes’ construction will be described in the next post of the series. Before that, in this post we present the original construction of Erdős. While this construction is mentioned in several places (e.g., see here), I could not locate the original paper that describes it. Many years later Edelsbrunner and Welzl rediscovered this construction.
Pach and Tóth use a variant of this construction to obtain the best known constant for the lower bound for the maximum number of point-line incidences. Specifically,
Recall that our goal is to construct a set of points and a set of lines, for any . Specifically, we assume that for a sufficiently large constant whose value will be determined below. As our point set, we take the following subset of the integer lattice.
Given a pair of relatively prime integers , we define the line set:
Notice that . Our set of lines is the union of many sets of the form . Specifically, we set (for a constant that will be set below) and
The resulting point-line configuration is depicted in the following figure.
We claim that the lines of are distinct. Indeed, two lines from the same set are distinct since they intersect the -axis in distinct points. Two lines from two different sets are distinct since they have distinct slopes. We recall Euler’s totient function:
Since (e.g., this is a variant of the proof of Theorem 330 in this book by Hardy and Wright), we have
Thus, by an appropriate choice of , we obtain .
It remains to bound the number of incidences in . Consider a line that is defined by and notice that is incident to a point in every -th column of the integer lattice. The slope of is smaller than one and it intersects the -axis below the point . Moreover, by setting to be sufficiently large (with respect to ) so that , we obtain that intersects the -axis above the point . Combining these properties, we notice that is incident to at least points of , and thus
Since (e.g., see Theorem 330 in this book by Hardy and Wright), we have
This completes Erdős’ construction.