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