Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 2, 475-477.

The Maximum Number of Unit Distances Among n Points in Dimension Four

Paul van Wamelen

Department of Mathematics, Louisiana State University Baton Rouge, LA 70803-4918, U.S.A. e-mail: wamelen@math.lsu.edu

Abstract. We complete P. Brass’ determination of the maximum number of unit distances that can occur among n points in dimension 4.

1. Introduction

The problem of finding the maximal number of unit distances that can occur among n points in various dimensions is a well-known problem in combinatorial geometry. In [2] P. Brass gives an intricate argument proving a formula for the exact maximum number of unit distances that can occur in ℝ^{4}. He showed that for n ≥ 10 the extremal sets consist of n points equally distributed on two circles in orthogonal planes with a common center such that each point on one circle has distance one to each point on the other (so r_{1}^{2} + r_{2}^{2} = 1), and such that the number of unit distances within each circle is maximal. This maximum, for m points, occurs if the graph of unit distances is a union of cycles (giving m unit distances) or a path with m − 1 unit distances. In order to fit cycles on both circles the following equation must have a solution,

(sin \frac{ν_{1}π}{⌊\frac{1}{2}n⌋})^{−2} + (sin \frac{ν_{2}π}{⌈\frac{1}{2}n⌉})^{−2} = 4,  (1)

with ν_{1}, ν_{2} ∈ ℕ and ν_{1}, ν_{2} < \frac{n}{2}. In this paper we determine exactly those n for which this equation has solutions. Combining this with Brass’ result leads to a very simple formula for the maximum number of unit distances among n points in dimension 4.

See Brass’ article [2] for more background and references to other results in this field.

I would like to thank K. J. Swanepoel for bringing this problem to my attention.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1999 Heldermann Verlag

476 P. van Wamelen: The Maximum Number of Unit Distances …

2. The theorems

Lemma 1. The only solutions to the equation

\frac{1}{sin^{2}(pπ)} + \frac{1}{sin^{2}(qπ)} = 4, with p, q ∈ ℚ ∩ [0, \frac{1}{2}] and p ≤ q

are

p = \frac{1}{4} and q = \frac{1}{4},

or

p = \frac{1}{5} and q = \frac{2}{5}.

Note that, as sin^{2}(pπ) = sin^{2}((1 − p)π), all solutions with p, q ∈ ℚ can be generated from those given.

Proof. In [1] D. H. Lehmer shows that for an integer i > 2 and an integer s relatively prime to i, cos(\frac{s}{i}2π) is an algebraic number of degree ϕ(i)/2 (where ϕ is the Euler Totient function) and that its conjugates are the cos(\frac{s′}{i} 2π) with s′ relatively prime to i. Using the identity cos(\frac{s}{i}2π) = 1 − 2 sin^{2}(\frac{s}{i}π) we immediately see that

\frac{1}{sin^{2}(sπ/i)}

is an algebraic integer of degree ϕ(i)/2 and it’s conjugates are all \frac{1}{sin^{2}(s′π/i)} with s′ prime to i. Now suppose

\frac{1}{sin^{2}(sπ/i)} + \frac{1}{sin^{2}(rπ/j)} = 4  (2)

with (i, s) = 1, (j, r) = 1 and i ≥ j. Let p(x) be the minimal polynomial for \frac{1}{sin^{2}(sπ/i)} and q(x) the minimal polynomial for \frac{1}{sin^{2}(rπ/j)}. Then equation (2) expresses the fact that p(x) and q(4 − x) have a root in common. As they are both irreducible they must have all their roots in common. But \frac{1}{sin^{2}(π/i)} is a root of p(x) and so we see that 4 − \frac{1}{sin^{2}(π/i)} is a root of q(x). Therefore there must exist an r′ (relatively prime to j) such that \frac{1}{sin^{2}(r′π/j)} = 4− \frac{1}{sin^{2}(π/i)}. But if i ≥ 6, then the right hand side of this equation is ≤ 0 while the left hand side is positive. We conclude that for equation (2) to hold we must have i, j ≤ 5. This leaves only a finite number of cases to check and we find that essentially the only solutions are

\frac{1}{sin^{2}(π/4)} + \frac{1}{sin^{2}(π/4)} = 4

and

\frac{1}{sin^{2}(π/5)} + \frac{1}{sin^{2}(2π/5)} = 4.  □

Now we apply this result to Brass’ formula.

Theorem 1. The maximum number of unit distances among n ≥ 5 points in ℝ^{4} is

\begin{cases}⌊\frac{1}{4}n^{2}⌋ + n & if 8 | n or 10 | n, \\ ⌊\frac{1}{4}n^{2}⌋ + n − 1 & otherwise. \end{cases}

Proof. In [2] Brass shows that this number is ⌊\frac{1}{4}n^{2}⌋+n if (1) has a solution and ⌊\frac{1}{4}n^{2}⌋+n−1 otherwise. From Lemma 1 we see that (1) only has a solution if _{\frac{ν_{1}}{⌊\frac{1}{2} n⌋}} and _{\frac{ν_{2}}{⌈\frac{1}{2} n⌉}}, in reduced

form, have the same denominators. As these denominators must be either both 4 or both 5, we see that ⌊\frac{1}{2}n⌋ − ⌈\frac{1}{2}n⌉ must be divisible by 4 or 5. This can only happen if ⌊\frac{1}{2}n⌋ = ⌈\frac{1}{2}n⌉. So n must be even. Furthermore ⌊\frac{1}{2}n⌋ must be divisible by 4 or 5. So (1) can only have solutions if 8 | n or 10 | n (and then (1) will have solutions). This proves the theorem. □

So we see that the extremal sets have the following structure. If 8 | n, two orthogonal circles of radius \frac{1}{\sqrt{2}}, with the \frac{n}{2} points arranged on each in \frac{n}{8} inscribed squares of sidelength one; and for 10 | n two orthogonal circles of radii \frac{1}{2 sin \frac{π}{5}} and \frac{1}{2 sin \frac{2π}{5}} , with the \frac{n}{2} points arranged on each in \frac{n}{10} inscribed regular pentagons of sidelength one and diagonal length one, respectively. For the other n, one radius is chosen such that ⌊\frac{n}{2}⌋ (or ⌈\frac{n}{2}⌉) points can form unit distance cycles on one circle and the remaining points on the other circle form a unit distance path.

References

[1] Lehmer, D. H.: A Note on Trigonometric Algebraic Numbers. Amer. Math. Monthly 40 (1933), 165–166.

[2] Brass, P.: On the maximum number of unit distances among n points in dimension four. Intuitive Geometry (Budapest 1995), Bolyai Soc. Math. Stud. 6 (1997), 277–290.

Received June 24, 1998