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.

* Shakhar Smorodinsky and Frank de Zeeuw.*

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*

Advertisements