Few distinct distances implies no heavy lines or circles

This post is about another new distinct distances result, which was just uploaded to arXiv. It is a paper by Zahl, de Zeeuw, and myself.

Joshua Zahl and Frank de Zeeuw.

Let us start by asking what are currently the main challenges in studying distinct distances (you’re welcome to share your thoughts about this in the comments). It seems to me that most people consider the main challenge to be the d  -dimensional variant of the distinct distances problem (see the second half of this post for more details). I would like to suggest that another main problem is characterizing the point sets that determine a small number of distinct distances.

I already wrote about the characterization problem in this post, and I will now repeat a few sentences from there. So far, all the known point sets that determine a sublinear number of distinct distances are \sqrt{n}\times\sqrt{n}  lattices, possibly with some minor changes. For example, any \sqrt{n}\times\sqrt{n}  subset of the integer lattice determines O(n/\sqrt{\log n})  distinct distances, and so does a \sqrt{n}\times\sqrt{n}  subset of the following triangular lattice:

\displaystyle \left\{a\cdot (1,0) + b\cdot (1/2, \sqrt{3}/2) \ \mid \mbox{ for any } a,b\in{\mathbb Z} \right\}.

intgrid grid3

Over 25 years ago Erdős asked whether every point set that determines O(n/\sqrt{\log n})  distinct distances “has lattice structure”. However, even after so many years and Guth and Katz’s breakthrough, we still hardly know anything about this problem. A proof by Szemerédi (unpublished and originally described in a 1975 paper by Erdős) implies that for every n  -point set \cal P  , there exists a line \ell  that contains \Omega(\sqrt{\log n})  points of \cal P  . It had been conjectured by Erdős that this bound can be improved to \Omega(n^{1/2})  , though no improvement had been discovered in the decades that passed. It is an interesting challenge to prove even the case of \Omega(n^{\varepsilon})  points on a line.

In the new paper, we study the “complementary” problem of proving that there must not be a line with too many points on it.

Theorem 1. (S’, Zahl, and de Zeeuw) Let \cal P  be a set of n  points that determine o(n)  distinct distances. Then no line contains \Omega(n^{7/8})  points of \cal P  .

Recall that a recent result of Pach and de Zeeuw implies that a set of n  points on a constant-degree curve, that does not contain any lines or circles, determines \Omega(n^{4/3})  distinct distances. This immediately implies that for every set \cal P  of n  points that determine o(n)  distinct distances, no constant-degree curve that contains no lines or circles can contain \Omega(n^{3/4})  points of \cal P  . However, this result cannot be extended to lines and circles, since there exist sets of n  collinear (or cocircular) points that determine \Theta(n)  distinct distances. Our approach overcomes this difficulty by considering the number of distinct distances between points that are on the line and points that are not on the line (or circle).


To have a bound for every type of curve, we also derive the following theorem.

Theorem 2. (S’, Zahl, and de Zeeuw) Let \cal P  be a set of n  points that determine o(n)  distinct distances. Then no circle contains \Omega(n^{5/6})  points of \cal P  .

For both proofs we use a partial and bipartite variant of the Elekes-Sharir framework, which reduces the problem two a point-curve incidence problem. However, the two proofs are quite different. In the case of lines, the main problem is that some of the curves might have a large multiplicity. To attend this problem, we rely on a result from additive combinatorics by Elekes, Nathanson, and Ruzsa. In the case of circles there is no curve multiplicity. To show this we rely on some algebraic geometry, and then apply a very recent incidence bound by Wang, Yang, and Zhang.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s