Dvoretzky's theorem

From Wikipedia, the free encyclopedia

In mathematics, Dvoretzky's theorem is an important structural theorem about normed vector spaces proved by Aryeh Dvoretzky in the early 1960s,[1] answering a question of Alexander Grothendieck. In essence, it says that every sufficiently high-dimensional normed vector space will have low-dimensional subspaces that are approximately Euclidean. Equivalently, every high-dimensional bounded symmetric convex set has low-dimensional sections that are approximately ellipsoids.

A new proof found by Vitali Milman in the 1970s[2] was one of the starting points for the development of asymptotic geometric analysis (also called asymptotic functional analysis or the local theory of Banach spaces).[3]

Original formulations

Summarize
Perspective

For every natural number k  N and every ε > 0 there exists a natural number N(k, ε)  N such that if (X, ‖·‖) is any normed space of dimension N(k, ε), there exists a subspace E  X of dimension k and a positive definite quadratic form Q on E such that the corresponding Euclidean norm

on E satisfies:

In terms of the multiplicative Banach-Mazur distance d the theorem's conclusion can be formulated as:

where denotes the standard k-dimensional Euclidean space.

Since the unit ball of every normed vector space is a bounded, symmetric, convex set and the unit ball of every Euclidean space is an ellipsoid, the theorem may also be formulated as a statement about ellipsoid sections of convex sets.

Further developments

Summarize
Perspective

In 1971, Vitali Milman gave a new proof of Dvoretzky's theorem, making use of the concentration of measure on the sphere to show that a random k-dimensional subspace satisfies the above inequality with probability very close to 1. The proof gives the sharp dependence on k:

where the constant C(ε) only depends on ε.

We can thus state: for every ε > 0 there exists a constant C(ε) > 0 such that for every normed space (X, ‖·‖) of dimension N, there exists a subspace E  X of dimension k  C(ε) log N and a Euclidean norm || on E such that

More precisely, let SN  1 denote the unit sphere with respect to some Euclidean structure Q on X, and let σ be the invariant probability measure on SN  1. Then:

  • there exists such a subspace E with
  • For any X one may choose Q so that the term in the brackets will be at most

Here c1 is a universal constant. For given X and ε, the largest possible k is denoted k*(X) and called the Dvoretzky dimension of X.

The dependence on ε was studied by Yehoram Gordon,[4][5] who showed that k*(X)  c2 ε2 log N. Another proof of this result was given by Gideon Schechtman.[6]

Noga Alon and Vitali Milman showed that the logarithmic bound on the dimension of the subspace in Dvoretzky's theorem can be significantly improved, if one is willing to accept a subspace that is close either to a Euclidean space or to a Chebyshev space. Specifically, for some constant c, every n-dimensional space has a subspace of dimension k  exp(clog N) that is close either to k
2
or to k
.[7]

Important related results were proved by Tadeusz Figiel, Joram Lindenstrauss and Milman.[8]

References

Further reading

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.