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.

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