Dvoretzky's theorem

Last updated October 30, 2022

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.

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

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

on E satisfies:

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

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

where $\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:

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

|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

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

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,^[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]

Related Research Articles

In mathematics, more specifically in functional analysis, a Banach space is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and is complete in the sense that a Cauchy sequence of vectors always converges to a well defined limit that is within the space.

The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed vector space to make the study of the dual space "interesting". Another version of the Hahn–Banach theorem is known as the Hahn–Banach separation theorem or the hyperplane separation theorem, and has numerous uses in convex geometry.

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz. $L p$ spaces form an important class of Banach spaces in functional analysis, and of topological vector spaces. Because of their key role in the mathematical analysis of measure and probability spaces, Lebesgue spaces are used also in the theoretical discussion of problems in physics, statistics, economics, finance, engineering, and other disciplines.

In the area of mathematics known as functional analysis, a reflexive space is a locally convex topological vector space (TVS) for which the canonical evaluation map from $into its bidual is an isomorphism of TVSs. Since a normable TVS is reflexive if and only if it is semi-reflexive, every normed space is reflexive if and only if the canonical evaluation map from into its bidual is surjective; in this case the normed space is necessarily also a Banach space. In 1951, R. C. James discovered a Banach space, now known as James' space, that is not reflexive but is nevertheless isometrically isomorphic to its bidual.$

In mathematics, the uniform boundedness principle or Banach–Steinhaus theorem is one of the fundamental results in functional analysis. Together with the Hahn–Banach theorem and the open mapping theorem, it is considered one of the cornerstones of the field. In its basic form, it asserts that for a family of continuous linear operators whose domain is a Banach space, pointwise boundedness is equivalent to uniform boundedness in operator norm.

In mathematics, an isometry is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος isos meaning "equal", and μέτρον metron meaning "measure".

Vapnik–Chervonenkis theory was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

In mathematics, especially in functional analysis, the Tsirelson space is the first example of a Banach space in which neither an ℓ^p space nor a c₀ space can be embedded. The Tsirelson space is reflexive.

In mathematics, concentration of measure is a principle that is applied in measure theory, probability and combinatorics, and has consequences for other fields such as Banach space theory. Informally, it states that "A random variable that depends in a Lipschitz way on many independent variables is essentially constant".

In functional analysis and related areas of mathematics, a sequence space is a vector space whose elements are infinite sequences of real or complex numbers. Equivalently, it is a function space whose elements are functions from the natural numbers to the field K of real or complex numbers. The set of all such functions is naturally identified with the set of all possible infinite sequences with elements in K, and can be turned into a vector space under the operations of pointwise addition of functions and pointwise scalar multiplication. All sequence spaces are linear subspaces of this space. Sequence spaces are typically equipped with a norm, or at least the structure of a topological vector space.

In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).

In functional analysis, compact operators are linear operators on Banach spaces that map bounded sets to relatively compact sets. In the case of a Hilbert space H, the compact operators are the closure of the finite rank operators in the uniform operator topology. In general, operators on infinite-dimensional spaces feature properties that do not appear in the finite-dimensional case, i.e. for matrices. The compact operators are notable in that they share as much similarity with matrices as one can expect from a general operator. In particular, the spectral properties of compact operators resemble those of square matrices.

Vitali Davidovich Milman is a mathematician specializing in analysis. He is a professor at the Tel Aviv University. In the past he was a President of the Israel Mathematical Union and a member of the “Aliyah” committee of Tel Aviv University.

In mathematics, uniformly convex spaces are common examples of reflexive Banach spaces. The concept of uniform convexity was first introduced by James A. Clarkson in 1936.

In mathematics, the quotient of subspace theorem is an important property of finite-dimensional normed spaces, discovered by Vitali Milman.

In mathematics, particularly, in asymptotic convex geometry, Milman's reverse Brunn–Minkowski inequality is a result due to Vitali Milman that provides a reverse inequality to the famous Brunn–Minkowski inequality for convex bodies in n-dimensional Euclidean space Rⁿ. Namely, it bounds the volume of the Minkowski sum of two bodies from above in terms of the volumes of the bodies.

In mathematics, Schilder's theorem is a result in the large deviations theory of stochastic processes. Roughly speaking, Schilder's theorem gives an estimate for the probability that a (scaled-down) sample path of Brownian motion will stray far from the mean path. This statement is made precise using rate functions. Schilder's theorem is generalized by the Freidlin–Wentzell theorem for Itō diffusions.

<span class="mw-page-title-main">Equilateral dimension</span> Max number of equidistant points in a metric space

In mathematics, the equilateral dimension of a metric space is the maximum size of any subset of the space whose points are all at equal distances to each other. Equilateral dimension has also been called "metric dimension", but the term "metric dimension" also has many other inequivalent usages. The equilateral dimension of a $-dimensional Euclidean space is, achieved by a regular simplex, and the equilateral dimension of a -dimensional vector space with the Chebyshev distance is, achieved by a hypercube. However, the equilateral dimension of a space with the Manhattan distance is not known; Kusner's conjecture, named after Robert B. Kusner, states that it is exactly, achieved by a cross polytope.$

In mathematics, a uniformly smooth space is a normed vector space $satisfying the property that for every there exists such that if with and then$

In mathematics, specifically in functional analysis and Hilbert space theory, vector-valued Hahn–Banach theorems are generalizations of the Hahn–Banach theorems from linear functionals to linear operators valued in topological vector spaces (TVSs).

References

↑ Dvoretzky, A. (1961). "Some results on convex bodies and Banach spaces". Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960). Jerusalem: Jerusalem Academic Press. pp. 123–160.
↑ Milman, V. D. (1971). "A new proof of A. Dvoretzky's theorem on cross-sections of convex bodies". Funkcional. Anal. I Prilozhen. (in Russian). 5 (4): 28–37.
↑ Gowers, W. T. (2000). "The two cultures of mathematics". Mathematics: frontiers and perspectives. Providence, RI: Amer. Math. Soc. pp. 65–78. ISBN 978-0-8218-2070-4. The full significance of measure concentration was first realized by Vitali Milman in his revolutionary proof [Mil1971] of the theorem of Dvoretzky ... Dvoretzky's theorem, especially as proved by Milman, is a milestone in the local (that is, finite-dimensional) theory of Banach spaces. While I feel sorry for a mathematician who cannot see its intrinsic appeal, this appeal on its own does not explain the enormous influence that the proof has had, well beyond Banach space theory, as a result of planting the idea of measure concentration in the minds of many mathematicians. Huge numbers of papers have now been published exploiting this idea or giving new techniques for showing that it holds.
↑ Gordon, Y. (1985). "Some inequalities for Gaussian processes and applications". Israel Journal of Mathematics . 50 (4): 265–289. doi: 10.1007/bf02759761 .
↑ Gordon, Y. (1988). "Gaussian processes and almost spherical sections of convex bodies". Annals of Probability. 16 (1): 180–188. doi: 10.1214/aop/1176991893 .
↑ Schechtman, G. (1989). "A remark concerning the dependence on ε in Dvoretzky's theorem". Geometric aspects of functional analysis (1987–88). Lecture Notes in Math. Vol. 1376. Berlin: Springer. pp. 274–277. ISBN 978-0-387-51303-4.
↑ Alon, N.; Milman, V. D. (1983), "Embedding of $\scriptstyle \ell _{\infty }^{k}$ in finite-dimensional Banach spaces", Israel Journal of Mathematics , 45 (4): 265–280, doi: 10.1007/BF02804012 , MR 0720303 .
↑ Figiel, T.; Lindenstrauss, J.; Milman, V. D. (1976). "The dimension of almost spherical sections of convex bodies". Bull. Amer. Math. Soc. 82 (4): 575–578. doi: 10.1090/s0002-9904-1976-14108-0 ., expanded in "The dimension of almost spherical sections of convex bodies", Acta Math. 139 (1977), 53–94.

Dvoretzky's theorem

Contents

Original formulations

Further developments

Related Research Articles

References

Further reading