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

On Equilateral Simplices in Normed Spaces

Dedicated to Prof. H. Harborth on occasion of his sixtieth birthday

Peter Braß

Institut für Informatik, FU Berlin D-14195 Berlin, Germany

Abstract. It is the aim of this note to improve the lower bound for the problem of Petty on the existence of equilateral simplices in normed spaces. We show that for each k there is a d(k) such that each normed space of dimension d ≥ d(k) contains k points at pairwise distance one, and that if the norm is sufficiently near to the euclidean norm, the maximal equilateral sets behave like their euclidean counterparts.

1. Introduction

The question whether each d-dimensional normed space contains d + 1 points at pairwise distance one, i.e. an equilateral simplex, was first raised by Petty in 1971 [7]. This seems obvious at first, especially in the equivalent packing version: each convex body K admits a packing (K + t_{i})_{i=1}^{d+1} of d + 1 pairwise touching translates. But it turned out much more difficult, as illustrated by the following near-counterexample constructed by Petty: define a norm on IR^{d} by ∥(x_{1}, …, x_{d})∥ := |x_{1}| + \sqrt{x_{2}^{2} + ⋯ + x_{d}^{2}}, so the unit ball is a double cone over a (d−1)-dimensional euclidean ball (Figure 1). Start with the two points (0, 0, …, 0) and (1, 0, …, 0) (the center of that double cone and one apex). Then any further point with distance one to both these points must be of the form (\frac{1}{2}, x_{2}, …, x_{d}) with \sqrt{x_{2}^{2} + ⋯ + x_{d}^{2}} = \frac{1}{2}. So all possible extensions of these two starting points to larger equilateral sets lie on a (d−1)-dimensional euclidean sphere with radius \frac{1}{2}, which admits at most two points with pairwise distance one. So there are norms in IR^{d} for which there exist nonextendable equilateral sets of four points. Petty also showed that each normed space of dimension at least three contains four points at pairwise distance one; in fact, each equilateral set of less than four points can be extended to a four-point set. He conjectured that each normed space contains d+1 points at pairwise distance one; this conjecture occurs also in the book of Thompson [11, Problem 4.1.1], but no progress was made beyond the lower bound of four ([4], [6]). There are, of course, normed spaces that admit much larger equilateral sets, the upper bound is 2^{d} [9], as reached by the maximum norm. For further material on equilateral and few-distance sets in normed spaces see [10], for combinatorial distance problems also [1]. In this note, we show:

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

Theorem 1. For each k there is a d(k) such that each normed space of dimension d ≥ d(k) contains k points at pairwise distance one.

This follows by an application of Dvoretzky’s theorem from

Theorem 2. For each dimension d there is a ε_{d}^{∗} > 0 such that if (V, ∥·∥) is a d-dimensional normed space with

(1 − ε_{d}^{∗})∥x∥_{euclidean} ≤ ∥x∥ ≤ (1 + ε_{d}^{∗})∥x∥_{euclidean}  for all x ∈ V,  (∗)

then each equilateral set in V can be extended to an equilateral set of d + 1 points.

So if the norm is sufficiently near to a euclidean norm, then the equilateral sets behave like euclidean equilateral sets: they can be freely rotated, without ‘forbidden directions’ as in Petty’s double-cone example.

Figure 1

2. Proof of the theorems

Metric spaces (M, dist(·, ·)) that are realizable in euclidean d-dimensional space have been characterized by Menger [5] using the sign of the Cayley-Menger determinant CMD(p_{1}, …, p_{k}) of subsets p_{1}, …, p_{k} ∈ M. Here CMD(p_{1}, …, p_{k}) is the determinant of the (k + 1) × (k + 1)-matrix with 0’s in the main diagonal, 1’s in the first column and

first row, and the squared distance (dist(p_{i}, p_{j}))^{2} at position (i + 1), (j + 1).

Theorem 3. (Menger [5]) A metric space (M, dist(·, ·)) is realizable in euclidean d-dimen-sional space if and only if one of the following conditions is satisfied:

(1) |M| ≤ d and M is realizable in (d−1)-dimensional space.

(2) |M| = d + 1, (−1)^{d+1} CMD(M) ≥ 0 and each subset of d points of M is realizable in (d−1)-dimensional space.

(3) |M| = d + 2, CMD(M) = 0 and each subset of d + 1 points of M is realizable in d-dimensional space.

(4) |M| = d + 3, CMD(M) = 0 and each subset of d + 2 points of M is realizable in d-dimensional space.

(5) |M| ≥ d + 4 and each subset of d + 2 points of M is realizable in d-dimensional space.

It is an immediate consequence of this characterization that a whole neighbourhood of the d-dimensional regular unit simplex (d + 1 points with all pairwise distances one) is realizable in euclidean d-space: The realizability of a (d+1)-point set depends only on the sign conditions of Cayley-Menger determinants of the subsets, which are satisfied for dist(p_{i}, p_{j}) ≡ 1, and will remain satisfied by continuity if we change each distance independently by a small amount from one. The exact maximum amount how much we may change the distances and still always remain realizable has been determined by Dekster and Wilker [2].

Theorem 4. (Dekster, Wilker [2]) Let ε_{d} := \frac{2d + 2}{d^{2} + 2d} (1 + \sqrt{\frac{d^{2} − 2}{d^{2} + 2d}})^{−2} for d even and

ε_{d} := \frac{2}{d + 1} (1 + \sqrt{\frac{d − 1}{d + 1}})^{−2} for d odd. Then

(1) each metric space of d + 1 points whose distances are all in the interval [1 − ε_{d}, 1 + ε_{d}] can be realized in euclidean d-dimensional space.

(2) each metric space of d + 1 points whose distances are all in the open interval ]1 − ε_{d}, 1 + ε_{d}[ cannot be realized in euclidean (d−1)-dimensional space.

The given value of ε_{d} is best possible; the limiting situation (in which the determinant vanishes and the set collapses to a (d−1)-dimensional realization) is given by a minimumdiameter two-distance set of d + 1 points in (d−1)-dimensional space. This consists of two regular simplices of ⌊\frac{d+1}{2}⌋ and ⌈\frac{d+1}{2}⌉ points in orthogonal subspaces, with a common center and with edgelength 1 − ε_{d}; the distance of points in distinct simplices is then 1 + ε_{d} [2]. This is also equivalent to a minimum-diameter packing of d + 2 unit balls in dimension d.

Using this theorem, we now prove Theorem 2. Let (V, ∥·∥) be a d-dimensional normed space with property (∗) for the ε_{d}^{∗} := \frac{1}{2}ε_{d} of Theorem 4. Let p_{1}, …, p_{k} be a set of points in V with pairwise distance one with respect to that norm. We first note that k is at most d + 1; for otherwise we had a set of d + 2 points in euclidean d-dimensional space with pairwise distances between (1 + ε_{d}^{∗})^{−1} and (1 − ε_{d}^{∗})^{−1}, contradicting the second assertion of Theorem 4.

To prove Theorem 2, we have to show that for k ≤ d there is an extension point p_{k+1} that also has distance one to p_{1}, …, p_{k}. For this we select a k-dimensional linear subspace V_{k} ⊆ V that contains p_{2} − p_{1}, …, p_{k} − p_{1} and one further dimension, and a halfspace H in the affine space p_{1} + V_{k} that is bounded by the hyperplane through p_{1}, …, p_{k}.

The points p_{1}, …, p_{k} have pairwise distances one with respect to the norm, so their pairwise euclidean distances are in the interval [(1+ε_{d}^{∗})^{−1}, (1−ε_{d}^{∗})^{−1}] ⊂ [1−ε_{d}, 1+ε_{d}] = : I_{d}. By the Theorem 4 we can prescribe arbitrary euclidean distances d_{1}, …, d_{k} in the interval I_{d} from a further point x to the points p_{1}, …, p_{k}, and always find a euclidean realization. This realization is made unique by choosing the point x from the halfspace H. So we can apply these distances as coordinates for a well-defined point p(d_{1}, …, d_{k}); this defines a continuous mapping from I_{d}^{d} into H. For this point p(d_{1}, …, d_{k}) we can again determine the norm distances to p_{1}, …, p_{k}; by property (∗) we have

∥p(d_{1}, …, d_{k}) − p_{i}∥ ∈ [(1 − ε_{d}^{∗})d_{i}, (1 + ε_{d}^{∗})d_{i}] ,

and we search for a point for which each of these norm distances is one.

We now consider the mapping ϕ: (x_{1}, …, x_{d}) ↦ (y_{1}, …, y_{d}) defined by

y_{i} := x_{i} + (1 − ∥p(x_{1}, …, x_{k}) − p_{i}∥) for i = 1, …, k.

This is a continuous mapping which maps the compact set I_{d}^{d} into itself, for

1 + ε_{d} ≥ 1 + ε_{d}^{∗}(1 + ε_{d})
≥ 1 + ε_{d}^{∗}x_{i} = 1 + x_{i} − (1 − ε_{d}^{∗})x_{i}
≥ 1 + x_{i} − ∥p(x_{1}, …, x_{k}) − p_{i}∥ = : y_{i}
≥ 1 + x_{i} − (1 + ε_{d}^{∗})x_{i} = 1 − ε_{d}^{∗}x_{i}
≥ 1 − ε_{d}^{∗}(1 + ε_{d})
≥ 1 − ε_{d} .

By Brouwer’s Fixed-point Theorem this mapping has a fixed point (x_{1}, …, x_{d}) ∈ I_{d}^{d}; for this point the correction terms in each coordinate vanish, so ∥p(x_{1}, …, x_{k}) − p_{i}∥ = 1 for each i. Therefore p_{k+1} := p(x_{1}, …, x_{k}) is the point extending p_{1}, …, p_{k} to a bigger set of points with pairwise distance one. This completes the proof of Theorem 2.

Theorem 1 follows from Theorem 2 by application of a theorem of Dvoretzky ([3], [12]) which states that for each dimension d and each ε there is a d′ such that each normed space of dimension at least d′ has a subspace of dimension d that is ε-near to a euclidean space in the sense required by Theorem 2. This completes the proof.

To obtain an estimate for the function d(k) of Theorem 1, we can use that the d′ in Dvoretzky’s theorem can be chosen less than e^{cdε^{−2} log \frac{1}{ε}} (but there are examples that require at least d′ > e^{ĉd log \frac{1}{ε}}) for some c > 0 [12]. Since we require the k-dimensional subspace to be ε_{k}^{∗}-near to a euclidean space, and ε_{k}^{∗} = \frac{1}{4k} + o(\frac{1}{k}), we get an upper bound of d(k) < e^{ck^{3} log k}.

References

[1] Braß, P.: Erdős distance problems in normed spaces. Comput. Geom. 6 (1996), 195–214.

[2] Dekster, B. V.; Wilker, J. B.: Edge lengths guaranteed to form a simplex. Arch. Math. 49 (1987), 351–366.

[3] Dvoretzky, A.: Some results on convex bodies and Banach spaces. Proc. Symp. on Linear Spaces (1961), 123–160.

[4] Lawlor, G.; Morgan, F.: Paired calibrations applied to soap films, immiscible fluids, and surfaces or networks minimizing other norms. Pacific J. Math. 166 (1994), 55–83.

[5] Menger, K.: Untersuchungen über allgemeine Metrik. Math. Ann. 100 (1928), 75– 163.

[6] Morgan, F.: Minimal surfaces, crystals, shortest networks and undergraduate research. Math. Intelligencer 14/3 (1992), 37–44.

[7] Petty, C. M.: Equilateral sets in Minkowski spaces. Proc. Amer. Math. Soc. 29 (1971), 369–374.

[8] Piepmeyer, L.: Punktmengen mit minimaler Anzahl verschiedener Abstände. Dissertation, TU Braunschweig 1993.

[9] Soltan, P. S.: Analogues of regular simplices in normed spaces. Sov. Math. Dokl. 16 (1975), 787–789.

[10] Swanepoel, K. J.: Cardinalities of k-distance sets in Minkowski spaces. To appear in Discrete Math.

[11] Thompson, A. C.: Minkowski geometry. Encyclopedia Math. Appl. 63, Cambridge Univ. Press 1996.

[12] Zong, C.: Strange phenomena in convex and discrete geometry. Springer-Verlag 1996.

Received January 20, 1998