Tverberg’s theorem

At Combinatorics and More, Gil Kalai has a nice explanation of the beautiful theorems of Helly, Radon, Carathéodory, and Tverberg (here and here). I’m looking forward to the next installment.

LaTeX hints

I guess this is off-topic, but I’m always forgetting how to do stuff in \LaTeX. Here are two useful things:

Braces with labels

Do this:

$\ell_p^d=\overbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}^{m \text{ times}}\oplus\ell_p^r$

to get this:

\ell_p^d=\overbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}^{m \text{ times}}\oplus\ell_p^r

With the obvious variation

$\ell_p^d=\underbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}_{m \text{ times}}\oplus\ell_p^r$

to get this:

\ell_p^d=\underbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}_{m \text{ times}}\oplus\ell_p^r

Breaking “n-dimensional”

In order to convince \LaTeX to break n-dimensional correctly, use


(Otherwise \LaTeX will not do anything).

Latex blogs

For more serious stuff, see the Blog on Latex Matters or the Blog on Latex Matters (yes, you’re seeing double). The WordPress FAQ is also useful for latexblogging.

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.