Dvoretzky's theorem

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 (also called asymptotic functional analysis or the local theory of Banach spaces).^[3]

Original formulations[]

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 quadratic form Q on E such that the corresponding Euclidean norm

${\displaystyle |\cdot |={\sqrt {Q(\cdot )}}}$

on E satisfies:

${\displaystyle |x|\leq \|x\|\leq (1+\varepsilon )|x|\quad {\text{for every}}\ x\in E.}$

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

${\displaystyle d(E,\ \ell _{k}^{2})\leq 1+\varepsilon }$

where ${\displaystyle \ell _{k}^{2}}$ 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[]

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:

${\displaystyle N(k,\varepsilon )\leq \exp(C(\varepsilon )k)}$

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

We can thus state: for every ε > 0 and 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

${\displaystyle |x|\leq \|x\|\leq (1+\varepsilon )|x|\quad {\text{for every}}\ x\in E.}$

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

• there exists such a subspace E with

${\displaystyle k=\dim E\geq C(\varepsilon )\,\left({\frac {\int _{S^{N-1}}\|\xi \|\,d\sigma (\xi )}{\max _{\xi \in S^{N-1}}\|\xi \|}}\right)^{2}\,N.}$

• For any X one may choose Q so that the term in the brackets will be at most

${\displaystyle c_{1}{\sqrt {\frac {\log N}{N}}}.}$

Here c₁ is a universal constant. For given X and ε, the largest possible k is denoted k_*(X) and called the of X.

The dependence on ε was studied by ,^[4][5] who showed that k_*(X) ≥ c₂ ε² 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(c√log N) that is close either to ℓ^k
₂ or to ℓ^k
_∞.^[7]

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

References[]

Further reading[]

• Vershynin, Roman (2018). "Dvoretzky–Milman Theorem". High-Dimensional Probability : An Introduction with Applications in Data Science. Cambridge University Press. pp. 254–264. doi:10.1017/9781108231596.014.