Home » Discrete Geometry » Unit distances in high dimensions: the Lenz construction

# Unit distances in high dimensions: the Lenz construction

One of the nicest problems of combinatorial geometry was asked by Paul Erdös. Let $S$ be a set of $n$ points in $\Bbb R^d$. Let $f(S)$ denote the number of pairs ${x,y}\subseteq S$ that are a distance of 1 apart (where we use Euclidean distance: $|x-y|_2=1$). Finally, let

$f_d(n) = \max{f(S):S\subset\Bbb R^d, \#S=n}.$

Thus we want to find a set of $n$ points in $\Bbb R^d$ with as many unit distance pairs as possible. The question is to determine $f_d(n)$, at least asymptotically for fixed $d$ as $n\to\infty$. This question is notoriously difficult in dimensions 2 and 3. When the dimension $d\geq 4$, 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: $\Bbb R^4$. Consider two orthogonal two-dimensional subspaces $V$ and $W$, i.e., write

$\Bbb R^4=\Bbb R^2\oplus\Bbb R^2=V\oplus W$.

Let $C_1$ be the circle of radius $r_1$ centered at the origin in the first copy of $\Bbb R^2$, and $C_2$ the circle of radius $r_2$ centered at the origin in the second copy of $\Bbb R^2$. Then any point on $C_1$ is at the distance $r_1^2+r_2^2$ to any point on $C_2$. It remains to choose $r_1$ and $r_2$ such that $r_1^2+r_2^2=1$, choose $\lfloor n/2\rfloor$ points on $C_1$ and $\lceil n/2\rceil$ points on $C_2$, and we already have $\lfloor n^2/4\rfloor$ unit distances. This construction of Lenz can now be fine-tuned. For example, we can let $r_1=r_2=1/\sqrt{2}$ and choose the points on each circle to be vertices of different squares inscribed in the circle. This gives an additional $n-O(1)$ unit distances. By choosing the radii more carefully, it is possible to obtain $\lfloor n^2/4\rfloor +n$ when $n$ is divisible by 8 or 10, and $\lfloor n^2/4\rfloor +n-1$ 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: $\Bbb R^5$. Write it as the orthogonal sum of a two-dimensional subspace $V$ and a three-dimensional subspace $W$, thus $\Bbb R^5=\Bbb R^2\oplus\Bbb R^3=V\oplus W$. As before, $C_1$ is the circle of radius $r_1$ centered at the origin in $V$, but now let $\Sigma_2$ be the sphere of radius $r_2$ centered at the origin in $W$. As before, any point on $C_1$ is at the distance $r_1^2+r_2^2$ to any point on $\Sigma_2$. As before, we choose the radii appropriately. As before, choose $\lfloor n/2\rfloor$ points on $C_1$ and $\lceil n/2\rceil$ points on $\Sigma_2$. As before, we obtained $\lfloor n^2/4\rfloor$ unit distances. So what have we gained?

The answer is that there exist $n/2$ points on the 2-sphere of radius $1/\sqrt{2}$ with at least $cn^{4/3}$ unit distance pairs! (Here $c>0$ is some absolute constant.) This observation is a construction of Erdös, Hickerson and Pach. It follows that $f_5(n)\geq n^2/4 + \Omega(n^4/3)$. Erdös and Pach then used results from extremal graph theory to show that this bound is essentially correct:

$f_5(n)= n^2/4 + \Theta(n^4/3)$.

Recently, in this paper I have shown that all sets of sufficiently many points in $\Bbb R^5$ in which the number of unit distance pairs are maximized, are necessarily Lenz configurations: they are contained in some such circle $C_1$ and sphere $\Sigma_2$ 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 $\Bbb R^5$ do not contain $K_{3,3,3}$.) 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

$\Bbb R^6=\Bbb R^2\oplus\Bbb R^2\oplus \Bbb R^2$,

all extremal configurations are Lenz constructions, i.e., they are on 3 pairwise orthogonal circles, this time each of radius $1/\sqrt{2}$. Further details are in my paper.

References.

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.