In this post I will show that if a planar point set spans a small number of distinct distances, there must exist a line containing points of the set. This result originated in a conversation between Shakhar Smorodinsky, Frank de Zeeuw, and myself, a few months ago in IPAM. I understand that Orit Raz and Micha Sharir independently obtained similar observations at about the same time.
Guth and Katz proved that every set of points in determines distinct distances. This almost completely settled a conjecture of Erdős , who observed that the integer lattice determines distinct distances, and conjectured that every set of points determines at least this number of distinct distances. Beyond the remaining gap, a major open problem is characterizing the point sets that determine a small number of distinct distances.
Given a set of points in , we say that it is near-optimal if it determines distinct distances. Erdős asked whether every near-optimal set “has lattice structure”. Since this seems to be a very challenging problem, Erdős wrote “The first step would be to decide if there always is a line which contains of the [i.e., of the points of the set], (and in fact would already be interesting).”
Embarrassingly, almost three decades later the bound seems as distant as it ever was. Up to now, the best known bound was a variant of a proof of Szemerédi, which was communicated by Erdős.
Theorem 1 (Szemerédi). Let be a near-optimal set of points. Then there exists a line containing points of .
Proof. Let denote the maximum number of points of that are on a common line. Let , where are three distinct points and where and are counted as the same triple. The proof is based on double counting , and we begin by deriving an upper bound for it. Given a pair of points , the triplet is in if and only if is on the perpendicular bisector of the segment . By the assumption, each such perpendicular bisector contains at most points of , which implies
For the lower bound, notice that for every point , the points of are contained in at most concentric circles around . We denote these circles as and set . Notice that for every . By the Cauchy-Schwarz inequality, we have . This in turn implies
Combining and immediately implies
Szemerédi’s proof is almost identical to the proof of the Kővári–Sós–Turán theorem. We now prove a variant of this theorem.
Theorem 2 (Kővári–Sós–Turán variant). Let be a set of circles and let be a set of points, both in , such that the incidence graph of contains no copy of (where may depend on ). Then
Proof. The proof is a variant of the standard proof of the Kővári–Sós–Turán theorem. We double count the number of triplets , such that , , and is incident to both and . On one hand, there are pairs of vertices of , and each can have at most circles of that are incident to each point of the set. That is, we have
On the other hand, for each , let denote the number of points of that are contained in , and notice that
. Then we have
. Then we have
By applying the Cauchy-Schwarz inequality, we obtain
By combining and , we obtain
Hence , as asserted.
Theorem 1 can be easily derived from Theorem 2.
Alternative proof of Theorem 1. Denote the set of distinct distances that are spanned by as . Let be a set of circles: around every point of we place circles whose radii are the values of . It can be easily verified that .
Let denote the maximum number of points of that are on a common line. Given two points , a circle of can contain both and only if the perpendicular bisector of is incident to the center of the circle. This implies that the incidence graph of contains no copy of . Thus, by Theorem 2 we have
Combining this bound with immediately completes the proof.
Now that the proof is reformulated as an incidence problem, we can apply stronger incidence tools to obtain an improved bound. Specifically, we use polynomial partitioning (see my guide to polynomial partitioning here). If you are not interested in polynomial partitioning, you are welcome to skip the proof of the following theorem.
Theorem 3. Let be a set of circles and let be a set of points, both in , such that the incidence graph of contains no copy of (where may depend on ). Then .
Proof. We consider an -partitioning polynomial for . According to polynomial partitioning theorem, the degree of is and every cell in is an open set that contains at most points of . Let denote the number of cells in (i.e., connected components of) .
We set , and similarly denote by the set of circles that are fully contained in . For , let denote the set of points that are contained in the -th cell and let denote the set of circles that intersect the ‘th cell. Notice that
We bound each of these three expressions separately. Consider a circle , and notice that . By Bézout’s theorem, we have
Every regular point of is incident to at most one circle of . Thus, points of that are on a regular point yield incidences with . By Bézout’s theorem, every circle of can intersect at most singular point of . Therefore, we have
It remains to bound . By Warren’s theorem, the number of cells in the partition is . We set and . Since every circle of intersects in points, we get . According to the Cauchy-Schwarz inequality, we have
By applying Theorem 2 separately in each cell, we obtain
which completes the proof.
By replacing Theorem 2 with Theorem 3 in the alternative proof of Theorem 1, we obtain the following improved bound.
Theorem 4. Let be a near-optimal set of points. Then there exists a line containing points of .
Proof sketch. As before, we have . By applying Theorem 3, we have
Combining these two bounds yields the assertion of the theorem.