LOW M^{∗}-ESTIMATES ON COORDINATE SUBSPACES

A. A. GIANNOPOULOS AND V. D. MILMAN

Abstract. Let K be a symmetric convex body in R^{n}. It is well-known that for every θ ∈ (0, 1) there exists a subspace F of R^{n} with dim F = [(1 − θ)n] such that

(∗)  P_{F} (K) ⊇ \frac{c\sqrt{θ}}{M_{K}} D_{n} ∩ F,

where P_{F} denotes the orthogonal projection onto F. Consider a fixed coordinate system in R^{n}. We study the question whether an analogue of (∗) can be obtained when one is restricted to choose F among the coordinate subspaces R^{σ}, σ ⊆ {1, …, n}, with |σ| = [(1 − θ)n]. We prove several “coordinate versions” of (∗) in terms of the cotype-2 constant, of the volume ratio and other parameters of K. The basic source of our estimates is an exact coordinate analogue of (∗) in the ellipsoidal case. Applications to the computation of the number of lattice points inside a convex body are considered throughout the paper.

1. Introduction

Notation. Our setting is R^{n} equipped with an inner product ⟨., .⟩ and the associated Euclidean norm defined by |x| = ⟨x, x⟩^{1/2}, x ∈ R^{n}. We denote the Euclidean unit ball and the unit sphere by D_{n} and S^{n−1} respectively, and we write σ for the rotationally invariant probability measure on S^{n−1}.

Let K be a symmetric convex body in R^{n}. Then, K induces in a natural way a norm ∥.∥_{K} on R^{n}. In what follows we shall denote by X_{K} the normed space (R^{n}, ∥.∥_{K}). As usual, K^{o} = {y ∈ R^{n} : ⟨y, x⟩ ≤ 1 for every x ∈ K} is the polar body of K, and X_{K^{o}} = (R^{n}, ∥.∥_{K^{o}}) is the dual space of X_{K}.

Finally, we consider the integral parameters

M = M_{K} = (∫_{S^{n−1}} ∥x∥_{K}^{2} σ(dx))^{1/2} , M^{∗} = M_{K^{o}} = (∫_{S^{n−1}} ∥x∥_{K^{o}}^{2} σ(dx))^{1/2} ,

which are up to a constant the mean widths of K^{o} and K respectively.

Results. The following inequality of the second named author plays an important role in developing a proportional theory of high-dimensional convex bodies:

This work was initiated at the Institute for Advanced Study and completed at the Mathematical Sciences Research Institute. Research at MSRI is supported in part by NSF grant DMS-9022140.

Theorem A (Low M^{∗}-estimate). There exists a function f : (0, 1) → R^{+} such that for every symmetric convex body K in R^{n} and for every θ ∈ (0, 1) one can find a subspace F of R^{n} with dim F = [(1 − θ)n] satisfying

(1.1)  ∥x∥_{K} ≥ \frac{f(θ)}{M_{K^{o}}} |x| , x ∈ F.

Theorem A was originally proved in [M1] and a second proof using the isoperimetric inequality on S^{n−1} was given in [M2] where it was shown that (1.1) holds with f(θ) ≥ cθ for some absolute constant c > 0 (and with an estimate f(θ) ≥ θ + o(1 − θ) as θ → 1^{−}). This was later improved to f(θ) ≥ c\sqrt{θ} in [PT], see also [M3] for a different proof with this best possible \sqrt{θ}-dependence. Finally, it was proved in [Go] that one can have

(1.2)  f(θ) ≥ \sqrt{θ}(1 + O(\frac{1}{θn})).

Moreover, if we fix some θ ∈ (0, 1) and consider the Grassmannian manifold G_{n,k} of all k-dimensional subspaces of R^{n}, where k = k(θ, n) = [(1 − θ)n], equipped with the Haar probability measure ν_{n,k}, then (1.1) holds true with f(θ) ≥ c\sqrt{θ} for all subspaces F in a subset A_{n,k} of G_{n,k} which is of almost full measure ν_{n,k}(A_{n,k}) as n → ∞.

Interchanging the roles of K and K^{o}, we may equivalently read Theorem A in the following geometric form:

(1.3)  P_{F} (K) ⊇ \frac{c\sqrt{θ}}{M_{K}} D_{n} ∩ F,

where P_{F} denotes the orthogonal projection onto F. In this paper we will follow the tradition and continue calling an inclusion of the type (1.3) a “low M^{∗}-estimate” (for K^{o}).

Among other applications of (1.3), let us mention the quotient of subspace theorem and the reverse Santaló inequality [M1], [BM].

Let {e_{1}, …, e_{n}} be an arbitrary but fixed orthonormal basis of R^{n} with respect to ⟨., .⟩. For a subset σ ⊆ {1, …, n} we naturally define the coordinate subspace R^{σ} = {x ∈ R^{n} : ⟨x, e_{j}⟩ = 0 if j ∉ σ}. We write D_{σ} for D_{n} ∩ R^{σ} and Q_{σ} for the unit cube Q_{n} ∩ R^{σ} = [−1, 1]^{σ} in R^{σ}.

Our purpose is to discuss “low M^{∗}-estimates” in the form (1.3) when one is restricted to choose F among the coordinate subspaces of R^{n} of a certain dimension m proportional to n.

In Section 2 we study the case of an ellipsoid E in R^{n}. It turns out that for any orthonormal basis of R^{n} one has results analogous to (1.3) with almost the same \sqrt{θ}-dependence on the parameter θ:

Theorem B (Coordinate low M^{∗}-estimate for ellipsoids). Let E be an ellipsoid in R^{n} and θ ∈ (0, 1). Then, there exists σ ⊆ {1, …, n}, |σ| ≥ (1 − θ)n, with

P_{σ}(E) ⊇ \frac{c\sqrt{θ}}{log^{1/2}(\frac{2}{θ})M_{E}} D_{σ},

where P_{σ} denotes the orthogonal projection onto R^{σ}, and c > 0 is an absolute constant.

It is perhaps surprising that this type of geometric result about ellipsoids is new and non-trivial. Note that our investigation of these questions was started from a simpler fact of the same nature about a special class of ellipsoids, which was discovered in [Gi].

It can be checked that Theorem B is optimal apart from the logarithmic term (see Remark 2.5). A result of the same type can be proved for an ellipsoid E of smaller but sufficiently large dimension living in an arbitrary subspace F of R^{n} (Theorem 2.3). We also consider the corresponding problem for sections (instead of projections) of E with coordinate subspaces (Theorem 2.4).

Simple examples show that one cannot achieve the same strong estimate in full generality: for an arbitrary symmetric convex body K and an arbitrary orthonormal basis in R^{n}. Consider e.g the case of the unit cube Q_{n} and the standard basis of R^{n}: observe that M_{Q_{n}} ≃ \sqrt{log n/n}, while the radius of the largest Euclidean ball contained in any coordinate projection of Q_{n} is 1. In Section 3 we give a general low M^{∗}-estimate in terms of the cotype-2 constant C_{K} of X_{K}:

Theorem C (M^{∗}-estimate in terms of C_{K}). For an arbitrary symmetric convex body K in R^{n} and for any θ ∈ (0, 1), one can find σ ⊆ {1, …, n}, |σ| ≥ (1 − θ)n, satisfying

P_{σ}(K) ⊇ \frac{c_{1}θ}{log^{2}(\frac{2}{θ})h(C_{K})M_{K}} D_{σ},

where h(y) = y log 2y, y ≥ 1, and c_{1} > 0 is an absolute constant.

Let us note that one can give a simpler argument, based on the isomorphic Sauer-Shelah lemma of S. J. Szarek and M. Talagrand and a factorization theorem of B. Maurey, which results in a weaker estimate of the same type (we sketch it in Remark 3.6). We also obtain results of the same nature in which M_{K} is replaced by various other “volumic” parameters of K or K^{o} (see Remark 3.7).

In Section 4 we give a general low M^{∗}-estimate in terms of the volume ratio vr(K) of K:

Theorem D (M^{∗}-estimate in terms of vr(K)). Let K be a symmetric convex body in R^{n}. For every θ ∈ (0, 1), there exists σ ⊆ {1, …, n}, |σ| ≥ (1 − θ)n, such that

P_{σ}(K) ⊇ \frac{1}{[c_{2}vr(K)]^{\frac{c_{3} log( \frac{2}{θ})}{θ}} M_{K}} D_{σ},

where c_{2}, c_{3} > 0 are absolute constants.

In Sections 5 and 6 we give some further applications of the low M^{∗}-estimate for ellipsoids. We demonstrate an exact dependence between coordinate sections of an ellipsoid and its polar in the spirit of [M5]. We also apply Theorems 2.2 and 2.4 to questions related to the number of integer or “almost integer” points inside an ellipsoid.

Recall that the cotype-2 constant C_{K} of X_{K} is the smallest constant λ > 0 for which

(Ave_{ε_{j}=±1}∥ ∑_{j=1}^{m} ε_{j}x_{j}∥_{K}^{2})^{1/2} ≥ \frac{1}{λ} (∑_{j=1}^{m} ∥x_{j}∥_{K}^{2})^{1/2}

holds for all choices of m ∈ N and {x_{j}}_{j≤m} in X_{K}. We refer to [MS] and [TJ] for basic facts about type, cotype and p-summing operators which are used below. The letter c will always denote an absolute positive constant, not necessarily the same in all its occurrences. By |.| we denote the cardinality of a finite set, volume of appropriate dimension, and the Euclidean norm (this will cause no confusion).

2. Ellipsoidal case

In this Section we consider the case of an arbitrary ellipsoid E in R^{n}. There exists a linear isomorphism T : R^{n} → R^{n} such that T (E) = D_{n}. It will be convenient for us to write E in the form

(2.1)  E = {x = ∑_{j=1}^{n} x_{j}e_{j} ∈ R^{n} : | ∑_{j=1}^{n} x_{j}u_{j}| ≤ 1},

where u_{j} = T (e_{j}), j = 1, …, n. Writing E in this way, we can easily express M_{E} in terms of the u_{j}’s as follows:

(2.2)  M_{E} = (∫_{S^{n−1}} ∥x∥_{T^{−1}(D_{n})}^{2} σ(dx))^{1/2} = (∫_{S^{n−1}} | ∑_{j=1}^{n} x_{j}u_{j}|^{2} σ(dx))^{1/2}

= (\frac{1}{n} ∑_{j=1}^{n} |u_{j}|^{2})^{1/2} .

Under the extra assumption that |u_{j}| ≤ 1, j = 1, …, n, an estimate for coordinate projections of E was given in [Gi] in connection with the problems of the Banach-Mazur distance to the cube and the proportional Dvoretzky-Rogers factorization. Its proof combines the structure of the ellipsoid with the well-known Sauer-Shelah lemma and factorization arguments analogous to the ones in [BT, Theorem 1.2]:

Lemma 2.1. Let E_{τ} = {x = ∑_{j∈τ} x_{j}e_{j} ∈ R^{τ} : | ∑_{j∈τ} x_{j}u_{j}| ≤ 1}, where u_{j} ∈ R^{n}, j ∈ τ, with |u_{j}| ≤ 1. Then, for every ζ ∈ (0, 1) there exists σ ⊆ τ, |σ| ≥ (1 − ζ)|τ|, such that

P_{σ}(E_{τ}) ⊇ c\sqrt{ζ} D_{σ},

where c > 0 is an absolute constant.

One more step is needed in order to obtain a low M^{∗}-estimate for coordinate subspaces in the ellipsoidal case:

Theorem 2.2. Let E be an ellipsoid in R^{n}. For every θ ∈ (0, 1) there exists a subset σ of {1, …, n} with |σ| ≥ (1 − θ)n, such that

P_{σ}(E) ⊇ \frac{c\sqrt{θ}}{log^{1/2}(\frac{2}{θ})M_{E}} D_{σ},

where c > 0 is an absolute constant.

Proof: We write E in the form (2.1) and assume as we may that M_{E} = 1. If ρ = \{j ≤ n : |u_{j}| ≥ \sqrt{2/θ}\}, then by (2.2) we have 2|ρ|/θ ≤ ∑_{j≤n} |u_{j}|^{2} = n, hence |ρ| ≤ θn/2. Consider the sets of indices:

τ_{0} = {j ≤ n : |u_{j}| ≤ 1},

τ_{k} = {j ≤ n : e^{k−1} < |u_{j}| ≤ e^{k}}, k ≥ 1.

If k_{0} = [log(\sqrt{2/θ})] + 1, we have | ⋃_{0≤k≤k_{0}} τ_{k}| ≥ n − |ρ| ≥ (1 − \frac{θ}{2})n.

We define ζ_{k} = \frac{θn}{2} \frac{e^{k}/\sqrt{|τ_{k}|}}{∑_{k} e^{k}\sqrt{|τ_{k}|}} for all k ≤ k_{0} with τ_{k} ≠ ∅, and consider the set

I = {k ≤ k_{0} : τ_{k} ≠ ∅ and ζ_{k} < 1}. For each k ∈ I we can apply Lemma 2.1 for the ellipsoid E_{τ_{k}} = E ∩ R^{τ_{k}} to find σ_{k} ⊆ τ_{k} with |σ_{k}| ≥ (1 − ζ_{k})|τ_{k}| such that

(2.3)  P_{σ_{k}}(E_{τ_{k}}) ⊇ c_{1} \frac{\sqrt{ζ_{k}}}{e^{k}} D_{σ_{k}},

where c_{1} is the constant from Lemma 2.1. Finally, we set σ = ⋃_{k∈I} σ_{k}. Note that the above choice of ζ_{k}’s implies that

| ⋃_{k=0}^{k_{0}} τ_{k}| − |σ| ≤ ∑_{k=0}^{k_{0}} ζ_{k}|τ_{k}| = \frac{θn}{2},

and therefore, |σ| ≥ (1 − θ)n.

Suppose that w ∈ D_{σ}. If we write w = ∑_{k∈I} w_{k}, where w_{k} = P_{σ_{k}}(w), then by (2.3),

(2.4)  w ∈ \frac{1}{c_{1}} ∑_{k∈I} |w_{k}|\frac{e^{k}}{\sqrt{ζ_{k}}} P_{σ_{k}}(E ∩ R^{τ_{k}}) ⊆ \frac{1}{c_{1}} (∑_{k∈I} |w_{k}|\frac{e^{k}}{\sqrt{ζ_{k}}} ) P_{σ}(E),

and since w ∈ D_{σ} was arbitrary, an application of the Cauchy-Schwartz inequality shows that

(2.5)  D_{σ} ⊆ \frac{1}{c_{1}} (∑_{k∈I} \frac{e^{2k}}{ζ_{k}} )^{1/2} P_{σ}(E).

Inserting our ζ_{k}’s in the sum above, we conclude that

(2.6)  D_{σ} ⊆ \frac{1}{c_{2}\sqrt{θn}} (∑_{k=0}^{k_{0}} e^{k}\sqrt{|τ_{k}|}) P_{σ}(E).

It remains to give an upper bound for the sum ∑_{k≤k_{0}} e^{k}\sqrt{|τ_{k}|}: to this end, note that for k = 1, …, k_{0}, we have |τ_{k}|e^{2k−2} ≤ ∑_{j∈τ_{k}} |u_{j}|^{2} ≤ n and thus e^{k}\sqrt{|τ_{k}|} ≤ e\sqrt{n} for k = 1, …, k_{0} which allows a first upper bound of the order of k_{0}\sqrt{n}.

We partition the set of indices {0, 1, …, k_{0}} setting

φ_{0} = \{k ≤ k_{0} : |τ_{k}| ≤ \frac{1}{k_{0}} \frac{n}{e^{2k−2}} \},

φ_{s} = \{k ≤ k_{0} : \frac{e^{s−1}}{k_{0}} \frac{n}{e^{2k−2}} < |τ_{k}| ≤ \frac{e^{s}}{k_{0}} \frac{n}{e^{2k−2}} \}, s ≥ 1.

If s_{0} = [log k_{0}] + 2, we have ⋃_{0≤s≤s_{0}} φ_{s} = {0, 1, …, k_{0}}, and for every s = 1, …, s_{0} we easily check that

|φ_{s}|\frac{e^{s−1}}{k_{0}} \frac{n}{e^{2k−2}} e^{2k−2} ≤ ∑_{k∈φ_{s}} ∑_{j∈τ_{k}} |u_{j}|^{2} ≤ n,

which means that

(2.7)  |φ_{s}| ≤ \frac{k_{0}}{e^{s−1}} ,

for all s ≤ s_{0}. By the definition of φ_{s} and by (2.7), we can now estimate the sum in (2.6) as follows:

(2.8)  ∑_{k=0}^{k_{0}} e^{k}\sqrt{|τ_{k}|} = ∑_{s=0}^{s_{0}} ∑_{k∈φ_{s}} e^{k}\sqrt{|τ_{k}|} ≤ ∑_{s=0}^{s_{0}} |φ_{s}|\frac{e^{k}e^{s/2}\sqrt{n}}{\sqrt{k_{0}}e^{k−1}}

≤ \frac{e\sqrt{n}}{\sqrt{k_{0}}} ∑_{s=0}^{s_{0}} \frac{k_{0}}{e^{s−1}} e^{s/2} ≤ e^{2}(∑_{s=0}^{∞} e^{−s/2})\sqrt{n}\sqrt{k_{0}} ≤ c_{3}\sqrt{k_{0}}\sqrt{n}.

Therefore, (2.6) becomes

(2.9)  D_{σ} ⊆ \frac{1}{c_{4}\sqrt{θ}}\sqrt{k_{0}}P_{σ}(E),

which completes the proof, since k_{0} ≃ log(2/θ) and we had assumed that M_{E} = 1.

We proceed to prove an extension of Theorem 2.2 concerning the case where E is an ellipsoid of dimension m < n living in an arbitrary m-dimensional subspace F of R^{n}. If m is proportional to n, with m/n sufficiently close to 1, then we still have coordinate projections of E of large dimension containing large Euclidean balls. This result will be useful for our treatment of the general case in Sections 3 and 4:

Theorem 2.3. Let ε ∈ (0, 1) and F be a subspace of R^{n} with dim F = m ≥ (1−ε)n. Then, for every non-degenerate ellipsoid E in F and for every ζ ∈ [c_{1}ε log(\frac{2}{ε}), 1) there exists σ ⊆ {1, …, n} with |σ| ≥ (1 − ζ)n, such that

P_{σ}(E) ⊇ \frac{c\sqrt{ζ}}{2\sqrt{2} log^{1/2}(\frac{2}{ζ})M_{E}} D_{σ},

where c is the constant from Theorem 2.2 and c_{1} = max\{\frac{8}{c^{2}} , \frac{1}{log 2}\}.

Proof: Suppose that an ellipsoid E is given in F. We can find an orthonormal basis {w_{1}, …, w_{m}} of F and λ_{1}, …, λ_{m} > 0 such that

E = \{x ∈ F : ∑_{j=1}^{m} \frac{⟨x, w_{j}⟩^{2}}{λ_{j}^{2}} ≤ 1\}.

We extend to an orthonormal basis {w_{j}}_{j≤n} of R^{n} and consider the ellipsoid

E′ = \{x ∈ R^{n} : ∑_{j=1}^{m} \frac{⟨x, w_{j}⟩^{2}}{λ_{j}^{2}} + ∑_{j=m+1}^{n} \frac{⟨x, w_{j}⟩^{2}}{b^{2}} ≤ 1\},

where b = \sqrt{ε}/M_{E}. It is easy to check that

(2.10)  M_{E′}^{2} = \frac{1}{n} [∑_{j=1}^{m} \frac{1}{λ_{j}^{2}} + \frac{n − m}{b^{2}}] = \frac{mM_{E}^{2} + (n − m)M_{E}^{2}/ε}{n} ≤ 2M_{E}^{2}.

Let ζ ∈ [c_{1}ε log(\frac{2}{ε}), 1). Applying Theorem 2.2 for E′ and taking into account (2.10), we find σ ⊆ {1, …, n} with |σ| ≥ (1 − ζ)n for which

(2.11)  P_{σ}(E′) ⊇ \frac{c\sqrt{ζ}}{\sqrt{2} log^{1/2}(2/ζ)M_{E}} D_{σ}.

Since ζ ≥ c_{1}ε log(\frac{2}{ε}) and the function ζ/ log(\frac{2}{ζ}) is increasing on (0,1), one can easily check that

(2.12)  \frac{c\sqrt{ζ}}{\sqrt{2} log^{1/2}(\frac{2}{ζ})} ≥ 2\sqrt{ε}.

On the other hand, we clearly have E′ ⊆ E+bD_{n} and hence P_{σ}(E′) ⊆ P_{σ}(E)+bD_{σ}. Combining this with (2.11) and (2.12) we conclude that

(2.13)  \frac{c\sqrt{ζ}}{\sqrt{2} log^{1/2}(\frac{2}{ζ})M_{E}} D_{σ} ⊆ P_{σ}(E) + \frac{1}{2} \frac{c\sqrt{ζ}}{\sqrt{2} log^{1/2}(\frac{2}{ζ})M_{E}} D_{σ}.

Claim: If A and B are convex symmetric bodies in R^{σ} and A ⊆ B + \frac{1}{2}A, then A ⊆ 2B.

[One easily checks that A ⊆ (1 + \frac{1}{2} + … + \frac{1}{2^{k}})B + \frac{1}{2^{k}} A and the claim follows by letting k → ∞.]

Our claim and (2.13) imply that

P_{σ}(E) ⊇ \frac{c}{2\sqrt{2}} \frac{\sqrt{ζ}}{log^{1/2}(\frac{2}{ζ})M_{E}} D_{σ},

and the proof of the theorem is complete.

Our next result concerns coordinate sections of ellipsoids: again, we are interested in finding large balls contained in them. Using a result of [AM] which was recently improved in [T] (in our case each of them works equally well), we can give an essentially optimal answer to this question when the dimension of the coordinate sections is small (of order roughly not exceeding \sqrt{n}):

Theorem 2.4. Let E be an ellipsoid in R^{n}. For every m ≤ c\sqrt{n} we can find a subset σ of {1, …, n} of cardinality |σ| = m, such that

E ∩ R^{σ} ⊇ \frac{c′}{\sqrt{m}M_{E}} D_{σ}.

In the statement above, c and c′ are absolute positive constants.

Proof: We write E in the form (2.1). As a consequence of (2.2), observe that for every s ≤ n the following identity holds:

(2.14)  Ave_{|τ|=s} M_{E∩R^{τ}}^{2} = [\binom{n − 1}{s − 1}/\binom{n}{s}] \frac{1}{s} ∑_{j=1}^{n} |u_{j}|^{2} = M_{E}^{2},

where the average is over all τ ⊆ {1, …, n} with |τ| = s. This means in particular that for every s ≤ n we can find τ with |τ| = s for which M_{E∩R^{τ}} ≤ M_{E}.

Assume that m ≤ c\sqrt{n} is given, where c > 0 is an absolute constant to be chosen. We choose s = [\frac{m^{2}}{c^{2}} ] and find τ with |τ| = s and M_{E∩R^{τ}} ≤ M_{E}. Observe that

Ave_{ε_{j}=±1} ∥ ∑_{j∈φ} ε_{j}e_{j}∥_{E} ≤ \sqrt{|τ|}M_{E∩R^{τ}} ≤ \sqrt{|τ|}M_{E}.

Hence, if c is small enough, the results of [AM] or [T] allow us to find φ ⊆ τ with |φ| = 2m such that

(2.15)  ∥ ∑_{j∈φ} ε_{j}e_{j}∥_{E} ≤ c_{1}\sqrt{|τ|}M_{E},

for all (ε_{j})_{j∈φ} ∈ {−1, 1}^{φ}, where c_{1} is a positive absolute constant. In other words, the coordinate section of E by R^{φ} satisfies

(2.16)  E ∩ R^{φ} ⊇ \frac{1}{c_{1}\sqrt{|τ|}M_{E}} Q_{φ}.

This means that the identity operator id : ℓ_{∞}^{φ} → X_{E} ∩ R^{φ} has norm ∥id∥ ≤ c_{1}\sqrt{|τ|}M_{E}, and this implies that π_{2}(id) ≤ c_{1}K_{G}\sqrt{|τ|}M_{E} where K_{G} is Grothendieck’s constant. Applying Pietch’s factorization theorem we can find (λ_{i})_{i∈φ}, ∑_{i∈φ} λ_{i}^{2} = 1:

(2.17)  ∥ ∑_{i∈φ} t_{i}e_{i}∥_{E} ≤ c_{1}K_{G}\sqrt{|τ|}M_{E} (∑_{i∈φ} λ_{i}^{2}t_{i}^{2})^{1/2}

for every choice of reals (t_{i})_{i∈φ}. By Markov’s inequality, we find σ_{1} ⊆ φ, |σ_{1}| ≥ |φ|/2 ≥ m, such that |λ_{i}| ≤ \begin{matrix}√ & \overline{2} \\ √ & \overline{|φ|} \end{matrix} for all i ∈ σ_{1}. Then, for any (t_{i})_{i∈σ_{1}} we have

(2.18)  ∥ ∑_{i∈σ_{1}} t_{i}e_{i}∥_{E} ≤ c_{1}K_{G}\sqrt{|τ|}M_{E} \begin{matrix}√ & \overline{2} \\ √ & \overline{|φ|} \end{matrix} (∑_{i∈σ_{1}} t_{i}^{2})^{1/2} .

The choice of |τ| and |φ| shows that

(2.19)  E ∩ R^{σ_{1}} ⊇ \frac{c′}{\sqrt{m}M_{E}} D_{σ_{1}},

for some absolute constant c′ > 0, and we conclude the proof by choosing any σ ⊆ σ_{1} of cardinality |σ| = m.

Remark 2.5. An iteration of the argument above shows that one can extend the range of m’s for which Theorem 2.4 holds to e.g the set \{1, …, [\sqrt{n}]\}, with some loss in the constant c′. The dependence on m is sharp as it can be seen by the following example: consider the ellipsoid E = {(t_{j})_{j≤n} ∈ R^{n} : | ∑ t_{j}u_{j}|_{n+1} ≤ 1}, where u_{j} = e_{j}+e_{n+1}, j = 1, …, n, and {e_{j}}_{j≤n+1} is the standard orthonormal basis in R^{n+1}. Given any σ ⊆ \{1, …, n\} with |σ| = m, we have that (\frac{t}{\sqrt{m}}, …, \frac{t}{\sqrt{m}}) ∈ E ∩R^{σ} precisely when (1 + m)t^{2} ≤ 1. In particular, we must have |t| ≤ \frac{1}{\sqrt{m}}. This means that the largest ball contained in E ∩ R^{σ} cannot have radius larger than \frac{1}{\sqrt{m}}. On the other hand, observe that M_{E} = \sqrt{2}.

The same example shows that the estimate in Theorem 2.2 is best possible apart from the log^{1/2}(\frac{2}{θ}) term. By Lemma 2.1, this logarithmic term can be removed if all the u_{j}’s are of about the same Euclidean norm.

3. General case: estimate in terms of the cotype-2 constant

In this Section we study the general case, that is K is an arbitrary symmetric convex body in R^{n}, and {e_{j}}_{j≤n} is a fixed orthonormal basis. We shall make use of the maximal volume ellipsoid E of K and of the better information we have for coordinate projections of ellipsoids. For this purpose we will also need an estimate for the parameters A_{m}(K) = sup{(|K ∩ F |/|E ∩ F |)^{1/m} : dim F = m}, m = 1, …, n.

It was proved in [BM] that the volume ratio vr(K) = (|K|/|E|)^{1/n} of K is bounded by f(C_{K}) = cC_{K}[log C_{K}]^{4}, with the power of log C_{K} improved to 1 in [MiP]. A third proof of the same fact is given in [M4], where it is also shown that vr(K) ≤ ch(C_{K}), where h(y) = y log 2y, y ≥ 1, and c > 0 is an absolute constant. Our first lemma is a modification of the argument presented in [M4] which provides an estimate for A_{m}(K), m ≤ n, in terms of C_{K}:

Lemma 3.1. Let K be a symmetric convex body in R^{n}, and E be the maximal volume ellipsoid of K. If F is an m-dimensional subspace of R^{n}, then

(\frac{|K ∩ F |}{|E ∩ F |})^{1/m} ≤ ch(\sqrt{n/m}C_{K}),

where h(y) = y log 2y, y ≥ 1.

Proof: We may clearly assume that E = D_{n}. The proof will be based on an iteration schema, analogous to the one in [M4].

We set K_{0} = K, α_{0} = n, β_{0} = n, and for j = 1, 2, … we define:

(i) α_{j} = log α_{j−1} = log^{(j)} n, the j-iterated logarithm of n, (ii) β_{j} = α_{j}M_{(K_{j−1}∩F)^{o}}, (iii) K_{j} = K ∩ β_{j}D_{n}.

Note that for every j the maximal volume ellipsoid of K_{j} is D_{n}. Also, C_{K_{j}} ≤ 2C_{K} and d(X_{K_{j}}, ℓ_{2}^{n}) ≤ β_{j}. By Sudakov’s inequality [Su], [P1] the covering number of K_{j−1} ∩ F by β_{j}D_{n} ∩ F can be estimated as follows:

N(K_{j−1} ∩ F, β_{j}D_{n} ∩ F) = N ≤ exp(c_{1}mM_{(K_{j−1}∩F)^{o}}^{2}/β_{j}^{2}) = exp(c_{1}m/α_{j}^{2}),

and since, by Brunn’s theorem, |K_{j−1} ∩ (x + β_{j}D_{n} ∩ F)| ≤ |K_{j−1} ∩ β_{j}D_{n} ∩ F |, x ∈ F, we have |K_{j−1} ∩ F | ≤ N|K_{j} ∩ F | and hence

(3.1)  |K_{j−1} ∩ F |^{1/m} ≤ exp(\frac{c_{1}}{α_{j}^{2}} ) |K_{j} ∩ F |^{1/m}

By well-known results of [DMT], [MP], and [P2] we have the string of inequalities

M_{(K_{j}∩F)^{o}} ≤ c_{2}\sqrt{\frac{n}{m}}M_{K_{j}^{o}} ≤ c_{3}\sqrt{\frac{n}{m}}T_{2}(X_{K_{j}^{o}}) ≤ c_{4}\sqrt{\frac{n}{m}}C_{K_{j}} log(2d(X_{K_{j}}, ℓ_{2}^{n}))

and therefore

M_{(K_{j}∩F)^{o}} ≤ 2c_{4}\sqrt{\frac{n}{m}}C_{K} log(2β_{j}).

It follows that the sequence {β_{j}}_{j≥0} satisfies the relation

(3.2)  β_{j+1} ≤ 2c_{4}\sqrt{\frac{n}{m}}C_{K}α_{j} log(2β_{j}).

We stop this procedure at the smallest t for which α_{t} < 6c_{4}. Induction and (3.2) show that

(3.3)  β_{t} ≤ 36c_{4}^{2}\sqrt{\frac{n}{m}}C_{K} [log(\sqrt{\frac{n}{m}}C_{K}) + 6c_{4}] ≤ c′h(\sqrt{n/m}C_{K}).

By (3.1) we see that

(3.4)  |K ∩ F |^{1/m} ≤ |K_{t} ∩ F |^{1/m} exp(c_{1}[\frac{1}{α_{1}^{2}} + … + \frac{1}{α_{t}^{2}} ]) ≤ c′′|K_{t} ∩ F |^{1/m},

since ∑ \frac{1}{α_{j}^{2}} is easily seen to be uniformly bounded. Taking into account (3.3), (3.4) and the Blaschke-Santaló inequality we conclude that

(3.5)  (\frac{|K ∩ F |}{|D_{n} ∩ F |})^{1/m} ≤ c′′ (\frac{|D_{n} ∩ F |}{|(K_{t} ∩ F)^{o}|})^{1/m} ≤ c′′M_{(K_{t}∩F)^{o}}

≤ 2c_{4}c′′\sqrt{\frac{n}{m}}C_{K} log(2c′h(\sqrt{n/m}C_{K})) ≤ ch(\sqrt{n/m}C_{K}).

Simple examples (see Remark 3.3) show that one cannot compare M_{K} and M_{E} even if C_{K} is small: the only estimate one can give is that M_{E} ≤ \sqrt{n}M_{K}, which is a direct consequence of the fact that K ⊆ \sqrt{n}E by John’s theorem. However, there exist subspaces F of R^{n} of proportional dimension on which we can compare M_{K} with M_{E∩F} reasonably well:

Lemma 3.2. Let E be the maximal volume ellipsoid of K. For every ε ∈ (0, 1) there exists a subspace F of R^{n} with dim F = m ≥ (1 − ε)n such that

M_{E∩F} ≤ \frac{ch(C_{K}) log(\frac{2}{ε})}{\sqrt{ε}} M_{K},

where h(y) = y log 2y, y ≥ 1, and c > 0 is an absolute constant.

Proof: Let {w_{1}, …, w_{n}} be an orthonormal basis of R^{n} and λ_{1} ≥ … ≥ λ_{n} > 0 such that

E = \{x ∈ R^{n} : ∑_{j=1}^{n} \frac{⟨x, w_{j}⟩^{2}}{λ_{j}^{2}} ≤ 1\}.

For k = 1, …, n, set W_{k} = span{w_{k}, …, w_{n}}. By Lemma 3.1 we have

(3.6)  (\frac{|K ∩ W_{k}|}{|E ∩ W_{k}|})^{\frac{1}{n−k+1}} ≤ c_{1}h(\sqrt{\frac{n}{n − k + 1}}C_{K}).

Note that E ∩ W_{k} ⊆ λ_{k}(D_{n} ∩ W_{k}), and hence

(3.7)  (\frac{|K ∩ W_{k}|}{|E ∩ W_{k}|})^{\frac{1}{n−k+1}} ≥ \frac{1}{λ_{k}} (\frac{|K ∩ W_{k}|}{|D_{n} ∩ W_{k}|})^{\frac{1}{n−k+1}}

≥ \frac{1}{λ_{k}M_{K∩W_{k}}} ≥ \frac{1}{c_{2}λ_{k}\sqrt{\frac{n}{n−k+1}}M_{K}} .

Combining (3.6), (3.7) we obtain

(3.8)  \frac{1}{λ_{k}} ≤ c_{1}c_{2}\sqrt{\frac{n}{n − k + 1}}h(\sqrt{\frac{n}{n − k + 1}}C_{K})M_{K} , k = 1, …, n.

Given ε ∈ (0, 1), let m = [(1 − ε)n] and set F_{m} = span{w_{1}, …, w_{m}}. By (3.8) we can estimate M_{E∩F_{m}} as follows:

(3.9)  M_{E∩F_{m}} = (\frac{1}{m} ∑_{k=1}^{m} \frac{1}{λ_{k}^{2}} )^{1/2}

≤ c_{1}c_{2}C_{K}M_{K} [∑_{k=1}^{m} \frac{n^{2}}{m(n − k + 1)^{2}} log^{2}(2\sqrt{\frac{n}{n − k + 1}}C_{K})]^{1/2}

≤ c_{1}c_{2}C_{K} log(2\sqrt{\frac{n}{n − m}}C_{K})\sqrt{\frac{n}{n − m}}M_{K} ≤ \frac{ch(C_{K}) log(\frac{2}{ε})}{\sqrt{ε}}M_{K}.

Remark 3.3. The estimate (3.9) is essentially sharp, even if C_{K} is small: to see this, consider the class of bodies K = K(a, b; s) = \{x ∈ R^{n} : ∑_{j≤s} \frac{|x_{j}|}{a} + ∑_{j>s} \frac{|x_{j}|}{b} ≤ 1}, where a, b are positive parameters and s ∈ {0, 1, …, n − 1}. It is clear that the ellipsoid of maximal volume in K is E = E(a, b; s) = \{x ∈ R^{n} : ∑_{j≤s} \frac{|x_{j}|^{2}}{a^{2}} +

∑_{j>s} \frac{|x_{j}|^{2}}{b^{2}} ≤ 1\}. It is also clear that both the cotype-2 constant and the volume ratio of K are uniformly bounded (independently of n, s, a and b).

Given ε ∈ (0, 1), choose b = a\sqrt{ε}, s = m = (1 − ε)n. Then, it is easy to check that M_{K} ≃ \sqrt{n}\sqrt{ε}/a, while M_{E∩F_{m}} ≃ \sqrt{n}/a.

Also, we can have the ratio M_{E}/M_{K} as close to \sqrt{n} as we like: choose, for example, s = n − 1 and b = \frac{a}{n−1}. Then, M_{K} ≃ 1/\sqrt{n}b while M_{E} ≃ 1/b.

Combining Theorem 2.3 and Lemma 3.2 we prove our M^{∗}-estimate in terms of the cotype-2 constant of X_{K}:

Theorem 3.4. Let K be a symmetric convex body in R^{n}, and X_{K} = (R^{n}, ∥.∥_{K}). For every θ ∈ (0, 1) there exists σ ⊆ {1, …, n}, |σ| ≥ (1 − θ)n, such that

P_{σ}(K) ⊇ \frac{cθ}{log^{2}(\frac{2}{θ})h(C_{K})M_{K}} D_{σ},

where h(y) = y log 2y, y ≥ 1, and c > 0 is an absolute constant.

Proof: Let E be the maximal volume ellipsoid of K, and set ε = ε(θ) = θ/c_{2} log(\frac{2}{θ}), where c_{2} > 0 is a constant to be chosen. By Lemma 3.2 we can find a subspace F of R^{n} with dim F ≥ (1 − ε)n such that

(3.10)  M_{E∩F} ≤ \frac{c_{3}h(C_{K}) log(\frac{2}{ε})}{\sqrt{ε}} M_{K}.

Observe that if c_{2} is large enough, then θ ≥ c_{1}ε log(\frac{2}{ε}) where c_{1} is the constant in Theorem 2.3. Thus, we can apply Theorem 2.3 for E ∩ F to find σ ⊆ {1, …, n} with |σ| ≥ (1 − θ)n for which

(3.11)  P_{σ}(E ∩ F) ⊇ \frac{c\sqrt{θ}}{2\sqrt{2} log^{1/2}(\frac{2}{θ})M_{E∩F}} D_{σ}.

Combining (3.10) with (3.11) we finish the proof.

Remark 3.5. It should be noted that the estimate given by Theorem 3.4 is exact not only when C_{K} is small (like e.g in the ellipsoidal case), but in the whole range [1, \sqrt{n}] of possible values of C_{K} i.e even if C_{K} is extremely large. This can be easily seen if one considers the case of B_{p}^{n}, p > 2, the unit ball of ℓ_{p}^{n}, and the standard coordinate system in R^{n}. Fix for example θ = \frac{1}{2}. Then, the radius of the largest Euclidean ball inscribed in any [\frac{n}{2}]-dimensional coordinate projection of B_{p}^{n} is 1, and the well-known estimates for C_{B_{p}^{n}} and M_{B_{p}^{n}} show that Theorem 3.4 is sharp apart from logarithmic terms. We do not know if the “almost linear” dependence on θ which our method provides is optimal. However, the ellipsoidal case shows that \sqrt{θ} dependence is the best one might hope for.

Remark 3.6. One can give a weaker estimate, analogous to the one obtained in Theorem 3.4, using the isomorphic Sauer-Shelah lemma of Szarek-Talagrand [ST] and a factorization result of Maurey [Ma] (see also [TJ]). Starting with the body K and the orthonormal basis {e_{j}}_{j≤n}, we have the inequality

Ave_{ε_{j}=±1} ∥ ∑_{j=1}^{n} ε_{j}e_{j}∥_{K} ≤ \sqrt{n}M_{K},

and therefore, by Markov’s inequality we can find A ⊆ {−1, 1}^{n} of cardinality |A| ≥ 2^{n−1} such that ∥ ∑ ε_{j}e_{j}∥_{K} ≤ 2M_{K} \sqrt{n} whenever ε = (ε_{1}, …, ε_{n}) ∈ A. If we view A as a set of points in R^{n}, this means that A ⊆ 2M_{K} \sqrt{n}K. On the other hand, the isomorphic Sauer-Shelah lemma shows that for some absolute constant c_{1} > 0 and for every θ ∈ (0, 1) there exists σ ⊆ \{1, …, n\}, |σ| ≥ (1 − \frac{θ}{2})n, with co(P_{σ}(A) ⊇ c_{1} \frac{θ}{2}Q_{σ}, and hence

P_{σ}(K) ⊇ \frac{c_{1}θ}{4M_{K} \sqrt{n}} Q_{σ}.

It follows that if Y = (R^{σ_{1}}, ∥.∥_{K^{o}}), then id : ℓ_{∞}^{σ_{1}} → Y^{∗} has norm ∥id∥ ≤ \frac{4M_{K} \sqrt{n}}{c_{1}θ}, and Maurey’s theorem shows that

π_{2}(id) ≤ c_{2} \frac{M_{K} \sqrt{n}}{θ} g(Y^{∗}),

where g(Y^{∗}) = C_{Y^{∗}} \sqrt{1 + log(C_{Y^{∗}})}. Then, we can apply Pietch’s factorization theorem in the context of [BT, Theorem 1.2] to find σ ⊆ σ_{1} with |σ| ≥ (1−\frac{θ}{2})|σ_{1}| ≥ (1−θ)n for which

(∑_{i∈σ} t_{i}^{2})^{1/2} ≤ c_{3} \frac{M_{K}g(Y^{∗})}{θ^{3/2}}∥ ∑_{i∈σ} t_{i}e_{i}∥_{K^{o}}

is true for all (t_{i})_{i∈σ}. Taking polars in R^{σ} and using the fact that C_{Y^{∗}} ≤ c_{4}C_{K}∥Rad_{X_{K}}∥, we conclude that

P_{σ}(K) ⊇ \frac{cθ^{3/2}}{f(K)M_{K}} D_{σ},

where c > 0 is an absolute constant, and f(K) = C_{K}∥Rad_{X_{K}}∥\sqrt{1 + log(C_{K}∥Rad_{X_{K}}∥)}.

Remark 3.7. One can modify the proof of Theorem 3.6 to give analogous estimates in which M_{K} is replaced by other “volumic” parameters of K or K^{o}.

Consider e.g the sequence of volume numbers of K^{o}

(3.12)  v_{s}(K^{o}) = max{(|P_{F} (K^{o})|/|D_{n} ∩ F |)^{1/s} : dim F = s},

where s = 1, …, n. As a consequence of the Aleksandrov-Fenchel inequalities, one can easily see that {v_{s}(K^{o})}_{s≤n} is non increasing (see [P1]):

(3.13)  v_{1}(K^{o}) ≥ v_{2}(K^{o}) ≥ … ≥ v_{n}(K^{o}) = v.rad(K^{o}).

Let K be a symmetric convex body in R^{n} and let E be the ellipsoid of maximal volume in K as in Lemma 3.4. Using the inverse Santaló inequality in (3.6), (3.7) we get

(3.14)  \frac{1}{λ_{k}} ≤ (\frac{|D_{n} ∩ W_{k}|}{|K ∩ W_{k}|})^{\frac{1}{n−k+1}} (\frac{|K ∩ W_{k}|}{|E ∩ W_{k}|})^{\frac{1}{n−k+1}}

≤ c (\frac{|P_{W_{k}}(K^{o})|}{|D_{n} ∩ W_{k}|})^{\frac{1}{n−k+1}} c_{1}h(\sqrt{\frac{n}{n − k + 1}}C_{K})

for k = 1, …, n. By the definition (3.11) of v_{n−k+1}(K^{o}) this means that

(3.15)  \frac{1}{λ_{k}} ≤ c_{2}h(C_{K})v_{n−k+1}(K^{o})\sqrt{\frac{n}{n − k + 1}} log(2\sqrt{\frac{n}{n − k + 1}}).

Inserting this estimate in (3.9) we obtain:

(3.16) M_{E∩F_{m}}^{2} = \frac{1}{m} ∑_{k=1}^{m} \frac{1}{λ_{k}^{2}} ≤ \frac{c_{2}^{2}h^{2}(C_{K}) log^{2}(\frac{2n}{n−m+1})}{m} ∑_{k=1}^{m} \frac{n}{n − k + 1}v_{n−k+1}^{2}(K^{o}).

The monotonicity of volume numbers shows that v_{n−k+1}(K^{o}) ≤ v_{n−m+1}(K^{o}), k = 1, …, m, and combining with the fact that

∑_{k=1}^{m} \frac{n}{n − k + 1} ≤ n log(\frac{n}{n − m})

we arrive at

(3.17)  M_{E∩F_{m}} ≤ \frac{cn}{m}h(C_{K})v_{n−m+1}(K^{o}) log^{3/2}(\frac{2n}{n − m}).

Set m = [(1 − θ)n]. Then, (3.17) can be rewritten as

M_{E∩F_{m}} ≤ c′h(C_{K})v_{[θn]}(K^{o}) log^{3/2}(\frac{2}{θ}),

and, using Theorem 2.3 exactly as in the proof of Theorem 3.4, we can find σ ⊆ \{1, …, n\} with |σ| ≥ (1 − c_{1}θ log(\frac{2}{θ}))n for which

(3.18)  P_{σ}(K) ⊇ \frac{c\sqrt{θ}}{log^{3/2}(\frac{2}{θ})v_{[θn]}(K^{o})h(C_{K})} D_{σ}.

A similar argument shows that for some σ of the same cardinality we have

(3.19)  P_{σ}(K) ⊇ \frac{c\sqrt{θ}w_{[θn]}(K)}{log^{3/2}(\frac{2}{θ})h(C_{K})} D_{σ},

where w_{s}(K) = min{(|K ∩ F |/|D_{n} ∩ F |)^{1/s} : dim F = s}, s = 1, …, n.

4. General case: estimate in terms of the volume ratio

In this Section we use the volume ratio vr(K) of K instead of the cotype-2 constant of X_{K} as a parameter for our low M^{∗}-estimate. Let E be the maximal volume ellipsoid of K. We start with a lemma which estimates the covering number N(K, E) in terms of the volume ratio vr(K) = (|K|/|E|)^{1/n}. Our proof is based on Lemma 4.4 from [MS2], actually the argument given there leads to a stronger estimate, but we include a simple proof of what we need here for the sake of completeness. Recall that N(K, L) is the smallest natural number N for which there exist x_{1}, …, x_{N} ∈ R^{n} with K ⊆ ⋃_{i≤N}(x_{i} + L):

Lemma 4.1. Let K and L be two symmetric convex bodies in R^{n} such that L ⊆ K. Then,

N(K, L) ≤ c^{n} \frac{|K|}{|L|},

where c > 0 is an absolute constant.

Proof: Consider a set N of points in K such that ∥x−x′∥_{L} ≥ 1 for every x, x′ ∈ N, x ≠ x′, which has the maximal possible cardinality. Observe that the sets \frac{2}{3}x + \frac{L}{3}, x ∈ N have disjoint interiors and, since L ⊆ K, they are all contained in K. We easily deduce that

(4.1)  |N| ≤ 3^{n} \frac{|K|}{|L|}.

Finally, it is clear that K ⊆ ⋃_{x∈N}(x + L), which completes the proof.

Suppose that K is any symmetric convex body in R^{n} and E is the ellipsoid of maximal volume in K. The analogue of Lemma 3.2 in the “volume ratio” formulation is the following:

Lemma 4.2. Let E be the maximal volume ellipsoid of K. For every ε ∈ (0, 1) there exists a subspace F of R^{n} with dim F = m ≥ (1 − ε)n, such that

M_{E∩F} ≤ [c vr(K)]^{1/ε}M_{K},

where c > 0 is an absolute constant.

Proof: As in the proof of Lemma 3.2, let

E = \{x ∈ R^{n} : ∑_{j=1}^{n} \frac{⟨x, w_{j}⟩^{2}}{λ_{j}^{2}} ≤ 1\},

where {w_{1}, …, w_{n}} is an orthonormal basis of R^{n} and λ_{1} ≥ … ≥ λ_{n} > 0. Fix k ∈ {1, …, n} and consider the subspace W_{k} = span{w_{k}, …, w_{n}}. According to Lemma 4.1, we can find x_{1}, …, x_{N} ∈ K such that N = N(K, E) ≤ [c_{1}vr(K)]^{n} and K ⊆ ⋃(x_{i} + E). Project all the (x_{i} + E)’s onto W_{k}. Then,

(4.2)  K ∩ W_{k} ⊆ P_{W_{k}}(K) ⊆ ⋃_{j≤N} P_{W_{k}}(x_{j} + E) = ⋃_{j≤N}(P_{W_{k}}(x_{i}) + E ∩ W_{k}),

and hence, N(K ∩ W_{k}, E ∩ W_{k}) ≤ N(K, E). Thus, we can estimate the ratio of the volumes of K ∩ W_{k} and E ∩ W_{k} using (4.2):

(4.3)  (\frac{|K ∩ W_{k}|}{|E ∩ W_{k}|})^{\frac{1}{n−k+1}} ≤ [N(K, E)]^{\frac{1}{n−k+1}} ≤ [c_{1}vr(K)]^{\frac{n}{n−k+1}} .

Combining with (3.7) we get

(4.4)  \frac{1}{λ_{k}} ≤ c_{2}\sqrt{\frac{n}{n − k + 1}} [c_{1}vr(K)]^{\frac{n}{n−k+1}} M_{K}, k = 1, …, n.

We continue as in Lemma 3.2: Given any ε ∈ (0, 1), we consider the first m for which m ≥ (1 − ε)n and set F_{m} = span{w_{1}, …, w_{m}}. In view of (4.5) we can compare M_{E∩F_{m}} with M_{K} as follows:

(4.5)  M_{E∩F_{m}} = (\frac{1}{m} ∑_{k=1}^{m} \frac{1}{λ_{k}^{2}} )^{\frac{1}{2}}

≤ c_{2}M_{K} (∑_{k=1}^{m} \frac{n}{m(n − k + 1)}[c_{1}vr(K)]^{\frac{2n}{n−k+1}} )^{\frac{1}{2}}

≤ M_{K}[c_{3}vr(K)]^{\frac{n}{n−m+1}} \sqrt{\frac{n}{m}} log^{1/2}(\frac{n}{n − m}),

and the lemma follows with the observation that \frac{log(1/ε)}{1−ε} → 1 as ε → 1^{−}.

Remark 4.3. By well-known results of S.J. Szarek and N. Tomczak-Jaegermann (see [Sz], [STJ]) which were extending previous work of Kashin, if E is the maximal volume ellipsoid of K, then for every k = 1, …, n − 1 there exist k-dimensional subspaces F of R^{n} for which E ∩ F ⊆ K ∩ F ⊆ (c vr(K))^{\frac{n}{n−k}} E ∩ F, and this obviously implies that M_{E∩F} ≤ [c vr(K)]^{\frac{n}{n−k}} M_{K∩F}. This leads to the same estimate as in Lemma 4.2 above, actually if E = D_{n} this is true for all subspaces F in a subset A of G_{n,k} with almost full measure ν_{n,k}(A) > 1 − 2^{−n}. The argument provided by Lemmata 4.1 and 4.2 gives a concrete example of a subspace on which the weaker “M_{E∩F} and M_{K∩F} ” comparison is true: it can be chosen as the k-dimensional subspace which is coordinate with respect to E and corresponds to the k largest semiaxes of E. If E = D_{n}, then this weak comparison is true for all F ∈ G_{n,k}.

Combining Lemma 4.2 with Theorem 2.3 we prove our volume-ratio result:

Theorem 4.4. Let K be a symmetric convex body in R^{n}. For every θ ∈ (0, 1) there exists σ ⊆ {1, …, n}, |σ| ≥ (1 − θ)n, such that

P_{σ}(K) ⊇ \frac{1}{[c_{1}vr(K)]^{\frac{c_{2} log( \frac{2}{θ})}{θ}} M_{K}} D_{σ},

where c_{1}, c_{2} are absolute positive constants.

Proof: Let E be the maximal volume ellipsoid of K, and set ε = ε(θ) = \frac{θ}{c_{2} log( \frac{2}{θ})}, where c_{2} > 0 is a constant to be chosen. Using Lemma 4.2 we find a subspace F of R^{n} with dim F ≥ (1 − ε)n such that

(4.6)  M_{E∩F} ≤ [c_{4}vr(K)]^{1/ε}M_{K}.

If c_{2} is large enough, we easily check that θ ≥ c_{1}ε log(\frac{2}{ε}) where c_{1} is the constant in Theorem 2.3. We can therefore apply Theorem 2.3 for E ∩ F to find σ ⊆ {1, …, n} with |σ| ≥ (1 − θ)n, such that

(4.7)  P_{σ}(E ∩ F) ⊇ \frac{c\sqrt{θ}}{2\sqrt{2} log^{1/2}(\frac{2}{θ})M_{E∩F}} D_{σ}.

Combining (4.6) with (4.7) we conclude the proof.

For classes of spaces with uniformly bounded volume ratio, Theorem 4.3 gives an optimal answer as long as, say, θ ≥ \frac{1}{2}. The estimate obtained “explodes” if vr(K) is large or if θ is needed to be close to 0.

5. Linear duality relations for coordinate sections of ellipsoids

Let K be a symmetric convex body in R^{n}. We introduce the integer valued functions t, t_{c} : R^{+} → N defined by

t(r) = t(K, r) = max{k ≤ n : there exists a subspace E

with dimE = k, such that\frac{1}{r}|x| ≤ ∥x∥ for every x ∈ E\}

and

t_{c}(r) = t_{c}(K, r) = max{k ≤ n : there exists a coordinate subspace E
with dim E = k such that \frac{1}{r}|x| ≤ ∥x∥ for every x ∈ E\}.

It is easy to see that if K is an ellipsoid in R^{n}, then t(K, r) + t(K^{o}, \frac{1}{r}) ≥ n. In [M5] it is proved that for every body K, for every r > 0, and for every τ ∈ (0, 1), one has a similar duality relation:

(5.1)  t(K, r) + t(K^{o}, \frac{1}{τr}) ≥ (1 − τ)n − C,

where C > 0 is a universal constant. The proof of this fact is based on the strong form (1.2) of the low M^{∗}-estimate and on the “distance lemma”: if \frac{1}{a}|x| ≤ ∥x∥ ≤ b|x| for every x ∈ R^{n} and if (M_{K}/b)^{2} + (M_{K^{o}}/a)^{2} = s > 1, then ab ≤ \frac{1}{s−1}.

In this Section we establish a coordinate version of (5.1) in the ellipsoidal case. Our estimate depends on how close the ellipsoid is to being in M-position:

Definition: For a symmetric convex body K in R^{n} we denote by λ_{K} its volume radius: λ_{K} = (|K|/|D|)^{1/n}. We also write N_{K} for N(K, λ_{K}D) and say that K is in M_{δ}-position if δ ≥ \frac{1}{n} log N_{K}.

Our first lemma provides some simple estimates which show that this position is “stable” under the operations of taking intersection or convex hull with a ball:

Lemma 5.1. Let K be a symmetric convex body in R^{n}, and let r, r_{1} > 0 be given. Define K_{r} = K ∩ rD and K^{r_{1}} = co(K ∪ r_{1}D). Then,

(i) N_{K_{r}} ≤ max{3^{n}N_{K}^{2}, 9^{n}N_{K}}.

(ii) N_{K^{r_{1}}} ≤ 5^{n}N_{K}.

Proof: (i) From the Brunn-Minkowski inequality it easily follows that |K ∩ rD| ≥ |K ∩ (x + rD)|, x ∈ R^{n}. This implies that |K| ≤ N(K, rD)|K ∩ rD| or, equivalently,

(5.2)  λ_{K}^{n} ≤ N(K, rD)λ_{K_{r}}^{n}.

We distinguish two cases:

(1) If λ_{K} < r, then N(K, rD) ≤ N_{K} and, by (5.2), λ_{K}^{n} ≤ N_{K}λ_{K_{r}}^{n}. It follows that

N_{K_{r}} ≤ N(K, λ_{K_{r}}D) ≤ N_{K}N(D, \frac{λ_{K_{r}}}{λ_{K}} D) ≤ N_{K}N(D, \frac{1}{N_{K}} D) ≤ 3^{n}N_{K}^{2}.

(2) If λ_{K} > r, then N(K, rD) ≤ N(K, λ_{K}D)N(D, \frac{r}{λ_{K}} D) ≤ N_{K}3^{n}(\frac{λ_{K}}{r})^{n} and hence, by (5.2), (\frac{r}{λ_{Kr}})^{n} ≤ 3^{n}N_{K}. It follows that

N_{K_{r}} ≤ N(rD, λ_{K_{r}}D) ≤ 3^{n}(\frac{r}{λ_{K_{r}}})^{n} ≤ 9^{n}N_{K}.

(ii) We obviously have λ_{K^{r_{1}}} ≥ max{λ_{K}, r_{1}}. Also, K^{r_{1}} ⊆ K + r_{1}D, which gives

N_{K^{r_{1}}} ≤ N(K^{r_{1}}, 2λ_{K^{r_{1}}}D)N(D, \frac{1}{2}D) ≤ 5^{n}N(K + r_{1}D, (λ_{K} + r_{1})D) ≤ 5^{n}N_{K}.

For an arbitrary symmetric convex body K, one has in general the information λ_{K}M_{K} ≥ 1 as a consequence of the polar coordinates formula for volume. Our next lemma provides an “inverse” inequality in terms of the parameters N_{K^{o}} and b = sup{∥x∥ : x ∈ S^{n−1}}:

Lemma 5.2. Let K be a symmetric convex body in R^{n}, and assume that ∥x∥ ≤ b|x| for all x ∈ R^{n}. Then,

M_{K} ≤ \frac{c}{λ_{K}} N_{K^{o}}^{t/n}

where c > 0 is an absolute constant, and t ≤ C(\frac{b}{M_{K}})^{2}.

Proof: Using Theorem 6 from [BLM] (to be more precise, using an argument identical to the one given there and the observation that what is really used is the ratio b/M_{K}), one can find orthogonal transformations u_{1}, …, u_{t} ∈ O(n) such that

(5.4)  \frac{M_{K}}{2} D ⊆ T = \frac{1}{t} ∑_{i=1}^{t} u_{i}(K^{o}) ⊆ 2M_{K}D,

with t ≤ C(\frac{b}{M_{K}})^{2}, where C > 0 is an absolute constant.

On observing that N(T, λ_{K^{o}}D) ≤ [(N(K^{o}, λ_{K^{o}}D)]^{t} = N_{K^{o}}^{t}, we can estimate M_{K} by (5.4) as follows:

(5.5)  M_{K} ≤ 2(\frac{|T |}{|D|})^{1/n} ≤ 2λ_{K^{o}}N_{K^{o}}^{t/n}.

Finally, the Blaschke-Santaló inequality implies that λ_{K}λ_{K^{o}} ≤ 1, and hence the proof of the Lemma is complete.

We can now pass to the proof of the main result of this section:

Theorem 5.3. Let E be an ellipsoid in R^{n}, and assume that both E and E^{o} are in M_{δ}-position. For every r > 0 and every τ ∈ (0, 1) we have

t_{c}(E, r) + t_{c}(E^{o}, \frac{u(τ, δ)}{r}) ≥ (1 − τ)n,

where u(τ, δ) = \frac{c log( \frac{2}{τ})}{\sqrt{τ}}e^{\frac{cδ log^{2}( \frac{2}{τ})}{τ}}, and c > 0 is an absolute constant.

Proof: Let r > 0 and τ ∈ (0, 1) be given. Consider the body E_{r} = E ∩ rD. Since E_{r} is \sqrt{2}-isomorphic to an ellipsoid, one can easily check that Theorem 2.2 holds for E_{r}: for every θ ∈ (0, 1) we can find σ ⊆ {1, …, n} with |σ| ≥ (1 − θ)n such that P_{σ}(E_{r}^{o}) ⊇ [g(θ)/M(E_{r}^{o})]D_{σ}, where g(θ) = c\sqrt{θ}/2\sqrt{log(2/θ)} and c is the same constant as in Theorem 2.2.

We distinguish three cases:

Case 1: \frac{M(E_{r}^{o})}{r} ∈ [g(τ), g(1)).

In this case, consider any λ ∈ (τ, 1] with \frac{1}{r}M(E_{r}^{o}) < g(λ). We can find σ_{1} ⊆ {1, …, n} with |σ_{1}| ≥ (1 − λ)n such that

P_{σ_{1}}(E_{r}^{o}) ⊇ \frac{g(λ)}{M(E_{r}^{o})}D_{σ_{1}},

and it is easy to check that, for every x ∈ R^{σ_{1}}, max\{∥x∥, \frac{1}{r}|x|\} = ∥x∥_{E_{r}} > \frac{1}{r}|x|, which means that \frac{1}{r}|x| ≤ ∥x∥, i.e

(5.6)  t_{c}(E, r) ≥ (1 − λ)n.

Taking the infimum of all λ’s for which \frac{M(E_{r}^{o})}{r} < g(λ), we conclude that (5.6) also holds for the solution in λ of the equation M(E_{r}^{o}) = rg(λ).

Now, choose μ ∈ (0, 1) such that (1 − λ) + (1 − μ) = 1 − τ, and r_{1} > 0 satisfying M((E_{r})^{r_{1}})r_{1} < g(μ) (this is always possible since the left hand side is decreasing in r_{1} and tends to zero as r_{1} → ∞). Since (E_{r})^{r_{1}} is 2-isomorphic to an ellipsoid, we can find σ_{2} ⊆ {1, …, n}, |σ_{2}| ≥ (1 − μ)n, with

P_{σ_{2}}((E_{r})^{r_{1}}) ⊇ \frac{g(μ)}{M((E_{r})^{r_{1}})}D_{σ_{2}},

thus max\{r_{1}|x|, ∥x∥_{E_{r}^{o}}\} = ∥x∥_{[(E_{r})^{r_{1}}]^{o}} ≥ \frac{g(μ)}{M((E_{r})^{r_{1}})}|x| > r_{1}|x|, i.e ∥x∥_{E^{o}} ≥ ∥x∥_{E_{r}^{o}} > r_{1}|x| on R^{σ_{2}}, which means that

(5.7)  t_{c}(E^{o}, \frac{1}{r_{1}} ) ≥ (1 − μ)n.

Again, we may take r_{1} to be the solution of the equation M((E_{r})^{r_{1}})r_{1} = g(μ) in r_{1}.

Combining (5.6) with (5.7) we obtain

(5.8)  t_{c}(E, r) + t_{c}(E^{o}, \frac{1}{r_{1}} ) ≥ (1 − τ)n,

and it remains to compare r with r_{1}. Let us write W for the body (E_{r})^{r_{1}}. By the way W has been constructed, it is easily checked that the following are satisfied:

(i) M(W)r_{1} = g(μ) and M(W^{o}) ≥ M(E_{r}^{o}) = rg(λ).

(ii)∥x∥_{W} ≤ \frac{1}{r_{1}} |x| and ∥x∥_{W^{o}} ≤ r|x|, x ∈ R^{n}.

(iii) N_{W}^{1/n} ≤ c_{1}N_{E}^{c_{2}/n} and N_{W^{o}}^{1/n} ≤ c_{1}N_{E^{o}}^{c_{2}/n}, where c_{1}, c_{2} > 0 are absolute constants. This is a simple consequence of Lemma 5.1, since both W and W^{o} are formed from E and E^{o} with two successive operations of taking intersection and convex hull with balls.

We simply write

\frac{r}{r_{1}} = \frac{r}{M(W^{o})} \frac{1}{r_{1}M(W)} M(W)M(W^{o})

and making use of (i)-(iii) and of Lemma 5.2 we arrive at

(5.9)  \frac{r}{r_{1}} ≤ \frac{c}{g(λ)g(μ)}N_{E^{o}}^{C/ng^{2}(μ)}N_{E}^{C/ng^{2}(λ)}.

Note that, at some point, we also used the fact that λ_{E}λ_{E^{o}} ≃ 1. Finally, assuming that both E and E^{o} are in M_{δ}-position, we rewrite (5.9) as follows:

(5.10)  \frac{r}{r_{1}} ≤ \frac{c}{g(λ)g(μ)}e^{Cδ/g^{2}(λ)g^{2}(μ)}.

We have λ + μ = 1 + τ and with this condition we can easily check that \frac{1}{g(λ)g(μ)} ≤

\frac{c log( \frac{2}{τ})}{\sqrt{τ}}, which completes the proof in this case.

Case 2: \frac{M(E_{r}^{o})}{r} ≥ g(1).

We choose r_{1} > 0 such that M((E_{r})^{r_{1}})r_{1} = g(τ) and as above we conclude that t_{c}(E^{o}, \frac{1}{r_{1}} ) ≥ (1 − τ)n. The estimate for r/r_{1} is done exactly in the same way, the only difference being that now r/M(E_{r}^{o}) ≤ 1/g(1).

Case 3: \frac{M((E_{r})^{o})}{r} < g(τ).

This is the simplest case since we already have t_{c}(E, r) ≥ (1 − τ)n.

6. Integer points inside an ellipsoid: some remarks

Consider an arbitrary ellipsoid E in R^{n}. Write E in the form (2.1), so that ∑_{j≤n} |u_{j}|^{2} = nM_{E}^{2}. Without loss of generality we may assume that the |u_{j}|’s are arranged in the increasing order, therefore a simple application of Markov’s inequality shows that

(6.1)  |u_{j}| ≤ \sqrt{\frac{n}{n − j + 1}}M_{E} , j = 1, …, n.

Recall that the j-th successive minimum λ_{j}(E) of E is defined by λ_{j}(E) = min{λ > 0 : dim(span(λE ∩ Z^{n})) ≥ j}. Inequality (6.1) gives an estimate on the successive minima of E in terms of M_{E}:

Fact I: Let E be an ellipsoid in R^{n}. Then, λ_{j}(E) ≤ \sqrt{\frac{n}{n−j+1}}M_{E}, j = 1, …, n. In particular, if M_{E} ≤ 1 then E contains an integer point different from the origin.

Note that if M_{E} > 1 then E may contain no integer points other than the origin. Consider for example a ball of radius r = \frac{1}{M_{E}}.

Let us concentrate on the case M_{E} < 1. If M_{E} < |D_{n}|^{1/n}/2, then we obviously have |E| > 2^{n} and Minkowski’s theorem with its relatives start giving estimates on the cardinality of the set of integer points in E. We are interested in the range |D_{n}|^{1/n}/2 < M_{E} < 1. From Fact I we know that E contains non-trivial integer points, and using M_{E} as a parameter we try to estimate the number of them. Theorem 2.4 can be useful in this direction:

Let D_{m} be the m-dimensional Euclidean unit ball, and define d(t, m) = |tD_{m} ∩Z^{m}| be the cardinality of the set of integer points in tD_{m}. A simple lower bound for d(t, m) can be given by counting the points with coordinates 0, ±1 in tD_{m}:

(6.2)  d(t, m) ≥ ∑_{k=0}^{[t^{2}]} \binom{n}{k}2^{k} ≥ \binom{n}{[t^{2}]}2^{[t^{2}]}.

By Theorem 2.4, for every m ≤ c_{1}\sqrt{n} we can find σ ⊆ \{1, …, n\} with |σ| = m and E ∩R^{σ} ⊇ \frac{c_{2}}{\sqrt{m}M_{E}} D_{σ}, where c_{1}, c_{2} > 0 are absolute constants. Assuming that M_{E} < c_{2} and using (6.2) we have some non-trivial information: It is clear that

(6.3)  |E ∩ Z^{n}| ≥ max_{m}\{|E ∩ Z^{σ}| : |σ| = m ≤ c_{1}\sqrt{n}\}

Thus, we have:

Fact II: Let E be an ellipsoid in R^{n} with M_{E} < c_{2} < 1. Then,

|E ∩ Z^{n}| ≥ max_{m}\{d(\frac{c_{2}}{\sqrt{m}M_{E}} , m) : m ≤ c_{1}\sqrt{n}\}

≥ max_{m}\{\binom{n}{[c_{2}^{2}/mM_{E}^{2}]}2^{[c_{2}^{2}/mM_{E}^{2}]} : m ≤ c_{1}\sqrt{n}\}.

The question of computation of the number of integer points inside an ellipsoid (or, more generally, inside a symmetric convex body) in R^{n} was relaxed in several directions in [M6]. One of the questions stated asks for “almost integer” points inside E in the following precise sense: for a given θ ∈ (0, 1), find a projection of E onto some coordinate subspace R^{σ} with |σ| ≥ (1−θ)n, which contains as many as possible integer points. Then, E itself will contain many points with [(1 − θ)n] coordinates which are distinct [(1 − θ)n]-dimensional integers.

Our low M^{∗}-estimate for ellipsoids provides an answer to this question in terms of M_{E}. We know that there exists σ ⊆ {1, …, n}, |σ| = [(1 − θ)n], such that

P_{σ}(E) ⊇ \frac{c\sqrt{θ}}{\sqrt{log(\frac{2}{θ})}M_{E}} D_{σ}.

This, and (6.2), lead to the following:

Fact III: Let E be an ellipsoid in R^{n}. For every θ ∈ (0, 1) there exists σ ⊆ {1, …, n} with |σ| = [(1 − θ)n] for which

|P_{σ}(E) ∩ Z^{σ}| ≥ d(\frac{c\sqrt{θ}}{\sqrt{log(\frac{2}{θ})}M_{E}} , [(1 − θ)n])

≥ \binom{[(1 − θ)n]}{[\frac{c^{2}θ}{log( \frac{2}{θ})M_{E}^{2}} ]}2^{[ \frac{c^{2}θ}{log( \frac{2}{θ})M^{2}_{E}} ]}.

Clearly, the results in Sections 3 and 4 give analogous estimates for an arbitrary symmetric convex body.

References

[AM] N. Alon and V. D. Milman, Embedding of ℓ_{∞}^{k} in finite dimensional Banach spaces, Israel J. Math. 45 (1983), 365-380.

[BM] J. Bourgain and V. D. Milman, New volume ratio properties of convex symmetric bodies, Inventiones Math. 88 (1987), 319-340.

[BT] J. Bourgain and L. Tzafriri, Invertibility of large submatrices with applications to the geometry of Banach spaces and harmonic analysis, Israel J. Math. 57 (1987), 137-224.

[BLM] J. Bourgain, J. Lindenstrauss and V. D. Milman, Minkowski sums and symmetrizations, Lecture Notes in Mathematics 1317 (1988), 44-66.

[DMT] W. J. Davis, V. D. Milman and N. Tomczak-Jaegermann, The distance between certain n-dimensional spaces, Israel J. Math. 39 (1981), 1-15.

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

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

[Ma] B. Maurey, Théorèmes de factorization pour les operateurs linéaires à valeurs dans les espaces L^{p}, Astérisque 11 (1974), 1-163.

[M1] V. D. Milman, Geometrical inequalities and mixed volumes in the local theory of Banach spaces, Astérisque 131 (1985), 373-400.

[M2] V. D. Milman, Random subspaces of proportional dimension of finite dimensional normed spaces: approach through the isoperimetric inequality, Lecture Notes in Mathematics 1166 (1985), 106-115.

[M3] V. D. Milman, A note on a low M^{∗} estimate, Geometry of Banach Spaces, Proceedings of the Conference held in Strobl, Austria, 1989, edited by P.F.X. Muller and W. Schachermayer, LMS Lecture Note Series 158, Cambridge University Press (1990), 219-229.

[M4] V. D. Milman, Some remarks on Uryshon’s inequality and volume ratio of cotype-2 spaces, Lecture Notes in Mathematics 1267 (1987), 75-81.

[M5] V. D. Milman, Spectrum of a position of a convex body and linear duality relations, Israel Math. Conf. Proceedings (IMCP) 3, Festschrift in Honor of Professor I. Piatetski-Shapiro (Part II), Weizmann Science Press of Israel (1990), 151-162.

[M6] V. D. Milman, Some applications of duality relations, Lecture Notes in Mathematics 1469 (1991), 13-40.

[MP] B. Maurey and G. Pisier, Séries de variables aleatoires vectorielles independantes et propriétés geometriques des espaces de Banach, Studia Math. 58 (1976), 45-90.

[MiP] V. D. Milman and G. Pisier, Banach spaces with a weak cotype 2 property, Israel J. Math. 54 (1986), 139-158.

[MS] V. D. Milman and G. Schechtman, Asymptotic Theory of Finite-Dimensional Normed Spaces, Lecture Notes in Mathematics 1200 (1986).

[MS2] V. D. Milman and G. Schechtman, Global vs. local asymptotic theories of finite dimensional normed spaces, Preprint.

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

[P2] G. Pisier, Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert, Ann. Sci. Ecole Norm. Sup. 13 (1980), 23-43.

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

[ST] S. J. Szarek and M. Talagrand, An isomorphic version of the Sauer-Shelah lemma and the Banach-Mazur distance to the cube, Lecture Notes in Mathematics 1376 (1989), 105-112.

[STJ] S. J. Szarek and N. Tomczak-Jaegermann, On nearly Euclidean decompositions of some classes of Banach spaces, Compositio Math. 40 (1980), 367-385.

[Su] V. N. Sudakov, Gaussian random processes and measures of solid angles in Hilbert spaces, Soviet Math. Dokl. 12 (1971), 412-415.

[Sz] S. J. Szarek, On Kashin’s almost Euclidean orthogonal decomposition of ℓ_{1}^{n}, Bull. Acad. Polon. Sci. 26 (1978), 691-694.

[T] M. Talagrand, Embedding of ℓ_{∞}^{n} and a theorem of Alon and Milman, Operator Theory: Advances and applications, vol. 77 (1995), 289-293.

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

A. A. Giannopoulos, Department of Mathematics, University of Crete, Iraklion, Crete, Greece

  E-mail address: deligia@talos.cc.uch.gr

V. D. Milman, Department of Mathematics, Tel Aviv University, Tel Aviv, Israel

  E-mail address: vitali@math.tau.ac.il

Current address: (both authors) Mathematical Sciences Research Institute, 1000 Centennial Road, Berkeley, CA 94720