The Steiner problem in normed spaces II

Other norms

In part I I discussed the Steiner problem in the Euclidean plane. Here I give an overview of various normed spaces for which geometric Steiner minimal trees have been considered. This motivates the study of Steiner minimal trees in arbitrary (finite-dimensional) normed spaces.

Continue reading

Equilateral sets in normed spaces II: lower bounds

In a previous post I explained the 2^n upper bound for the maximum number of equidistant points in an n-dimensional normed space. Lower bounds on the other hand are much more diificult to come by.

It is widely conjectured that any n-dimensional normed space has an equilateral set of at least n+1 points. This is easily seen to be true for n=2: just mimic Euclid’s proof of his Proposition 2 to construct an equilateral triangle!

Petty (1971) proved the n=3 case. He used the topological fact that a Jordan curve in the plane enclosing the origin cannot be contracted without passing through the origin at some stage. Make’ev proved the conjecture for n=4, using a lot more topology.

One obstruction is that there exists, in each dimension n\geq 4, a norm with 4 equidistant points that can not be extended to 5 equidistant points. Thus a naive induction approach does not work.

The first lower bound that goes to infinity with n was found independently by Brass and Dekster. They used Dvoretzky’s theorem to find an almost Euclidean subspace of dimension in the order of \log n, thus giving many almost equilateral sets. Then they used topology (the n-dimensional Brouwer fixed point theorem) to find an exact equilateral set. This gave a lower bound for the maximum size of an equilateral set that goes to infinity with n. At the time that their proofs appeared, the best bound in the Dvoretzky theorem was due to Gordon, and gave at least (\log n)^{1/3}.

Rafa Villa and I found a lower bound which is slightly better: e^{c\sqrt{\log n}} for some c>0. We use a result of Alon and Milman which says that if a finite dimensional normed space does not have an almost Euclidean subspace of relatively high dimension, then it must contain a relatively large subspace which is almost isometric to the infinity norm. Geometrically it says that any unit ball must have a relatively large (in the sense of dimension) central slice which is either an ellipsoid or an affine cube.

When there is a large Euclidean subspace we use the Brass-Dekster theorem. On the other hand, when there is a large \ell_\infty subspace we prove an \ell_\infty version of the Brass-Dekster theorem: all spaces close to \ell_\infty^m have at least m+1 equilateral points.

For more (as well as references), see:

  • KJ Swanepoel and R Villa, A lower bound for the equilateral number of normed spaces, Proceedings of the American Mathematical Society 136 (2008), 127-131.
  • KJ Swanepoel, Equilateral sets in finite-dimensional normed spaces. In: Seminar of Mathematical Analysis, eds. Daniel Girela Álvarez, Genaro López Acedo, Rafael Villa Caro, Secretariado de Publicationes, Universidad de Sevilla, Seville, 2004, pp. 195-237.
  • Equilateral sets in normed spaces: upper bounds

    A set S in a normed space X is equilateral if any two points of S are at the same distance:

    There exists \rho>0 such that \|x-y\|=\rho for all distinct x,y\in S.

    From now on we fix \rho=1 by scaling.

    If X is n-dimensional, then an equilateral set has at most 2^n elements (Petty 1971, Soltan 1975). The following is a very simple proof. Let P be the convex hull of S. Then the homothets x+\frac12(P-x), x\in S, are all contained in P, and have pairwise disjoint interiors. This follows from the triangle inequality. Now use the fact that the Lebesgue measure of each homothet is (1/2)^n times that of P.

    The next proof is by Füredi, Lagarias and Morgan (1993). Let A=\bigcup_{x\in S} B(x,\frac12), the union of all balls of radius \frac12 centered at the points in S. Then A has diameter 2. Now, by the isodiametric inequality (Busemann 1947, Mel’nikov 1963), the unit ball is the set of diameter 2 of largest Lebesgue volume. Again comparing volumes gives the upper bound.

    The isodiametric inequality has a simple proof from the Brunn-Minkowski inequality, so it is not surprising that there is also a proof using the latter inequality. Again consider the set A. Since it has diameter 2, its central symmetral A-A:=\{x-y : x,y\in A\} is contained in a ball of radius 2. By the Brunn-Minkowski inequality, \mu(A-A)^{1/n}\geq\mu(A)^{1/n}+\mu(-A)^{1/n}, and the 2^n upper bound follows.


    1. H. Busemann, Intrinsic area, Ann. Math. 48 (1947), 234-267. [It is quite a challenge to find the isodiametric inequality in this paper. It’s equation (2.2) on p. 241.]
    2. Z. Füredi, J. C. Lagarias, and F. Morgan, Singularities of minimal surfaces and networks and related extremal problems in Minkowski space, Discrete and computational geometry (New Brunswick, NJ, 1989/1990), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991. pp. 95-109.
    3. M. S. Mel’nikov, Dependence of volume and diameter of sets in an n-dimensional Banach space (Russian), Uspehi Mat. Nauk 18 (1963), 165-170.
    4. C. M. Petty, Equilateral sets in Minkowski spaces, Proc. Amer. Math. Soc. 29 (1971), 369-374.
    5. P. S. Soltan, Analogues of regular simplexes in normed spaces (Russian), Dokl. Akad. Nauk SSSR 222 (1975), 1303-1305. English translation: Soviet Math. Dokl. 16 (1975), 787-789.

    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.

    Continue reading

    Complex and hypercomplex Sylvester-Gallai theorems

    The following is more-or-less the content of a talk I gave at the Sächsischer Geometrietag on 7 December 2007 at the University of Magdeburg.

    In a previous post I discussed the Sylvester-Gallai theorem. It says the following:

    Theorem 1. Let \mathcal{S} be a finite set of points in \mathbb{R}^n. Suppose that the line through any two points of \mathcal{S} passes through a third point of \mathcal{S}. Then \mathcal{S} spans an affine subspace of dimension 1.

    In that post I suggested that Sylvester was motivated by a 2-dimensional counterexample of the 9 inflection points of a nonsingular cubic curve in the complex plane. Probably motivated by the same example, Jean-Paul Serre asked the following in the problem section of the American Mathematical Monthly (1961):

    Let \mathcal{S} be a finite set of points in \mathbb{C}^n. Suppose that the line through any two points of \mathcal{S} passes through a third point of \mathcal{S}. Does it follow that \mathcal{S} spans an affine subspace of dimension at most 2?

    No solution to this problem ever appeared in the Monthly. In 1986 L. M. Kelly published a proof of the following theorem.

    Continue reading

    The prehistory of the Sylvester-Gallai theorem

    In 1893 James Joseph Sylvester posed the following problem:

    Prove that it is not possible to arrange any finite number of real points so that a right line through every two of them shall pass through a third, unless they all lie in the same right line.

    This problem was subsequently solved by Tibor Gallai in 1933 and later many solutions appeared. It is nowadays known as the:

    Sylvester-Gallai Theorem. Let \mathcal{S} be a finite set of points in the plane. Suppose that the line through any two points of \mathcal{S} passes through a third point of \mathcal{S}. Then all the points of \mathcal{S} are collinear.

    Much has been written about this theorem and its history. See for example this article. Here I want to speculate about its prehistory. How did Sylvester arrive at this problem? The answer may most likely be found in this figure:

    Affine plane of order 3

    Continue reading