Preprint (1999),

Embedding subspaces of L_{p} into ℓ_{p}^{N}, 0 < p < 1

By Gideon Schechtman of Rehovot and Artem Zvavitch of Rehovot

( February, 1999)

Abstract. It is shown that if X is n-dimensional subspace of L_{p}, 0 < p < 1, then there exists a subspace Y of ℓ_{p}^{N} such that d(X, Y) ≤ 1 + ε and N ≤ C(ε, p)n(log n)^{3}.

1. Introduction

Given an n-dimensional subspace X of L_{p}([0, 1], dt) and, ε > 0 what is the smallest integer N = N(n, ε) such that there is a subspace Y of ℓ_{p}^{N} with d(X, Y) ≤ 1 + ε, where d(X, Y) is the Banach-Mazur distance? For p ≥ 1 the dependence of N on n is known, except for possibly redundant log factors. (It is, forgetting log factors, n, for 1 ≤ p < 2, and n^{p/2}, for 2 < p < ∞. See Bourgain, Lindenstrauss and Milman [1], Talagrand [10], [11] for the best known results). In the case of 0 < p < 1 the known result is only N(n, ε) ≤ c(ε, p)n^{2} (see Schechtman [9]). Recently Peña [8] considered the problem we address in the present paper, i.e. extending the result of [1] to the range 0 < p < 1, and observed that any X as above admits a Y ⊆ ℓ_{p}^{N} with N ≤ C(p)n and d(X, Y) ≤ C(p)(log n)^{1/p}. The problem of reducing the log n factor to 1 + ε was left open in [8] and was the trigger to the present note. For a more extensive review of the background material see the forthcoming [7].

In this paper we extend the result of [1] to the range 0 < p < 1 by proving the following result.

Theorem 1.1. Let 0 < p < 1 then

N(n, ε) ≤ C(p, ε)n(log n)^{3}.

Throughout this paper C, c, c_{1} etc. denote absolute constants whose value may change from line to line. Similarly C(p), c(p), C(p, ε) denote constants depending on the arguments, p or p and ε, only.

1991 Mathematics Subject Classification. Primary 46E30, 46B07; Secondary 46B09, 60G15.

Keywords and phrases. L_{p}, ℓ_{p}^{N}, Lewis’ change of density, entropy estimates.

The proof is by the method initiated in [9] and refined in [1] of random selection of coordinates. We may assume that X ⊆ ℓ_{p}^{M} for some finite (but large) M and we would like to choose randomly a small set A of coordinates for which the operator of restriction to A is an isomorphism on X. It is easy to see that this is impossible in general (for example if X is essentially supported on a small subset of the coordinates). So we need to first change the “location” of X in ℓ_{p}^{M}. This is done (as in all the previous references) via change of density. In the existing literature referred to above one uses the so called Lewis’ change of density. This was available until now only in the range p ≥ 1, indeed, the proof in [4] uses duality in an essential way. In section 2. below we extend Lewis’ result to the range 0 < p < 1. The proof is new and simpler even in the known range and we believe it is of independent interest.

Rather than choosing the set A of coordinates in one step we prefer do to it iteratively reducing the size of M by a factor of approximately 1/2 each time. (This is the approach of [10].) This amounts to estimating

sup_{x∈X,∥x∥≤1} | ∑_{i=1}^{M} ε_{i}|x_{i}|^{p}| (1.1)

over a typical choice of signs ε_{i}, i = 1, 2, …, M. Indeed, if for a particular choice of signs this quantity is smaller than δ then it is easy to see that the restriction operator

to both A = \{i; ε_{i} = 1\} and A^{c} = \{i; ε_{i} = −1\} is an (\frac{1+δ}{1−δ} )^{1/p}-isomorphism.

The expected value of (1.1) over all choices of signs is dominated by a similar expression with independent Gaussian variables replacing the ε_{i} -s:

IE sup_{x∈X,∥x∥≤1} | ∑_{i=1}^{M} g_{i}|x_{i}|^{p}|.

To estimate this quantity we use, as is done implicitly in [1], a theorem of Dudley. This is done in section 4.. The method requires fine entropy estimates and these are developed in section 3.. The proof of the entropy estimates is based on a proof of a similar estimate in [1]. The main difficulty for us was to realize that in spite of the way it is written there these estimates do not use duality in an essential way. In the last section of this paper we gather all the ingredients into a proof of Theorem 1.1

2. Lewis’ theorem in the non-convex setting

We first state and prove a theorem (due to Lewis [4] in the range 1 ≤ p < ∞) concerning the existence of special bases in finite dimensional subspaces of L_{p}. Even for p ≥ 1 the proof is somewhat different and more direct than that of Lewis and in particular does not use explicitly Lewis’ lemma [5] nor the notion of p-summing operators.

Schechtman, Zvavitch, Embedding subspaces of L_{p} into ℓ_{p}^{N}  3

Theorem 2.1. Let X be an n-dimensional subspace of L_{p}(Ω, μ), 0 < p < ∞. Then, there is a basis f_{1}, …, f_{n} of X satisfying

∫ ( ∑_{i=1}^{n} f_{i}^{2})^{(p−2)/2}f_{k}f_{l}dμ = δ_{kl}, 1 ≤ k, l ≤ n. (2.1)

In particular, one can find a probability measure ν on Ω and a subspace X̃ of L_{p}(Ω, ν) isometric to X which admits a basis h_{1}, …, h_{n} orthonormal in L_{2}(Ω, ν), such that ∑_{i=1}^{n} h_{i}^{2} ≡ n.

Proof. We first assume that Ω is finite. Assume without loss of generality that X has maximal support, i.e., for every t ∈ Ω, there is a x ∈ X with x(t) ≠ 0.

Let {x_{i}}_{i=1}^{n} be a basis for X. Given an n × n matrix B = (b_{ij})_{i,j=1}^{n}, we consider it as an operator from IR^{n} into X sending the basis vector e_{i} to ∑_{j=1}^{n} b_{ij}x_{j}. Let A = (a_{ij})_{i,j=1}^{n} be the n × n matrix which maximizes det(B) subject to

∥( ∑_{i=1}^{n}(Be_{i})^{2})^{1/2}∥_{p} ≤ 1.

Note that necessarily {Ae_{i}}_{i=1}^{n} is a basis for X and in particular ∑_{i=1}^{n}(Ae_{i})^{2}(t) > 0 for

all t ∈ Ω. Consequently, for every t the function ( ∑_{i=1}^{n}(Be_{i})(t)^{2})^{p/2} is continuously differentiable at A as a function of (b_{ij}) and

\frac{∂}{∂b_{kl}} ∥( ∑_{i=1}^{n}(Be_{i})^{2})^{1/2}∥_{p}^{p} = \frac{∂}{∂b_{kl}} ∫ ( ∑_{i=1}^{n} ( ∑_{j=1}^{n} b_{ij}x_{j}(t))^{2})^{p/2}dμ(t) (2.2)

= p ∫ ( ∑_{i=1}^{n} ( ∑_{j=1}^{n} b_{ij}x_{j}(t))^{2})^{(p−2)/2}( ∑_{s=1}^{n} b_{ks}x_{s}(t))x_{l}(t)dμ(t).

Now, as is well known (expand det(B) by the k^{th} row), \frac{∂}{∂b_{kl}} det(B) is the lk element of B^{−1} multiplied by det(B). By the method of Lagrange multipliers, we get that

C = (\frac{∂}{∂a_{kl}} ∥( ∑_{i=1}^{n}(Ae_{i})^{2})^{1/2}∥_{p}^{p})_{i,j}^{n} is a multiple of (\frac{∂}{∂a_{kl}} det(A))_{i,j}^{n} which, as we have

just remarked, is a multiple of A^{∗−1}, i.e., A^{∗}C is a multiple of the identity matrix. Put f_{k} = ∑_{s=1}^{n} a_{ks}x_{s}, then it follows from (2.2) that for some λ ∈ IR,

∫ ( ∑_{i=1}^{n} f_{i}^{2}(t))^{(p−2)/2}f_{k}(t)f_{u}(t)dμ(t) = λδ_{uk}

which, after normalization, gives a basis satisfying (2.1). Put

f(t) = ( ∑_{i=1}^{n} f_{i}^{2}(t))^{1/2}, ν({t}) = f^{p}(t)/ ∫ f^{p}(s)dμ(s),

X̃ = {x/f ; x ∈ X} and h_{i} = n^{1/2}f_{i}/f

then h_{1}, …, h_{n} is the required basis in the ‘In particular’ part of the theorem.

This finishes the proof in the case that μ is finitely supported. This case is all we need for the rest of this paper so we only sketch the easy generalization. First, by changing the density, i.e. dividing the elements of X by some positive L_{p} function φ and changing the measure to φ^{p}dμ, we may assume that for some constant K (depending on n) every norm one function in X is bounded by K. Now, for every ε there is a subspace X_{ε} of the same L_{p} space which consists of simple functions and which is ε close to X in the sense that for every norm one function f in X (resp. X_{ε}) there is a function g in X_{ε} (resp. X) with ∥f − g∥ < ε. By the first part of the proof there is a basis f_{1}^{ε}, …, f_{n}^{ε} in X_{ε} satisfying (2.1). Any limit f_{1}, …, f_{n} of these bases as ε → 0 along some subsequence, will satisfy (2.1) as well and be in X. To get the basis h_{1} …, h_{n} we change the density again as in the discrete case above. □

Remarks: 1. Note that if X is a subspace of ℓ_{p}^{M} and μ is the probability measure on {1, …, M} given by the theorem above then, as observed in [6] we can split each atom of ν of mass large than 4/M into pieces each of size between 2/M and 4/M. This will enlarge the number of atoms by at most M/2. The new measure, which we still denote by ν, is now supported on {1, …, M′}, where M′ ≤ 3M/2. μ({i}) ≤ 4/M for all i, X is still isometric to a subspace (which we continue to denote by X) of L_{p} of the new measure space and the new X admits an orthonormal basis h_{1}, …, h_{n} whose sum of squares is a constant.

2. Let X̃ be as given in Theorem 2.1. If x ∈ X̃ then, for 0 < p < 2,

∥x∥_{2} ≤ n^{1/p−1/2}∥x∥_{p} and ∥x||_{∞} ≤ n^{1/p}∥x∥_{p}.

Indeed, If x ∈ X̃ and x = ∑_{i=1}^{n} α_{i}h_{i} then

∥x∥_{∞} ≤ (∑_{i=1}^{n} α_{i}^{2})^{1/2}∥(∑_{i=1}^{n} h_{i}^{2})^{1/2}∥_{∞} ≤ n^{1/2}∥x∥_{2}

and

∥x∥_{2}^{2} ≤ ∥x∥_{∞}^{2−p}∥x∥_{p}^{p} ≤ n^{(2−p)/2}∥x∥_{2}^{2−p}∥x∥_{p}^{p}.

Thus ∥x∥_{2} ≤ n^{1/p−1/2}∥x∥_{p}. Note that this implies in particular that d(X, ℓ_{2}^{n}) ≤ n^{1/p−1/2} for every n dimensional subspace of L_{p}. This extends a result of Lewis [4] to the range 0 < p < 1.

3. The basis with property (2.1) is unique up to orthogonal transformation: Let X and f_{1}, …, f_{n} be as in Theorem 2.1 and let g_{1}, …, g_{n} be another basis satisfying (2.1), i.e. ∫ F^{p−2}f_{k}f_{l}dμ = ∫ G^{p−2}g_{k}g_{l}dμ = δ_{kl}, 1 ≤ k, l ≤ n (2.3)

where F = ( ∑_{i=1}^{n} f_{i}^{2})^{1/2} and G = ( ∑_{i=1}^{n} g_{i}^{2})^{1/2}. Then there exists an orthonormal matrix U = (a_{ij}) such that f_{i} = ∑_{j=1}^{n} a_{ji}g_{j}, i = 1, …, n. We are going to show

that F = G from which the assertion easily follows. Denote by X_{F} (resp. X_{G}) X considered as a subspace of L_{2}(F^{p−2}dμ) (resp. L_{2}(G^{p−2}dμ). Define three Hilbert space isometries, u : ℓ_{2}^{n} → X_{F}, v : ℓ_{2}^{n} → X_{G}, and T : X_{F} → X_{G} by

u(e_{i}) = f_{i}, v(e_{i}) = g_{i}, i = 1, …, n and T x = xG^{−(p−2)/2}F^{(p−2)/2}.

U = v^{−1}T u is a unitary operator on ℓ_{2}^{n} represented by the orthogonal matrix U = (a_{ij}). Then on one hand T f_{i} = ∑_{j=1}^{n} a_{ji}g_{j} and on the other hand T f_{i} = f_{i}G^{−(p−2)/2}F^{(p−2)/2} squaring, summing over i and using the fact that ∑_{i=1}^{n}(∑_{j=1}^{n} a_{ji}g_{j})^{2} ≡ ∑_{i=1}^{n} g_{i}^{2} we get that F = G.

4. As we remarked above Lewis’ proof of Theorem 2.1 is based on another theorem of Lewis [5] which states that if α is a norm on IR^{n^{2}} regarded as the space of n×n matrices and α^{∗} is the dual norm where duality is given by the trace (traceBA = ⟨B^{∗}, A⟩, where ⟨·, ·⟩ is the usual scalar product in IR^{n^{2}}) then there is an invertible matrix A with α(A) = 1 and α^{∗}(A^{−1}) = n. The proof (first used by F. John for α being an operator norm) is by a variational argument and A is obtained as a point at which det(A) is maximal under the constraint: α(A) ≤ 1. The proof is quite simple but it may be instructive to notice that, although this is not the way it is commonly presented, it is really just a solution of a maximization problem under constraints, using the method of Lagrange multipliers. Indeed, assuming the norm α is smooth, the gradient of α(A) considered as a function on IR^{n^{2}} \ {0} is (like the gradient of any norm on IR^{m}) the norming functional of A, i.e., a matrix B = B_{A} such that α(B) = 1 and traceBA = α(A). Since the gradient of det(A) is a multiple of A^{∗−1} we get that B_{A} is a multiple of A^{−1}. (The reason for removing the adjoint is the relation between trace duality and the usual duality in IR^{n^{2}}.) It is now easy to see that the multiple must be 1/n.

3. Entropy estimates

Let X be an n dimensional subspace of L_{p}(Ω, ν) for some probability measure ν and assume X admits an orthonormal basis f_{1}, …, f_{n} with ∑ f_{i}^{2} ≡ n. For 0 < q ≤ ∞ denote by B_{q} = B_{q}(X) the unit ball of X in the L_{q}(Ω, ν) norm. By E(B_{r}, B_{s}, t) we denote the metric entropy of B_{p} with respect to tB_{s}, i.e., the minimal number of translates of tB_{s} needed to cover B_{r}. The case p ≥ 1 of the next proposition has been implicitly proved in [1] (see the proof of Proposition 7.2 there). A superficial glance at the proof there seems to imply that duality is used. As we shall see below this is not really the case and a small variation of the proof works also in the range 0 < p < 1.

Proposition 3.1. Let 0 < p < 2 then, for any t > 1,

log E(B_{p}, B_{2}, t) ≤ c(p)n(log n)t^{−2p/(2−p)}.

Proof. For k = 0, 1, …, let E_{k} be a maximal subset of B_{p} with respect to the condition: ||f − g||_{2} > 8^{k}t for every f ≠ g in E_{k}. (For k such that 8^{k}t > n^{(2−p)/2p} we take E_{k} = {0}). Then

|E_{k}| ≥ E(B_{p}, B_{2}, 8^{k}t).

Since, for every k there are x_{i} ∈ B_{p}, i = 1, 2, …, E = E(B_{p}, B_{2}, 8^{k+1}t), satisfying ∪_{i=1}^{E}{x_{i} + 8^{k+1}tB_{2}} ⊇ B_{p}, we can find for every k a y_{k} ∈ B_{p} such that

|\{y_{k} + 8^{k+1}tB_{2}\} ∩ E_{k}| ≥ \frac{|E_{k}|}{E(B_{p}, B_{2}, 8^{k+1}t)} ≥ \frac{E(B_{p}, B_{2}, 8^{k}t)}{E(B_{p}, B_{2}, 8^{k+1}t)}. (3.1)

Let L_{k} = {(f − y_{k})/8^{k+1}t, f ∈ {y_{k} + 8^{k+1}tB_{2}}} ∩ E_{k}. Then,

||g||_{2} ≤ 1, ||g||_{p} ≤ 2^{1/p}/8^{k+1}t, for any g ∈ L_{k}

and

||g − g′||_{2} > 1/8, for any g ≠ g′, g, g′ ∈ L_{k}.

For g ≠ g′ and 0 < θ < p,

\begin{aligned}||g − g′||_{2}^{2} & = ∫_{Ω} |g − g′|^{θ}|g − g′|^{2−θ}dν \\ & ≤ (∫_{Ω} |g − g′|^{p}dν)^{θ/p} (∫_{Ω} |g − g′|^{(2−θ)p/(p−θ)}dν)^{(p−θ)/p} . \end{aligned}

Let r = (2 − θ)p/(p − θ), then r > 2, and for any g ≠ g′, g, g′ ∈ L_{k},

\begin{aligned}8^{−2} & < ||g − g′||_{2}^{2} = ∫ |g − g′|^{θ}|g − g′|^{2−θ} \\ & ≤ ||g − g′||_{p}^{θ}||g − g′||_{r}^{2−θ} ≤ (2^{1/p}/8^{k+1}t)^{θ}||g − g′||_{r}^{2−θ} \end{aligned}

or

||g − g′||_{r} > 8^{−3/(2−θ)}(8^{k+1}t)^{θ/(2−θ)} for all g ≠ g′, g, g′ ∈ L_{k}.

It particular, E(B_{2}, B_{r}, 8^{−3/(2−θ)}(8^{k+1}t)^{θ/(2−θ)}) ≥ |L_{k}|. (3.2)

We now use (7.13) in the proof of Proposition 7.2 of [1] according to which

log E(B_{2}, B_{r}, s) ≤ crn(log n)(s/c)^{−2 \frac{(2−θ)p}{θ(2−p)}} .

It follows that

log E(B_{2}, B_{r}, 8^{−3/(2−θ)}(8^{k+1}t)^{θ/(2−θ)}) ≤ c^{1+2 \frac{(2−θ)p}{θ(2−p)}} rn(log n)(8^{k+1}t)^{−2p/(2−p)}

and picking θ = p/2 we get

log E(B_{2}, B_{r}, 8^{−3/(2−θ)}(8^{k+1}t)^{θ/(2−θ)}) ≤ c^{1/(2−p)}n(log n)(8^{k+1}t)^{−2p/(2−p)}.

Now, (3.1) and (3.2) imply that

c^{1/(2−p)}n(log n)(8^{k+1}t)^{−2p/(2−p)} ≥ log |L_{k}| = log |{y_{k} + 8^{k+1}tB_{2}} ∩ E_{k}|
≥ log E(B_{p}, B_{2}, 8^{k}t) − log E(B_{p}, B_{2}, 8^{k+1}t).

By summing these inequalities over all k we obtain

log E(B_{p}, B_{2}, t) ≤ c(p)n(log n)t^{−2p/(2−p)}.

The constant c(p) is bounded by c^{1/(2−p)}/p for some universal c. □

Remark: As in [1] one can get also that for every n dimensional subspace X of L_{p} and for every ε there is another subspace X̃ of L_{p} whose Banach-Mazur distance from X is at most 1 + ε and, letting B̃_{q} denote the unit ball of X̃ with respect to the L_{q} norm,

log E(B̃_{p}, B̃_{∞}, t) ≤ c(p)n log(nε^{−1})t^{−p}

for t > 1.

4. A Bound on a Gaussian process

Let X be an n dimensional subspace of L_{p}(Ω, ν) for a set Ω with K points and some probability measure ν satisfying ν({i}) ≤ 6/K and assume X admits an orthonormal basis f_{1}, …, f_{n} with ∑ f_{i}^{2} ≡ n.

Proposition 4.1. Let 0 < p < 1 and let g_{i}, i = 1, …, K be independent standard Gaussian random variables. Then

IE sup_{x∈B_{p}} | ∑_{i=1}^{K} ν(\{i\})g_{i}|x(i)|^{p}| ≤ c(p) (\frac{n}{K} (log n)^{3})^{\frac{1}{2}} .

Proof. Let δ be the natural distance associated with the Gaussian process {G_{x} =

∑_{i=1}^{K} ν({i})g_{i}|x(i)|^{p}}_{x∈B_{p}}, i.e.,

δ(y, z) = ( ∑_{i=1}^{K}[ν({i})(|y_{i}|^{p} − |z_{i}|^{p})]^{2})^{1/2}, y, z ∈ B_{p}.

Let θ = (1 − p)/(2 − p) then

(4.1)  δ(y, z)^{2} ≤ ∑_{i=1}^{K} ν({i})^{2}|y_{i} − z_{i}|^{2p}
≤ 6K^{−1}||y − z||_{p}^{θ2p}||y − z||_{2}^{(1−θ)2p}
≤ 12K^{−1}||y − z||_{2}^{2p/(2−p)}.

By the second remark following Theorem 2.1 ∥x∥_{2} ≤ n^{(2−p)/2p}∥x∥_{p} for all x ∈ X It follows that the δ diameter of B_{p} is at most (12n)^{1/2}K^{−1/2}.

Proposition 3.1 and (4.1) also imply

log E(B_{p}, δ, t) ≤ log E(B_{p}, (12K^{−1})^{1/2}|| · ||_{2}^{p/(2−p)}, t)
≤ log E(B_{p}, || · ||_{2}, 12^{−(2−p)/2p}K^{(2−p)/2p}t^{(2−p)/p})
≤ c(p)n(log n)K^{−1}t^{−2}.

The last inequality in the later display requires that t ≥ 12^{1/2}K^{−1/2}. For 0 < t < 12^{1/2}K^{−1/2} we first obtain that

δ(y, z)^{2} ≤ ∑_{i=1}^{K} ν({i})^{2}|y_{i} − z_{i}|^{2p}

≤ ( ∑_{i=1}^{K}(ν{i})|y_{i} − z_{i}|^{p})^{2} ≤ ||y − z||_{p}^{2p}.

Then we use standard volume considerations in the n-dimensional space X to obtain

log E(B_{p}, δ, t) ≤ log E(B_{p}, || · ||_{p}^{p}, t)
≤ log E(B_{p}, || · ||_{p}, t^{1/p}) ≤ cn log t^{−1}.

Finally, by Dudley’s theorem ([2], [3]),

IE sup_{x∈B_{p}} | ∑_{i=1}^{K} ν({i})g_{i}|x(i)|^{p}| ≤ c ∫_{0}^{(12n)^{1/2}K^{−1/2}}(log E(B_{p}, δ, t))^{1/2}

≤ ∫_{12^{1/2}K^{−1/2}}^{(12n)^{1/2}K^{−1/2}} c(p)n^{1/2}(log n)^{1/2}K^{−1/2}t^{−1}dt

+c ∫_{0}^{12^{1/2}K^{−1/2}} n^{1/2}(log t^{−1})^{1/2}dt
≤ c(p) (\frac{n}{K} (log n)^{3})^{\frac{1}{2}} .
□

5. The proof of Theorem 1.1

By a simple approximation we may assume that X is a subspace of ℓ_{p}^{M} for some finite M. Using Theorem 2.1 and the first remark following it we may then assume that X ⊆ L_{p}(Ω, ν) where |Ω| ≤ 3M/2, ν_{i} = ν({i}) ≤ 4/M for all i ∈ Ω and X admits an orthonormal basis f_{1}, …, f_{n} with ∑ f_{i}^{2} ≡ n. We would like to find a subset A ⊂ Ω for which

sup_{x∈X,∥x∥≤1} |2 ∑_{i∈A} ν_{i}|x_{i}|^{p} − ∑_{i∈ω} ν_{i}|x_{i}|^{p}| ≤ (c(p)nM^{−1}(log n)^{3})^{1/2}. (5.1)

Then the restriction operators to both A and the complement of A are

(\frac{1+(c(p)nM^{−1}(log n)^{3})^{1/2}}{1−(c(p)nM^{−1}(log n)^{3})^{1/2}} )^{1/p}-isomorphisms and of course one of A or A^{c} is of cardinality at most 3M/4. This reduces the dimension of the containing space from M to 3M/4. Iterating, we get that as long as

∏_{i=1}^{l} (\frac{1 + (c(p)n3^{i}(4M)^{−i}(log n)^{3})^{1/2}}{1 − (c(p)n3^{i}(4M)^{−i}(log n)^{3})^{1/2}} )^{1/p} ≤ 1 + ε, (5.2)

X (1 + ε)-embeds into ℓ_{p}^{m} for some m ≤ M(3/4)^{−l−1}. Now (5.2) is satisfied for l such that M(3/4)^{−l−1} ≤ C(p, ε)n(log n)^{3} (for C(p, ε) of the form C(p)/ε^{2}) which would conclude the proof if we only could establish (5.1).

To find a set A satisfying (5.1) it is enough to prove that

Ave_{A} sup_{x∈X,∥x∥≤1} |2 ∑_{i∈A} ν_{i}|x_{i}|^{p} − ∑_{i∈Ω}^{m} ν_{i}|x_{i}|^{p}|
= IE sup_{x∈X,∥x∥≤1} | ∑_{i∈Ω} ε_{i}ν_{i}|x_{i}|^{p}| ≤ (c(p)nM^{−1}(log n)^{3})^{1/2}.

(5.3)

Here Ave_{A} denotes the average over all subsets of Ω while IE is the expectation with respect to the natural product measure on {−1, 1}^{Ω}. The contraction principle (which is simple in this case) implies

IE sup_{x∈X,∥x∥≤1} | ∑_{i∈Ω} ε_{i}ν_{i}|x_{i}|^{p}| ≤ \sqrt{\frac{π}{2}} IE sup_{x∈X,∥x∥≤1} | ∑_{i∈Ω} g_{i}ν_{i}|x_{i}|^{p}|

which together with Proposition 4.1 gives (5.3).

Acknowledgements

Supported by ISF.

References

[1] J. Bourgain, J. Lindenstrauss and V. Milman, Approximation of zonoids by zonotopes, Acta Math. 162 (1989), 73-141.

[2] R. M. Dudley, The sizes of compact subsets of Hilbert space and continuity of Gaussian processes, J. Functional Analysis 1 (1967), 290–330.

[3] M. Ledoux and M. Talagrand, Probability in Banach spaces Ergeb. Math. Grenzgeb. vol 23, Springer, Berlin (1991).

[4] D. R. Lewis, Finite dimensional subspaces of L_{p}, Studia Math. 63 (1978), 207–212.

[5] D. R. Lewis, Ellipsoids defined by Banach ideal norms, Mathematika 26 (1979), 18–29.

[6] W. B. Johnson and G. Schechtman, Computing p-Summing Norms With Few Vectors, Israel Journal of Math. 87 (1994), 19-31.

[7] W. B. Johnson and G. Schechtman, Finite dimensional subspaces of L_{p}, in preparation.

[8] Ana Peña, A note on the embedding of subspaces of L_{p} into l_{r}^{N} , 0 < r < 1, r ≤ p < 2, Math. Nachr. 189 (1998), 195–207.

[9] G. Schechtman, More on embedding subspaces of L_{p} in l_{r}^{n}, Compositio Math. 61 (1987), 159-170.

[10] M. Talagrand, Embedding subspaces of L_{1} into L_{1}^{N}, Proc. Amer. Math. Soc. 108 (1990), 363-369.

[11] M. Talagrand, Embedding subspaces of L_{p} in l_{p}^{N}, Geometric aspects of functional analysis (Israel, 1992–1994), Oper. Theory Adv. Appl. 77 (1995), 311–325.

Department of Theoretical Mathematics Weizmann Institute of Science Rehovot Israel e-mail: gideon@wisdom.weizmann.ac.il e-mail: tim@wisdom.weizmann.ac.il