Distinct Distances: Open Problems and Current Bounds (part 1)

This is the first in a series of posts about open problems that are related to the distinct distances problem. I wish to thank Micha Sharir for helping in the preparation of this post (the mistakes are of course all mine).

Given a set \mathcal P  of n  points in the real plane, let D({\mathcal P})  denote the number of distinct distances that are determined by pairs of points from \mathcal P  . Let D(n) = \min_{|{\mathcal P}|=n}D({\mathcal P})  ; that is, D(n)  is the minimum number of distinct distances that any set of n  points in {\mathbb R}^2   must always determine. In his celebrated 1946 paper, Erdős derived the bound D(n) = O(n/\sqrt{\log n})  . More specifically, Erdős proved that an \sqrt{n} \times \sqrt{n}  square lattice determines \Theta(n/\sqrt{\log n})  distinct distances (for more details, see the second post of this series). Though almost 70 years have passed since Erdős considered this lattice configuration, no configuration with o(n/\sqrt{\log n})  distinct distances was discovered.

For the celebrations of his 80’th birthday, Erdős compiled a survey of his favorite contributions to mathematics, in which he wrote

My most striking contribution to geometry is, no doubt, my problem on the number of distinct distances. This can be found in many of my papers on combinatorial and geometric problems.”

Recently, after 65 years and a series of increasingly larger lower bounds, Guth and Katz provided the bound D(n) = \Omega(n/\log n)  , almost matching the best known upper bound. (For a comprehensive list of the previous bounds, see this dedicated webpage by William Gasarch.) To derive this bound, Guth and Katz developed several novel techniques, relying on tools from algebraic geometry. Notice that a relatively small gap of O(\sqrt{\log n})  remains between the best known lower and upper bounds.

Problem 1. Find the exact asymptotic value of D(n)  .

Since this problem is almost solved, one might wonder what is the purpose of these posts. The answer is that there are many interesting variants of the distinct distances problem which are still wide open (many of those were also posed by Erdős). For some of these variants (such as the ones presented in the first part of the next post of this series) even after several decades of work hardly anything is known. Papers that discuss problems from the set that is surveyed in the first part of this post contain phrases such as “Our ignorance in this area is really shocking!” and “It is rather frustrating that I got nowhere with…”. I wish to maintain a dynamic document, keeping track of the best known bounds for the various distinct distances variants, as time goes by. These posts are the first step towards this document.

Erdos guth katz Szem
Names that appear quite often in this set of posts: Paul Erdős, Larry Guth, Nets Katz, and Endre Szemerédi.

This first post of the series surveys problems in which a planar point set is constrained in some manner. The following post will discuss two families of problems: the structure of planar point sets that determine a small number of distinct distances, and distinct distances in higher dimensions. A great collection of open problems related to distinct distances can be found in the book “Research Problems in discrete Geometry” by Brass, Moser, and Pach (though due to various recent developments, the collection in this book is already somewhat outdated).

A more general version of Problem 1 asks to find the minimum value \hat{D}(n)  , such that for every set {\mathcal P}  of n  points in the plane there exists a point p \in {\mathcal P}  which determines at least \hat{D}(n)  distinct distances with the other points of {\mathcal P}  (e.g., see this paper by Erdős). An immediate upper bound is \hat{D}(n) \le D(n) = O(n/\sqrt{\log n})  . However, the bound of Guth and Katz does not immediately imply a matching lower bound for \hat{D}(n)  . The best known lower bound, obtained by Katz and Tardos, is \hat{D}(n) = \Omega(n^{(48-14e)/(55-16e)})\approx \Omega(n^{0.864})  .

Problem 2. Find the exact asymptotic value of \hat{D}(n)  .

Constrained sets of points

We now consider variants of the distinct distances problem where the point sets are constrained in some way. The best known bounds for the various variants are listed in the following table; see the figure and text below for an explanation of the notation used in the table. Unless stated otherwise, the point sets in this part are planar.

Variant Lower Bound Upper Bound
D_{\text{no3}}(n)  \displaystyle \lceil (n-1)/3\rceil  \displaystyle \lfloor n/2\rfloor
\hat{D}_{\text{no3}}(n)  \displaystyle \lceil (n-1)/3\rceil  \displaystyle \lfloor n/2\rfloor
\hat{D}_{\text{conv}}(n)  \left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1)  \displaystyle \lfloor n/2\rfloor
D_{\text{gen}}(n)  \Omega(n)  \displaystyle n2^{O(\sqrt{\log n})}
\hat{D}_{\text{gen}}(n)  \lceil (n-1)/3 \rceil  n-O(1)
D_{\text{para}}(n)  \Omega(n)  \displaystyle O(n^2/\sqrt{\log n})
D_{\text{lines}}(n)  \Omega(n^{4/3})  \displaystyle O(n^2/\sqrt{\log n})

RelAndConv

General and convex position. We begin with a set of problems that ask for exact bounds, instead of asymptotic ones, where the “fight” is for the best constant of proportionality. The hierarchy between the different types of constraints that are presented in this part is depicted in the above figure. Denote by D_{\text{no3}}(n)  the minimum number of distinct distances that can be determined by a set of n  points, no three which are collinear (that is, D_{\text{no3}}(n) = \min_{|{\mathcal P}|=n}D({\mathcal P})  where the minimum is taken over all sets of n  points containing no three collinear points). Notice that the vertices of a regular n  -gon, such as the set depicted in the above figure, satisfy this property and determine \lfloor \frac{n}{2}\rfloor  distinct distances, implying D_{\text{no3}}(n) \le \lfloor \frac{n}{2}\rfloor  . The best known lower bound, due to Szemerédi (this bound is briefly mentioned here and here, and the proof can be found in the book Combinatorial Geometry by Pach and Agarwal. However, it seems that it was never formally published by Szemerédi. Any further information will be appreciated.), is D_{\text{no3}}(n) \ge \lceil \frac{n-1}{3}\rceil  . Szemerédi also conjectured that D_{\text{no3}}(n) = \lfloor \frac{n}{2}\rfloor  (again, see here and here).

Problem 3. Find the exact value of D_{\text{\em no3}}(n)  .

As before, let \hat{D}_{\text{no3}}(n)  denote the maximum number satisfying that for any set {\mathcal P}  of n  points, no three of which are collinear, there exists a point p\in {\mathcal P}  such that \{p\}\times{\mathcal P}  determines at least \hat{D}_{\text{no3}}(n)  distinct distances.

Problem 4. Find the exact value of \hat{D}_{\text{\em no3}}(n)  .

It can be easily noticed that the regular n  -gon configuration implies \hat{D}_{\text{no3}}(n) \le \lfloor \frac{n}{2}\rfloor  , and Szemerédi’s bound for D_{\text{no3}}(n)  also remains valid for \hat{D}_{\text{no3}}(n)  . Thus, the best known bounds for Problems 3 and 4 are currently identical (as opposed to the case of Problems 1 and 2).

Though Problems 3 and 4 have been stuck for several decades, more recent advances have been obtained for several more “degenerate” variants of them. Similarly to D_{\text{no3}}(n)  , let D_{\text{conv}}(n)  denote the minimum number of distinct distances that can be determined by a set of n  points in convex position. Let \hat{D}_{\text{conv}}(n)  denote the maximum number satisfying that for any set {\mathcal P}  of n  points in convex position, there exists a point p\in {\mathcal P}  such that \{p\}\times{\mathcal P}  determines at least \hat{D}_{\text{conv}}(n)  distinct distances.

By considering the regular n  -gon once again, we notice that D_{\text{conv}}(n) \le \lfloor \frac{n}{2}\rfloor  and that \hat{D}_{\text{conv}}(n) \le \lfloor \frac{n}{2}\rfloor  . Already in his 1946 paper, Erdős conjectured that D_{\text{conv}}(n) = \lfloor \frac{n}{2}\rfloor  . This was proven by Altman, which led Erdős to suggest the stronger conjecture \hat{D}_{\text{conv}}(n) = \lfloor \frac{n}{2}\rfloor  . Since, for any set of points in (strict) convex position, no three points can be collinear, we have \hat{D}_{\text{conv}}(n) \ge \hat{D}_{\text{no3}}(n) \ge \lceil \frac{n-1}{3}\rceil  . In 2006, Dumitrescu derived the improved bound \hat{D}_{\text{conv}}(n) \ge \lceil \frac{13n-6}{36}\rceil  . Recently, Nivasch, Pach, Pinchasi, and Zerbib obtained the slightly improved bound \hat{D}_{\text{conv}}(n) \ge \left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1)  .

Problem 5. Find the exact value of \hat{D}_{\text{\em conv}}(n)  .

We say that a set of points is in general position if no three points are collinear and no four points are cocircular. Denote by D_{\text{gen}}(n)  the minimum number of distinct distances that can be determined by a set of n  points in general position. The convex n  -gon configuration is not in general position, and it is in fact unknown whether D_{\text{gen}}(n) = \Theta(n)  or not. The best know upper bound D_{\text{gen}}(n) = n2^{O(\sqrt{\log n})}  was derived by Erdős, Füredi, Pach, and Ruzsa. This bound is obtained by a very different construction: taking an integer grid G  in a d  -dimensional space (where d  is roughly \sqrt{\log n}  ), considering a subset G'  of the points of G  that lie on a specific sphere, and projecting G'  on a generic plane. The generic projection guarantees that the resulting planar set is in general position, while the “integer grid on a sphere” structure implies a relatively small number of distinct distances. For an easy lower bound, notice that D_{\text{gen}}(n) \ge D_{\text{no3}}(n) = \Omega(n)  .

Problem 6. Find the asymptotic value of D_{\text{\em gen}}(n)  .

Erdős also suggested to study the maximum number \hat{D}_{\text{\em gen}}(n)  satisfying that for any set {\mathcal P}  of n  points in general position, there exists a point p\in {\mathcal P}  such that \{p\}\times{\mathcal P}  determines at least \hat{D}_{\text{gen}}(n)  distinct distances. Consider a point set {\mathcal P}  in general position and a point p\in {\mathcal P}  . If p  has a distance of d  from four other points of {\mathcal P}  , then each of these four points is incident to the circle whose center is p  and radius is d  , contradicting the general position assumption. Thus, a trivial lower bound is \hat{D}_{\text{\em gen}}(n) \ge \lceil (n-1)/3 \rceil  . No non-trivial bound is known for \hat{D}_{\text{\em gen}}(n)  (neither a lower nor an upper bound), and Erdős’s quote from the introduction “It is rather frustrating that I got nowhere with…” was said with respect to this problem.

Problem 7. Find the exact value of \hat{D}_{\text{\em gen}}(n)  .

We conclude this set of problems with an even more constrained type of point sets. The point configuration that implies D_{\text{gen}}(n) = n2^{O(\sqrt{\log n})}  spans many duplicate vectors, which leads to the following notation. Let D_{\text{para}}(n)  denote the minimum number of distinct distances determined by a set of n points in general position that do not determine any parallelograms. Erdős, Hickerson, and Pach asked whether D_{\text{para}}(n)= o(n^2)  . This was recently confirmed by Dumitrescu, who proved D_{\text{para}}(n)= O(n^2/\sqrt{\log n})  by considering, for prime n  , the point set

\left\{ (i,j) \mid i=0,1,\ldots,(n-1)/4, \ j= i^2 \hspace{-2mm}\mod n \right\}.

The trivial D_{\text{para}}(n)= \Omega(n)  is currently the best known lower bound.

Problem 8. Find the asymptotic value of D_{\text{\em para}}(n)  .

Points on curves. We now consider a different type of constrained point sets. Let {\mathcal P}_1  and {\mathcal P}_2  be two sets of n  points each, such that all the points of {\mathcal P}_1  (resp., {\mathcal P}_2  ) lie on a line \ell_1  (resp., \ell_2  ). Let D({\mathcal P}_1,{\mathcal P}_2)  denote the number of distinct distances between the pairs of {\mathcal P}_1\times{\mathcal P}_2  (that is, only distinct distances between points on different lines are considered). When the two lines are either parallel or orthogonal, the points can be arranged such that D({\mathcal P}_1,{\mathcal P}_2) = \Theta(n)  ; for example, see the following figure.

Twolines

Purdy conjectured that if the lines are neither parallel nor orthogonal then D({\mathcal P}_1,{\mathcal P}_2) = \omega(n)  (e.g., see Section 5.5 of the research problems book). Let us denote as D_{\text{lines}}(n)  the minimum number of distinct distances in such a scenario. Elekes and Rónyai proved Purdy’s conjecture, though without deriving any specific superlinear lower bound. Later, Elekes showed that D_{\text{lines}}(n) = \Omega(n^{5/4})  . Recently, Sharir and Sheffer proved D_{\text{lines}}(n) = \Omega(n^{4/3})  . More generally, they derived the bound \Omega(\min\{n^{2/3}m^{2/3},m^2,n^2\})  for the asymmetric case when one line contains n  points and the other m  points (another recent related result, which is subsumed by the bound of Sharir and Sheffer, was derived by Schwartz, Solymosi, and de Zeeuw). Elekes also derived the upper bound D_{\text{lines}}(n) = O(n^2/\sqrt{\log n})  .

Problem 9. Find the asymptotic value of D_{\text{\em lines}}(n)  .

It seems likely that the techniques presented by Elekes and by Sharir and Sheffer can be applied to cases where the points are on other curves (e.g., on two circles, one circle and one line, etc.). The more interesting extension would be to provide a general framework for solving sets of such problems (e.g., for all algebraic curves of a specific degree or having some other property).

Problem 10. Develop a framework for solving variants of Problem 9.

Another interesting extension of Problem 9 is to consider it in higher dimensions. The following formulation is perhaps the simplest such problem. Let D_{\text{planes}}(n)  denote the minimum number of distinct distances between two sets of n  points, each fully contained on a different plane in {\mathbb R}^3  .

Problem 10. Find the asymptotic value of D_{\text{\em planes}}(n)  .

In this case, it is unclear whether asking the planes to be neither parallel nor orthogonal has any effect. Consider two non-parallel non-orthogonal planes \Pi_1,\Pi_2 \subset {\mathbb R}  . Then there are two orthogonal lines \ell_1,\ell_2  such that \ell_1 \subset \Pi_1  and \ell_2 \subset \Pi_2  and \ell_1 \cap \ell_2  is a point on \Pi_1 \cap \Pi_2  . By spreading the point sets on \ell_1,\ell_2  as in the figure above, we obtain D_{\text{\em planes}}(n) = O(n)  . On the other hand, an unrestricted set of points in {\mathbb R}^3  can determine only O(n^{2/3})  distinct distances (more on this in the following post of this series).

3 thoughts on “Distinct Distances: Open Problems and Current Bounds (part 1)

  1. Pingback: Distinct Distances: Open Problems and Current Bounds #2 | The Plane Truth

  2. Pingback: The Elekes-Sharir Framework (part 1) | Some Plane Truths

  3. Pingback: A short update | Some Plane Truths

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