One of the nicest problems of combinatorial geometry was asked by Paul Erdös. Let be a set of points in . Let denote the number of pairs that are a distance of 1 apart (where we use Euclidean distance: ). Finally, let
Thus we want to find a set of points in with as many unit distance pairs as possible. The question is to determine , at least asymptotically for fixed as . This question is notoriously difficult in dimensions 2 and 3. When the dimension , the situation changes completely, due to a construction of Lenz, as written up by Erdös in 1960.
Let’s start with the simplest case: . Consider two orthogonal two-dimensional subspaces and , i.e., write
Let be the circle of radius centered at the origin in the first copy of , and the circle of radius centered at the origin in the second copy of . Then any point on is at the distance to any point on . It remains to choose and such that , choose points on and points on , and we already have unit distances. This construction of Lenz can now be fine-tuned. For example, we can let and choose the points on each circle to be vertices of different squares inscribed in the circle. This gives an additional unit distances. By choosing the radii more carefully, it is possible to obtain when is divisible by 8 or 10, and otherwise. This is indeed the maximum (apart for some small exceptions), and the full details can be found in papers by Peter Brass and Paul van Wamelen.
Now consider the next case: . Write it as the orthogonal sum of a two-dimensional subspace and a three-dimensional subspace , thus . As before, is the circle of radius centered at the origin in , but now let be the sphere of radius centered at the origin in . As before, any point on is at the distance to any point on . As before, we choose the radii appropriately. As before, choose points on and points on . As before, we obtained unit distances. So what have we gained?
The answer is that there exist points on the 2-sphere of radius with at least unit distance pairs! (Here is some absolute constant.) This observation is a construction of Erdös, Hickerson and Pach. It follows that . Erdös and Pach then used results from extremal graph theory to show that this bound is essentially correct:
Recently, in this paper I have shown that all sets of sufficiently many points in in which the number of unit distance pairs are maximized, are necessarily Lenz configurations: they are contained in some such circle and sphere in two orthogonal subspaces. The only caveat is that my proof only applies to sufficiently large n. The reason is that I use the Erdös-Simonovits stability theorem from extremal graph theory. (Unit distance graphs in do not contain .) For small n it seems that there are just too many small exceptional cases to get a straightforward induction proof going.
The same is true for all higher dimensions. For example, in
all extremal configurations are Lenz constructions, i.e., they are on 3 pairwise orthogonal circles, this time each of radius . Further details are in my paper.
P. Brass, On the maximum number of unit distances among n points in dimension four, in: Intuitive Geometry, I. Barany et al., eds., Bolyai Soc. Mathematical Studies 6 (1997) 277–290.
P. Erdös, On sets of distances of n points in Euclidean space, Magyar Tud. Akad. Mat. Kut. Int. Közl. 5 (1960), 165–169.
P. Erdös, D. Hickerson, and J. Pach, A problem of Leo Moser about repeated distances on the sphere, Amer. Math. Monthly 96 (1989), 569–575.
P. Erdös and J. Pach, Variations on the theme of repeated distances, Combinatorica 10 (1990), 261–269.
K. J. Swanepoel, Unit distances and diameters in Euclidean space, accepted by Discrete & Computational Geometry. arxiv
P. van Wamelen, The maximum number of unit distances among n points in dimension four, Beiträge Algebra Geom. 40 (1999), 475–477.