COVERING NUMBERS AND “LOW M^{∗}-ESTIMATE” FOR QUASI-CONVEX BODIES

A. E. LITVAK, V. D. MILMAN, AND A. PAJOR

Abstract. This article gives estimates on covering numbers and diameters of random proportional sections and projections of symmetric quasi-convex bodies in R^{n}. These results were known for the convex case and played an essential role in development of the theory. Because duality relations can not be applied in the quasiconvex setting, new ingredients were introduced that give new understanding for the convex case as well.

1. Introduction and notation

Let | · | be a euclidean norm on R^{n}. Let D be an ellipsoid associated with this

norm. Denote A = \sqrt{\frac{n}{k}} ∫_{S^{n−1}} \sqrt{∑_{i=1}^{k} x_{i}^{2}} dσ(x), where σ is the normalized rotation

invariant measure on the euclidean sphere S^{n−1}. Then A = A(n, k) < 1 and A ⟶ 1 as n, k ⟶ ∞. For any star-body K in R^{n} define M_{K} = ∫_{S^{n−1}} ∥ x ∥ dσ(x), where

∥ x ∥ is the gauge of K. Let M_{K}^{∗} be M_{K^{0}}, where K^{0} is the polar of K. For any subsets K_{1}, K_{2} of R^{n} denote by N(K_{1}, K_{2}) the smallest number N such that there are N points y_{1}, ..., y_{N} in K_{1} such that

K_{1} ⊂ ⋃_{i=1}^{N}(y_{i} + K_{2}).

Recall that a body K is called quasi-convex if there is a constant c such that K + K ⊂ cK, and given a p ∈ (0, 1] a body K is called p-convex if for any λ, μ > 0 satisfying λ^{p} + μ^{p} = 1 and any points x, y ∈ K the point λx + μy belongs to K. Note that for the gauge ∥ · ∥ = ∥ · ∥_{K} associated with the the quasi-convex (p-convex) body K the following inequality holds for any x, y ∈ R^{n}

∥ x + y ∥≤ C max{∥ x ∥, ∥ y ∥} (∥ x + y ∥^{p} ≤ ∥ x ∥^{p} + ∥ y ∥^{p}) .

In particular every p-convex body K is also quasi-convex one and K + K ⊂ 2^{1/p}K. A more delicate result is that for every quasi-convex body K ( K + K ⊂ cK) there exists a q-convex body K_{0} such that K ⊂ K_{0} ⊂ 2cK, where 2^{1/q} = 2c. This is Aoki-Rolewicz theorem ([KPR], [R], see also [K], p.47). In this note by a body we always mean a centrally-symmetric compact star-body, i.e. a body K satisfying tK ⊂ K for any t ∈ [−1, 1], however not all results use symmetry. Lemma 2, some analog of Lemma 4 for p-convex body K, and Theorem 3 hold in non-symmetric case also.

Litvak’s and Milman’s research was partially supported by BSF. Research at MSRI is supported in part by NSF grant DMS-9022140.

Let us remind of the so-called “low M^{∗}-estimate” result.

Theorem 1. Let λ > 0 and n be large enough. Let K be a convex body in R^{n} and ∥ · ∥ be the gauge of K. Then there exists a subspace E of (R^{n}, ∥ · ∥) such that dim E = [λn] and for any x ∈ E the following inequality holds

∥ x ∥≥ \frac{f(λ)}{M_{K}^{∗}}|x|

for some function f(λ), 0 < λ < 1.

Remark. Inequality of this type was first proved in [M1] with very poor dependence on λ and then improved in [M2] to f(λ) = C(1 − λ). It was later shown ([PT]), that one can take f(λ) = C\sqrt{1 − λ} (for different proofs see [M3] and [G]).

By duality this theorem is equivalent to the following theorem.

Theorem 1’ Let λ > 0 and n be large enough. For any convex body K in R^{n} there exists an orthogonal projection P of rank [λn] such that

P D ⊂ \frac{M_{K}}{f(λ)}P K ,

where c is an absolute constant.

In this note we will extend both theorems to quasi-convex bodies. Because duality arguments can not be applied to a non-convex body these two theorems become different statements. Also “”M_{K}^{∗}” should be substituted by an appropriate quantity not involving duality. Note that by avoiding the use of convexity assumption we in

fact simplified proof also for a convex case.

2. Main results

The following theorem is an extension of Theorem 1’.

Theorem 2. Let λ > 0 and n be large enough (n > c/(1 − λ)^{2}). For any p-convex body K in R^{n} there exists an orthogonal projection P of the rank [λn] such that

P D ⊂ \frac{A_{p}M_{K}}{(1 − λ)^{1+1/p}} P K ,

where A_{p} = const^{\frac{ln(2/p)}{p}}.

The proof of this theorem is based on the next three lemmas. The first one was proved by W.B.Johnson and J.Lindenstrauss in [JL]. The second one was proved in [PT] for convex bodies and is the dual form of Sudakov minoration theorem.

Lemma 1. There is an absolute constant c such that if ε > \sqrt{c/k} and N < e^{ε^{2}k/c}, then for any set of points y_{1}, ..., y_{N} ∈ R^{n} and any orthogonal projection P of rank k

μ (\{U ∈ O_{n} | ∀j : A(1 − ε)\sqrt{k/n} |y_{j}| ≤ |P Uy_{j}| ≤ A(1 + ε)\sqrt{k/n} |y_{j}|\}) ≥
≥ 1 − \sqrt{π/2} · e^{−ε^{2}k/c}

Lemma 2. Let K be a body such that K −K ⊂ aK. Then N(D, tK) ≤ 2e^{2n(aM_{K}/t)^{2}}.

M. Talagrand gave a direct simple proof of this lemma for a convex case ([T]). Below, using his idea, we prove more general lemma for p-convex bodies, so we do not prove Lemma 2 now.

Lemma 3. Let B be a star-body, K be a p-convex set, r ∈ (0, 1), {x_{i}} ⊂ rB and B ⊂ ⋃(x_{i} + K). Then B ⊂ t_{r}K, where t_{r} = \frac{1}{(1−r^{p})^{1/p}}.

Proof: Obviously t_{r} = max{∥ x ∥_{K} | x ∈ B}. Since B ⊂ ⋃(x_{i} + K), for any point x in B there are points x_{0} in rB and y in K such that x = x_{0} + y. Then by maximality of t_{r} and p-convexity of K we have t_{r}^{p} ≤ r^{p}t_{r}^{p} + 1. That proves the lemma. Remark. Somewhat similar argument was used by N. Kalton in dealing with pconvex sets.

Proof of Theorem 2: Any p-convex body K satisfies K − K ⊂ aK with a = 2^{1/p}. By Lemma 1 and Lemma 2, we obtain for c_{p} ≈ 2^{1/p} that if

c_{p}n (\frac{M_{K}}{t} )^{2} ≤ \frac{ε^{2}k}{c}

and ε > \sqrt{c/k}, then there exist points x_{1}, ..., x_{N} in D and an orthogonal projection P of rank k such that

P D ⊂ ⋃(P x_{i} + tP K) and |P x_{i}| ≤ (1 + ε)\sqrt{\frac{k}{n}}|x_{i}| .

Let λ = k/n. Denote r = (1 + ε)\sqrt{λ}. Lemma 3 gives us

P D ⊂ tt_{r}P K for t = \frac{\sqrt{cc_{p}}M_{K}}{ε\sqrt{λ}} and ε^{2} > \frac{c}{λn} , r < 1 .

Choose

ε = \frac{1 − \sqrt{λ}}{2\sqrt{λ}} .

Then for n large enough we get

P D ⊂ \frac{A_{p}M_{K}}{(1 − λ)^{1+1/p}} P K ,

for A_{p} = const^{\frac{ln(2/p)}{p}} . This completes the proof.

Theorem 2 can be formulated in the global form.

Theorem 2’ Let K be a p-convex body in R^{n}. Then there is an orthogonal operator U such that

D ⊂ Ap^{′}M_{K}(K + UK) , where Ap^{′} = const^{\frac{ln(2/p)}{p}} .

This theorem can be proved independently, but we show how it follows from Theorem 2. Proof of Theorem 2’: It follows from the proof of Theorem 2 that actually the measure of such projections is large. So we can choose two orthogonal subspaces E_{1}, E_{2} of R^{n} such that dim E_{1} = [n/2], dim E_{2} = [(n + 1)/2] and

P_{i}D ⊂ Ap^{′′}M_{K}P_{i}K ,

where P_{i} is the projection on the space E_{i} (i = 1, 2). Denote I = idR^{n} = P_{1} + P_{2} and U = P_{1} − P_{2}. So P_{1} = 1/2(I + U) and P_{2} = 1/2(I − U). Then U is an orthogonal operator and for any x ∈ D we have

x = P_{1}x + P_{2}x ⊂ 1/2 Ap^{′′}M_{K}(I + U)K + 1/2 Ap^{′′}M_{K}(I − U)K =

= Ap^{′′}M_{K} \frac{K + K}{2} + Ap^{′′}M_{K} \frac{UK − UK}{2} = Ap^{′}M_{K}(K + UK) .

That proves Theorem 2’.

Let us complement Lemma 2 by mentioning how covering number N(K, tD) can be estimated. In convex case this estimate is given by Sudakov inequality, using quantity M^{∗}. More precisely, if K is a convex body, then

N(K, tD) ≤ 2e^{cn(M_{K}^{∗}/t)^{2}} .

Of course, using duality for a non-convex setting leads to a weak result, and we suggest below a substitution for quantity M^{∗}.

For two quasi-convex bodies K, B define the following number

M(K, B) = \frac{1}{|K|} ∫_{K} ∥ x ∥_{B} dx ,

where |K| is volume of K, and ∥ x ∥_{B} is the gauge of B. Such numbers are considered in [MP1], [MP2] and [BMMP].

Lemma 4. Let K and B be star-bodies. Assume B + B ⊂ aB. For θ > 0 denote by c_{θ} = c_{θ}(K) the best possible constant such that

∥ x + y ∥_{K}^{θ} + ∥ x − y ∥_{K}^{θ}≤ 2 · c_{θ}^{θ} (∥ x ∥_{K}^{θ} + ∥ y ∥_{K}^{θ}) for any x, y ∈ R^{n} .

Then

N(K, tB) ≤ 2c_{θ}^{n}e^{(cn/θ)(aM(K,B)/t)^{θ}} , where c is an absolute constant.

Note, that in a case θ = 1 which correspond to the general convex case this lemma was announced in [MP2]. Proof: We follow the idea of M.Talagrand of estimating covering numbers in case K = D ([T], see also [BLM] Proposition 4.2). Denote the gauge of K by ∥ · ∥ and the gauge of B by | · |. Define the measure μ by following

dμ = \frac{1}{A}e^{−∥x∥^{θ}}dx , where A chosen such that \begin{matrix}∫ \\ R & ^{n} \end{matrix} dμ = 1 .

Let L = \begin{matrix}∫ \\ R & ^{n} \end{matrix} |x|dμ. Then μ\{|x| ≤ 2L\} ≥ 1/2. Let x_{1}, x_{2}, ... be a maximal set of points

in K such that |x_{i} − x_{j}| ≥ t. So the sets x_{i} + \frac{t}{a}B have mutually disjoint interiors. Let y_{i} = \frac{ab}{t}x_{i} for some b. Then, by symmetry of B and convexity of the function e^{t}, we have

μ\{y_{i} + bB\} = \frac{1}{A} ∫_{bB} e^{−∥x+y_{i}∥^{θ}}dx = \frac{1}{2A} ∫_{bB} e^{−∥x+y_{i}∥^{θ}} + e^{−∥x−y_{i}∥^{θ}}dx ≥

≥ \frac{1}{A} ∫_{bB} e^{− \frac{1}{2} (∥x+y_{i}∥^{θ}+∥x−y_{i}∥^{θ})}dx ≥ \frac{1}{A} ∫_{bB} e^{−c_{θ}^{θ}(∥x∥^{θ}+∥y_{i}∥^{θ})}dx =

= \frac{1}{A}e^{−∥c_{θ}y_{i}∥^{θ}} ∫_{bB} e^{−∥c_{θ}x∥^{θ}}dx ≥ e^{−(c_{θ}ba/t)^{θ}}c_{θ}^{−n}μ\{c_{θ}bB\}

Choose b = 2L/c_{θ}. Then μ{c_{θ}bB} ≥ 1/2 and, hence,

N(K, tB) ≤ 2c_{θ}^{n}e^{(2aL/t)^{θ}} .

Now compute L. First, the normalization constant A is equal

A =\begin{matrix}∫ \\ R & ^{n} \end{matrix} e^{−∥x∥^{θ}}dx =\begin{matrix}∫ \\ R & ^{n} \end{matrix} ∫_{∥x∥}^{∞}(−e^{−t^{θ}})′dtdx = ∫_{0}^{∞}θt^{θ−1}e^{−t^{θ}} ∫_{∥x∥≤t} dxdt =

= ∫_{∥x∥≤1} dx ∫_{0}^{∞}θt^{θ+n−1}e^{−t^{θ}}dt = |K| · Γ (1 + \frac{n}{θ}) ,

where Γ is the gamma-function. The remaining integral is

\begin{matrix}∫ \\ R & ^{n} \end{matrix} |x|e^{−∥x∥^{θ}}dx =\begin{matrix}∫ \\ R & ^{n} \end{matrix} |x| ∫_{∥x∥}^{∞}(−e^{−t^{θ}})′dtdx = ∫_{0}^{∞}θt^{θ−1}e^{−t^{θ}} ∫_{∥x∥≤t} |x|dxdt =

= ∫_{∥x∥≤1} |x|dx ∫_{0}^{∞}θt^{θ+n}e^{−t^{θ}}dt = |K| · M(K, B) · Γ (1 + \frac{n + 1}{θ}) .

Using Stirling’s formula we get

L ≈ (\frac{n}{θ})^{1/θ} M(K, B) .

That proves the lemma.

This lemma is an extension of Lemma 2. Indeed, since Euclidean space is a 2smooth space, then in case K = D being an ellipsoid, we have c_{2}(D) = 1. By direct computation, M(D, B) = \frac{n}{n+1}M_{B}. Thus,

N(D, tB) ≤ 2e^{(cn)(M_{B}/t)^{2}} .

Define the following characteristic of K,

M̃_{K} = \frac{1}{|K|} ∫_{K} |x|dx .

By definition, if K is a p-convex body, then for any x, y ∈ R^{n} holds

∥ x + y ∥_{K}^{p} + ∥ x − y ∥_{K}^{p}≤ 2 · (∥ x ∥_{K}^{p} + ∥ y ∥_{K}^{p}) .

So, the last lemma shows that for p-convex body K

N(K, tD) ≤ 2e^{(cn/p)(2M̃_{K}/t)^{p}} .

The Theorem 3 follows from this estimate by arguments similar of that in [MP].

Theorem 3. Let λ > 0 and n be large enough. Let K be a p-convex body in R^{n} and ∥ · ∥ be the gauge of K. Then there exists subspace E of (R^{n}, ∥ · ∥) such that dim E = [λn] and for any x ∈ E the following inequality holds

∥ x ∥≥ \frac{(1 − λ)^{1/2+1/p}}{a_{p}M̃_{K}} |x| ,

where a_{p} depends on p only (more precisely a_{p} = const^{\frac{ln(2/p)}{p}}).

Proof: By Lemma 4 there are points x_{1}, ..., x_{N} in K, such that N < e^{c_{p}n(M̃_{K}/t)^{p}} and for any x ∈ K there exists some x_{i} such that |x − x_{i}| < t. By Lemma 1 there exists an orthogonal projection P on a subspace of dimension δn such that for

c_{p}n (\frac{M̃_{K}}{t} )^{p} < \frac{ε^{2}δn}{c} and ε > \sqrt{\frac{c}{δn}}

we have

b|x_{i}| = (1 − ε)A\sqrt{δ}|x_{i}| ≤ |P x_{i}| ≤ (1 + ε)A\sqrt{δ}|x_{i}|

for every x_{i}. Let E = KerP. Then dim E = λn, where λ = 1 − δ. Take x in K ⋂ E. There is x_{i} such that |x − x_{i}| < t. Hence

|x| ≤ |x − x_{i}| + |x_{i}| ≤ t + \frac{|P x_{i}|}{b} = t + \frac{|P (x − x_{i})|}{b} ≤

≤ t + \frac{|x − x_{i}|}{b} ≤ t(1 + \frac{1}{b}) ≤ \frac{const · t}{(1 − ε)\sqrt{δ}}

Therefore for n large enough and

t = (\frac{const · c_{p}}{ε^{2}δ} )^{1/p} M̃_{K}

we get

∥ x ∥≥ \frac{const · ε^{2}(1 − ε)δ^{1/2+1/p}}{c_{p}^{1/p}M̃_{K}} |x| .

To obtain our result take ε, say, equal to 1/2.

As was noted in [MP2] in some cases M̃_{K} << M^{∗} and then Theorem 3 gives better estimate than Theorem 1 even for a convex body (in some range of λ). As an example, K = B(l_{1}^{n}), M̃_{K} ≤ const · n^{−1/2}, but M_{K}^{∗} ≥ const · n^{−1/2}(log n)^{1/2}.

3. Additional remarks

In fact, during the proof of Theorem 2 a more general fact was proved.

Fact. Let D be an ellipsoid and K be a p-convex body. Let

N(D, K) ≤ e^{αn} .

Denote for an integer 1 ≤ k ≤ n the ratio λ = k/n. Then for some absolute constant c and

γ = c\sqrt{α} , k ∈ (γ^{2}n, (1 − 2γ)^{2}n)

there exists an orthogonal projection P of rank k such that

(p(1 − \sqrt{λ})/2)^{1/p} P D ⊂ P K .

In terms of entropy numbers this means

\frac{(p(1 − \sqrt{k/n})/2)^{1/p}}{e_{k}(D, K)} P D ⊂ P K ,

where e_{k}(D, K) = inf{ε > 0 | N(D, εK) ≤ 2^{k−1}} .

It is worth to point out that Theorem 2 can be obtained from this results.

We thank E. Gluskin for his remarks on the first draft of this note.

References

[BLM]: Bourgain, J. ; Lindenstrauss, J. ; Milman, V. Approximation of zonoids by zonotopes.

Acta Math. 162 (1989), no. 1-2, 73–141. [BMMP]: Bourgain, J. ; Meyer, M. ; Milman, V. ; Pajor, A. On a geometric inequality. Geomet-

ric aspects of functional analysis (1986/87), 271–282, Lecture Notes in Math., 1317, Springer, Berlin-New York, 1988.

[JL]: Johnson, W. B.; Lindenstrauss, J. Extensions of Lipschitz mappings into a Hilbert space.

Conference in modern analysis and probability (New Haven, Conn., 1982), 189–206, [G]: Gordon, Y. On Milman’s inequality and random subspaces which escape through a mesh

in R^{n}. Geometric aspects of functional analysis (1986/87), 84–106, Lecture Notes in Math., 1317, Springer, Berlin-New York, 1988.

[KPR]: N.J.Kalton, N.T.Peck, J.W.Roberts, An F -space sampler, London Mathematical Soci-

ety Lecture Note Series, 89, Cambridge University Press, Cambridge and New York, 1984. [K]: König, H. Eigenvalue Distribution of Compact Operators , Birkhäuser, 1986. [M1]: Milman, V. D. Almost Euclidean quotient spaces of subspaces of a finite-dimensional

normed space. Proc. Amer. Math. Soc. 94 (1985), no. 3, 445–449. [M2]: Milman, V. D. Random subspaces of proportional dimension of finite-dimensional normed

spaces: approach through the isoperimetric inequality. Banach spaces (Columbia, Mo., 1984), 106–115, Lecture Notes in Math., 1166, Springer, Berlin-New York, 1985.

[M3]: Milman, V. D. A note on a low M^{∗}-estimate. Geometry of Banach spaces (Strobl, 1989), 219–229, London Math. Soc. Lecture Note Ser., 158, Cambridge Univ. Press, Cambridge, 1990.

[MP1]: Milman, V. D. ; Pajor, A. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space. Geometric aspects of functional analysis (1987–88), 64–104, Lecture Notes in Math., 1376, Springer, Berlin-New York, 1989.

[MP2]: Milman, V. ; Pajor, A. Cas limites dans des inégalités du type de Khinchine et applications géométriques. (French) [Limit cases of Khinchin-type inequalities and some geometric applications] C. R. Acad. Sci. Paris Sér. I Math. 308 (1989), no. 4, 91–96.

[PT]: Pajor, A. ; Tomczak-Jaegermann, N. Subspaces of small codimension of finite-dimensional

Banach spaces. Proc. Amer. Math. Soc. 97 (1986), no. 4, 637–642. [R]: Rolewicz, S. Metric linear spaces. Monografie Matematyczne, Tom. 56. [Mathematical

Monographs, Vol. 56] PWN-Polish Scientific Publishers, Warsaw, 1972.

A. E. Litvak, Department of Mathematics, Tel Aviv University, Ramat Aviv, Israel

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

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

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

A. Pajor, Universite de Marne-la-Vallée, Equipe de Mathematiques, 2 rue de la Butte Verte, 93166 Noisy-le-Grand Cedex, France

E-mail address: pajor@math.univ-mlv.fr