Randomness and Pattern

in Convex Geometric Analysis

Vitali Milman^{1}

1991 Mathematics Subject Classification: 46B, 52A

0. This text can be complemented by the survey [M96] where surprising geometric phenomena observed in high dimensional spaces are described. The presentation there is more geometric with the emphasis on convex asymptotic geometry. In this talk we try to understand the reasons behind these very unusual geometric phenomena. A perceived random nature of high dimensional spaces we observe is at the root of the reasons I will discuss in the talk and the patterns it produces create the unusual phenomena we observe.

A more technical description of the results of the Asymptotic Theory of Finite Dimensional Normed Spaces up to 1986 can be found in [M86]. The following surveys and books may complete the picture in the direction of Local Theory: [MS86], [P89], [TJ88], [LM93], [M92]. For a description of the Concentration Phenomenon technique and its applications to Functional Analysis, Probability and Discrete Mathematics, see [MS86], [M88a], [T95], [T96], [LT91], [AlSp92].

In the dictionary, “randomness” is exactly the opposite of “pattern”. Randomness means “no pattern”. But, in fact, objects created by independent identically distributed random processes, being different, are in a sense, most undistinguishable and similar in the statistical sense. It is a challenge to discover these similarities, a pattern, in very different looking objects. We will do this on the example of convex bodies and normed spaces of high dimension. In fact, when we discover very similar patterns in arbitrary, and apparently very diverse convex bodies or normed spaces of high dimension we interpret them as a manifestation of the randomness principle mentioned above.

1. We demonstrate one such pattern through the following theorem. We first put it in a non-precise “meta” form: for every convex compact body K ⊂ ℝ^{n} there corresponds an ellipsoid E_{K} of the same volume (vol K = vol E_{K}) and with the same barycenter – “a pattern” – which represents K in many respects.

To put this in an exact form we will need some notation.

Let X = (ℝ^{n}, ∥ · ∥, | · |) be a normed space equipped with a norm ∥ · ∥ and the standard euclidean norm | · |. Let D be the standard euclidean ball and K(= K_{X}) be the unit ball of the normed space (X, ∥ · ∥). We write |A| for the volume of the set A. We call the family of convex bodies {uK | u ∈ SL_{n}} associated with K the family of its positions. We have two parallel languages to describe the same results. On one hand, we construct some special ellipsoid, say E, which represents the body K (in a sense which will be specified later), but on the other hand, we may change the position of K and consider K̂ = uK, u ∈ SL_{n}, where u is chosen such that uE = λD (λ :=vol.rad. E = (|E|/|D|)^{1/n} is the volume radius of E). Then the euclidean ball λD now represents K̂; however this position of K is a specially chosen position and our “pattern” is shifted from a “special ellipsoid” to a “special position”. Below, we prefer the language of positions.

1Partially supported by a Binational US-Israel Science Foundation Grant.

Documenta Mathematica · Extra Volume ICM 1998 · II · 665–677

Theorem 1. ∃C s.t. ∀n and any four convex bodies K_{i}, i = 1, …, 4, of volume radius 1, i.e. |K_{i}| = |D|, and with 0 being the centroid of K_{i}, the following is true: there are positions K̂_{i} = u_{i}K, u_{i} ∈ SL_{n}, for every i, and a couple of orthogonal operators {v_{1}, v_{2}} ⊂ O(n) so that the body

Q = Conv[(K̂_{1} ∩ v_{1}K̂_{2}) ∪ v_{2}(K̂_{3} ∩ v_{1}K̂_{4})]

is C-close to the euclidean ball D, i.e. D/\sqrt{C} ⊂ Q ⊂ \sqrt{C}D. Moreover, (i) the probability that a randomly chosen couple {v_{1}; v_{2}} ⊂ O(n) × O(n) satisfies the theorem is very high; it is larger than 1 − 1/2^{n} (this is the reason we will call such a couple “a random couple”); (ii) for any v ∈ O(n)

vol. rad.(K̂_{1} ∩ vK̂_{2}) ≥ \frac{1}{\sqrt{C}} and vol. rad. Conv(K̂_{1} ∪ vK̂_{2}) ≤ \sqrt{C} .

(We may say that ellipsoids E_{i} = u_{i}^{−1}D represent “essential” symmetries of K, but only in an “isomorphic” sense, and not in the “isometric” one as it is usual in geometry.)

(This Theorem was proved by the author in the centrally-symmetric case; see [M96] for references. For an extension to the general case, see [MP98].)

2. To continue with examples of very “regular” asymptotic behavior of an arbitrary high dimensional space we need more notation. As before, let a normed space X = (ℝ^{n}, ∥ · ∥) be equipped with the euclidean norm | · |. Denote b = ∥Id : (ℝ^{n}, | · |) → (ℝ^{n}, ∥ · ∥)∥ and a = \frac{1}{2} Diam K_{X}. So, \frac{1}{a}|x| ≤ ∥x∥ ≤ b|x|. The dual norm ∥x∥^{∗} = sup_{y≠0} \frac{|(x,y)|}{∥y∥} is naturally defined and then b = \frac{1}{2} Diam K^{0} where the polar body K^{0} = K_{X^{∗}}, X^{∗} is the dual space to X. Let M ≡ ∫_{S^{n−1}} ∥x∥dμ(x), S^{n−1} = ∂D be the unit euclidean sphere and μ(x) be the probability rotation invariant measure on S^{n−1}. Similarly, M^{∗} is the expectation of ∥x∥^{∗} on the sphere S^{n−1}, i.e. M^{∗} = ∫_{S^{n−1}} ∥x∥^{∗}dμ(x). There is the natural geometric meaning of M^{∗} as being half of the mean width of K_{X}.

We will show below that these four numbers: a, b, M and M^{∗}, uniquely describe (but again in an “isomorphic” sense) many geometric and analytic properties of the space X (and its unit ball K_{X}). Some of these properties are quantitively described by the following parameters:

k(X)= max \{k | μ_{G_{n,k}}\{E ∈ G_{n,k} | \frac{1}{2}M|x| ≤ ∥x∥≤2M|x|, for ∀x ∈ E\}>1−\frac{k}{n+k} \},

where μ_{G_{n,k}} in the formula is the Haar probability measure on the Grassmannian manifold G_{n,k} of all k-dimensional subspaces of n-dimensional space ℝ^{n},

t(X) = min \{t | ∃u_{i} ∈ O(n) and \frac{1}{2}M · |x| ≤ \frac{1}{t} ∑_{1}^{t} ∥u_{i}x∥ ≤ 2M|x|\} .

Randomness and Pattern in Convex Geometric Analysis 667

So, k(X) is a “local” parameter, meaning it describes the behavior of the subspaces of a space which belongs to a set of properties we call “the local structure”, and t(X) is a “global” parameter because it relates to a property of the whole space. Let us also agree to write f ∼ φ when there are two universal constants (independent of anything) c_{1} and c_{2} and c_{1}φ ≤ f ≤ c_{2}φ. So the two quantities φ and f are uniformly (universally) equivalent.

Theorem 2. (i) ([M71]; [MS97]) k(X) ∼ n(\frac{M}{b})^{2}; (ii) [(BLM88]; [MS97]) t(X) ∼ (\frac{b}{M})^{2}. Therefore, these local and global parameters are related in a very precise form: k(X) · t(X) ∼ n ([MS97]).

A few comments and interpretations:

(i) For any operator A : ℓ_{2}^{n} → X we may similarly introduce M(A) = ∫_{S^{n−1}} ∥Ax∥dμ(x) and k(A) (putting ∥Ax∥ instead of ∥x∥ in the definition of k(X)). Then (i) may be rewritten in the form ∥A∥ ∼ M(A)\sqrt{n/k(A)}. Here ∥A∥ is the standard operator norm of operator A and this gives an asymptotic formula for the operator norm through the average and some geometric parameters related to the operator A.

(ii) Considering the dual space X^{∗} we have, of course, k^{∗} ≡ k(X^{∗}) ∼ n(M^{∗}/a)^{2}, meaning that a “random” orthogonal projection P_{E}K onto a subspace E of dimension k^{∗}, looks, up to a factor 4, like a euclidean ball: \frac{1}{2}M^{∗} · D(E) ⊂ P_{E}K ⊂ 2M^{∗} · D(E). Furthermore, for any integer n ≥ k ≥ k^{∗} and for a “random” subspace E, dim E = k,

Diam P_{E}K ∼ Diam K · \sqrt{k/n}

and P_{E}K ∼ M^{∗}D(E) for k ≤ k^{∗} (in particular, Diam P_{E}K is stabilized on 2M^{∗}).

So, we observe the regular decay (by a factor \sqrt{k/n}) of the diameter of a “random” k-dimensional projection of K till stabilization when this projection becomes almost a euclidean ball itself, and this fact is true for any convex centrally symmetric body – another pattern of behavior. It also provides us with an example of ”phase transition” - a typical asymptotic phenomenon as we will see also later.

For quite a long time, we have known how to write very precise estimates, reflecting different asymptotic behavior of high dimensional normed spaces. Usually, we knew that these estimates are exact on some important subclasses of spaces. However, the new ”message”, based on many recent results, indicates that, in fact, available estimates are exact for every sequence of spaces of increasing dimension (we can say, ”for every individual space”). We call such exact estimates ”asymptotic formulas”.

In the next three sections we will demonstrate more asymptotic formulas, each of which represents a specific pattern of behavior of an arbitrary high dimensional normed space. We would like to emphasize that it is less important in this presentation how these formulas look. The central issue is that such asymptotic formulas do exist and are applicable to any norm, that very little information on a norm ( or a convex body) implies deep understanding of a complicated behavior of these normed spaces.

3. Can we also describe how the ball M^{∗}D(E) is “filled” by random projections from the inside? A clear pattern of behavior is seen again in asymptotic formulas for the radius of the largest ball inscribed into the random projection P_{E}K for dim E = k, k ≫ k^{∗}. We compute it in the dual form. This means that we compute (estimate) the diameter of a random k-dimensional section of the polar body K^{0}. There is a well-known and useful fact, the so-called Low M^{∗}-estimate (see [M85], [PT86], [Gor88]), which gives a simply formulated upper bound for such sections. However, it is not exact and is far from being the asymptotic formula we are interested in. To perceive the kind of result that should be expected here, I will mention one particular fact from [GM97a]: Let k = [n/2] and r be the solution of the following equation: M^{∗}(K ∩ rD) = \frac{1}{2}r (the unique solution always exists); then the diameter of a random k-dimensional central section of K is less than 2r. On the other hand, solve the equation M^{∗}(K ∩ r_{1}D) = (1 − \frac{1}{48.36})r_{1}; a random k-dimensional section of K has diameter greater than \frac{1}{60}r_{1}.

There is a more precise form of answer which requires deeper information on the body K but is still easily computable (I am now taking a Computational Geometry point of view). Define the following functions: for k = λn, 0 < λ < 1,

S_{K}^{∗}(λ) = ∫_{E∈G_{n,k}} M^{∗}(K∩E)dμ(E) , and D_{K}(λ) = \frac{1}{2} ∫_{E∈G_{n,k}}diam (K∩E)dμ(E) .

Theorem 3 ([GM98a]). Let \frac{1}{b}D ⊂ K ⊂ aD and ab ≤ n^{t} (the non-degeneracy condition). Then ∀λ ∈ (0, 1)

S_{K}^{∗}(λ) ≤ D_{K}(λ) ≤ c′S_{K}^{∗}(λ_{1})/\sqrt{1 − λ_{2}}

for λ = λ_{1}λ_{2} (and λ_{1} − λ ≥ c′′t log n/n) and c′, c′′ two universal constants.

4. We will return to these asymptotic formulas but let us now continue our search for patterns of asymptotically “similar behavior” of any convex set in ℝ^{n}. We will now study (following [LMS98]) the geometric structure of the level sets K ∩ rS^{n−1} = A(r) and will see that, from a point of view we put forward below, these sets in some interval of values of “r” appear very similar. Define

r_{t} = min \{\frac{1}{2} Diam ⋂_{1}^{t} u_{i}K | u_{i} ∈ O(n)\} ,

and also the inverse function T (r) = min {t | ∃u_{i} ∈ O(n) and ⋂_{1}^{t} u_{i}K ⊂ rD} . (So, T (r_{t}) = t.) Of course, the meaning of T (r) is that there is a covering of rS^{n−1} by T (r) rotations of rS^{n−1}\A(r) and there is no covering with a smaller number of rotations. Again, in the interval 2/b ≤ r ≤ 1/2M the function T (r) is exactly described [LMS98]: log T (r) ≃ n/r^{2}b^{2} , although under some kind of nondegeneracy condition: br ≲ \sqrt{n/ log n} (just note that always br ≤ b/2M ≲ \sqrt{n}).

The exponential behavior of T (r) for r ≤ 1/2M (and any fixed number λ > 1 may be substituted for 2) changes to “polynomial” around level 1/M: Let T ∼ (\frac{b}{M})^{2} · \frac{1}{ε^{2}} ; then, (i) for a random choice of \{u_{i}\}_{1}^{T} ⊂ O(n), ∩u_{i}K ⊂ \frac{1+ε}{M}D, but, (ii) for any choice \{u_{i}\}_{1}^{T} ⊂ O(n), the intersection ∩u_{i}K ⊈ \frac{1}{(1+ε)M} D.

Of course, not for every spherical level r do different convex bodies look similar. Consider, for example, the unit balls of ℓ_{∞}^{n} and ℓ_{1}^{n} (the cube and the cross-polytope) normalized so that they are inscribed in the euclidean ball D of the same radius (say 1). Then the contact points with the sphere are in the first case 2^{n} and in the second, only 2n. Naturally, for r < 1 but close to 1, the level sets are completely different. So, on what level does this phenomenon of similarity of spherical level sets start? Naturally, in this language the maximal such expected level cannot be above r_{2}. So, can r_{2} be described by very little “statistical” information about K? The answer is “Yes”:

Theorem 4 ([GM97b]). (i) r_{2} ≤ \sqrt{2}D_{K}(1/2) (we introduced the average diameter D_{K}(λ) above); (ii) there are universal numbers C > 1 and 0 < c < 1 such that D_{K}(c) ≤ C · r_{2}.

I would like to recall that we also saw that D_{K}(λ) is well described by the well computable function S_{K}^{∗}(λ).

5. Much more delicate analytic information about the level sets for r < 1/M (and even slightly above this level) may, in fact, be provided in another language.

Let M_{q} = ( ∫_{S^{n−1}} ∥x∥^{q}dμ(x))^{1/q}, q ≥ 1, and let

t_{q}(X) = min \{t | ∃\{u_{i}\}_{1}^{t}⊂O(n) such that \frac{1}{2}M_{q}|x| ≤ (\frac{1}{t} ∑_{1}^{t} ∥u_{i}x∥^{q})^{1/q}≤ 2M_{q}|x|\}.

(Note, that the information on the level sets is obtained by choosing q such that r = 1/M_{q}.) Then we again have asymptotic formulas describing the behavior of M_{q} and t_{q}.

Theorem 5 ([LMS98]). (i) M_{q} ∼ M_{1} for 1 ≤ q ≤ k(X) ∼ n(M/b)^{2}, M_{q} ∼ b\sqrt{q/n} for k(X) ≤ q ≤ n and M_{q} ∼ b for q ≥ n. (Note again a “phase transition”).

(ii) t_{q} ∼ t_{1} (= t(X) ∼ (b/M)^{2}) for 1 ≤ q ≤ 2, t_{q}^{2/q} ∼ t_{1}(M_{1}/M_{q})^{2} for 2 ≤ q; again a phase transition. However, because also M_{q} has its phase transition, we have two phase transitions for the function t_{q} on the interval 1 ≤ q ≤ n: t_{q} ∼ (b/M)^{2} for 1 ≤ q ≤ 2, t_{q}^{2/q} ∼ (b/M)^{2} for 2 ≤ q ≤ k(X) and t_{q}^{2/q} ∼ n/q for k(X) ≤ q ≤ n.

6. As another example of pattern-type behavior of any convex body in ℝ^{n}, let us mention the following recent fact, proved in [ABV98]:

Theorem 6. Let K be a convex body in ℝ^{n} with 0 in its interior. For any ε > 0 the probability (measured by the standard Lebesgue measure on K) of two points, say x and y, in K having K-distance of at most t = \sqrt{2}(1 − ε), i.e. x − y ∈ tK, is at most exp{−ε^{2}n/2}. (Therefore there are exponentially many points in K such that their pairwise differences do not belong to tK for t < \sqrt{2}(1 − ε)).

So, we again see that the number “\sqrt{2}” which is natural for the euclidean ball is also the crucial bound for any other convex body K.

7. Let us return to the study of the special position of the body K (or, equivalently, the special ellipsoid) which we already encountered in Theorem 1. It is usually called the M-position of K. Its formal definition is the following. Let N(K, T) denote the covering number of K by T (i.e. the minimum number of shifts of T which cover K). Then K is in an M-position (with parameter σ > 0) if, for λ = (|K|/|D|)^{1/n}

(∗)  N(K, λD) · N(λD, K) · N(K^{0}, λD) · N(λD, K^{0}) ≤ e^{σn} .

(It is enough to assume N(K, λD) ≤ e^{σn} and (∗) will follow with a different σ_{1} = C · σ, where C is a universal number – see [MS97], [MP98].)

Theorem 7. There is a universal number σ > 0 such that any convex body K with barycenter 0 has an M-position with parameter σ (i.e. ∃u ∈ SL_{n} such that uK is in this M-position).

(For centrally symmetric K, see [M88b] or [M96] for references or the book, [P89]; extension for general convex bodies, [MP98]; generalization to centrallysymmetric p-convex bodies, [BBP95]).

This position of K gives the “correct balance” between the body K (in such a position) and the euclidean ball (or, between the norm and the euclidean structure). Let us explain this by some facts. First, we already demonstrated the use of M-position of a body K in Theorem 1. A few more facts:

Theorem 8 ([MS97]). Assume that the unit ball K of a space X = (ℝ^{n}, ∥·∥, |·|) is in an M-position. Assume further that there are {u_{i}}_{1}^{t} ⊂ O(n) and 0 < r, C < ∞ such that

r|x| ≤ \frac{1}{t} ∑_{1}^{t} ∥u_{i}x∥ ≤ Cr|x| (for all x ∈ ℝ^{n}) .

Then there is a C′, depending on t, C and the σ-constant of the M-position only, and v ∈ O(n) such that, for some r′,

r′|x| ≤ ∥x∥ + ∥vx∥ ≤ C′r′|x| (for all x ∈ ℝ^{n}) .

Note that the assumption that K is in an M-position (i.e. that the euclidean structure is specially chosen for our norm ∥ · ∥) is absolutely essential. Without this assumption, for any t ≪ n/ log n, and any λ < 1, one may construct a family of norms (for spaces of dimensions increasing to infinity) such that some average of t-rotations will be uniformly isomorphic to the euclidean norm, but no averages of λt rotations can be uniformly equivalent to any euclidean norm (for other such facts, see [MS97]).

Also we observe a remarkable “restructuring” of volume distribution over K under “random” projections where “randomness” is understood in an M-euclidean structure:

Theorem 9 ([M90]-symmetric case; [MP98]-general case). Let a convex set K with barycenter at 0 be in an M-position. Then for any 0 < λ < 1 a random orthogonal projection P_{E}K ⊂ E ∈ G_{n,[λn]} has volume ratio bounded by a constant C(λ, σ) depending only on the proportion of the space λ (dim E = [λn]) and the constant σ of the M-position. (The volume ratio of a body T is the \frac{1}{n}th power of the ratio of |T | and the volume of the maximal volume ellipsoid inscribed in T, called John’s ellipsoid of T; see [P89] for the importance of this notion in Local Theory).

8. Additional results. In this section I would like to give a brief review of a few recent developments in Local Theory/Convexity.

(i) Brascamp-Lieb inequalities and their applications. In 1989 Keith Ball [Bal89] discovered the relevance of the Brascamp-Lieb [BL76] inequalities to convex geometry. He put these inequalities in the following form:

Theorem 10. Let m ≥ n, (u_{i})_{i=1}^{m} be unit vectors in ℝ^{n} and let (c_{i})_{i=1}^{m} be positive real numbers such that ∑_{i=1}^{m} c_{i}u_{i} ⊗ u_{i} = I_{n}. Then for all non-negative functions f_{i} ∈ L_{1}(ℝ), i = 1, …, m one has

∫_{ℝ^{n}} ∏_{i=1}^{m} f_{i}^{c_{i}}(⟨x, u_{i}⟩)dx ≤ ∏_{i=1}^{m} ( ∫ f)^{c_{i}} .

The additional condition which relates the u_{i}’s and the c_{i}’s is often available in convexity and describes, for example, the isotropicity of the John ellipsoid of a given body K. The Brascamp-Lieb inequalities provide sharp upper estimates for volumes. As an application K. Ball obtained sharp upper bounds for the volumes of central linear sections of the unit cube. He also proved that the volume ratio of any symmetric convex body in ℝ^{n} is less than that of the cube [Bal89], and that the simplex has maximal volume ratio [Bal91]. This article also contains a reverse isoperimetric inequality: for every convex body K there exists an affine image T K of K such that the ratio |∂(T K)|/|T K|^{\frac{n−1}{n}} is less than the same quantity computed for the simplex (in the symmetric case, the cube is extremal). For other applications, see [SSc95], [Sc98].

A general reverse Brascamp-Lieb inequality conjectured earlier by Ball [Bal91] was proved by F. Barthe [Bar98b]. His proof uses measure transportation, a new tool started by the result of Brenier [Br91] and developed by McCann [MC95]. It provides Lieb’s general inequality and its converse altogether. This new proof allows one to settle the problem of equality cases in the applications of the Brascamp-Lieb inequality to convexity. The reverse inequality may be viewed as a generalization of the Prekopa-Leindler inequality. In particular, it provides lower estimates of volumes of convex hulls and new Brunn-Minkowski type estimates for sum of convex sets sitted in subspaces ([Bar98b]). The particular case of these inequalities which corresponds to Ball’s formulation of the Brascamp-Lieb inequalities says:

Theorem 11 ([Bar97]; [Bar98b]). Let m ≥ n, let (u_{i})_{i=1}^{m} be unit vectors in ℝ^{n} and let (c_{i})_{i=1}^{m} be positive real numbers such that ∑_{i=1}^{m} c_{i}u_{i} ⊗ u_{i} = I_{n}. Then for all non-negative functions f_{i} ∈ L_{1}(ℝ), i = 1, …, m one has

∫_{ℝ^{n}}^{∗} sup ; x=∑ c_{i}θ_{i}u_{i} ∏_{i=1}^{m} f_{i}^{c_{i}}(θ_{i})dx ≥ ∏_{i=1}^{m} ( ∫ f)^{c_{i}} .

This result allows Barthe ([Bar98b]) to find the convex bodies of extremal exterior volume ratio and to prove that among the bodies whose John ellipsoid is the Euclidean unit ball, the regular n-simplex has maximal mean width [Bar98a] (this is dual to [Sc98]).

Returning to measure transportation type results let us emphasize that thay are used together with regularity results by Caffarelli [Ca92]. Another curious and useful consequence of this combination of results is the following statement [ADM98]: Let K and T be convex open sets of the same (finite) volume; then there is a smooth measure preserving onto map φ : K → T such that K + T = {x + φ(x)|x ∈ K}. (ii) Economic embedding of n-dimensional subspaces of L_{q} to ℓ_{p}^{N}. Let us mention here a few new groups of results on embedding some classical spaces to other classical spaces which is a more traditional direction in Local Theory. First, the problem of embedding euclidean subspaces (up to a (1 + ε)-isomorphism) into different classes of normed spaces was well understood in the earlier stages of the theory (see [MS86]). Interesting additions in isometric embeddings of ℓ_{2}^{n} into ℓ_{p}^{N} were done in [M88c], [L70], [R92], [LV93], [K95].

Also, an “isomorphic form” of Dvoretzky Theorem was proved in [MS95] and [MS98] showing that ℓ_{∞}^{n} gives essentially the worst embedding of ℓ_{2}^{k} for any k > log n. More precisely, for some absolute constant K > 0 and for every n and every log n ≤ k < n, any n-dimensional normed space, X, contains a k-dimensional subspace, Y, satisfying d(Y, ℓ_{2}^{k}) ≤ K\sqrt{\frac{k}{log(1+n/k)}}, and this is exact for all the range of k for ℓ_{∞}^{n} spaces ([CP88], [Gl89]).

However, the main interest was directed to non-euclidean embeddings. First, an extremely surprising result by Johnson-Schechtman [JS82] stated that ℓ_{q}^{n} may be (1 + ε)-embedded into ℓ_{p}^{N} for p < q < 2 and N ∼ c(ε; p; q)n (for some function c(ε; p; q)). Then Schechtman [S85], [S87] discovered another simple approach to deal with the problem of economic embedding of subspaces of L_{q} into another ℓ_{p} (the so-called “empirical method”). This method is not connected with a euclidean structure and the standard use of the Concentration Phenomenon through euclidean spaces, and is equally well applied to the search for large subspaces in a given space without special consideration to the structure of the norm we are working with. It was then used in [BLM89] and [T90] and the question of economic “random” embedding of a subspace E_{n} ⊂ L_{q} of dimension n into ℓ_{p}^{N} with exact bounds on N(n) is well understood although some “residual” log n factors are still distorting the picture.

The question of “natural” embedding (as opposed to “random” embedding) of some subspaces of L_{p} in low dimensional ℓ_{p}-spaces happened to be completely different. The whole theory of such embeddings arose in [FJS91]. A few sample results follow:

Theorem 12. (i) Let R_{n} be the span of the first n Rademacher functions in L_{1}; if X is a subspace of L_{1} containing R_{n} and 2-isomorphic to ℓ_{1}^{m} then m > c^{n} for some universal c > 1 (and the same is true for n Gaussian functions).

(ii) Every norm one operator from a C(K) space which is a good isomorphism when restricted to a k-dimensional well isomorphic to euclidean subspace also preserves a subspace of dimension c^{k} (for some c > 1) which is well isomorphic to an ℓ_{∞}-space.

Another important type of embedding is a complemented embedding (i.e. embedding of a space to another space with a well bounded projection on it). The empirical method mentioned before provides good estimates for complemented embeddings as well. However additional remarkable results were achieved in [JS91] using some kind of “discrete homothety”. For example,

Theorem 13 [JS91]. If ℓ_{p}^{n} is decomposed into a direct sum X + Y with X well isomorphic to a Hilbert space, then Y is well isomorphic to an ℓ_{p}^{m}-space.

The final result given by the theorem is in a direction where some hard work was also done previously (see [BTz87]). (iii) Extension of the Dvoretzky-Rogers Lemma and corresponding factorization results. In 1988, Bourgain and Szarek [BS88] strongly improved the classical Dvoretzky-Rogers Lemma. In the form of a “proportional factorization” their result states: If X is an n-dimensional normed space, then for every δ ∈ (0, 1) one can find m ≥ (1 − δ)n and two operators α : ℓ_{2}^{m} → X, β : X → ℓ_{∞}^{m}, such that id_{2,∞} = β ∘ α and ∥α∥ · ∥β∥ ≤ C(δ) for some constant C(δ) depending on δ only. The dependence on δ was improved to C(δ) ≲ δ^{−2} in [ST89]. It is now known (see [G96], [Ru97]) that the best possible exponent on δ in the proportional Dvoretzky-Rogers factorization must lie between 1 and 1/2. (All these results have immediate application for estimating the maximal Banach-Mazur distance of ℓ_{∞}^{n} to any other n-dimensional normed space.)

It was observed in [GM97c] that the factorization result from [G96] is a consequence of a coordinate version of the Low M^{∗}-estimate. The following “coordinate” result was proved: If E is an ellipsoid then for every δ ∈ (0, 1) we can find a coordinate subspace ℝ^{σ}(= F) where σ ⊆ {1, …, n}, |σ| ≥ (1 − δ)n, such that for the orthogonal (coordinate) projection P_{F} (E),

P_{F} (E) ⊇ \frac{c\sqrt{δ}}{\sqrt{log 2/δ} M(E)}D ∩ F

(for the definition of the expectation M(E), see Sect.2). Note that the factorization discussed above is a consequence of such a coordinate estimate. There is also an extension of this fact to some general classes of bodies (instead of to an ellipsoid).

9. Isotropic positions in convex geometry. In all previous results an isomorphic view on the theory was one of the main messages. Even some definitions were done in an isomorphic form (say, a universal constant σ in the definition of an M-position or M-ellipsoid). However, it is not impossible that a more traditional isometric approach exists which would describe our isomorphic results. (K. Ball suggested such a possibility to me some time ago based on, I believe, his results which I described in 8(i); the “isotropic” view presented below is based on our joint work with Giannopoulos [GM98b].)

Let us start with the isotropic position of a centrally symmetric convex body K ⊂ ℝ^{n} equipped with an inner product (·, ·). So, K is isotropic iff |K| = 1 and there is a constant L such that

∫_{K}(f, x)(x, φ)dx = L(f, φ)

for any f and φ in ℝ^{n}. Many remarkable properties of such a position are known and well studied (see, e.g. [MP89]). But our interest is in the following remark (from the same source): Consider min_{u∈SL_{n}} ∫_{uK} |x|^{2}dx (where |x|^{2} = (x, x)). Then min. is achieved on the isotropic position.

We understand now that it is a very general fact and for many natural functionals f(uK) considered as functions defined on SL_{n} (i.e. u ∈ SL_{n}), the minimum is achieved on some kind of isotropic position (but for a measure which should be found and properly described). For example, the result of F. John about the maximal volume ellipsoid in K provides such an isotropic measure supported on contact points of K and the maximal volume ellipsoid (and the theorem is a consequence of such a general view [GM98b]). But our interest in the framework of this paper has resulted in the fact that some positions used in Asymptotic Convex Geometry (and, in fact, all important used positions we know) have an isometric description as isotropic positions which we derive by minimizing a correctly chosen functional. In such a way the very important ℓ-position, after slight modification becomes an isotropic position for some measure on the sphere. We will mention in addition only an M-position which is also an isotropic position. Indeed, let |K| = |D|, and consider the problem

min{|uK + D| | u ∈ SL_{n}} .

The minimum is achieved for some u_{0} such that the body u_{0}K + D has minimal surface area ([GM98b]) and u_{0}K is in an M-position. At the same time it is known ([Pe61], [GP98]) that a convex body T has minimal surface area iff its surface area measure (supported on S^{n−1}) is isotropic. So, an originally isomorphically defined position also has a purely isometric description. Concluding Remark. I see the results of this theory as “a window” to the World of very high degree of freedom, just examples of organized behavior we should expect in the study of that World; not a chaotic diversity, exponentially increasing with increasing degree of freedom (=dimension in the presented Theory), but on the contrary, an asymptotically well organised World with “residual freedom” reflected in our Theory in a “uniformly isomorphic” view on the results.

References

[ABV98] J. Arias-de-Reyna, K. Ball, R. Villa, Concentration of the distance in finite dimensional normed spaces, to appear in Mathematika.

[ADM98]S. Alesker, S. Dar, V.D. Milman, A remarkable measure preserving diffeomor-

phism between two convex bodies in R^{n}, to appear in Geom. Ded.

[AlSp92] N. Alon, J.H. Spencer, The Probabilistic Method, Wiley Interscience, 1992.

[Bal89] K.M. Ball, Volumes of sections of cubes and related problems. In J. Lindenstrauss, V.D. Milman, eds., GAFA Israel Seminar 1376, Springer LNM 1989.

[Bal91] , Volume ratio and a reverse isoperimetric inequality, J. London Math. Soc. 44:2 (1991),351–359.

[Bar98a] F. Barthe, An extremal property of the mean width of the simplex, to appear in Math. Annalen.

[Bar98b] , On a reverse form of the Brascamp-Lieb inequality. To appear in Invent. Math.

[Bar97] , Inégalités de Brascamp-Lieb et convexité. C.R. Acad. Sci. Paris 324 (1997), 885–888.

[BBP95] J. Bastero, J. Bernués, A. Peña, An extension of Milman’s reverse Brunn-Minkowski inequality, GAFA 5:3 (1995), 572–581.

[BS88] J. Bourgain, S.J. Szarek, The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization, Israel J. Math. 62 (1988), 169–180.

[BLM88] J. Bourgain, J. Lindenstrauss, V.D. Milman, Minkowski sums and symmetrizations, Springer LNM 1317 (1988), 44–66.

[BLM89] , Approximation of zonoids by zonotopes, Acta Math. 162:1-2 (1989), 73–141.

[BL76] H.J. Brascamp, E.H. Lieb, Best constants in Young’s inequality, its converse and its generalization to more than three functions, Adv. Math. 20 (1976), 151–173.

[BTz87] J. Bourgain, L. Tzafriri, Complements of subspaces of l_{p}^{n}, p ≥ 1, which are uniquely determined, GAFA Israel Seminar (1985/86), Springer LNM 1267 (1987), 39–52.

[Br91] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44 (1991), 375–417.

[CP] B. Carl, A. Pajor, Gelfand numbers of operators with values in Hilbert spaces, Invent. Math. 94 (1988), 479-504.

[Ca92] L.A. Caffarelli, A-priori Estimates and the Geometry of the Monge-Ampère Equation, Park City/IAS Mathematics Series II, 1992.

[FJS88] T. Figiel, W.B. Johnson, G. Schechtman, Factorizations of natural embeddings of l_{p}^{n} into L_{r}, I, Studia Math. 89:1 (1988), 79–103.

[FJS91] , Factorizations of natural embeddings of l_{p}^{n} into L_{r}, II, Pacific J. Math. 150:2 (1991), 261–277.

[G96] A.A. Giannopoulos, A proportional Dvoretzky-Rogers factorization result, Proc. Amer. Math. Soc. 124 (1996), 233–241.

[GM97a] A.A. Giannopoulos, V.D. Milman, On the diameter of proportional sections of a symmetric convex body, International Math. Res. Notices 1 (1997), 5–19.

[GM97b] , How small can the intersection of a few rotations of a symmetric convex body be?, C.R. Acad. Sci. Paris 325 (1997), 389–394.

[GM97c] , Low M^{∗}-estimates on coordinate subspaces, Journal of Funct. Analysis 147 (1997), 457–484.

[GM98a] , Mean width and diameter of proportional sections of a symmetric convex body, Journal für die reine und angewandte Mathematik 497 (1998), 113– 140.

[GM98b] , Extremal problems and isotropic positions of convex bodies, preprint.

[GPa] A.A. Giannopoulos, M. Papadimitrakis, Isotropic surface area measures, to appear in Mathematika.

[Gl89] E.D. Gluskin, Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces, Math. USSR Sbornik 64 (1989), 85-96.

[Gor88] Y. Gordon, On Milman’s inequality and random subspaces which escape through a mesh in R^{n}, Springer Lecture Notes in Mathematics 1317 (1988), 84–106.

[JS82] W.B. Johnson, G. Schechtman, Embedding l_{p}^{m} into l_{1}^{n}, Acta Math. 149:1-2 (1982), 71–85.

[JS91] , On the distance of subspaces of l_{p}^{n} to l_{p}^{k}, Trans. Amer. Math. Soc. 324:1 (1991), 319–329.

[K95] H. König, Isometric imbeddings of euclidean spaces into finite dimensional l_{p}- spaces, Banach Center Publ. 34 (1995), 79–87.

[LM93] J. Lindenstrauss, V.D. Milman, The local theory of normed spaces and its

676 V. Milman

applications to convexity. Handbook of Convex Geometry, Vol. A,B, 1149– 1220, North-Holland, Amsterdam, 1993.

[LMS98] A.E. Litvak, V.D. Milman, G. Schechtman, Averages of norms and quasi-norms, to appear in Math. Ann.; see also A.E. Litvak, V.D. Milman, G. Schechtman, Averages of norms and behavior of families of projective caps on the sphere, C.R. Acad. Sci. Paris Ser. I Math. 325:3 (1997), 289–294.

[LT91] M. Ledoux, M. Talagrand, Probability in Banach Spaces, Ergeb. Math. Grenzgeb. 3. Folge, Vol. 23 Springer, Berlin (1991).

[L70] Yu. Lyubich, On the boundary spectrum of a contraction in Minkowski spaces, Siberian Math. J. 11 (1970), 271–279.

[LV93] Yu. Lyubich, L. Vaserstein, Isometric imbeddings between classical Banach spaces, cubature formulas, and spherical designs, Geom. Ded. 47 (1993), 327– 362.

[McC95] R.J. McCann, Existence and uniqueness of monotone measure preserving maps, Duke Math. J. 80 (1995), 309-323.

[M71] V.D. Milman, New proof of the theorem of Dvoretzky on sections of convex bodies, Funct. Anal. Appl. 5 (1971), 28–37.

[M85] , Random subspaces of proportional dimension of finite dimensional normed spaces: Approach through the isoperimetric inequality, Springer Lecture Notes in Math. 1166 (1985), 106–115.

[M86] , The concentration phenomenon and linear structure of finitedimensional normed spaces, Proceedings of the ICM, Berkeley, California, USA (1986), 961-975.

[M88a] , The heritage of P. Lévy in geometrical functional analysis, Colloque Paul Lévy sur les Processus Stochastiques (Palaiseau, 1987), Asterisque 157-158 (1988), 273–301.

[M88b] , Isomorphic symmetrization and geometric inequalities, GAFA Sem. (1986/87), Springer Lecture Notes in Math. 1314 (1988), 107–131.

[M88c] , A few observations on the connections between local theory and some other fields, GAFA Sem. (1986/87), Springer LNM 1317, (1988), 283–289.

[M90] , Some geometric duality relations, C.R. Acad. Sci. Paris Ser. I Math. 310:4 (1990), 183–187.

[M92] ,Dvoretzky’s theorem–thirty years later, GAFA 2:4 (1992), 455–479.

[M96] , Surprising geometric phenomena in high-dimensional convexity theory, to appear in Proceedings of ECM2 .

[MP89] V.D. Milman, A. Pajor, Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space, Springer LNM 1376 (1989), 64–104.

[MP98] , Entropy and asymptotic geometry of non-symmetric convex bodies, preprint.

[MS86] V.D. Milman, G. Schechtman, Asymptotic Theory of Finite Dimensional Normed Spaces, Springer LNM 1200 (1986).

[MS95] , An ”isomorphic” version of Dvoretzky’s theorem, C.R. Acad. Sci. Paris Ser. I Math. 321:5 (1995), 541–544.

[MS97] , Global versus Local asymptotic theories of finite-dimensional normed spaces, Duke Math. J. 90 (1997), 73–93.

[MS98] , An ”Isomorphic” Version of Dvoretzky’s Theorem, II, to appear in Convex Geometry, MSRI Publications 34 (1998).

[PT86] A. Pajor, N. Tomczak-Jaegermann, Subspaces of small codimension of finite dimensional Banach spaces, Proc. Amer. Math. Soc. 97 (1986), 637–642.

[Pe61] C.M. Petty, Surface area of a convex body under affine transformations, Proc. Amer. Math. Soc. 12 (1961), 824–828.

[P89] G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, Cambridge Tracts in Mathematics 94 (1989).

[R92] B. Reznick, Sums of even powers of real linear forms, Memoirs AMS 96 (1992), no. 463.

[Ru97] M. Rudelson, Contact points of convex bodies, Israel J. Math. 101 (1997), 93–124.

[S85] G. Schechtman, Fine embeddings of finite-dimensional subspaces of L_{p}, 1 ≤ p < 2, into l_{1}^{m}, Proc. Amer. Math. Soc. 94:4 (1985), 617–623.

[S87] More on embedding subspaces of L_{p} in l_{r}^{n}, Compositio Math. 61:2 (1987), 159–169.

[SSc95] G. Schechtman, M. Schmuckenschläger, A concentration inequality for harmonic measures on the sphere, GAFA Sem. (1992-1994), Oper. Theory Adv. Appl. 77, Birkhauser (1995), 255–273.

[Sc98] M. Schmuckenschläger, An Extremal Property of the Regular Simplex, to appear.

[ST89] S.J. Szarek, M. Talagrand, An ”isomorphic” version of the Sauer-Shelah lemma and the Banach-Mazur distance to the cube, GAFA Sem. (1987–88), Springer Lecture Notes in Math. 1376 (1989), 105–112.

[T90] M. Talagrand, Embedding subspaces of L_{1} into l_{1}^{N}, Proc. Amer. Math. Soc. 108:2 (1990), 363–369.

[T95] , Concentration of measure and isoperimetric inequalities in product spaces. IHES Publ. Math. 81 (1995), 73–205.

[T96] , A new look at independence. Ann. Probab. 24:1 (1996), 1–34.

[TJ88] N. Tomczak-Jaegermann, Banach-Mazur Distances and Finite Dimensional Operator Ideals, Pitman Monographs 38 (1989), Pitman, London.

V. D. Milman

School of Math. Sci.,

Sackler Faculty of Exact Sciences, Tel Aviv Univ. Tel Aviv 69978, Israel 678

Documenta Mathematica · Extra Volume ICM 1998 · II ·