I am wondering if anyone has an enlightening explanation of why Dvoretzky's theorem (which says that a high-dimensional convex body has an almost round central section) is true -- there are a number of proofs but all of them seem a bit technical...
$\begingroup$
$\endgroup$
13
asked Sep 29, 2013 at 19:00
-
$\begingroup$ It is at least suggestive that every ellipsoid in $\mathbb{R}^3$ has a planar section that is a circle. $\endgroup$– Joseph O'RourkeCommented Sep 29, 2013 at 19:17
-
$\begingroup$ Arelated question in $\mathbb{R}^3$ ($3$ is not usually viewed as close to infinity, but...) is: given two concentric ellipsoids $E_1, E_2,$ and letting $\chi(E)$ be the excentricity of the ellipse $E,$ what is $\min_P \max_{i=1, 2} \chi(P\cap E_i),$ where the min is taken over all planes through the origin [think of $E_1, E_2$ as the John ellipsoids of some $K$] $\endgroup$– Igor RivinCommented Sep 29, 2013 at 19:22
-
2$\begingroup$ Do you accept concentration of measure (and specifically, Levy's theorem that Lipschitz functions on a high-dimensional sphere are almost constant outside of a set of very small measure) as intuitive? From that theorem it is not hard to show that if a convex body is somewhat round, then most of its low-dim slices will be very round, which is already a large part of Milman's proof of Dvoretzky's thm. $\endgroup$– Terry TaoCommented Sep 30, 2013 at 4:20
-
$\begingroup$ @TerryTao I certainly do not deny concentration of measure, the question is whether it is intuitive (or can be made intuitive). What's your take on this? $\endgroup$– Igor RivinCommented Sep 30, 2013 at 4:44
-
2$\begingroup$ Personally, my take is that measure concentration is initially decidedly unintuitive, because it's an intrinsically high-dimensional phenomenon, and our intuition is trained by two- and three-dimensional experience. You could say the same thing about Dvoretzky's theorem itself. Working in high dimensions requires (in part) retraining your intuition to encompass measure concentration. Once you've done that, Terry's one-line summary gives you most of Milman's proof: the norm corresponding to your convex body is almost constant on most of the sphere. $\endgroup$– Mark MeckesCommented Sep 30, 2013 at 11:53
|
Show 8 more comments
2 Answers
$\begingroup$
$\endgroup$
2
There is a more difficult proof than the quantitative finite dimensional proofs that gives only the qualitative version of Dvoretzky's theorem but is arguably more intuitive. You use Ramsey's theorem to prove that if $X$ is an infinite dimensional Banach space, then there is a Banach space $Y$ that has a monotonely unconditional basis $(e_n)$ s.t. $(e_n)$ is isometrically equivalent to every subsequence of itself and such that $Y$ is finitely representable in $X$ (meaning that for every $\epsilon > 0$, every finite dimensional subspace of $Y$ is $1+\epsilon$-isomorphic to a subspace of $X$). This is at the beginning of the Brunel-Sucheston spreading model theory and is elementary. So $Y$ looks a bit like the spaces $\ell_p$, $1\le p < \infty$, and $c_0$. Now $c_0$ is universal for finite dimensional spaces (up to $1+\epsilon$), and $L_p$ for all $p$ contains $\ell_2$ isometrically (span of IID $N(0,1)$ random variables when $p<\infty$), and $L_p$ is finitely representable in $\ell_p$, so this is a pretty good hint that Dvoretzky's theorem is true. To finish the proof, just apply Krivine's theorem, which says that for some $1\le p \le \infty$, the space $\ell_p$ is finitely represented in $Y$ (in fact, for each $n$ there are disjointly supported elements in $Y$ that are $1+\epsilon$-equivalent to the unit vector basis of $\ell_p^n$). Krivine's theorem is proved in the Springer Lecture Notes volume written by V. Milman and S. Schechtman.
If you are willing to settle for subspaces of $Y$ that are just uniformly isomorphic to $\ell_2^n$, you can replace Krivine's theorem with more elementary arguments. Tzfriri did that in
Tzafriri, L. On Banach spaces with unconditional bases. Israel J. Math. 17 (1974), 84–93.
answered Sep 29, 2013 at 20:26
-
$\begingroup$ I will need to digest this... I guess one question is: why did Grothendieck suspect Dvoretzky's theorem was true? $\endgroup$ Commented Sep 30, 2013 at 1:26
-
$\begingroup$ Grothendieck knew the Dvoretzky-Rogers theorem, which I guess is some evidence. He had another proof of an important application of the D-R theorem that motivated the discovery of the theorem (namely, that in every infinite dimensional Banach space there is an unconditionally converging series that is not absolutely convergent). Actually, these days the D-R theorem is considered the most difficult step in the proof of Dvoretzky's theorem. $\endgroup$ Commented Sep 30, 2013 at 4:25
$\begingroup$
$\endgroup$
8
To develop some intuition, the following argument might help, suggested (and dismissed) by K. Villaverde, O. Kosheleva, and M. Ceberio, Why Ellipsoid Constraints, Ellipsoid Clusters, and Riemannian Space-Time: Dvoretzky's Theorem Revisited.
A stronger version of Dvoretzky’s theorem (due to Milman) asserts that almost all low-dimensional sections of a convex set have an almost ellipsoidal shape. An $n$-dimensional section consists of points $(x_1,x_2,\ldots x_n)$ such that $g(x_1,x_2,\ldots x_n)\leq 0$. Generically, this function $g$ will be smooth and a Taylor expansion to second order would be a good approximation, $$\sum_{i,j=1}^n a_{ij}x_i x_j+\sum_{i=1}^n b_i x_i \leq a_0,$$ producing an ellipsoid.
answered Sep 29, 2013 at 20:41
-
$\begingroup$ I am a little confused -- low-dimensional sections have an almost SPHERICAL shape (and Milman, as you say, makes this into a "most sections" statement). Also, in the paper you mention they seem to use Dvoretzky's theorem (rather than give any sort of argument for it). Am I confused? $\endgroup$ Commented Sep 29, 2013 at 20:46
-
$\begingroup$ @IgorRivin --- my very limited understanding of Dvoretzky/Milman is based on Keith Ball's "Elementary Introduction to Modern Convex Geometry", where it is shown that "any symmetric convex body in $R^n$ has almost ellipsoidal sections of dimension about $\log n$." I would be surprised if almost all sections would be spherical, ellipsoidal seems the generic thing to expect. $\endgroup$ Commented Sep 29, 2013 at 21:13
-
1$\begingroup$ @IgorRivin : perhaps you should ask why high dimensional ellipsoids have large almost spherical sections, intuitively ? $\endgroup$– BS.Commented Sep 30, 2013 at 7:06
-
1$\begingroup$ Milman's proof shows that after applying a linear transformation, most low-dimensional sections have an almost spherical shape. Applying the inverse transformation, you get almost ellipsoidal sections, but the "most" part gets lost. But, since ellipsoids have (about half-dimensional) precisely spherical sections, you still get almost spherical sections of the original body. I'm sure I've seen a short proof of the existence of spherical sections of ellipsoids in some lecture notes by Schechtman, but I can't find it now. $\endgroup$ Commented Sep 30, 2013 at 12:06
-
3$\begingroup$ @Mark and Igor : the half dimension of spherical section is the clue ! Let the ellipsoid be $\sum_1^{2k} a_i x_i^2=1$ and $(a_i)_{i=1..2k}$ be increasing. Take $c$ in $[a_k,a_{k+1}]$. Then the subspace $x_{k+1-i}=t_ix_i$, $i=1..k$ will do the job if $a_i+t_i^2 a_{k+1-i}=(1+t_i^2) c$, which is possible by choice of $c$ (maybe with infinite $t_i$). An obvious adaptation works in the odd $2k+1$ dimensional case, giving a $k+1$-dim spherical section. $\endgroup$– BS.Commented Sep 30, 2013 at 12:33