Isometric embeddings of finite-dimensional normed spaces

Let \ell_p^n denote the n-dimensional real space with the norm \|x\|_p=\left(\sum_{k=1}^n|x_k|^p\right)^{1/p} or \|x\|_\infty=\max_k |x_k|. In two-dimensional case n=2 it is easy to plot the unit notice the pattern: from squareness to roundness back to squareness, as p increases from 1 to \infty.

Unit spheres, from http://en.wikipedia.org/wiki/Unit_ball

In particular, \ell_1^2 and \ell_\infty^2 are isometric spaces. But n=2 is an exception: already in three dimensions we see that the unit balls are different. In \ell_1^3 it is an octahedron

Octahedron, from http://en.wikipedia.org/wiki/File:Octahedron.svg

and in \ell_1^\infty it is a hexahedron aka cube:

Cube, from http://en.wikipedia.org/wiki/File:Hexahedron.svg

They differ in the number of faces and of vertices. But how can we use this discrepancy to show that \ell_1^n and \ell_\infty^n are not isometric for n>2?

One possibility it to invoke the Mazur-Ulam theorem which states that any surjective isometry between normed spaces is affine. Then the proof is finished by observing that the unit balls differ in the number of extreme points: 2^n for \ell_\infty^n but only 2n for \ell_1^n. The high-dimensional versions of the octahedron, called cross-polytopes, have very few vertices which are, in some sense, extremely pointy (a lot of curvature must concentrate at each vertex since there are so few).

But the following proof does not rely on the Mazur-Ulam theorem and gives a stronger result:

\ell_{\infty}^n does not admit an isometric embedding into \ell_1^N for N<2^{n-1}

Note that the Mazur-Ulam theorem does not apply here, since non-surjective isometries may well be non-linear. For example, the map F\colon \ell_{\infty}^2\to \ell_{\infty}^3 defined by F(x_1,x_2)=(x_1,x_2,\sin x_2) is an isometric embedding.

Proof: Suppose F\colon \ell_\infty^n\to \ell_1^N is an isometric embedding. We may assume F(0)=0. Let V\subset \ell_\infty^n be the set of vertices of the unit cube, i.e., the set of all vectors with entries \pm 1. Note three properties of V:

  1. all points are at distance 1 from the origin
  2. all points are at distance 2 from one another
  3. the cardinality of the set is 2^n.

All these properties must be shared by W=F(V). For each vector v\in W consider its positive and negative supports \mathrm{supp}^+v=\{1\le j\le N : v_j> 0\} and \mathrm{supp}^-v=\{1\le j\le N : v_j < 0\}. Since 2^n>2N, we may assume that at least N+1 vectors in W have nonempty positive supports. It follows that at least two of them, say v' and v'', have overlapping positive supports. This creates cancellation when we compute the distance between them: \|v'-v''\|_1 < \|v'\|_1+\|v''\|_1=2, a contradiction. QED

After some tweaks the argument can be applied to e^\epsilon-biLipschitz embeddings, defined by the double inequality e^{-\epsilon}\|x-y\| \le \|F(x)-F(y)\|_{\#}\le e^{\epsilon}\|x-y\|, where \|\| and \|\|_{\#} are the norms of the domain and the target space. (I used to write 1+\epsilon in such inequalities but recently picked e^\epsilon notation from a paper by Gromov.) I give only the most straightforward modification: define \mathrm{supp}^{+\delta}v=\{1\le j\le N : v_j \ge \delta\} and \mathrm{supp}^{-\delta}v=\{1\le j\le N : v_j \le -\delta\}. Observe that with \delta=e^{-\epsilon}/N each vector of W has nonempty support of one or of the other kind. Repeating the same proof brings us to the point where \|v'-v''\|_1 \le \|v'\|_1+\|v''\|_1-2e^{-\epsilon}/N \le 2e^{\epsilon}-2e^{-\epsilon}/N. This yields e^{-\epsilon}(1+1/N)\le e^{\epsilon}, and we conclude that for N<2^{n-1} there is no e^\epsilon-biLipschitz embedding with \epsilon<\frac12\log (1+1/N). The estimate is wasteful since the 1/N bound and the support-counting argument cannot be sharp at the same time. But in any case this proof is just a toy; the real stuff can be found, for example, in the book by Milman and Schechtman.

Bonus content: there is a simple (and well-known) isometric embedding in the opposite direction, from \ell_{1}^n into \ell_\infty^N with N=2^{n-1}. It is best illustrated by an example with n=3: the vector (x_1,x_2,x_3) is mapped into the vector with coordinates x_1+x_2+x_3, x_1+x_2-x_3, x_1-x_2+x_3, x_1-x_2-x_3. At least one of the sums will have all terms of the same sign, and therefore have absolute value equal to \|x\|_1.

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