Point Sets with Few Distinct Distances

Ben Lund and I were sitting in a small Korean restaurant and discussing an old conjecture of Erdős. Erdős suggested that if a set of n  points in {\mathbb R}^2  spans O(n/\sqrt{\log n})  distinct distances, then the vertices of this set must span either a square or an equilateral triangle. Presumably, this conjecture was made because the two best-known examples of sets with O(n/\sqrt{\log n})  distinct distances are n\times n  subsets of the integer lattice and of the triangular lattice. (By the triangular lattice, I mean the vertices of a tiling of the plane with equilateral triangles.)

intGrid grid3
A subset of the integer lattice and a subset of the triangular lattice.

A subset of the integer lattice spans many squares and no equilateral triangles, while a subset of the triangular lattice spans many equilateral triangles and no squares. We can create various similar configurations by taking one of these two configurations and then applying rotations, uniform scaling, and taking subsets. Such configurations still contain squares or equilateral triangles. Ben and I were wondering whether we can find additional configurations, which are not “related” to the integer lattice or to the triangular lattice. Surprisingly, we managed to find a large family of other configurations. Moreover, many of these configurations do not span any squares or triangles, disproving Erdős’ conjecture. We then discovered that these configurations were already known, and appeared in a paper by Moree and Osburn. I guess that this is another case of lack of communication between different mathematical communities…

For any integer r>1  , we define the rectangular lattice

{\mathcal L}_r = \{ (i,j\sqrt{r}) \ \mid \ i,j\in{\mathbb Z} \quad \text{and} \quad  1 \le i,j \le \sqrt{n} \}.

We now show that every point set {\mathcal L}_r  spans O(n/\sqrt{\log n})  distinct distances. Moree and Osburn present a more general-looking formulation. However, if I am not mistaken, each of their configurations can be obtained by taking a lattice {\mathcal L}_r  and performing a rotation, uniform scaling, and possibly also taking a subset. As an example, you might want to convince yourself that the aforementioned triangular lattice can be obtained in this way.

To prove that an n\times n  subset of the integer lattice determines a small number of distinct distances, Erdős relied on a result of Landau and Ramanujan. This result estimates the number of integers between 1 and n that can be expressed as a sum of two squares. We rely on the following generalization of the Landau-Ramanujan result, originally from Paul Bernays’ 1912 Ph.D. dissertation, under the supervision of Landau.

Theorem 1 (Bernays). Let f(x,y)=ax^2+bxy+c^2  for constants a,b,c\in{\mathbb Z}  , such that the discriminant b^2-4ac  is not an integer square. Then the number of integers between 1  and n  that can be expressed as f(u,v)  with u,v\in{\mathbb Z}  is O(n/\sqrt{\log n})  .

Every distance between a pair of points of {\mathcal L}_r  is of the form \sqrt{i^2+j^2r}  , where i,j\in{\mathbb Z}  and 1 \le i,j \le \sqrt{n}  . That is, every such distance is the square root of an integer between 1  and (r+1)n  that can be expressed as i^2+j^2r  . By applying Theorem 1 with a=1  , b=0  , and c=r  , we obtain that the number of such distances is O(n/\sqrt{\log n})  (where the constant of proportionality depends on r  ). Notice that in this case the discriminant b^2-4ac  is negative, and thus cannot be a square.

Disproving Erdős’ conjecture. We disprove the conjecture by showing that some of the lattices {\mathcal L}_r  span neither squares nor equilateral triangles. For equilateral triangles, we use a variant of a nice trick that I saw here.

Assume, for contradiction, that r  is not a multiple of three and that the points of {\mathcal L}_r  span an equilateral triangle. Denote the three vertices of this triangle as o,p,q  . We translate the plane so that o  becomes the origin. After this translation, we write p=(p_x,p_y)  and q=(q_x,q_y)  . Denote the length of an edge of the triangle as \ell  . We have

\ell = \sqrt{p_x^2+p_y^2} = \sqrt{q_x^2+q_y^2} = \sqrt{(p_x-q_x)^2 + (p_y-q_y)^2}.

We thus have

\ell^2 = p_x^2 - 2p_xq_x +q_x^2 + p_y^2 -2p_yq_y + q_y^2 = 2\ell^2 - 2p_xq_x -2p_yq_y,

or

p_xq_x + p_yq_y = \ell^2/2.

(a^2+b^2)(c^2+d^2) = (ac+bd)^2 +(ad-bc)^2.

This inequality implies

(p_x^2+p_y^2)(q_x^2+q_y^2) = (p_xq_x+p_yq_y)^2 +(p_xq_y-p_yq_x)^2,

or

3\ell^4 = 4(p_xq_y-p_yq_x)^2 = 4rN^2,

for some integer N  . Since r  is not a multiple of three, it is impossible for \frac{3}{r}\ell^4  to be a square, which is a contradiction. That is, for any r  that is not divisible by three, the points of the lattice {\mathcal L}_r  do not span any equilateral triangles.

We next assume, for contradiction, that the points of {\mathcal L}_r  span a square. This implies that the points of {\mathcal L}_r  also span a right-angled isosceles triangle. As before, we denote the vertices of this triangle as o,p,q  , translate the plane so that o  becomes the origin, and write p=(a,b)  . It is then not difficult to verify that either q=(-b,a)  or q=(a,-b)  . But then a  has to be both an integer (since it is an x  -coordinate) and a multiple of \sqrt{r}  (since it is a y  -coordinate). This is a contradiction for every r  that is not a square.

From the above, we notice that infinitely many of the lattices {\mathcal L}_r  do not span any squares or equilateral triangles; for example, when r=2,5,7,8,\ldots  . It’s time to update my distinct distances open problems survey!

Advertisements

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