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 points in spans 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 distinct distances are 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.)
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 , we define the rectangular lattice
We now show that every point set spans 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 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 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 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 for constants , such that the discriminant is not an integer square. Then the number of integers between and that can be expressed as with is .
Every distance between a pair of points of is of the form , where and . That is, every such distance is the square root of an integer between and that can be expressed as . By applying Theorem 1 with , , and , we obtain that the number of such distances is (where the constant of proportionality depends on ). Notice that in this case the discriminant is negative, and thus cannot be a square.
Disproving Erdős’ conjecture. We disprove the conjecture by showing that some of the lattices 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 is not a multiple of three and that the points of span an equilateral triangle. Denote the three vertices of this triangle as . We translate the plane so that becomes the origin. After this translation, we write and . Denote the length of an edge of the triangle as . We have
We thus have
We recall the Brahmagupta–Fibonacci identity
This inequality implies
for some integer . Since is not a multiple of three, it is impossible for to be a square, which is a contradiction. That is, for any that is not divisible by three, the points of the lattice do not span any equilateral triangles.
We next assume, for contradiction, that the points of span a square. This implies that the points of also span a right-angled isosceles triangle. As before, we denote the vertices of this triangle as , translate the plane so that becomes the origin, and write . It is then not difficult to verify that either or . But then has to be both an integer (since it is an -coordinate) and a multiple of (since it is a -coordinate). This is a contradiction for every that is not a square.
From the above, we notice that infinitely many of the lattices do not span any squares or equilateral triangles; for example, when . It’s time to update my distinct distances open problems survey!