Dvoretzky's theorem

Summarize Timeline Fact Check

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

${\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.

As a consequence, we have the following statement. For any ${\displaystyle \epsilon >0}$, we call a ${\displaystyle \epsilon }$-sphere a convex body ${\displaystyle K}$ such that there exists a ball ${\displaystyle B}$, such that ${\displaystyle B\subset K\subset (1+\epsilon )B}$. Then, for any integer ${\displaystyle n}$ and any ${\displaystyle \epsilon \in (0,1)}$, for all large enough ${\displaystyle N}$, and any ${\displaystyle N}$-dimensional centrally symmetric body, there exists an ${\displaystyle n}$-dimensional subspace ${\displaystyle V\subset \mathbb {R} ^{N}}$, such that ${\displaystyle K\cap V}$ is an ${\displaystyle \epsilon }$-sphere.^[4]

Summarize Timeline Fact Check

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 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

${\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 Dvoretzky dimension of X.

The dependence on ε was studied by Yehoram Gordon,^[5][6] who showed that k_*(X) ≥ c₂ ε² log N. Another proof of this result was given by Gideon Schechtman.^[7]

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
_∞.^[8]

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