You are currently browsing the tag archive for the ‘Dvoretzky’s theorem’ tag.

A regular tetrahedron (in $\mathbb{R}^3$) can be thought of as the convex hull of four pairwise non-adjacent vertices of a regular cube. A bisecting plane parallel to a face of the cube intersects the tetrahedron in a square (one can think of this as the product of two intervals, contained as the middle slice of the join of two intervals). A plane bisecting the long diagonal of a regular cube intersects the cube in a regular hexagon. In each case, the “slice”  one obtains is “rounder” (in some sense) than the original pointy object.

The unit ball in the $L_1$ norm on $\mathbb{R}^n$ is a “diamond”, the dual polyhedron to an $n$-cube (which is the unit ball in the $L_\infty$ norm). In three dimensions, the unit cube is an octahedron, the dual of an (ordinary) cube. This is certainly a very pointy object — in fact, for very large $n$, almost all the mass of such an object is arbitrarily close to the origin (in the ordinary Euclidean norm). Suppose one intersects such a diamond with a “random” $m$-dimensional linear subspace $V$. The intersection is a polyhedron, which is the unit ball in the restriction of the $L_1$ norm to the subspace $V$. A somewhat surprising phenomenon is that when $n$ is very big compared to $m$, and $V$ is chosen “randomly”, the intersection of $V$ with this diamond is very round — i.e. a “random” small dimensional slice of $L_1$ looks like (a scaled copy of) $L_2$. In fact, one can replace $L_1$ by $L_p$ here for any $p$ (though of course, one must be a bit more precise what one means by “random”).

We can think of obtaining a “random” $m$-dimensional subspace of $n$-dimensional space by choosing $n$ linear maps $L_i \in (\mathbb{R}^m)^*:= \text{Hom}(\mathbb{R}^m,\mathbb{R})$ and using them as the co-ordinates of a linear map $L = \oplus_i L_i:\mathbb{R}^m \to \mathbb{R}^n$. For a generic choice of the $L_i$, the image has full rank, and defines an $m$-dimensional subspace. So let $\mu$ be a probability measure on $(\mathbb{R}^m)^*$, and let $L$ define a random embedding of $\mathbb{R}^m$ into $\mathbb{R}^n$. The co-ordinates of $L$ determine a finite subset of $(\mathbb{R}^m)^*$ of cardinality $n$; the uniform probability measure with this subset as support is itself a measure $\nu$, and we can easily compute that $\|L(v)\|_p = \left( \int_{\pi \in (\mathbb{R}^m)^*} |\pi(v)|^p d\nu \right)^{1/p}$. For $n$ big compared to $m$, the measure $\nu$ is almost surely very close (in the weak sense) to $\mu$.  If we choose $\mu$ to be $\text{O}(m)$-invariant, it follows that the pullback of the $L_p$ norm on $\mathbb{R}^n$ to $\mathbb{R}^m$ under a random $L$ is itself almost $\text{O}(m)$-invariant, and is therefore very nearly propotional to the $L_2$ norm. In particular, the pullback of the $L_2$ norm on $\mathbb{R}^n$ is very nearly equal to (a multiple of) the $L_2$ norm on $\mathbb{R}^m$, so (after rescaling), $L$ is very close to an isometry, and the intersection of $L(\mathbb{R}^m)$ with the unit ball in $\mathbb{R}^n$ in the $L_p$ norm is very nearly round.

Dvoretzky’s theorem says that any infinite dimensional Banach space contains finite dimensional subspaces that are arbitrarily close to $L_2$ in given finite dimension $m$. In fact, any symmetric convex body in $\mathbb{R}^n$ for large $n$ depending only on $m,\epsilon$, admits an $m$-dimensional slice which is within $\epsilon$ of being spherical. On the other hand, Pelczynski showed that any infinite dimensional subspace of $\ell_1$ contains a further subspace which is isomorphic to $\ell_1$, and is complemented in $\ell_1$; in particular, $\ell_1$ does not contain an isometric copy of $\ell_2$, or in fact of any infinite dimensional Banach space with a separable dual (I learned these facts from Assaf Naor).