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

This is the second post in my attempt to survey the variants of the distinct distances problem and the best known bounds for them (for the first part click here). In this part we discuss two families of open problems: the structure of planar point sets that determine a small number of distinct distances, and distinct distances in higher dimensions. While there are still many variants that have not been covered yet, after this post I will take a break from this series to discuss other issues. My next couple of big posts will focus on the so-called Elekes-Sharir framework. Once again, thanks to Micha Sharir for helping in the preparation of this post.

Structure of the optimal solution

In this section we discuss attempts to characterize point sets that determine a small number of distinct distances. This is perhaps the class of problems on which we know the least; even after decades of study, hardly anything is known about these problems. We say that a set ${\mathcal P}$ of $n$ points in the plane is optimal if $D({\mathcal P}) = D(n)$. Since even the asymptotic value of $D(n)$ is still unknown, we also consider sets ${\mathcal P}$ of $n$ points such that $D({\mathcal P})=O(n/\sqrt{\log{n}})$, and refer to such sets as near-optimal. All the point sets in this section are planar.

Erdős asked whether every optimal (or near-optimal) set “has lattice structure”. To make this question clearer, let us first consider some of the known near-optimal sets. In the previous post we already mentioned that the $\sqrt{n} \times \sqrt{n}$ integer lattice, as depicted in the following figure, determines $O(n/\sqrt{\log n})$ distinct distances.

This was observed by Erdős, who noticed that this is an immediate corollary of the following theorem from number theory.

Theorem 1. (Landau-Ramanujan) The number of positive integers smaller than $n$ that are the sum of two squares is $\Theta(n/\sqrt{\log n})$.

Every distance in the $\sqrt{n} \times \sqrt{n}$ integer lattice is the square root of a sum of two squares between $0$ and $n$. Thus, Theorem 1 implies that the number of distinct distances in this case is $\Theta(n/\sqrt{\log n})$.

The above implies that the $\sqrt{n} \times \sqrt{n}$ integer lattice is a near-optimal set. More generally, for any integer $c \ge 1$, every $n$ point subset of the $c\sqrt{n} \times c\sqrt{n}$ integer lattice is a near-optimal set (since we can still apply Theorem 1 in such cases), and so are translations, rotations, and uniform scalings of such lattices. For example, the lattice to the left out of the two following figures can be obtained either by rotating and scaling the $\sqrt{n} \times \sqrt{n}$ integer lattice, or by removing from the $2\sqrt{n} \times 2\sqrt{n}$ integer lattice every point whose coordinates sum to an odd number.

Another interesting set of points is the triangular lattice, which is the one on the right in the above figure. This lattice corresponds to the vertices in a tiling of equilateral triangles (unlike the lattice to the left, which can be seen as the vertices of a tiling of isosceles right triangles). The points on this lattice can be described as

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

Due to the irrational $y$-coordinates, it can be easily noticed that such a lattice cannot be obtained from the integer lattice without applying a non-uniform scaling. However, the number of distinct distances determined by an $\sqrt{n} \times \sqrt{n}$ triangular lattice is still $\Theta(n/\sqrt{\log n})$. To see this, we first perform a uniform scaling of the grid, obtaining $\left\{a(2,0) + b(1, \sqrt{3}) \mid 1 \le a,b \le \sqrt{n} \right\}$. Any distance between two points in this lattice can be written as $\sqrt{i^2 + 3j^2}$, where $i,j \in {\mathbb Z}$. A variant of Theorem 1 by Bernays (a brief description in English can be found, e.g., in the introduction of this paper) implies that the number of of positive integers smaller than $n$ that can be expressed as $i^2 + 3j^2$ is $\Theta(n/\sqrt{\log n})$, immediately implying the above assertion. After obtaining optimal sets for a few small values of $n$, Erdős and Fishburn conjectured that, for infinitely many values of $n$, there is an $n$-point subset of the triangular lattice that is an optimal set.

For now, hardly anything is known regarding Erdős’s conjecture that every optimal set has a lattice structure. As a first step, Erdős suggested to determine whether every optimal point set contains $\Omega(\sqrt{n})$ points on a line, or even only $\Omega(n^\varepsilon)$. It might be better to consider the following slightly more general question:

Problem 1. (Erdős) Prove or disprove: For a sufficiently small $\varepsilon> 0$, every near-optimal point set contains $\Omega(n^\varepsilon)$ points on a common line.

A simple extension of Szemerédi’s result for sets with no three collinear points (which was discussed in the previous post) implies that for every near-optimal set ${\mathcal P}$ of $n$ points, there exists a line $\ell$ such that $|\ell\cap{\mathcal P}| = \Omega(\sqrt{\log n})$ (more on this in the following posts about the Elekes-Sharir framework). No better lower bound is known. The complement problem also seems interesting.

Problem 2. Prove or disprove: For a sufficiently small $\varepsilon >0$, no near-optimal point set contains $\Omega (n^{1-\varepsilon})$ points on a common line.

It is known that the points of the integer grid (as in the first figure of this post) do not determine any equilateral triangles. Thus, there are near-optimal sets that determine no equilateral triangles. On the other hand, it can easily be noticed that the points of any near-optimal set must determine many isosceles triangles. Erdős conjectured that any near-optimal set must contain either an equilateral triangle or a square.

Problem 3. (Erdős) Prove or disprove: The points of any near-optimal set of $n$ points determine either an equilateral triangle or a square.

We conclude this section with a couple other similar conjectures:

Problem 4. (Erdős) Prove or disprove: The points of every optimal set can be covered by $O(n^{1/2})$ lines (a weaker version asks for $O(n^{1-\varepsilon})$ lines).

Problem 5. (Guth and Katz) Prove or disprove: For any near-optimal point set ${\mathcal P}$, there are many rotations of the plane that map many points of ${\mathcal P}$ to other points of ${\mathcal P}$.

(The quantity “many” in Problem 5 is a bit vague; see the last part of Section 2 in Guth and Katz’s paper for more details.)

Higher dimensions

In this section we consider higher-dimensional variants of the distinct distances problem. Denote by $D_d(n)$ the minimum number of distinct distances that any set of $n$ points in ${\mathbb R}^d$ must always determine. Similarly to the planar case, the best known configuration for the $d$-dimensional case is an $n^{1/d} \times n^{1/d} \times \cdots \times n^{1/d}$ integer lattice. Every distance in this configuration is the square root of a sum of $d$ squares, each with a value between $0$ and $n^{2/d}$. Therefore, the number of distinct distances that are determined by such a lattice is $O(n^{2/d})$, implying $D_d(n) = O(n^{2/d})$. This bound was already observed in Erdős’s 1946 paper, and is conjectured to be tight.

Solymosi and Vu derived the following recursive relations on $D_d(n)$.

Theorem 2. (Solymosi and Vu)
(i) If $D_{d_0}(n) = \Omega(n^{\alpha_0})$, then for all $d>d_0$, we have

$D_d(N) = \Omega\left( n^{\frac{2d}{(d+d_0+1)(d-d_0)+2d_0/\alpha_0}} \right)$.
(ii) If $D_{d_0}(n) = \Omega(n^{\alpha_0})$, then for all $d>d_0$ where $d-d_0$ is even, we have
$\displaystyle D_d(N) = \Omega\left( n^{\frac{2(d+1)}{(d+d_0+2)(d-d_0)+2(d_0+1)/\alpha_0}} \right)$.

Recall that $D_2(n) = \Omega(n/\log{n})$. Combining this with Theorem 2(i) implies $D_3(n) = \Omega^*(n^{3/5})$ (in the $\Omega^*(\cdot)$ notation we neglect polylogarithmic factors; although the logarithm in the denominator of the lower bound for $D_{2}(n)$ does not fit the formulation of Theorem 2, the proof remains valid), while the above lattice example implies $D_3(n) = O(n^{2/3})$. Currently, these are the best known bounds for $D_3(n)$. The best known bounds for larger values of $d$ are obtained by combining Theorem 2(ii) with the bounds $D_2(n)=\Omega^*(n)$ and $D_3(n)=\Omega^*(n^{3/5})$ as base cases. That is, for even $d\ge4$ we have $D_d(n) = \Omega^*\left(n^{\frac{2d+2}{d^2+2d-2}}\right)$ and for odd $d\ge5$ we have $D_d(n) = \Omega^*\left(n^{\frac{2d+2}{d^2+2d-5/3}}\right)$. Notice that as $d$ goes to infinity $D_d(n)$ approaches the conjectured bound $\Theta(n^{2/d})$.

Problem 6.  Find the asymptotic value of $D_d(n)$.

It seems possible that the techniques used by Guth and Katz for analyzing $D(n)$ could also be applied to the higher dimensional variant. However, some of the steps in the analysis of Guth and Katz seem hard to extend to higher dimensions.

Let $D_d^{o}(n)$ denote the minimum number of distinct distances that any set of $n$ points on a hypersphere in ${\mathbb R}^d$ must always determine. Tao showed that the bound of Guth and Katz remains valid when the point set is on a sphere in ${\mathbb R}^3$ (or on a hyperbolic plane). That is, $D_3^{o}(n) = \Omega(n/\log{n})$. By placing a set of $n$ points on a common circle, we can create the vertex set of a regular planar $n$-gon, which spans $\Theta(n)$ distinct distances. Thus, we also have $D_3^{o}(n) = O(n)$.

Problem 7.  Find the asymptotic value of $D_3^o(n)$.

Erdős, Füredi, Pach, and Ruzsa derived the bounds $D_4^o(n) = O(n/\log \log n)$ and $D_d^o(n) = O(n^{2/(d-2)})$ for $d>4$. These bounds are obtained by taking an integer lattice in ${\mathbb R}^d$ and then choosing a sphere that contains many lattice points. No lower bound is known beyond the trivial $D_d^o(n) \ge D_d(n)$.

Problem 8.  Find the asymptotic value of $D_d^o(n)$ for $d\ge 4$.