21
$\begingroup$

Dvoretzky's theorem is a classic of convex geometry. Recently at a conference in quantum information I learned (from Patrick Hayden's talk) about a nontrivial application of the theorem to a problem in quantum cryptography (which was solved previously, but using more complicated tools). What are the unexpected applications of Dvoretzky's theorem that you have heard of, if any?

(by "unexpected" I mean applying it to a problem which is not directly connected to convex geometry, functional analysis etc. or perhaps is connected, but requires phrasing the problem in a different language in a non-obvious way)

$\endgroup$
6
  • 2
    $\begingroup$ Beautiful theorem with Ramsey theory flavor. $\endgroup$ Nov 16, 2010 at 20:14
  • $\begingroup$ As soon as I saw your title I thought of the application to quantum information theory that evidently inspired your question. $\endgroup$ Nov 16, 2010 at 20:23
  • 3
    $\begingroup$ I'd be amazed if Assaf Naor didn't have a good answer to this ... $\endgroup$
    – gowers
    Nov 16, 2010 at 20:49
  • 3
    $\begingroup$ This should be community wiki $\endgroup$
    – Yemon Choi
    Nov 16, 2010 at 22:04
  • 2
    $\begingroup$ @Alfredo: see these papers: arxiv.org/abs/0910.1189 and arxiv.org/abs/1003.4925 $\endgroup$ Oct 29, 2011 at 23:54

5 Answers 5

13
$\begingroup$

I am familiar with unexpected application of a Dvoretzky-type theorem (albeit not Dvoretzly's theorem itself) to the combinatorial theory of convex polytopes.

A theorem of Figiel, Lindenstrauss and Milman asserts that for arbitrary centrally symmetric d-dimensional polytopes P that for some absolute constant $\gamma$. $$\log f_0(P) \log f_{d-1}(P)\ge \gamma d.$$ (Here, $f_0(P)$ is the number of vertices of $P$ and $f_{d-1}(P)$ is the number of facets.) This is derived from a similar relation between the dimension of a spherical section of $P$ and that of $P*$. Dvoretzky's theorem asserts that we can find a log d dimensional spherical section and Fiegil-Lindenstraus-Milman proved that we can find a k-dimensional spherical section for $P$ and an m-dimensional spherical section for $P^*$ such that $mk \ge \gamma' d$. I dont know a different proof for this theorem.

A famous application of another Dvoretzky-type theorem is the work of Bourgain and Milman on Mahler's conjecture which derive a related inequality based on a theorem of Milman asserting that a spherical subquotients of $\delta d$ dimension always exists.

$\endgroup$
13
$\begingroup$

Lindenstrauss and Tzafriri proved that a Banach space in which every closed subspace is complemented must be isomorphic to a Hilbert space. Dvoretzky's theorem was a key ingredient in their proof (and no essentially different proof is known).

Davis and I proved that if a Banach space has non trivial type (which is equivalent to saying that $\ell_1^n$ does not uniformly embed into the space) then there is a compact non nuclear operator on the space. (An example of Pisier's suggests that the non trivial type assumption is needed, but that is still an open problem. It was observed by K. John that his space $X$ has the property that every compact operator from $X$ into its dual is nuclear.)

$\endgroup$
9
$\begingroup$

The one that Gil Kalai mentions is the best one.

Here is a couple of other applications, although they are not really applications of Dvoretsky's theorem per se.

Algebraic topology: Milman (or Gromov? or Makeev?) realized that Dvoretsky's theorem follows from the (now known to be false) Knaster conjecture in algebraic topology, in fact the conjecture implies huge improvement on the bound on the dimension of the almost spherical sections of Dvoretsky's theorem. (The dependance on d is tight but the dependance on epsilon is pretty bad). What ended up happening is that a counterexample to Knaster's conjecture comes from convex geometry. This is a result of Kashin and Szarek. But there are weak versions of the Knaster conjecture that could be true. There are some recent related results by Karasev and Dolnikov and no so recent by Burago (the known to be false, so-called topological Dvoretsky's theorem).

There are a couple of Nonlinear versions of Dvoretsky's theorem, one by Bourgain, Figiel and Milman, and a recent one conjectured by Tao and proved by Naor and Mendel.

Computer Science: The finite nonlinear Dvoretsky's theorem says that any finite space contains large subspaces that embed in $l_2$ with low distortion (when the distortion is a more than 2 or 3 one can actually find polynomial sized subspaces, while if one insists on $1+\epsilon$ distortion then the size is logarithmic). In "Ramsey partitions and proximity data structures", Naor and Mendel found some applications the partition trees of Calinescu, Karloff and Rabani tailored for this theorem to "proximity data structures" of Thorup and Zwick (CS).

Metric Geometry: The compact Dvoretsky's theorem claims that any compact space contains subspaces of large Hausdorff dimension that embed with constant distortion in an ultrametric. (Actually all the nonlinear versions factor the map into Hilbert space through an ultrametric which embeds isometrically in Hilbert space, this idea is from Linial, Bartal, Naor and Mendel - I believe). With this result, Naor observed that for any compact space of Hausdorff dimension more than n there is a surjective Lipschitz map to the n-dimensional unit ball of Euclidean space. (Why? This was easy to see).

I have often wondered about a Dvoretsky type theorem for Riemannian manifolds. Ten points for a good conjecture.

$\endgroup$
1
  • $\begingroup$ Actually, the existence surjective Lipschitz from any compact metric space of Hausdorff dimension >n to [0,1]^n is due to arxiv.org/abs/1203.0686 $\endgroup$ Feb 25, 2020 at 14:31
7
$\begingroup$

Let $X$ be a Banach space and $I: X \to X$ be the identity operator. From Dvoretzky's theorem, for any $\varepsilon > 0$ and positive integer $n$, there is a subspace $X_n \subset X$ such that $d(X_n, \ell^2_n) < 1+\varepsilon$. Then the operator $I|X_n$ is "similar" to the identity operator $\ell^2_n \to \ell^2_n$. This means that locally properties that are not true for the identity operator $\ell^2 \to \ell^2$ are also not true for the identity operator in any Banach space.

For example, the identity operator $I$ is not $(q,1)$-summing for $q<2$ (and not $q$-summing for any $q \in [1, +\infty)$.

Sorry for my English.

$\endgroup$
7
$\begingroup$

An exotic application to cosmology was suggested by K. Villaverde, O. Kosheleva, and M. Ceberio, Why Ellipsoid Constraints, Ellipsoid Clusters, and Riemannian Space-Time: Dvoretzky's Theorem Revisited.

Modern cosmology asserts that space-time is high-dimensional with some complex metric. Still, we observe a locally Euclidean metric in our four-dimensional world. Dvoretzky’s theorem explains this phenomenon: we observe a section of a high-dimensional convex unit ball, and such a section is close to an ellipsoid, implying a locally Euclidean metric.

$\endgroup$
1
  • 1
    $\begingroup$ Actually, this follows from the Milman version of Dvoretzky (that "most" low-dimensional sections are Euclidean). $\endgroup$
    – Igor Rivin
    Oct 2, 2013 at 15:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.