Finite dimensional subspaces of L_{p}

William B. Johnson^{1}

Department of Mathematics, Texas A&M University, College Station, Texas, USA

Gideon Schechtman^{2}

Department of Mathematics, Weizmann Institute of Science, Rehovot, Israel

We discuss the finite dimensional structure theory of L_{p}; in particular, the theory of restricted invertibility and classification of subspaces of ℓ_{p}^{n}.

Contents

1 Introduction 2 1.1 The good, the bad, the natural, and the complemented 2 1.2 The role of change of density 3

2 Subspaces of ℓ_{p}^{n} 8 2.1 Fine embeddings of subspaces of L_{p} into ℓ_{p}^{n} 8 2.2 Natural embeddings of ℓ_{r}^{k} into ℓ_{p}^{n} 18 2.3 ℓ_{r}^{k} subspaces of m-dimensional subspaces and quotients of ℓ_{p}^{n} 19

3 Finite dimensional subspaces of L_{p} with special structure 20

1 Supported in part by NSF DMS-9623260 and DMS-9900185, Texas Advanced Research Program 010366-163, and the U.S.-Israel Binational Science Foundation. 2 Supported in part by the U.S.-Israel Binational Science Foundation.

Preprint submitted to Elsevier Preprint 18 August 2000

3.1 Subspaces with symmetric basis 20

3.2 Subspaces with bad gl constant 25

4 Restricted invertibility and finite dimensional subspaces of L_{p} of maximal distance to Euclidean spaces 26

4.1 Restricted invertibility of operators on ℓ_{p}^{n} 26

4.2 Subspaces of L_{p} with maximal distance to Hilbert spaces 30

5 Complemented subspaces 32

5.1 Fine embeddings of complemented subspaces of L_{p} in ℓ_{p}^{n} 32

5.2 Finite decomposition and uniqueness of complements 33

References 36

1 Introduction

1.1 The good, the bad, the natural, and the complemented

There are many interesting problems about infinite dimensional subspaces of L_{p}(:= L_{p}[0, 1]) which have finite dimensional analogues. For example, it has long been a central problem in Banach space theory to classify the complemented subspaces of L_{p} up to isomorphism; the finite dimensional analogue is to find for any given C a description of the finite dimensional spaces which are C-isomorphic to C-complemented subspaces of L_{p}. A lot is known about both the infinite dimensional (see [1]) and finite dimensional (see section 5) versions of this complemented subspaces of L_{p} problem, but in neither case does a classification seem to be close at hand.

It sometimes happens that the finite dimensional version of an infinite dimensional problem leads to a theory which is much more interesting than the infinite dimensional theory. Take, for example, the problem of describing the subspaces of L_{p} which embed isomorphically into a “smaller” L_{p} space; namely, ℓ_{p}; for which there is a fairly simple answer (see [1]). Now it is clear that a finite dimensional subspace X of L_{p} embeds, with isomorphism constant 1 + ϵ, into ℓ_{p}^{N} if N = N(ϵ, X) is sufficiently large. The attempt to estimate well N in terms of ϵ and X (or the dimension of X) has led to a deep theory (see sections 2.1 and 5.1). A sideline of this investigation also led to deeper understanding of how certain natural subspaces of L_{p} (such as the span of a sequence of independent Gaussian random variables) are situated in L_{p} (see section 2.2).

Besides being an interesting subject in its own right, the study of finite dimensional subspaces of L_{p} is often needed in order to understand properties of infinite dimensional subspaces. For example, the easiest and best way to obtain subspaces of L_{p}, 2 < p < ∞, which fail GL-l.u.st. (cf. [28, section 9]) is to show that random large dimensional subspaces of ℓ_{p}^{n} are bad in a certain sense (see section 3.2).

The topic discussed herein which has the most applications is that of restricted invertibility (see section 4). Basically the theorem says that an n by n matrix which has ones on the diagonal and is of norm M, say, as operator on ℓ_{p}^{n}, must be invertible on a coordinate subspace of dimension at least δ(M)n. One of the many consequences of this result is that certain finite dimensional subspaces X of L_{p} contain well-complemented ℓ_{p}^{n} subspaces with n proportional to the dimension of X.

1.2 The role of change of density

Generally the structure of the L_{p} spaces is described for a fixed value of p. However, proofs of many of the results about L_{p} for a fixed p use the entire scale of L_{r} spaces, 1 ≤ p ≤ ∞. Consider, for example, the proof [28, section 4] that a subspace X of L_{p}, 2 < p < ∞, is either isomorphic to a Hilbert space or contains a subspace which is complemented in L_{p} and is isomorphic to ℓ_{p}. There one needs only to compare the L_{2} norm and the L_{p} norm on X.

In proofs of other theorems about L_{p} it is necessary to change the measure before making a comparison between the L_{p} norm and another norm. Since the technique of changing the measure (“making a change of density”) is used in the proofs of most of the results we discuss in this article, we chose to devote this section to describing the change of densities that arise later. It turns out that the framework in which this technique is most naturally used is that of an L_{p}(μ) space when μ is a probability. For us there is no loss of generality in restricting to that case since the space ℓ_{p}^{N} is isometric to L_{p}(μ) when μ is any probability on {1, …, N} for which μ({n}) > 0 for each 1 ≤ n ≤ N. For such a measure μ we denote L_{p}(μ) by L_{p}^{N}(μ), or just L_{p}^{N} if μ assigns mass 1/N to each integer n, 1 ≤ n ≤ N.

A density on a probability space (Ω, μ) is a strictly positive μ-measurable function g on Ω for which ∫ g dμ = 1. Such a density g induces for fixed 0 < p < ∞ an isometry M = M_{g,p} from L_{p}(μ) onto L_{p}(g dμ) defined by Mf = g^{−1/p}f. Sometimes a gain is achieved by making such a change of density; that is, by replacing L_{p}(μ) by its isometric copy L_{p}(g dμ). The gain usually occurs because for some subspace E of L_{p}(μ) and some value of r different from p, the space M_{g,p}E is better situated with respect to L_{r}(g dμ) than E is to L_{r}(μ). For example, it follows from the Pietsch factorization theorem [28, section 10] that if an operator T from some space X into L_{1}(μ) has p-summing adjoint, then by replacing the original L_{1} space by another isometrically equivalent L_{1} space, T X is actually contained in L_{p}. Formally,

Proposition 1 If T : X → L_{1}(μ) (μ a probability measure) has p-summing adjoint, then there is a change of density g and an operator T̃ : X → L_{p}(g dμ) so that M_{g,p}T is the composition of T̃ followed by the canonical injection from L_{p}(g dμ) into L_{1}(g dμ). Moreover, ∥T̃∥ = π_{p}(T^{∗}) as long as T X has full support; i.e., there is no subset Ω_{0} ⊂ Ω with μ(Ω_{0}) < 1 so that T x = 1_{Ω_{0}}T x μ-a.e. for every x in X.

To prove this factorization theorem, assume for simplicity that μ is a regular Borel measure on a compact space Ω and that T X has full support. Get a Pietsch measure ν for the restriction of T^{∗} to C(K), which means that ν is a regular probability measure on K such that ∥T^{∗}f∥^{p} ≤ π_{p}(T^{∗})^{p} ∫ |f|^{p} dν for all f in C(K). This same inequality is true if ν is replace by its Radon-Nikodyḿ derivative with respect to μ, so one can assume that ν is of the form g dμ with g ≥ 0 and 1 = νΩ = ∫ g dμ. It is easily checked that this g is the desired density provided that g is strictly positive μ-a.e., which it must be since T X has full support. (When T X does not have full support, reason the same way but at the end add a small constant function to g and renormalize.)

The next change of density result, due to D. Lewis [43], gives useful information about finite dimensional subspaces of L_{p}.

Theorem 2 Let μ be a probability measure and let E be a k dimensional subspace of L_{p}(μ), 0 < p < ∞, with full support. Then there is a density g so that M_{g,p}E has a basis {f_{1}, …, f_{k}} which is orthonormal in L_{2}(g dμ) and

such that ∑_{n=1}^{k} |f_{i}|^{2} ≡ k.

For a proof when 1 ≤ p < ∞ see [43]. The first step is to apply Lewis’ lemma ([28, section 8]) to get an operator T from ℓ_{2}^{N} onto E for which π_{p}(T) = 1 and I_{p^{∗}}(T^{−1}) = N. The rest of the proof involves checking that the choices g := (∑ |T e_{i}|^{2})^{1/2} and f_{i} := \sqrt{k}g^{−1/p}T e_{i} satisfy the conditions of Theorem 2. Another proof, for the entire range 0 < p < ∞, is contained in [55].

Recall that if T : X → Y is an operator, γ_{2}(T) is the infimum of ∥T ∥∥U∥ over all factorizations T = SU with U : X → ℓ_{2} and S : ℓ_{2} → Y.

Theorem 3 If E is a k-dimensional subspace of L_{p}(μ) then there is a projection P from L_{p}(μ) onto E with γ_{2}(P) ≤ k^{|1/p−1/2|}.

Since the Banach-Mazur distance from ℓ_{p}^{k} to ℓ_{2}^{k} is k^{|1/p−1/2|} [28, section 8], Theorem 3 implies that the distance of a k dimensional subspace of L_{p}(μ) to ℓ_{2}^{k} is maximized when the subspace is ℓ_{p}^{k}.

To prove Theorem 3, observe first that the case p = ∞ follows trivially from the fact proved in [28, section 10] that π_{2}(I_{E}) = \sqrt{k} for every k dimensional space E. When p < ∞, in view of the comments made in [28, section 10], there is no loss in generality in assuming the μ is a probability measure and that E has full support. Theorem 2 says that we can further assume that E has a

basis {f_{1}, …, f_{k}} which is orthonormal in L_{2}(μ) and such that ∑_{n=1}^{k} |f_{i}|^{2} ≡ k.

Let P be the orthogonal projection onto E. If p < 2, a simple computation shows that ∥P : L_{p}(μ) → L_{2}(μ)∥ ≤ k^{1/p−1/2} and so also γ_{2}(P : L_{p}(μ) → L_{p}(μ)) ≤ k^{1/p−1/2}. The case p > 2 is even easier.

For a generalization of Theorem 3 to spaces of type p > 1 see [59, 27.4,28.6].

The change of density in Theorem 2 is used in section 2.1 to show that a k dimensional subspace of L_{p} well embeds into ℓ_{p}^{n} with n not too large. There what is needed is the relation between the L_{∞} and the L_{p}(g dμ) norms on M_{g,p}E. The relevant estimate follows from a trivial observation which we record for later reference.

Lemma 4 Let μ be a probability measure and let E be a k dimensional subspace of L_{p}(μ) which has a basis {f_{1}, …, f_{k}} which is orthonormal in L_{2}(μ)

and such that ∑_{n=1}^{k} |f_{i}|^{2} ≡ k. Then for each f in E, ∥f∥_{∞} ≤ k^{1/p}∥f∥_{p} if

0 < p ≤ 2 and ∥f∥_{∞} ≤ k^{1/2}∥f∥_{p} if 2 ≤ p < ∞.

There is a pretty characterization, due to Maurey [44], [62, III.H.10] of subsets of L_{p}(μ) which are bounded in L_{q} after a change of density.

Theorem 5 Let μ be a probability measure, 0 < p < q < ∞, and S a subset of L_{p}(μ) of full support. Then there is a density g so that M_{g,p}S ⊂ B_{L_{q}(g dμ)} if and only if for all finite subsets S_{0} of S and {a_{x} : x ∈ S_{0}} ⊂ [0, 1],

∥( ∑_{x∈S_{0}} |a_{x}x|^{q})^{1/q}∥_{L_{p}(μ)} ≤ ( ∑_{x∈S_{0}} |a_{x}|^{q})^{1/q}. (1)

Assuming the Pietsch factorization theorem, for the case p = 1 and when S = T B_{X} for some operator T : X → L_{1}(μ), Corollary 6 is little more than a restatement of Theorem 5. Recall ([28, Section 5]) that when T is an operator into a Banach lattice, M^{(q)}(T) denotes the q-convexity norm of T.

Corollary 6 Suppose T is an operator from a Banach space X into an L_{1} space. Then M^{(p)}(T) = π_{p^{∗}}(T^{∗}).

A consequence of Theorem 5 that we shall need in section 4 is the result of [27] that an operator on L_{p} is bounded on L_{2} after an appropriate change of density:

Theorem 7 If 0 < p < ∞, μ is a probability measure, and T is an operator on L_{p}(μ), then ∥M_{g,p}T M_{g,p}^{−1} : L_{2}(g dμ) → L_{2}(g dμ)∥ ≤ 2K_{G}∥T ∥ for some density g ≥ 1/2, where K_{G} is the constant in Grothendieck’s inequality [28, section 10].

If one does not wish to make a change to the measure g dμ, then by throwing away the part of the measure space where g ≥ 2 one gets:

Corollary 8 If 0 < p < ∞, μ is a probability measure, and T is an operator on L_{p}(μ), then ∥R_{A}T R_{A} : L_{2}(μ) → L_{2}(μ)∥ ≤ 2K_{G}∥T ∥ for some set A with μA ≥ 1/2, where R_{A} is the restriction operator defined by R_{A}f := 1_{A}f.

Theorem 7 is a fixed point version of the following factorization consequence (due to Maurey [44]) of Theorem 5.

Theorem 9 Let μ be probability measure and T be an operator from a Banach lattice X into L_{p}(μ), 0 < p ≤ 2. Then there is a change of density g and an operator T̃ from X into L_{2}(g dμ) so that M_{g,p}T = I_{2,p}T̃, where I_{2,p} is the identity mapping from L_{2}(g dμ) into L_{p}(g dμ). Moreover, ∥T̃∥ ≤ K_{G}M^{(2)}(X)∥T ∥ if T X has full support.

For the proof of Theorem 9, let {x_{i}}_{i=1}^{n} be in X and assume that T X has full support. Then using a consequence of Grothendieck’s inequality (see [28, section 10]) in the first step we have

\begin{aligned}∥ (∑_{i=1}^{n} |T x_{i}|^{2})^{1/2} ∥_{L_{p}(μ)} & ≤ K_{G}∥T ∥∥ (∑_{i=1}^{n} |x_{i}|^{2})^{1/2} ∥ \\ & ≤ K_{G}∥T ∥M^{(2)}(X) (∑_{i=1}^{n} ∥x_{i}∥^{2})^{1/2} . \end{aligned}

Now apply Theorem 5 with S the image under T of the unit sphere of X to get the inequality in the conclusion of Theorem 9. A trivial perturbation argument now gives Theorem 9 when T X does not have full support. In the general case, given ϵ > 0, the density g can be chosen so that ∥T̃∥ ≤ (K_{G}M^{(2)}(X) + ϵ)∥T ∥.

We now deduce Theorem 7 in the range 1 < p < ∞ from Theorem 9. By duality we can assume that 2 < p < ∞, and also suppose that T L_{p}(μ) has full support. If h is a density and we apply Theorem 9 to the adjoint of the operator

L_{p}(μ)⟶^{M_{p,h}T}L_{p}(hdμ)⟶^{I_{p,2}}L_{2}(hdμ) (2)

we get a density g so that for every f in L_{p}(μ),

∫ |T f|^{2}h^{(p−2)/p}dμ ≤ K_{G}^{2}∥T ∥^{2} ∫ |f|^{2}g^{(p−2)/p}dμ. (3)

Set g_{0} := 1 and get densities g_{1}, g_{2}, … so that for each n, (3) is satisfied with h := g_{n} and g := g_{n+1}. Define g̃ := ∑_{n=0}^{∞} 2^{−n−1}g_{n}^{(p−2)/p}. This series is absolutely

convergent in L_{(p−2)/p}(μ) to a function whose norm is at most one, so the function g := ∥g̃∥_{L_{1}(μ)}g̃ is a density with g ≥ 1/2 which satisfies, for arbitrary f in L_{p}(μ),

∫ |T f|^{2}g^{(p−2)/p}dμ ≤ 2K_{G}^{2}∥T ∥^{2} ∫ |f|^{2}g^{(p−2)/p}dμ.

This gives Theorem 7 with a slightly better constant when T L_{p}(μ) has full support and hence also Theorem 7 as stated in the range 1 < p < ∞.

For 0 < p ≤ 1, Theorem 7 follows via interpolation from Theorem 10.

Theorem 10 If 0 < p ≤ 1, a > 1, μ is a probability measure, and T is an operator on L_{p}(μ), then ∥M_{g,p}T M_{g,p}^{−1} : L_{∞}(g dμ) → L_{∞}(g dμ)∥ ≤ a∥T ∥ for some density g.

To prove Theorem 10, it is enough to find a strictly positive function g̃^{1/p} in L_{p}(μ) so that T maps the order interval [−g̃^{1/p}, g̃^{1/p}] into [−a∥T ∥g̃^{1/p}, a∥T ∥g̃^{1/p}]. The main point is that every operator T on L_{p}(μ), 0 < p ≤ 1, has a modulus |T | which satisfies ∥|T |∥ = ∥T ∥ and |T f| ≤ |T ||f| for all f in L_{p}(μ) (see, e.g., the remark preceding Theorem 3.2 in [36]). One then defines g̃^{1/p} = 1 + ∑_{n=1}^{∞} a^{−n}∥T ∥^{−n}|T |^{n}1. See [27] for details when p = 1.

We conclude this section with a change of density lemma due to Pisier [50] which, except for constants, improves Theorem 5. Theorem 11 will be used in section 2.1

Theorem 11 Let μ be a probability measure, 0 < p < q < ∞, and S a subset of L_{p}(μ). The following statements are equivalent.

(i) There is a constant C_{1} and a density g so that for all measurable sets E and x in S, ∥1_{E}x∥_{L_{p}(μ)} ≤ C_{1} (∫_{E} gdμ)^{1/p−1/q}.

(ii) There is a constant C_{2} and a density g so that M_{g,p}S ⊂ C_{2}B_{L_{q,∞}(g dμ)}.

(iii) There is a constant C_{3} so that for all finite subsets S_{0} of S and subsets {a_{x} : x ∈ S_{0}} of [0, 1], ∥ sup_{x∈S_{0}} |a_{x}x|∥_{L_{p}(μ)} ≤ C_{3}(∑_{x∈S_{0}} |a_{x}|^{q})^{1/q}.

Moreover, there is a constant C = C(p, q) so that in the implication (i) ⇒ (j), C_{j} ≤ CC_{i}.

For a proof of Theorem 11, see [50]. This paper also contains a nice proof of Theorem 5.

2 Subspaces of ℓ_{p}^{n}

2.1 Fine embeddings of subspaces of L_{p} into ℓ_{p}^{n}

Let X be a k-dimensional subspace of L_{p}, 0 < p < ∞, and let ϵ > 0. What is the smallest n such that X (1 + ϵ)-embeds in ℓ_{p}^{n}? That is, what is the smallest n such that there is a k-dimensional subspace Y of ℓ_{p}^{n} and an isomorphism T : X → Y with ∥T ∥∥T^{−1}∥ ≤ 1 + ϵ? Let us denote this n by N_{p}(X, ϵ) and the maximal N_{p}(X, ϵ), when X ranges over all k-dimensional subspaces of L_{p}, by N_{p}(k, ϵ).

Fixing a basis in X and approximating each of its members by an appropriate simple function, one sees that N_{p}(X, ϵ) < ∞ for every k-dimensional X and ϵ. Moreover, it depends on X only through its dimension k so that N_{p}(k, ϵ) < ∞. However, one gets that way a (larger than) exponential in k bound on N_{p}(k, ϵ). In this section we shall review results which give much better bounds, close to the best possible ones.

The case p = 2 is of course trivial and one can take n = k even for ϵ = 0. The case p = 1 has a nice geometrical interpretation: The unit ball of the dual to a k-dimensional subspace of ℓ_{1}^{n} is easily seen to be (isometric to) the Minkowski sum of n segments in ℝ^{k} (centered at 0) and visa versa. Consequently, the n sought after is the smallest n such that every (centered at zero) body K in ℝ^{k} which is the Minkowski sum of arbitrarily many segments (or the limit of such bodies - these are called zonoids) can be ϵ-approximated by a body Z which is the sum of n such segments in the sense that Z ⊂ K ⊂ (1 + ϵ)Z.

The history of this problem can be traced to the offsprings of Dvoretzky’s theorem as discussed in [24]. There the case of X being a k-dimensional Hilbert space (which embeds isometrically in all the L_{p} spaces) is treated and solved quite satisfactory: For some absolute constant C, N_{p}(ℓ_{2}^{k}, ϵ) is at most Cϵ^{−2}k for p < 2 and Cϵ^{−2}pk^{p/2} for p > 2. This is best possible except that it is unknown whether the factor ϵ^{−2} can be replaced by a smaller function of ϵ. Notice the following nonintuitive special case: The k-dimensional Euclidean ball can be approximated by a body which the sum of a constant (depending on the degree of approximation) times k segments in ℝ^{k}.

The first result in this direction which did not involve Euclidean spaces was proved in [31]. There it was shown that, for 0 < p ≤ 1 and p < q < 2, ℓ_{q}^{k} (which is known to embed isometrically into L_{p} whenever 0 < p < q ≤ 2) (1+ϵ)-embeds into ℓ_{p}^{n} for some n ≤ C(p, q, ϵ)k. Later the second named author found some initial results indicating in particular that the dependence of n on k in the general problem stated at the beginning of this section is polynomial rather than exponential as one is first tempted to believe. The first proofs were quite complicated and worked only for p < 2 as they used fine properties of q-stable random variables. Later a much simpler method was introduced in [53]. Assuming, as we may, that X is already a subspace of ℓ_{p}^{N} for some finite N, pick randomly a “few” coordinates and hope that the natural projection onto these coordinates, restricted to X, is a good isomorphism. If we do it with no additional preparation this cannot work. Indeed, X may contain a vector with small support (say one of the unit vector basis elements of ℓ_{p}^{N}), in which case the chance that a coordinate in its support is picked is small; of course, if no such coordinate is picked, the said projection cannot be an isomorphism on X. The point is that one wants to change X first to another isometric copy of X in which each element of X is “spread out”. This can be done by a change of density. The method of [53] was used with other tools in [8], [57], and some other papers to produce the best known results. In these results it is not known what is the right dependence of n on ϵ and we shall not try to emphasize what are the exact estimates one gets from the proofs. However, the dependence of n on k is best possible except for log factors in some places; we shall pay more attention to this in the sequel.

We now state the best known results.

Theorem 12 (i) For p > 2, N_{p}(k, ϵ) ≤ C(p, ϵ)k^{p/2} log k. (ii) For 1 < p < 2, N_{p}(k, ϵ) ≤ C(ϵ)k log k(log log k)^{2}. (iii) For p = 1, N_{1}(k, ϵ) ≤ C(ϵ)k log k. (iv) For 0 < p < 1, N_{p}(k, ϵ) ≤ C(p, ϵ)k(log k)^{3}.

Under some conditions ensuring that X does not contain good copies of ℓ_{p}^{m} spaces, one gets better results for p < 2. Recall that a quasi-normed space X is of type p with constant C for some 0 < p ≤ 2 provided

(𝔼∥ ∑_{i=1}^{n} ϵ_{i}x_{i}∥^{2})^{1/2} ≤ C (∑_{i=1}^{n} ∥x_{i}∥^{p})^{1/p}

for all finite sequences x_{1}, …, x_{n} of elements of X. The best C is denoted T_{p}(X). The space L_{p}, 0 < p ≤ 2, is of type p. Recall also that K(X) denotes the K-convexity constant of X, i.e., the norm of the Rademacher projection in L_{2}(X). See [28] for a brief discussion of these notions (although it is restricted to the normed spaces, which always have type p ≥ 1) and [45] for a more comprehensive discussion.

Theorem 13

(i) Let 0 < p < q < 2 and let 0 < ϵ, C < ∞. Then for some constant C′ = C′(p, q, ϵ, C) and all k-dimensional subspace X of L_{p} with T_{q}(X) ≤ C, N_{p}(X, ϵ) ≤ C′k. For p = 1 we have a quantitatively better estimate:

(ii) For all k-dimensional subspaces X of L_{1}, N_{1}(X, ϵ) ≤ C(ϵ)K(X)^{2}k.

Theorem 13(i) was proved for p ≥ 1 in [8]. [32] contains the full statement with a different proof. [8] also contains Theorem 12(i) and somewhat weaker versions of Theorem 12(ii), (iii), and Theorem 13(ii). The exact Theorem 12(ii) is contained in [58] while Theorem 13(ii) is the main result of [57]. Theorem 12(iii) follows from it since it is known ([48]) that K(X) ≤ C\sqrt{log k} for every k-dimensional subspace X of L_{1}; see Lemma 17. Finally, Theorem 12(iv) was proved only recently [55] after noticing its omission while writing this survey.

Before describing the proofs, we mention that there are several unsettled problem related to Theorems 12 and 13. The most important one (or at least the one that attracted the most attention) is whether the various log factors and the dependence on the type and K-convexity are really needed. It is strange that the constants in the proofs blow up when X contains ℓ_{p}^{m} spaces. Actually, as we shall see below, in at least some of the proofs the worst case occurs when X is isometrically ℓ_{p}^{k}. Another problem is the determination of the dependence of N(·) on ϵ. Scant attention has been given to that in the published work. A problem we find particularly interesting is whether there is an “isomorphic” (as oppose to “almost isometric”) version to some of the results here. Here is an instance of this problem: is it true that for all 1 < p < 2 and all λ > 1 there is a positive constant C = C(p, λ) such that whenever n < λk, ℓ_{p}^{k} C-embeds into ℓ_{1}^{n}?

Next we would like to sketch some of the ideas involved in the proofs of some of the statements of Theorems 12 and 13. As we already indicated above, a common feature of all the proofs we shall sketch is that, using a change of density, we first find an isometric copy of X with some additional good properties. We delay stating theses properties and the actual change of density that ensure them until later and denote the new space by the same notation X. We may also assume without loss of generality that X lies in a finite (but large) dimensional ℓ_{p}^{m} space, say L_{p}^{m}(μ), where μ is a probability measure on {1, …, m}. We denote μ_{i} = μ({i}). We would like to show that the restriction operator to a set of relatively few of the m coordinates is a good isomorphism on X. We prefer to do it iteratively by first showing how to find a subset of cardinality at most m/2 such that the restriction operator is a (very) good isomorphism on X, provided m is much larger than k. We shall then show how to iterate this procedure. The choice of the subset will be random; for example, it is enough to show that, for an appropriate ϵ(k, m),

Ave_{A} sup_{x∈X,∥x∥≤1} |2 ∑_{i∈A} μ_{i}|x_{i}|^{p} − ∑_{i=1}^{m} μ_{i}|x_{i}|^{p}|
= 𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} ϵ_{i}μ_{i}|x_{i}|^{p}| ≤ ϵ(k, m).  (4)

Here Ave_{A} denotes the average over all subsets of {1, …, m} while 𝔼 is the expectation with respect to the natural product measure on {−1, 1}^{n}. Indeed, if this is the case then for some A the restriction operators to both A and the complement of A are (\frac{1+ϵ(k,m)}{1−ϵ(k,m)})^{1/p}-isomorphisms and of course either A or its complement A^{c} is of cardinality at most m/2.

Alternatively, in order to find such an A, it is enough to show that

P ( sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} ϵ_{i}μ_{i}|x_{i}|^{p}| > ϵ(k, m)) < 1.  (5)

In both cases after iterating we get that as long as

∏_{i=1}^{l} (\frac{1 + ϵ(k, m2^{−i})}{1 − ϵ(k, m2^{−i})})^{1/p} ≤ 1 + ϵ, (6)

X must (1 + ϵ)-embed into ℓ_{p}^{n} for some n ≤ m2^{−l−1}.

So this approach reduces the problem to finding good bounds on the quantity in (4) or (5). For technical reasons involving splitting of atoms, as explained in Lemma 14 below, we may need to enlarge m to at most 3m/2 before making the random choice in each step. This does not effect the process significantly; after the random choice we end up in ℓ_{p}^{3m/4} and this just means that instead of (6) we shall need to ensure that

∏_{i=1}^{l} (\frac{1 + ϵ(k, m(\frac{3}{4})^{i})}{1 − ϵ(k, m(\frac{3}{4})^{i})})^{1/p} ≤ 1 + ϵ. (7)

Before proceeding further, we would like to point out why there is very little hope of eliminating the log factors altogether using this approach. Consider, in ℓ_{1}^{cn log n}, n vectors of the form x_{i} = (c log n)^{−1} ∑_{j∈σ_{i}} e_{j} with σ_{i}, i = 1, …, c log n, disjoint sets of cardinality c log n (assuming it is an integer). It is easy to calculate (and appears in many probability books, sometimes as the coupon collector’s problem) that, if c is small, a random choice of \frac{c}{2}n log n of the coordinates will most likely miss at least one of the σ_{i}’s. Thus the restriction to a “random” subset of cardinality \frac{c}{2}n log n will not be an isomorphism on X = span{x_{i}} (which incidentally is isometric to ℓ_{1}^{n}). We did not change the density here, but it is not hard to see that a change of density is not going to help to reduce the minimal m for which this procedure works below cn log n for some absolute c > 0.

We now continue sketching the idea of the proofs. We first sketch a version of the simple argument of [53] which only gives

\begin{matrix}N_{p}(k, ϵ) & ≤ & C(ϵ)k^{2} for 0 < p < 2 and \\ N_{p}(k, ϵ) & ≤ & C(ϵ)k^{(p+2)/2} for p > 2. \end{matrix} (8)

By Lemma 4 there is a change of density on L_{p}^{m} so that for all x ∈ X,

\begin{matrix}∥x∥_{∞} & ≤ & k^{1/p}∥x∥_{p}, for 0 < p < 2 and \\ ∥x∥_{∞} & ≤ & k^{1/2}∥x∥_{p}, for p > 2. \end{matrix} (9)

Splitting the atoms of this change of density we may assume in addition that μ_{i} ≤ 4/m (paying by enlarging the original m to 3m/2). This follows from the following simple lemma.

Lemma 14 Let μ be a probability measure on {1, 2, …, m}. Then there is an m ≤ M ≤ 3m/2, a probability measure ν on {1, 2, …, M} and a partition {σ_{1}, σ_{2}, …, σ_{m}} of {1, 2, …, M} satisfying

(i) ν({i}) ≤ 4/m, i = 1, …, M, and (ii) ∑_{i∈σ_{j}} ν({i}) = μ({j}).

The proof of the lemma is very simple. Split the atoms of μ which have mass larger than 4/m into pieces each of size larger than 2/m. This does not add more than m/2 atoms to the original ones, thus ending the proof. Of course L_{p}(μ), and thus also X, naturally embeds into L_{p}(ν) in particular the estimates in 9 still hold for the image of X in L_{p}(ν). This justifies the statement in the paragraph preceding the statement of the lemma.

Fixing an x ∈ X of norm one, we get by classical deviation inequalities (see for example Proposition 5(iii) in [54]) that for 0 < p < 2,

P (|∑_{i=1}^{m} ϵ_{i}μ_{i}|x_{i}|^{p}| > t) ≤ K exp(−δt^{2}/ ∑_{i=1}^{m} μ_{i}|x_{i}|^{p})
≤ K exp(−δt^{2}/ max_{1≤i≤m} μ_{i}|x_{i}|^{p})
≤ K exp(−δ′t^{2}m/k).

Let 0 < t < 1 and pick a t-net N in the unit sphere of X which has at most (3/t)^{k} elements (see e.g. [47] p. 7 for an easy proof of the existence of such a net). Then as long as k^{2} < ct^{2} log^{−1}(1/t)m (for some absolute constant c > 0),

P (sup_{x∈N} |∑_{i=1}^{m} ϵ_{i}μ_{i}|x_{i}|^{p}| > t) ≤ K exp(−δ′t^{2}m/k),

from which it is easy to get that, as long as k ≤ cm^{1/2},

P ( sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} ϵ_{i}μ_{i}|x_{i}|^{p}| > Ck/m^{1/2}) < 1. (10)

This and (7) implies the desired result (8) for 0 < p < 2. The treatment for p > 2 is similar.

This sketch of the argument of [53] was given only to illustrate the basic method involved. We now continue to sketch the arguments which give the stronger statements of theorems 12 and 13. The point is to find estimates for the quantities in (4) or (5) which are better than (10). We first relate the second quantity in (4) to a similar one involving Gaussian variables. Let g_{1}, …, g_{m} be independent standard Gaussian variables. Then

𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} ϵ_{i}μ_{i}|x_{i}|^{p}| ≤ \sqrt{\frac{π}{2}} 𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} g_{i}μ_{i}|x_{i}|^{p}| .

This version of the “contraction principle” is easy to prove: Replace each of the g_{i} on the right by ϵ_{i}|g_{i}|, where {ϵ_{i}} is independent of {g_{i}}, and replace 𝔼 with the successive application of the two expectations 𝔼_{ϵ}𝔼_{g}. Now push the expectation 𝔼_{g} inside the outer | · | and use the fact that 𝔼|g_{1}| = \sqrt{\frac{2}{π}}.

The problem now reduces to evaluating the quantity

𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} g_{i}μ_{i}|x_{i}|^{p}| . (11)

Set G_{x} = ∑_{i=1}^{m} g_{i}μ_{i}|x_{i}|^{p}. Then {G_{x}}_{x∈X,∥x∥≤1} is a Gaussian process indexed by elements of B(X) and we are required to estimate the expectation of its supremum. This is a well studied area in probability theory (see e.g. [41]), related to the continuity of Gaussian processes. This quantity (or the similar one involving the Rademacher functions in (4)) is evaluated by different means in the proofs of the different parts of Theorems 12 and 13. We shall first present a

Sketch of proof of Theorem 13(ii). Consider the process {H_{x}}_{x∈X,∥x∥≤1} where H_{x} = ∑_{i=1}^{m} g_{i}μ_{i}x_{i}. Then

𝔼G_{x}^{2} = 𝔼H_{x}^{2} and 𝔼G_{x}G_{y} ≥ 𝔼H_{x}H_{y}

for all x, y ∈ X of norm at most 1. Slepian’s lemma (see e.g. [41, p. 75]) implies now that

𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} g_{i}μ_{i}|x_{i}|| ≤ 𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} g_{i}μ_{i}x_{i}| .

We shall show that after a change of density (and possibly enlarging m to 3m/2),

𝔼 sup_{x∈X,∥x∥≤1} |∑_{i=1}^{m} g_{i}μ_{i}x_{i}| ≤ CK(X) (\frac{k}{m})^{1/2} . (12)

Then one concludes the proof of Theorem 13(ii) by applying (7). To prove (12) we shall use the following two propositions.

Proposition 15 Let X be a k-dimensional subspace of L_{1}^{m}(μ) with μ a probability measure and let f_{1}, …, f_{k} be an orthonormal basis of X (considered as a subspace of L_{2}^{m}(μ)). Then, one can split some of the atoms of μ to a total of at most M = 3m/2 atoms getting a new probability measure ν and a natural embedding I : L_{1}^{m}(μ) → L_{1}^{M}(ν) satisfying

𝔼 sup_{y∈Y,∥y∥≤1} |∑_{i=1}^{M} g_{i}ν_{i}y_{i}| ≤ 2m^{−1/2}𝔼∥ ∑_{i=1}^{k} g_{i}f_{i}∥^{∗}.

Here Y = IX and ∥ · ∥^{∗} is the dual norm to that of X where duality is given by ⟨∑ a_{i}f_{i}, ∑ b_{i}f_{i}⟩ = ∑ a_{i}b_{i}.

Proposition 16 With the notation of the previous proposition,

𝔼∥ ∑_{i=1}^{k} g_{i}f_{i}∥^{∗} ≤ \sqrt{2}K(X)∥( ∑_{i=1}^{k} f_{i}^{2})^{1/2}∥_{∞}.

We now conclude the proof of 13(ii) by applying Lewis’ change of density, Theorem 2 to get an orthonormal basis for (an isometric copy of X) satisfying ∥( ∑_{i=1}^{k} f_{i}^{2})^{1/2}∥_{∞} ≤ n^{1/2}.

Before sketching the proofs of Propositions 15 and 16 we would like to deduce Theorem 12(iii). This follows from the following Lemma (first observed in [48]).

Lemma 17 Let X be a k-dimensional subspace of L_{1}. Then K(X) ≤ C\sqrt{log k} for some absolute C.

PROOF. Using Lewis’ change of density we may assume ∥x∥_{∞} ≤ k∥x∥_{1} for all x ∈ X. Then easily ∥x∥_{1} ≤ ∥x∥_{p} ≤ k^{(p−1)/p}∥x∥_{1} for all x ∈ X. Letting X_{p} denote X with the L_{p} norm we get (see [45]???) that

K(X) ≤ k^{(p−1)/p}K(X_{p}) ≤ k^{(p−1)/p}K(L_{p}) ≤ Ck^{(p−1)/p}\sqrt{p/(p − 1)}.

Picking p with p/(p − 1) = log k we get the result.

We now turn to the

Sketch of proof of Proposition 15. Using the contraction principle in the first inequality, we get

𝔼 sup_{x∈X,∥x∥≤1} | ∑_{i=1}^{m} g_{i}μ_{i}x_{i}| ≤ max_{1≤i≤m} μ_{i}^{1/2}𝔼 sup_{x∈X,∥x∥≤1} | ∑_{i=1}^{m} g_{i}μ_{i}^{1/2}x_{i}|
= max_{1≤i≤m} μ_{i}^{1/2}𝔼 sup_{x∈X,∥x∥≤1} |⟨ ∑_{i=1}^{m} g_{i}μ_{i}^{−1/2}e_{i}, x⟩|
= max_{1≤i≤m} μ_{i}^{1/2}𝔼 sup ; ∥ ∑ a_{j}f_{j}∥≤1 | ∑_{j=1}^{k} a_{j}⟨ ∑_{i=1}^{m} g_{i}μ_{i}^{−1/2}e_{i}, f_{j}⟩|.

Put h_{j} = ⟨ ∑_{i=1}^{m} g_{i}μ_{i}^{−1/2}e_{i}, f_{j}⟩. Then h_{1}, …, h_{k} are standard Gaussian variables which are easily seen to be independent (check that 𝔼h_{j}h_{l} = δ_{jl}). Thus

𝔼 sup ; ∥ ∑ a_{j}f_{j}∥≤1 | ∑_{j=1}^{k} a_{j}⟨ ∑_{i=1}^{m} g_{i}μ_{i}^{−1/2}e_{i}, f_{j}⟩| = 𝔼 sup ; ∥ ∑ a_{j}f_{j}∥≤1 | ∑_{j=1}^{k} a_{j}g_{j}|

= 𝔼∥ ∑_{i=1}^{k} g_{i}f_{i}∥^{∗}.  (13)

It remains to see that splitting the atoms we may also assume that μ_{i} ≤ 4/m, but this follows from the splitting of atoms lemma 14.

Proof of Proposition 16. The proposition follows easily from [17, Lemma 1] but we present a different proof. Let {ϵ_{ij}}_{i=1,j=1}^{n,k} denote nk independent Rademacher functions (i.e., the ϵ_{ij} are the coordinate functions in the product probability space {−1, 1}^{nk}). In the first inequality below we use the central limit theorem and in the last Khintchine’s inequality (with the best constant) [28].

𝔼 ∥ ∑_{i=1}^{k} g_{i}f_{i}∥^{∗} ≤ ( lim_{n→∞} 𝔼∥n^{−1/2} ∑_{j=1}^{k} ∑_{i=1}^{n} ϵ_{ij}f_{j}∥^{∗2})^{1/2}

= lim_{n→∞} n^{−1/2} sup {⟨ ∑_{j=1}^{k} ∑_{i=1}^{n} ϵ_{ij}f_{j}, f⟩ ; ∥f∥_{L_{2}(X)} ≤ 1}

≤ K(X) lim_{n→∞} n^{−1/2} sup { ∑_{j=1}^{k} ∑_{i=1}^{n}⟨ϵ_{ij}f_{j}, x_{ij}⟩ ; x_{ij} ∈ X, 𝔼∥ ∑_{i,j} ϵ_{ij}x_{ij}∥^{2} ≤ 1}

≤ K(X) lim_{n→∞} sup {∥(∑_{i,j} x_{i,j}^{2})^{1/2}∥_{L_{1}} ∥( ∑_{j=1}^{k} ∑_{i=1}^{n} n^{−1}f_{j}^{2})^{1/2}∥_{L_{∞}} ; 𝔼∥ ∑_{i,j} ϵ_{ij}x_{ij}∥^{2} ≤ 1}

= K(X)∥( ∑_{j=1}^{k} f_{j}^{2})^{1/2}∥_{L_{∞}} sup {∥(∑_{i,j} x_{i,j}^{2})^{1/2}∥_{L_{1}} ; 𝔼∥ ∑_{i,j} ϵ_{ij}x_{ij}∥^{2} ≤ 1}

≤ \sqrt{2}K(X)∥( ∑_{j=1}^{k} f_{j}^{2})^{1/2}∥_{L_{∞}}.

We now sketch a proof of Theorem 13(i). We have chosen a version of the proof of [32] since it is the shortest one. However, this proof does not give a good dependence on ϵ.

Sketch of proof of Theorem 13(i). We assume first as we may that X ⊂ ℓ_{p}^{m}. The condition of Theorem 11(iii) is easily seen to be satisfied for S_{0} = (any finite subset of) the unit ball of X and C_{3} = T_{q}(X). So we can deduce from that theorem that, without loss of generality, X ⊂ L_{p}^{m}(μ) for some probability measure μ and ∥x∥_{q,∞} ≤ C′∥x∥_{p} for all x ∈ X and some C′ which depends only on p, q and T_{q}(X). By Theorem 11(i) it is also easy to see that we may assume that μ_{i} ≥ 1/2m (replace g with \frac{g+1}{2}). Splitting the large atoms of μ as in Lemma 14 and changing m to 3m/2 we may assume in addition that μ_{i} ≤ 4/m for all 1 ≤ i ≤ 3m/2.

Put r = q/p and note that for x ∈ X with ∥x∥_{p} ≤ 1,

∥{μ_{i}|x_{i}|^{p}}_{i=1}^{3m/2}∥_{r,∞} = max_{1≤j≤3m/2} j^{1/r}(μ_{j}|x_{j}|^{p})^{∗}
= max_{t>0} t(#{i; μ_{i}|x_{i}|^{p} ≥ t})^{1/r}  (14)

with {(μ_{j}|x_{j}|^{p})^{∗}} denoting the decreasing rearrangement of {(μ_{j}|x_{j}|^{p})}.

Using the fact that μ_{i} is of order 1/m and relating the quantity in (14) to

∥x∥_{q,∞} = max_{t>0} t(μ({i; |x_{i}| ≥ t}))^{1/q}
≈ max_{t>0} t(m^{−1}#{i; |x_{i}| ≥ t})^{1/q},  (15)

we get that the quantity in (14) is at most Cm^{\frac{p}{q} −1} for some C depending only on p, q and T_{q}(X). We now use the inequality

P (| ∑_{i=1}^{n} ϵ_{i}a_{i}| > t) ≤ 2 exp(−δ(t/∥{a_{i}}∥_{r,∞})^{s}) (16)

which holds for all t > 0, 1 < r < 2 and all sequences of scalars {a_{i}}. Here s = \frac{r}{r−1} and δ is a positive constant depending only on r. The inequality is a special case of a martingale inequality of Pisier (see [47], p. 45 for a proof or [54], Proposition 5 for a discussion of this and other similar inequalities). Note that we may assume that r = q/p < 2. Using (16) we get from (14) that for all x ∈ X with ∥x∥_{p} = 1,

P (| ∑_{i=1}^{3m/2} ϵ_{i}μ_{i}|x_{i}|^{p}| > t) ≤ 2 exp(−δ′t^{s}m)

for some δ′ depending only on p, q and T_{q}(X). From this we get, as in the standard argument leading to (10),

P ( sup_{x∈X,∥x∥≤1} | ∑_{i=1}^{3m/2} ϵ_{i}μ_{i}|x_{i}|^{p}| > t) ≤ 2 exp(k log(3/t) − δ′′t^{s}m). (17)

It follows that, as long as δ′t^{s}m log^{−1}(3/t) > 2k, We can find a set of at most 3m/4 coordinates for which the restriction operator is an (1+2t)-isomorphism. Choosing t ≈ (\frac{k}{m} log \frac{m}{k})^{1/s} we get that there is a set of at most 3m/4 coordinates for which the restriction operator is an (1 + C(\frac{k}{m} log \frac{m}{k})^{1/s})^{1/p}- isomorphism where C depends only on p, q and T_{q}(X). Iterating, we get that as long as

∏_{i=1}^{l} (1 + C(\frac{k}{m(3/4)^{i}} log \frac{m(3/4)^{i}}{k} )^{1/s})^{1/p} ≤ 1 + ϵ

X must (1 + ϵ)-embed into ℓ_{p}^{n} for some n ≤ m(3/4)^{l+1}. Note that in each step of the iteration we get a space which is at most 2-isomorphic to X. Since the new space has type q constant at most twice that of the original space we can continue the iteration.

Now it is easy to get the conclusion.

2.2 Natural embeddings of ℓ_{r}^{k} into ℓ_{p}^{n}

The methods described in Section 2.1 as well as all other methods for producing “tight embeddings” are probabilistic and as such are not constructive and do not produce an explicit good embedding. The most basic question concerning explicit embeddings may be to produce a specific good embedding of ℓ_{2}^{n} into ℓ_{1}^{m} with m proportional to n (m ≤ 2n, say). We remark in passing that for p an even integer there are specific embeddings (even isometric ones) of ℓ_{2}^{n} into ℓ_{p}^{m} with the relation between m and n close to the optimal one (in particular, for p = 4, m ≈ n^{2}). See [38] for that.

A natural approach to get an explicit embedding of ℓ_{2}^{n} into ℓ_{1}^{m} is to fix a natural subspace X_{n} of L_{1} which is well isomorphic to ℓ_{2}^{n}, for example the span of n independent standard Gaussian variables or n independent Rademacher functions, and find a subspace Y_{m} with X_{n} ⊂ Y_{m} ⊂ L_{1}, Y_{m} well isomorphic to ℓ_{1}^{m}, and m small. However, this fails in a very strong sense: under the requirements above, the smallest m can be is C^{n} for some C > 1 depending only on the distance of Y_{m} to ℓ_{1}^{m}. Here is a somewhat stronger theorem from [22]. Recall that for an operator T : X → Y, γ_{1}(T) = inf ∥u∥∥v∥, where the inf is taken over all L_{1}(ν) spaces and all operators v : X → L_{1}(ν), u : L_{1}(ν) → Y, satisfying T = uv.

Theorem 18 For every 0 < K < ∞ there exists a δ = δ(K) > 0 such that if X is the span, in L_{1}, of n independent Gaussian variables or n independent Rademacher functions, X ⊂ Y ⊂ L_{1}, and the inclusion J : X → Y satisfies γ_{1}(J) ≤ K then, for some m ≥ e^{δn}, ℓ_{1}^{m} is 2-isomorphic to a subspace of Y. In particular dim Y ≥ e^{δn}.

The proof of this is rather technical and we shall not reproduce it here. [22] and [23] contain many refinements and variations of this theorem. Also, [59, p. 201] contains an exposition of the proof of the simplest instance of this class of results; namely, the statement in the “in particular” part of Theorem 18 for X being the span of n independent Rademacher functions.

2.3 ℓ_{r}^{k} subspaces of m-dimensional subspaces and quotients of ℓ_{p}^{n}

This short section deals with the question of what is the largest k such that ℓ_{p}^{k} well embeds into any m-dimensional subspace X of ℓ_{p}^{n}, as well as some related questions. We shall not present any proofs but only summarize what is known on this subject.

Note that, since X = ℓ_{2}^{m} well embeds into ℓ_{p}^{n}, p < 2, for m proportional to n, the answer to the question above for p < 2 is not very interesting (i.e., k must be bounded) unless n − m = o(n). We shall say something about this case latter. For 2 < p < ∞ the following theorem of Bourgain and Tzafriri [12] basically solves the problem. Let k = k_{p}(X, K) be the maximal dimension of a subspace Y of X which is K-isomorphic to ℓ_{p}^{k}.

Theorem 19 Let 2 < p < ∞ and ϵ > 0. Then there are positive constants c = c(p, ϵ), C = C(p, ϵ) such that for all m < n and every m-dimensional subspace X of ℓ_{p}^{n},

k_{p}(X, 1 + ϵ) ≥ c min{m^{p^{∗}/2}, (m/n^{2/p})^{p/(p−2)}}.

The result is best possible in the sense that for each m < n there exists a subspace X with k_{p}(X, 1+ϵ) ≤ C min{m^{p^{∗}/2}, (m/n^{2/p})^{p/(p−2)}}. (p^{∗} = p/(p−1).)

As can be suspected from the statement, the proof of this result is quite involved and very technical. It uses ideas from the work of Bourgain and Tzafriri concerning restricted invertibility (some of which is surveyed Section 4.1 below) as well as from Bourgain’s work on Λ_{p} sets [6]. We think it worthwhile to find a simpler proof.

As we said above, there can be no similar theorem in the range p < 2. However, one can prove a similar theorem for quotients of ℓ_{p}^{n}, 1 ≤ p < 2. This was done by Bourgain, Kalton and Tzafriri in [7].

Theorem 20 For each 1 ≤ p < 2 there is a constant C_{p} > 0 such that if X is an m-dimensional quotient space of ℓ_{p}^{n} then

k_{p}(X, C_{p}) ≥ C_{p}^{−1}(m^{p}/n^{2(p−1)})^{1/(2−p)},

for p > 1, while

k_{1}(X, C_{1}) ≥ C_{1}^{−1}m(/1 + log n/m).

Except for the constants involved the results are best possible.

Note that for m proportional to n the resulting dimension of the contained ℓ_{p}^{k} space is also proportional to n. For p = 1 this case was observed earlier in [15]. Note also that the conclusion of this theorem is “isomorphic” rather than “almost isometric”. We do not know if one can replace the constant C_{p} in the left hand side of the inequalities by 1 + ϵ (of course paying by replacing the constant in the right hand side by one depending on ϵ).

There is also a version of Theorem 19 for p = ∞: If m ≥ n^{δ}, with δ > 0, then every m-dimensional subspace X of ℓ_{∞}^{n} contains a well isomorphic copy of ℓ_{∞}^{k} with k ≥ c(δ)m^{1/2}. This was proved in [21] for m proportional to n, and in [5] in general.

When m is very large there is also a version of Theorem 19 for p = 1. It was proved in [25] that for every m-dimensional subspace X of ℓ_{1}^{n},

k_{1}(X, K) ≥ c min{(n/(n − m)) log(n/(n − m)), n}.

K and c are universal constants.

3 Finite dimensional subspaces of L_{p} with special structure

3.1 Subspaces with symmetric basis

In this section we treat the classification of the finite symmetric basic sequences in L_{p}, 1 ≤ p < ∞ and to some extent also the classification of the finite unconditional basic sequences in L_{p}, 1 ≤ p < 2.

Recall that a sequence x_{1}, …, x_{n} in a quasi normed space X (over ℝ) is said to be K-symmetric if for all scalars {a_{i}}, all sequences of signs {ϵ_{i}} and all permutations π of {1, …, n}

∥ ∑_{i=1}^{n} a_{i}x_{i}∥ ≤ K∥ ∑_{i=1}^{n} ϵ_{i}a_{π(i)}x_{i}∥.

If we require the inequality only for the identity permutation the sequence is called K-unconditional.

The article [60] treats the classification of symmetric basic sequences in L_{p}, p > 2 so we only state the result (from [29]; see [60], Theorem 4.4).

Theorem 21 For every 2 < p < ∞ and every constant K there is a constant D such that any normalized K-symmetric basic sequence in L_{p} is D equivalent to the unit vector basis of ℝ^{n} with the norm

∥{a_{i}}∥ = max{(∑ |a_{i}|^{p})^{1/p}, w(∑ |a_{i}|^{2})^{1/2}} (18)

for some w ∈ (0, 1).

Of course, since ℓ_{2}^{n} isometrically embeds in L_{p}, any norm of the form (18) embeds, with constant 2, into L_{p}.

For 1 ≤ p < 2 the structure of the symmetric sequences in L_{p} is more involved. Let M be a Orlicz function (see [28, Section 5]) and ℓ_{M} the associated Orlicz sequence space. It turns out that the space ℓ_{M} embeds isomorphically into L_{p} if and only if the unit vector basis of ℓ_{M} is p-convex and 2-concave and this happens if and only if M(|t|^{1/p}) is equivalent to a convex function and M(t^{1/2}) is equivalent to a concave function on [0, ∞) (see [14]). Recall that two functions M_{1}, M_{2} : ℝ → [0, ∞) are equivalent (at 0) if there exist constants K_{1}, K_{2}, λ, μ and x_{0} > 0 such that for all |x| < x_{0} K_{1}M_{2}(λx) ≤ M_{1}(x) ≤ K_{2}M_{2}(μx).

With the right quantifiers, a similar statement holds also for finite dimensional Orlicz spaces, ℓ_{M}^{n}. The embedding, when it exists, is as a span of independent, identically distributed symmetric random variables. It follows that if {M_{j}}_{j=1}^{m} is a collection of Orlicz functions such that ℓ_{M_{j}}^{n} K-embed in L_{p} for all j and λ_{j} > 0 for all j then also ℝ^{n} with the norm ∥·∥ = (∑_{j=1}^{m} λ_{j}∥·∥_{ℓ_{M_{j}}}^{p})^{1/p} K-embeds in L_{p}. The converse is also true.

Theorem 22 For every constant K and for every 0 < p < 2 there is a constant D such that given any normalized K-symmetric basic sequence {f_{i}}_{i=1}^{n} in L_{p} there is an m and there are m symmetric functions M_{j} : ℝ → [0, ∞), j = 1, …, m for which M_{j}(0) = 0, M_{j}(|t|^{1/p}) are convex and M_{j}(t^{1/2}) are concave on [0, ∞) and for some weights λ_{j}, {f_{i}}_{i=1}^{n} is D equivalent to the unit vector basis of ℝ^{n} with the norm

∥ · ∥ = ( ∑_{j=1}^{m} λ_{j}∥ · ∥_{ℓ_{M_{j}}}^{p} )^{1/p}. (19)

This theorem is a consequence of the following very nice inequality of Kwapień and Schütt [39].

Theorem 23 Let {a_{i,j}}_{i,j=1}^{n} ∈ ℝ^{n^{2}} and denote by {a_{i}^{∗}}_{i=1}^{n^{2}} the decreasing rearrangement of {a_{i,j}}. Then, for any 1 ≤ p < ∞,

\begin{matrix}Ave_{π}( ∑_{i=1}^{n} |a_{i,π(i)}|^{p})^{1/p} & ≤ & \frac{1}{n} ∑_{i=1}^{n} a_{i}^{∗} + (\frac{1}{n} ∑_{i=n+1}^{n^{2}} a_{i}^{∗p})^{1/p} \\ & ≤ & 5Ave_{π}( ∑_{i=1}^{n} |a_{i,π(i)}|^{p})^{1/p}. \end{matrix} (20)

Here Ave_{π} denotes the average over all permutations of 1, …, n.

The case p = 1 of Theorem 22 appears in [39]. The proof for the other values of p is quite similar and we shall sketch it below. The starting point is a lemma which gives another equivalent expression to the ones in (20). For 1 ≤ p < ∞ put

M(t) = M_{p}(t) = \{ \begin{matrix}(p − \frac{p−1}{n})^{−1}n^{p−1}|t|^{p} & if |t| ≤ 1/n \\ (p − \frac{p−1}{n})^{−1}(p|t| − \frac{p−1}{n}) & if |t| > 1/n. \end{matrix} (21)

Note that M_{p} is an Orlicz function and that M_{p}(t^{1/p}) is a concave function on [0, ∞).

Lemma 24 Let 1 ≤ p < ∞ and let a_{1} ≥ a_{2} ≥ … ≥ a_{n^{2}} ≥ 0. Then

\frac{1}{4n}∥\{a_{i}\}_{i=1}^{n^{2}}∥_{ℓ_{M}} ≤ \frac{1}{n} ∑_{i=1}^{n} a_{i} + (\frac{1}{n} ∑_{i=n+1}^{n^{2}} a_{i})^{1/p} ≤ \frac{p}{3n}∥\{a_{i}\}_{i=1}^{n^{2}}∥_{ℓ_{M}} (22)

PROOF. Note that M(pt) ≥ pM(t) for all t. Consequently, if ∥{a_{i}}_{i=1}^{n^{2}}∥_{ℓ_{M}} ≤ \frac{1}{p} then,

(p − \frac{p − 1}{n})^{−1}( ∑_{a_{i}>1/n} (pa_{i} − \frac{p − 1}{n}) + n^{p−1} ∑_{a_{i}≤1/n} a_{i}^{p}) ≤ \frac{1}{p}. (23)

It follows that ∑_{a_{i}>1/n} a_{i} ≤ ∑_{a_{i}>1/n} (pa_{i} − \frac{p−1}{n}) < 1 so that

∑_{i=1}^{n} a_{i} < 2 and #{i ; a_{i} > 1/n} ≤ n.

It now follows from (23) that ∑_{i=1}^{n} a_{i} + n(n^{−1} ∑_{i=n+1}^{n^{2}} a_{i}^{p})^{1/p} ≤ 3.

To prove the other side inequality assume ∑_{i=1}^{n} a_{i} + n(n^{−1} ∑_{i=n+1}^{n^{2}} a_{i}^{p})^{1/p} ≤ 1. Then

n^{p−1} ∑_{a_{i}≤1/n} a_{i}^{p} ≤ n^{p−1}( ∑_{i=n+1}^{n^{2}} a_{i}^{p} + ∑_{a_{i}≤1/n,i≤n} a_{i}^{p}) ≤ 2

and, since a_{n+1} ≤ \frac{1}{n} ∑_{i=1}^{n} a_{i} ≤ \frac{1}{n}, ∑_{a_{i}>1/n} a_{i} ≤ ∑_{i=1}^{n} a_{i} ≤ 1.

It follows that (for n ≥ 2)

\begin{aligned}∑_{i=1}^{n^{2}} M(a_{i}) & = & (p − \frac{p−1}{n})^{−1}( ∑_{a_{i}>1/n}(pa_{i} − \frac{p−1}{n}) + n^{p−1} ∑_{a_{i}≤1/n} a_{i}^{p}) \\ & ≤ & (p − \frac{p−1}{n})^{−1}(p + 2) ≤ 4. \end{aligned}

Since M(4t) ≥ 4M(t) this concludes the proof.

We now turn to a

sketch of the proof of Theorem 22 . Let {f_{i}}_{i=1}^{n} be a 1-symmetric basic sequence in l_{p}^{m}. Then up to a universal constant ,

\begin{aligned}∥ ∑_{i=1}^{n} a_{i}f_{i}∥ & ≈ & ( ∑_{k=1}^{m} Ave_{π}(∑_{i=1}^{n}(a_{π(i)}f_{i}(k))^{2})^{p/2})^{1/p} \\ & = & ( ∑_{k=1}^{m} λ_{k}^{p}Ave_{π}(∑_{i=1}^{n}(a_{π(i)}f_{i}(k)/λ_{k})^{2})^{p/2})^{1/p} \end{aligned}

where λ_{k}^{p} = ∥{f_{i}^{p}(k)}_{i=1}^{n}∥_{ℓ_{M_{2/p}}}.

By Theorem 23 and Lemma 24 the last expression is equivalent, with constants depending on p only, to

(\frac{1}{n} ∑_{k=1}^{m} λ_{k}^{p}∥\{a_{i}^{p}|f_{j}(k)|^{p}/λ_{k}^{p}\}_{i,j=1}^{n}∥_{ℓ_{M_{2/p}}} )^{1/p}. (24)

Put, for k = 1, …, m,

N_{k}(t) = ∑_{i=1}^{n} M_{2/p}(t|f_{i}(k)|^{p}/λ_{k}^{p}).

It is easy to check that the N_{k} are Orlicz functions with N_{k}(t^{p/2}) concave and that

∥{a_{i}^{p}|f_{j}(k)|^{p}/λ_{k}^{p}}_{i,j=1}^{n}∥_{ℓ_{M_{2/p}}} = ∥{a_{i}^{p}}_{i=1}^{n}∥_{ℓ_{N_{k}}} = ∥{a_{i}}_{i=1}^{n}∥_{ℓ_{M_{k}}}^{p}

Where M_{k}(t) = N_{k}(|t|^{p}). From this and (24) it is easy to conclude the proof.

The main result of [46] states that every unconditional basic sequence in L_{p}, 1 ≤ p ≤ 2, is equivalent to a block basis of a symmetric basic sequence in L_{p}. (The block basis can be chosen to be with equal coefficients and consequently the embedded space is also complemented. This will not be used here.) Of course if the unconditional basic sequence is finite also the containing symmetric sequence can be taken finite and the constants (of the symmetricity and of the equivalence) can be controlled by the unconditional constant. Recall that given a sequence of n Orlicz functions M̃ = {M_{i}}_{i=1}^{n} the modular space ℓM̃ is ℝ^{n} with the norm ∥x∥M̃ = inf{t > 0 ; ∑_{i=1}^{n} M_{i}(x_{i}/t) ≤ 1}. Using [46] and Theorem 22 one can now easily prove the following theorem.

Theorem 25 For every constant K and for every 1 ≤ p < 2 there is a constant D such that given any normalized K-unconditional basic sequence {f_{i}}_{i=1}^{n} in L_{p} there is an m, m Orlicz function sequences M̃_{j} = {M_{ji}}_{i=1}^{n}, j = 1, …, m, and positive constants λ_{j} and μ_{ji} such that M_{ji}(|t|^{1/p}) are convex and M_{ji}(t^{1/2}) are concave and {f_{i}}_{i=1}^{n} is D equivalent to the unit vector basis of ℝ^{n} with the norm

∥x∥ = ( ∑_{j=1}^{m} λ_{j}∥{x_{i}μ_{ji}}_{i=1}^{n}∥p ; M̃_{j} )^{1/p}. (25)

Of course if M_{ji}(t^{1/p}) are K-equivalent to convex functions and M_{ji}(t^{1/2}) are K-equivalent to concave functions then any norm as in (25) embeds into L_{p} with constant depending on K only.

3.2 Subspaces with bad gl constant

Recall first that the Gordon-Lewis constant, gl(X), of a Banach space X is defined to be

gl(X) = sup{γ_{1}(T) ; T : X → ℓ_{2}, π_{1}(T) ≤ 1}

where π_{1} denotes the 1-summing norm (see [28, section 10]) and γ_{1}(T : X → Y) = inf{∥A∥∥B∥}. Here the inf is taken over all L_{1} spaces L and over all decompositions T = AB with B : X → L, A : L → Y.

An easy but very useful theorem of Gordon and Lewis ([26] or [59, p. 260]) says that the unconditional constant of every basis of X is at least gl(X).

When 2 < p ≤ ∞ there is an abundance of “bad” subspaces of ℓ_{p}^{n}. By “bad” we mean here lacking good unconditional bases or even the weaker property of small Gordon-Lewis constant. Recall that L_{p}^{n} is L_{p} over the measure space consisting of n points and endowed with the uniform probability measure.

Theorem 26 There are positive constants c, c′ such that if X is any subspace of L_{p}^{n}, 2 < p ≤ ∞, satisfying dimX ≥ cn and ∥x∥_{L_{2}^{n}} ≤ 2∥x∥_{L_{1}^{n}} for all x ∈ X then gl(X) ≥ c′n^{1/2−1/p}.

Theorem 26 was proved by Figiel and Johnson in [21]. A somewhat weaker theorem, still ensuring the abundance of subspaces with large gl(X) was proved earlier by Figiel, Kwapień and Pełczyński [20]. We refer to [59, p. 261] for the proof of Theorem 26 for p = ∞. The case 2 < p < ∞ follows easily since the Banach-Mazur distance between L_{p}^{n} and L_{∞}^{n} is n^{1/p}.

Of course, for some c > 0, a random subspace X of L_{∞}^{n} of dimension cn satisfies the second assumption of Theorem 26, i.e., ∥x∥_{L_{2}^{n}} ≤ 2∥x∥_{L_{1}^{n}} for all x ∈ X (see [47] or [24]). This is why we claim that there is an abundance of subspaces of L_{p}^{n} satisfying the conclusion of Theorem 26.

For 1 ≤ p ≤ 2, gl(X) is uniformly bounded for any subspace X of L_{p}. Nevertheless, there are finite dimensional subspaces of L_{p} which have only bad unconditional bases (see [37]). This implies that sup{ubc(X) ; X ⊂ ℓ_{p}^{n}} → ∞ as n → ∞ but no estimates are known.

4 Restricted invertibility and finite dimensional subspaces of L_{p} of maximal distance to Euclidean spaces

4.1 Restricted invertibility of operators on ℓ_{p}^{n}

Motivated by some problems about the structure of finite dimensional subspaces of L_{p} that will be discussed in section (4.2), in [10] Bourgain and Tzafriri [10] proved Theorem 27 about the restricted invertibility of operators on ℓ_{p}^{n}. Qualitatively, this result says (or rather implies) that a bounded operator on ℓ_{p}^{n} which has ones on the diagonal must be invertible on a coordinate subspace of proportional dimension (even after projecting back into the coordinate subspace). In order to state Theorem 27 we introduce the following notation. Given a subset σ of {1, 2, …, n}, let ℓ_{p}^{σ} be the span in ℓ_{p}^{n} of the unit vector basis vectors {e_{i} : i ∈ σ} and let R_{σ} be the natural coordinate projection from ℓ_{p}^{n} onto ℓ_{p}^{σ}.

Theorem 27 Let 1 ≤ p ≤ ∞. For each ϵ > 0 there is δ_{p}(ϵ) > 0 so that if T is an n by n matrix, considered as an operator on ℓ_{p}^{n}, with zero diagonal, then for each ϵ > 0 there is a subset σ of {1, 2, …, n} of cardinality at least δ_{p}(ϵ)n so that ∥R_{σ}T R_{σ}∥_{p} ≤ ϵ∥T ∥_{p}. Consequently, if ϵ∥T ∥_{p} < 1, then ∥(R_{σ}(I + T)R_{σ})^{−1}∥_{p} ≤ \frac{1}{1−ϵ∥T ∥_{p}}.

The case p = 1, as well as the case p = ∞, which follows by duality, of Theorem 27 was proved earlier by the second author [30] and, independently, by Bourgain [4, p.113]. Bourgain’s argument gives more than what is stated in Theorem 27; namely, that there exists a splitting σ_{1}, σ_{2}, … σ_{k} of {1, 2, …, n} into k = k(ϵ) disjoint sets so that for each 1 ≤ i ≤ k, ∥R_{σ_{i}}T R_{σ_{i}}∥_{1} ≤ ϵ∥T ∥_{1}. Whether this strengthening of Theorem 27 remains valid for other values of p is open. For p = 2 this matrix splitting question is particularly interesting because it is equivalent to the Kadison-Singer problem [35] whether every pure state on ℓ_{∞} has a unique extension to a pure state on B(ℓ_{2}). For a discussion of the matrix splitting problem on ℓ_{2} see [16].

For a proof (due to K. Ball) of the matrix splitting result for ℓ_{1}^{n} which gives the estimate k(ϵ) ≤ 2/ϵ see [11]. Notice that in the case of ℓ_{1}^{n}, there is no loss of generality in treating only matrices with nonnegative entries because as operators on ℓ_{1}^{n}, T and |T | have the same norm. Berman, Halpern, Kaftal, and Weiss [3] independently used ideas similar to those used by Ball to prove an ℓ_{2}^{n} splitting result for matrices with nonnegative entries (which of course does not give a splitting result on ℓ_{2}^{n} for general matrices). It is amusing and instructive to note that the matrix splitting result for ℓ_{1}^{n} formally implies the matrix splitting result for nonnegative matrices on ℓ_{p}^{n} for all 1 ≤ p < ∞ via a change of density argument of L. Weis [61]. Here is the idea. First, after a change of density, a positive operator T on L_{p}(μ) (μ a probability) is nicely bounded on L_{∞}(μ). This follows from the fact that T maps the order interval [−f, f] for some f > 0 into the order interval [−(1 + ϵ)∥T ∥f, (1 + ϵ)∥T ∥f], which in turn follows via iteration and summing (as in the proof of 7) from the inclusion T [−g, g] ⊂ [−T g, T g], which is valid for all g ≥ 0 because T is a positive operator. Secondly, by working both with T and T^{∗}, one can get that, after a suitable change of density, a positive operator T on L_{p}(μ) (μ a probability) is nicely bounded on both on L_{1}(μ) and on L_{∞}(μ). Now specialize this to a positive operator on ℓ_{p}^{n}. The above discussion shows that this operator can be modeled as a (positive) operator T on L_{p}^{n}(μ) for some probability on {1, 2, …, n} in such a way that ∥T : L_{1}^{n}(μ) →: L_{1}^{n}(μ)∥ and ∥T : L_{∞}^{n}(μ) →: L_{∞}^{n}(μ)∥ do not exceed (2 + ϵ)∥T : L_{p}^{n}(μ) →: L_{p}^{n}(μ)∥. Since we know the splitting result for operators on ℓ_{1}^{n} and ℓ_{∞}^{n}, the result for ℓ_{p}^{n} follows by interpolation.

The proof of Theorem 27 for ℓ_{p}^{n} uses ℓ_{1}^{n} in a more serious way. By duality, it is enough to prove the case 1 < p < 2, so we restrict to this range of p. The “natural” approach to prove Theorem 27 is to show that if the set σ is chosen at random from among the subsets of {1, 2, …, n} having cardinality δn for small enough δ = δ(ϵ), then with big probability ∥R_{σ}T R_{σ}∥_{p} ≤ ϵ∥T ∥_{p}. This is, unfortunately, obviously wrong (consider the right shift operator). However, regarding ℓ_{p}^{n} as L_{p}^{n} (so that the injection I_{p,1} : L_{p}^{n} → L_{1}^{n} has norm one), it is true that for most such choices of σ the operator W := I_{p,1}R_{σ}T R_{σ} has norm not exceeding ϵδ^{1/p^{∗}}∥T ∥_{p} (the factor δ^{1/p^{∗}} is natural; it goes away when we regard W as an operator from L_{p}^{σ} into L_{1}^{σ}). For a proof, which is nice, and not particularly difficult, see [10, Proposition 1.10]. What is remarkable is that the p = 2 case in Theorem 27 then follows immediately by an application of Grothendieck’s inequality via Proposition 1! Indeed, W^{∗} maps L_{∞}^{n} into a Hilbert space and thus has 2-summing norm at most K_{G}∥W ∥, where K_{G} is Grothendieck’s constant (see [28, section 10]. Applying Proposition 1, we conclude that W = DU for some operator U on L_{2}^{n} of norm at most ϵK_{G}∥T ∥_{2} and some norm one diagonal operator D : L_{2}^{n} → L_{1}^{n}. The operator D is multiplication by some function g which has norm one in L_{2}^{n}, hence U is defined by the formula Uf = \frac{R_{σ}T R_{σ}f}{g}, whence ∥\frac{R_{σ}T R_{σ}f}{g} ∥_{2} ≤ ϵK_{G}∥T ∥_{2}∥f∥_{2} for

all f in L_{2}^{n}. Since ∥g∥_{2} = 1, ℙ[|g| ≥ \sqrt{2/δ}] ≤ δ/2; that is, |g(j)| ≥ \sqrt{2/δ} for at most (δn)/2 coordinates j. Throwing away any of these which are in the set σ and calling the resulting set σ′, we have that σ′ has cardinality at least (δn)/2 and ∥R_{σ′}T R_{σ′f}∥_{2} ≤ \sqrt{2}K_{G}ϵ∥T ∥_{2}.

That completes the outline of the proof of Theorem 27 in the Hilbertian case p = 2, which by itself has many applications (see [10] and [11]). It is, however, the other cases of Theorem 27 that have applications to the structure theory of finite dimensional L_{p} spaces. The proof we sketched for p = 2 does not carry over because operators from L_{∞} into L_{p^{∗}} need not be p^{∗}-summing when 1 < p < 2 (they are s-summing for all s > p^{∗}, but this is not sufficient). Lemma 28 is used to get around this problem.

Lemma 28 Suppose 1 < r < p < 2, μ, ν, τ are probabilities, X is a subspace of L_{p}(μ), T : X → L_{1}(ν) and U : X → L_{p}(τ) are operators so that

∥T x∥_{1} ≤ ∥Ux∥_{r}, x ∈ X. (26)

Then π_{p^{∗}}(T^{∗}) ≤ γ(r, p)∥U∥, where γ(r, p) is the L_{r}-norm of a p-stable random variable which is normalized in the L_{1}-norm.

In view of Corollary 6, to prove Lemma 28 it suffices to verify the estimate M^{(p)}(T) ≤ γ(r, p)∥U∥, which obviously follows from the the following inequality, valid for all finite sets of vectors x_{i} in X:

∥(∑_{i} |T x_{i}|^{p})^{1/p}∥_{1} ≤ γ(r, p)∥(∑_{i} |Ux_{i}|^{p})^{1/p}∥_{p}. (27)

To prove (27), write (∑_{i} |T x_{i}|^{p})^{1/p} = 𝔼| ∑_{i} f_{i}T x_{i}| where the f_{i} are independent

p-stable random variables with 𝔼|f_{i}| = 1 and interchange the expectation and the L_{1} norm to see that this is estimated from above by

∥(𝔼| ∑_{i} f_{i}Ux_{i}|^{r})^{1/r}∥_{r}. (28)

But (𝔼| ∑_{i} f_{i}Ux_{i}|^{r})^{1/r} = γ(r, p)(∑_{i} |Ux_{i}|^{p})^{1/p}, so (28) is dominated by the right

side of (27).

The main tool for proving Theorem 27 is:

Proposition 29 For each 0 < ϵ < 10^{−2} there is ρ = ρ(ϵ) > 0 so that if 1 < r < 2 and S is an operator on L_{2}^{n} (n ≥ n(ϵ, r)) with ∥S∥_{2} ≤ ρ, then there is a subset σ of {1, 2, …, n} of cardinality at least ϵn so that for all x,

∥R_{σ}Sx∥_{1} ≤ Cϵ(∥x∥_{r} + ∥Sx∥_{r}), (29)

where C is a numerical constant.

Here we are using as usual the L_{p}^{n} normalization. The important thing is that the factor Cϵ in (29) is a gain over the trivial factor ϵ^{1/r^{∗}}.

The p < 2 case of Theorem 27 follows easily from Lemma 28, Proposition 29, and the p = 2 case of Theorem 27. Indeed, Corollary 8 says that to prove Theorem 27 it is enough to consider norm one operators on L_{p}^{n} which have norm at most 2J_{p} as operators on L_{2}^{n}. The p = 2 case in Theorem 27 then says that it is enough to consider norm one operators on L_{p}^{n} which have norm at most ρ = ρ(ϵ) as operators on L_{2}^{n}. Now if S is an operator on L_{p}^{n} with ∥S∥_{p} = 1 and ∥S∥_{2} ≤ ρ, apply Proposition 29 to get σ. Define T = R_{σ}SR_{σ}, considered as an operator from L_{p}^{n} into L_{p}^{σ} (so that both the domain and range are L_{p} spaces of a probability), and set U = 2C(R_{σ} ⊕ SR_{σ}), considered as an operator from L_{p}^{n} into L_{p}^{2n} ≈^{2} L_{p}^{n} ⊕_{p} L_{p}^{n}. Then for, say, r = \frac{1+p}{2}, we have from Proposition 29 that for all x in ℝ^{n}, ∥T x∥_{L_{1}^{σ}} ≤ ∥Ux∥_{L_{r}^{2n}}. Lemma 28 then gives that π_{p^{∗}}(T^{∗}) ≤ γ(r, p)∥U∥_{p} ≤ 4Cγ(r, p). Changing back to the L_{p}^{n} normalization (that is, regarding R_{σ}SR_{σ} as an operator on L_{p}^{n}), we have that π_{p^{∗}}(R_{σ}S^{∗}R_{σ}) ≤ ϵ^{1/p}4Cγ(r, p). The completion of the proof of Theorem 27 is now just as in the p = 2 case.

For a proof of Proposition 29 see [11, Section 5]. Here is the idea: By the same kind of reasoning that works in the first part of the proof of Theorem 27, most choices of a subset σ of {1, …, n} of cardinality ϵn make it true that ∥R_{σ}Sx∥_{1} ≤ Cϵ∥Sx∥_{r} for all vectors x whose support has cardinality at most τn (an estimate for τ = τ(ϵ) comes out of the proof). For a general vector x, apply this to 1_{A}x, where A is the set of the τn largest coordinates of |x|, and use the smallness of ∥S∥_{2} to take care of x − 1_{A}x.

Corollary 30 gives a method, to be exploited in the next section, for building complemented copies of ℓ_{p}^{n} in subspaces of L_{p}.

Corollary 30 Let 1 ≤ p ≤ ∞ and 1 > ϵ > 0. If T is a norm one operator from ℓ_{p}^{n} into L_{p}(μ) and there are disjoint μ-measurable sets A_{i} so that ∥1_{A_{i}}T e_{i}∥_{p} ≥ ϵ for each 1 ≤ i ≤ n, then there is an operator S from L_{p}(μ) into ℓ_{p}^{n} with ∥S∥ ≤ 2/ϵ and a subset σ of {1, …, n} of cardinality at least δ_{p}(ϵ/2) so that ST_{|ℓ_{p}^{σ}} is the identity of ℓ_{p}^{σ}. Consequently, T R_{σ}S is a projection of L_{p}(μ) onto span {T e_{i}}_{i∈σ}.

Here the function δ_{p}(·) is taken from Theorem 27. For the proof of Corollary 30, take norm one vectors h_{i}, supported on A_{i}, so that ⟨T e_{i}, h_{i}⟩ = ∥T e_{i}∥_{p}.

Define S̃ from L_{p}(μ) to ℓ_{p}^{n} by S̃f = ∑_{i}^{n} ∥1_{A_{i}}T e_{i}∥_{p}^{−1}⟨f, h_{i}⟩e_{i}. Then ∥S̃∥ ≤ 1/ϵ

and S̃T has ones on the diagonal when represented as a matrix with respect to the unit vector basis for ℓ_{p}^{n}. Therefore, by Theorem 27 there is a subset σ of {1, …, n} of cardinality at least δ_{p}(ϵ/2) so that R_{σ}S̃T R_{σ} is a 1/2-perturbation of the identity operator on ℓ_{p}^{σ}. Set S = (R_{σ}S̃T R_{σ})^{−1}R_{σ}S.

4.2 Subspaces of L_{p} with maximal distance to Hilbert spaces

In this section we give some applications to the isomorphic structure theory of finite dimensional subspaces of L_{p}, 1 ≤ p < ∞, of the restricted invertibility theorem from the previous section. First, however, we mention what is known in the isometric and almost isometric theories. It is classical (see [1]) that a subspace of L_{p}(μ) which is isometric to an L_{p}(ν) space must be 1-complemented in L_{p}(μ). This was extended in [19] (for p = 1) and [52] (for 1 < p < ∞) to the almost isometric setting:

Theorem 31 For each 1 ≤ p < ∞ there is δ_{p} > 0 so that if 0 < ϵ < p and X is a subspace of L_{p}(μ) which is 1 + ϵ-isomorphic to an L_{p}(ν) space, then X is C_{p}(ϵ)-complemented in L_{p}(μ). Moreover, C_{p}(ϵ) → 1 as ϵ → 0.

Although Theorem 31 is stated for general subspaces X, it reduces easily to the case where X is finite dimensional, which is the case treated in [19] and [52]. A simpler proof of the p > 1 case is given in [11, Section 3].

Conversely, it is classical that a 1-complemented subspace of L_{p}(μ) is isometric to a L_{p}(ν) space (see [40]), but the almost isometric version of this result is open even for finite dimensional subspaces. (Here a result for finite dimensional spaces does not seem to imply formally a result for infinite dimensional spaces.)

It was mentioned already in section 1.2 that an n-dimensional subspace of L_{p}(μ) has Banach-Mazur distance at most n^{|1/p−1/2|} to ℓ_{2}^{n}. The converse to this is also true for 1 ≤ p < 2; see [10, Section 4] (as noted in [10], the p = 1 case is essentially done in [21]). For 2 < p < ∞ it is open whether there is an n-dimensional subspace of L_{p}(μ), not isometric to ℓ_{p}^{n}, which has Banach-Mazur distance n^{|1/p−1/2|} to ℓ_{2}^{n}.

We turn now to the isomorphic theory. Here and in the sequel we shall speak qualitatively about finite dimensional spaces, similar to the way one speaks about infinite dimensional spaces. In order for our statements to have content, statements should be quantified so as not to depend on dimension (but there may be dependence on other parameters). It takes only one example to illustrate why this convention is followed by Banach space local theorists. One of the main results we shall discuss is the following:

Theorem 32 If X is an n dimensional complemented subspace of L_{p}(μ), 1 < p < ∞, whose distance to ℓ_{2}^{n} is of maximal order, then X contains a subspace Y of proportional dimension (say, k) which is isomorphic to ℓ_{p}^{k} and complemented in L_{p}(μ).

The meaning of this statement is that there are functions f(p, δ, C) > 0 and g(p, δ, C) < ∞ (defined for 1 < p < ∞, δ > 0, and C < ∞) so that if X is an n-dimensional C-complemented subspace of L_{p}(μ) for some n and p, and d(X, ℓ_{2}^{n}) ≥ δn^{|1/p−1/2|}, then for some k ≥ f(p, δ, C)n there is a k-dimensional subspace Y of X with d(Y, ℓ_{p}^{k}) ≤ g(p, δ, C) and Y is g(p, δ, C)-complemented in L_{p}(μ).

Theorem 32 is also true for p = 1 ([30]), but in a stronger form – the complementation assumption is not needed. Given the method of [30], the main step in the proof of Theorem 32 which we sketch below is Theorem 27.

For p > 2 the complementation assumption in Theorem 32 is essential; this follows easily from Theorem 26. Whether the complementation assumption is needed when 1 < p < 2 is open.

A criterion for building a complemented copy of ℓ_{p}^{n} in a subspace X of L_{p}(μ) was given in Corollary 30. The idea for getting an operator T taking values in X which satisfies the hypothesis of the corollary is first to find vectors f_{i}, 1 ≤ i ≤ n, in the unit sphere of X for which the norm of the square function

S_{2}({f_{i}}_{i=1}^{n}) (where S_{r}({f_{i}}_{i=1}^{n}) := ( ∑_{i=1}^{n} |f_{i}|^{r})^{1/r} for r < ∞ and S_{∞}({f_{i}}_{i=1}^{n}) :=

max_{1≤i≤n} |f_{i}|) is nearly extremal; that is, the norm of S_{2}({f_{i}}) is proportional

to n^{1/p}. Once one has such a sequence, one uses an extrapolation argument. Indeed, for 1 ≤ p < 2, we shall outline an argument which deals with a somewhat more general situation. Suppose f̄_{i}, 1 ≤ i ≤ n, are in L_{p}(μ); and S_{2}({f̄_{i}}_{i=1}^{n}) ≥ δn^{1/p−1/2}(∑_{i=1}^{n} ∥f̄_{i}∥^{2})^{1/2}. Set θ = p/2 and f_{i} = f̄_{i}/∥f̄_{i}∥. Then, using the factorization S_{2}^{2}({f̄_{i}}_{i=1}^{n}) = ∑_{i=1}^{n} |f̄_{i}|^{p}∥f̄_{i}∥^{2−p}|f_{i}|^{2−p},

δn^{1/p−1/2}(∑_{i=1}^{n} ∥f̄_{i}∥^{2})^{1/2} ≤ ∥S_{2}({f̄_{i}}_{i=1}^{n})∥_{p}

≤ ∥S_{p}({f̄_{i}∥f̄_{i}∥^{(2−p)/p}}_{i=1}^{n})^{θ} S_{∞}({f_{i}}_{i=1}^{n})^{(1−θ)}∥_{p}

≤ ∥S_{p}({f̄_{i}∥f̄_{i}∥^{(2−p)/p}}_{i=1}^{n})∥_{p}^{θ} ∥S_{∞}({f_{i}}_{i=1}^{n})∥_{p}^{(1−θ)}

= (∑_{i=1}^{n} ∥f̄_{i}∥^{2})^{1/2} ∥S_{∞}({f_{i}}_{i=1}^{n})∥_{p}^{(1−θ)}

Letting Ã_{j} = [|f_{j}| = S_{∞}({f_{i}}_{i=1}^{n})] and setting A_{j} = Ã_{j} ∼ ∪_{i<j}Ã_{i}, we get

disjoint sets A_{i} so that δ^{2/(2−p)}n^{1/p} ≤ ∥ ∑_{i=1}^{n} 1_{A_{i}}f_{i}∥_{p}. Thus ∥1_{A_{i}}f_{i}∥_{p} is larger

than δ^{2/(2−p)}/2 for at least (δ^{2p/(2−p)}/2)n values of i.

Next suppose that 2 < p < ∞ and that f_{i}, 1 ≤ i ≤ n, are norm one vectors in L_{p}(μ) for which ∥S_{2}({f_{i}}_{i=1}^{n})∥ ≤ Cn^{1/p}. Set θ = 2/p. Then

\begin{aligned}n^{1/p} & = ∥S_{p}(\{f_{i}\}_{i=1}^{n})∥ ≤ ∥S_{2}(\{f_{i}\}_{i=1}^{n})^{θ}S_{∞}(\{f_{i}\}_{i=1}^{n})^{1−θ}∥ \\ & ≤ ∥S_{2}(\{f_{i}\}_{i=1}^{n})∥^{θ}∥S_{∞}(\{f_{i}\}_{i=1}^{n})∥^{1−θ} ≤ C^{θ}n^{θ/p}∥S_{∞}(\{f_{i}\}_{i=1}^{n})∥^{1−θ}. \end{aligned}

Thus there are disjoint sets A_{i} so that ∥1_{A_{i}}f_{i}∥_{p} is larger than 1/(2C^{2/(p−2))})

for at least (2C^{\frac{2p}{p−2}} )^{−1} n values of i.

To derive Theorem 32 from Corollary 30 we need the sequence {f_{i}} for which ∥1_{A_{i}}f_{i}∥_{p} is bounded away from zero also to be dominated by the ℓ_{p}^{k} basis. This can be accomplished in the following way.

Let 2 < p < ∞ and let P : L_{p}(μ) → L_{p}(μ) be the projection with range X. Assume that, for some k proportional to n, {f_{i}}_{i=1}^{k} is a sequence in the ball of the range of P^{∗} in L_{p^{∗}}(μ) satisfying ∥1_{A_{i}}f_{i}∥_{p} > δ > 0 for some disjoint sets {A_{i}}_{i=1}^{k}. Put g_{i} = P (|f_{i}|^{p^{∗}−1}sgn(f_{i})1_{A_{i}}). Note that {g_{i}}_{i=1}^{k} is dominated by the ℓ_{p}^{k} basis and in particular the norm of S_{2}({g_{i}}) is dominated by k^{1/p} and that the norms of the g_{i}-s are bounded away from zero since ∥g_{i}∥ ≥ ∫ g_{i}f_{i} ≥ δ^{p}. It follows that for a proportion of the g_{i}-s there are disjoint B_{i}-s for which ∥g_{i}1_{B_{i}}∥ are bounded away from zero. Now Corollary 30 applies to produce a subspace of X of proportional dimension isomorphic to ℓ_{p} of its dimension and complemented in L_{p}(μ). The case 1 < p < 2 follows by duality. We remark that this part of the argument, which is what we had in mind when we wrote [30], is considerably simpler than the one presented in [10].

Finally, we briefly indicate how to find in any n-dimensional subspace X of L_{p}(μ) of maximal order distance from ℓ_{2}^{n} a sequence {f_{i}}_{i=1}^{n} with ∥S_{2}({f_{i}})∥ of order n^{1/p−1/2}(∑_{i=1}^{n} ∥f̄_{i}∥^{2})^{1/2}. Assume for example that 1 < p < 2. By a theorem of Kwapien, [59, Th. 13.15] the type 2 constant of X is of order n^{1/p−1/2}, and by a theorem of Tomczak [59, Th. 25.6], this type 2 constant is attained, up to a universal constant, on n vectors; i.e., there are vectors {f_{i}}_{i=1}^{n} in X satisfying ∥S_{2}({f_{i}})∥ ≥ δn^{1/p−1/2}(∑_{i=1}^{n} ∥f_{i}∥^{2})^{1/2}.

5 Complemented subspaces

5.1 Fine embeddings of complemented subspaces of L_{p} in ℓ_{p}^{n}

Let X be a k-dimensional subspace of L_{p}, 1 ≤ p < ∞, and assume there is a projection of norm K from L_{p} onto X. Let ϵ > 0 and denote by P_{p}(X, K, ϵ) the smallest n such that X (1 + ϵ)-embeds in ℓ_{p}^{n} as a (1 + ϵ)K-complemented subspace; i.e., the smallest n such that there is a k-dimensional subspace Y of ℓ_{p}^{n}, an isomorphism T : X → Y with ∥T ∥∥T^{−1}∥ ≤ 1 + ϵ, and a projection of norm at most (1 + ϵ)K from ℓ_{p}^{n} onto Y. Also, denote by P_{p}(k, K, ϵ) the maximal P_{p}(X, K, ϵ) when X ranges over all k-dimensional subspaces of L_{p}. If 1 < p < ∞, looking at the case of X = ℓ_{2}^{k} shows that, at least for some K depending on p, P_{p}(k, K, ϵ) ≥ c(p) max{k^{p/2}, k^{p^{∗}/2}}, where p^{∗} = p/(p − 1). It turns out that, except for logarithmic terms, one can achieve this bound.

Theorem 33 ([8]) P_{p}(k, K, ϵ) ≤ C(p, K, ϵ) max{k^{p}/2, k^{p^{∗}}}(log k)^{C(p)}

For p = 1 one gets a better result

Theorem 34 P_{1}(k, K, ϵ) ≤ C(K, ϵ)k log k

The proofs follow the method of Section 2.1. Given a k-dimensional X ⊂ ℓ_{p}^{m}, 1 < p < ∞, and a projection P on ℓ_{p}^{m} with range X, we let Y = P^{∗}ℓ_{p^{∗}}^{m} and following the scheme of Section 2.1 we find a subset Ω ⊂ {1, 2, …, m} of the right cardinality such that

|m|Ω|^{−1} ∑_{i∈Ω} |x_{i}|^{p} − ∑_{i=1}^{m} |x_{i}|^{p}| < ϵ,  x ∈ X, ∥x∥_{p} = 1  (30)
|m|Ω|^{−1} ∑_{i∈Ω} |y_{i}|^{p^{∗})} − ∑_{i=1}^{m} |y_{i}|^{p^{∗}} | < ϵ, y ∈ Y, ∥y∥_{p^{∗}} = 1  (31)
|m|Ω|^{−1} ∑_{i∈Ω} x_{i}y_{i} − ∑_{i=1}^{m} x_{i}y_{i}| < ϵ, x ∈ X, y ∈ Y, ∥x∥_{p} = ∥y∥_{p^{∗}} = 1. (32)

For p = 1, (31) causes of course a problem. Fortunately enough, in this case the relevant inequality (stating that the restriction to Ω is a good isomorphism when restricted to Y ⊂ ℓ_{∞}^{m}) follows immediately from (30), (32) and the fact that a restriction to a subset is a norm one operator on ℓ_{∞}^{m}. Finally, it is easy to see that (30), (31) and (32) imply the desired result.

5.2 Finite decomposition and uniqueness of complements

The class of finite dimensional well complemented subspaces of L_{p} is a rich class, at least in the range 1 < p ≠ 2 < ∞. It follows from the previous section that the same is true for the well complemented k-dimensional subspaces of ℓ_{p}^{n} as long as k is smaller than a specific power of n. The situation for larger k is not known. In particular, it is not known whether a well complemented subspace of ℓ_{p}^{n} of proportional dimension is well isomorphic to a ℓ_{p}^{k} space. It is also not known whether ℓ_{p}^{n} is “primary”; i.e., whether ℓ_{p} = X ⊕ Y implies that either X or Y is well isomorphic to some ℓ_{p}^{k} (here we mean of course that the isomorphism constant should depend on the norm of the projection on X with kernel Y (and p) only). It is true however that if Y is “small” enough then X is well isomorphic to an ℓ_{p}^{k} space. There are two known instances of this statement with two different notions of smallness. These were proved in [33] following somewhat weaker results in [9] for the first theorem and [8] for the second.

Theorem 35 Assume 1 < p < ∞, ℓ_{p}^{n} = X + Y, d(Y, ℓ_{2}^{k}) ≤ K, and there is a projection P from ℓ_{p}^{n} onto X with kernel Y and ∥P ∥ ≤ L. Then d(X, ℓ_{p}^{n−k}) ≤ C = C(K, L, p).

Theorem 36 Let 1 < p < ∞ and put p̄ = max{p, p^{∗}}. Assume ℓ_{p}^{n} = X + Y with dimY = k < n^{2/p̄}/(log n)^{C(p)} and that there is a projection P from ℓ_{p}^{n} onto X with kernel Y and ∥P ∥ ≤ L. Then d(X, ℓ_{p}^{n−k}) ≤ C = C(L, p).

The proofs relay on a simple but powerful “decomposition method” applied to a “path” of complemented subspaces of L_{p} together with a proposition concerning “uniqueness of complements”.

We begin with the decomposition method from [33], which improved on the original finite dimensional decomposition method introduced in [2].

Lemma 37 Let 1 ≤ p ≤ ∞. Let Z_{i}, i = 1, …, m, be Banach spaces and, for i = 1, …, m, let Y_{i} be a K-complemented subspace of Z_{i}. Assume also d(Y_{i}, Y_{i−1}) ≤ L, i = 1, …, m. Then Y_{0} ⊕ ∑_{i=1}^{m} ⊕_{p}Z_{i} is CKL-isomorphic to Y_{m} ⊕ ∑_{i=1}^{m} ⊕_{p}Z_{i}. In particular, if Z_{i} = ℓ_{p}^{s_{i}}, i = 1, …, m, and s = ∑_{i=1}^{m} s_{i} then Y_{0} ⊕ ℓ_{p}^{s} is CKL-isomorphic to Y_{m} ⊕ ℓ_{p}^{s}.

The proof is very simple. Let X_{i} be the complement of Y_{i} in Z_{i}, i = 1, …, m. Then,

Y_{0} ⊕ ∑_{i=1}^{m} ⊕_{p}Z_{i} ≈ ( \begin{matrix}Y_{0} \\ ⊕_{p} \\ 0 \end{matrix} ) ⊕_{p} ( \begin{matrix}Y_{1} \\ ⊕_{p} \\ X_{1} \end{matrix} ) ⊕_{p} ( \begin{matrix}Y_{2} \\ ⊕_{p} \\ X_{2} \end{matrix} ) ⊕_{p} … ⊕_{p} ( \begin{matrix}Y_{m} \\ ⊕_{p} \\ X_{m} \end{matrix} ) . (33)

We now shift the top row to the right

≈ ( \begin{matrix}Y_{0} \\ ⊕_{p} \\ X_{1} \end{matrix} ) ⊕_{p} ( \begin{matrix}Y_{1} \\ ⊕_{p} \\ X_{2} \end{matrix} ) ⊕_{p} … ⊕_{p} ( \begin{matrix}Y_{m−1} \\ ⊕_{p} \\ X_{m} \end{matrix}) ⊕_{p} ( \begin{matrix}Y_{m} \\ ⊕_{p} \\ 0 \end{matrix} ) (34)

to get

Y_{0} ⊕ ∑_{i=1}^{m} ⊕_{p}Z_{i} ≈ Y_{m} ⊕ ∑_{i=1}^{m} ⊕_{p}Z_{i}. (35)

This picturesque proof can easily be justified.

To prove Theorem 35 we assume that p > 2 and k = 2^{m}. We build a path Y_{0}, …, Y_{m} of spaces connecting Y_{0} = ℓ_{2}^{k} with Y_{m} = ℓ_{p}^{k} with d(Y_{i}, Y_{i−1}) ≤ 2. This can be done in several ways but, since we also want Y_{i} to be well isomorphic to a well complemented subspace of ℓ_{p}^{s_{i}} with s_{i} as small as possible, we take Y_{i} to be the ℓ_{p} sum of 2^{i} copies of ℓ_{2}^{2^{m−i}}.

Given any δ > 0, ℓ_{2}^{2^{m−i}} embeds as a complemented subspace, with constants depending only on p and δ, into ℓ_{p}^{r_{i}} with r_{i} = [δ2^{(m−i)p/2}]. The fact that this holds for some δ < ∞ is exposed for example in [24]. To get it for all δ > 0 represent ℓ_{2}^{uv} as the ℓ_{p} sum of u copies of ℓ_{2}^{v} (introducing of course a constant depending on u and p), embed each summand complementably in an appropriate ℓ_{p} space, and take the ℓ_{p} sum of these u spaces as the containing ℓ_{p} space.

It follows that Y_{i} well embeds complementably into ℓ_{p}^{s_{i}} for s_{i} = [δ2^{i}2^{(m−i)p/2}]. Lemma 37 implies then that, for s = ∑_{i=1}^{m} s_{i}, ℓ_{2}^{k} ⊕ ℓ_{p}^{s} ≈ ℓ_{p}^{s+k}.

The assumption that ℓ_{2}^{k} is well complemented in ℓ_{p}^{n} implies that n = γk^{p/2} for some γ bounded away from zero (this is a result of [2]). It is now easy to see that, with the right choice of δ, s = n − k and ℓ_{2}^{k} ⊕ ℓ_{p}^{n−k} ≈ ℓ_{p}^{n}.

It remains to show that if also ℓ_{2}^{k} ⊕ X ≈ ℓ_{p}^{n} then X ≈ ℓ_{p}^{n−k}. This follows from the following simple “uniqueness of complement” result of [9] in the form proved in [33]. In the statement “+” denotes a direct sum of subspaces and the isomorphism constants implicit in the notation “ ≈ ” of the conclusions depend only on the constants for the “ ≈ ” and the projections in the hypotheses.

Proposition 38 Assume Z = Y + X = H + G with H ⊂ X, and assume H ≈ Y ⊕ W. Then X ≈ G ⊕ W. In particular, if for i = 1, 2, Z = Y_{i} + X_{i} = H_{i} + G_{i} with Y ≈ Y_{i}, G ≈ G_{i}, H ≈ H_{i} ⊂ X_{i} and H ≈ Y ⊕ W. Then X_{1} ≈ X_{2}.

To end the proof of Theorem 35 we only have to show that X, the complement of Y ≈ ℓ_{2}^{k} in ℓ_{p}^{n}, contains a subspace well isomorphic to ℓ_{2}^{k} and well complemented. Since n is of order at least k^{p/2}, the general theory of Euclidean sections as exposed in [24] implies that, for some δ > 0, X contains a subspace U_{1} well isomorphic to ℓ_{2}^{δk}. U_{1} is automatically well complemented (see [44] or [18, p. 46]). Now find another copy of ℓ_{2}^{δ′k} in the complement of U_{1} in X and iterate.

The proof of Proposition 38 ([33]) is very easy: Put F = X ∩ G. Then Z = Y + X = Y + F + H and consequently G ≈ Y ⊕ F. Thus X = F + H ≈ F ⊕ Y ⊕ W ≈ G ⊕ W.

The proof of Theorem 36 follows the same outline as that of the proof of Theorem 35. Given a k-dimensional well complemented subspace Y_{0} of L_{p}, 2 < p < ∞ we find a path Y_{0}, Y_{1}, …, Y_{m} of well complemented subspaces of L_{p} with d(Y_{i}, Y_{i−1}) < 4, Y_{m} well isomorphic to ℓ_{2}^{k}, and m = [log_{2} k]. We then use Theorem 33 to embed each of Y_{i} in a well complemented fashion in a low dimensional ℓ_{p} space and continue in a way similar to the proof of Theorem 35.

To build the path of spaces Y_{i}, apply first the change of density of Theorem 2 and then that of Theorem 7 to get that without loss of generality ∥y∥_{p} ≤ 2n^{1/2−1/p}∥y∥_{2} for each y ∈ Y_{0} and the projection P from L_{p} onto Y_{0} is also well bounded with respect to the L_{2} norm. Put

Y_{i} = {(y, 2^{i}y); y ∈ Y_{0}} ⊂ L_{p} ⊕_{p} L_{2}, i = 1, 2, …, m.

Then clearly d(Y_{i}, Y_{i−1}) < 4, i = 1, 2, …, m, Y_{m} is well isomorphic to ℓ_{2}^{k} and it only remains to show that each of Y_{i} is well isomorphic to a well complemented subspace of L_{p}.

Since P is bounded in both L_{p} and L_{2}, Y_{i} is well complemented in Z_{i} = {(z, 2^{i}z); y ∈ L_{p}} ⊂ L_{p} ⊕_{p} L_{2}. Finally, by a theorem of Rosenthal [51] (see also [1]) Z_{i} is well isomorphic to a well complemented subspace of L_{p}.

References

[1] Alspach, D. E.; Odell, E. W. This handbook.

[2] Bennett, G.; Dor, L. E.; Goodman, V.; Johnson, W. B.; Newman, C. M. On uncomplemented subspaces of L_{p}, 1 < p < 2. Israel J. Math. 26 (1977), no. 2, 178–187.

[3] Berman, Kenneth; Halpern, Herbert; Kaftal, Victor; Weiss, Gary Matrix norm inequalities and the relative Dixmier property. (English) Integral Equations Operator Theory 11 (1988), no. 1, 28–48.

[4] Bourgain, J. New classes of L^{p}-spaces. Lecture Notes in Mathematics, 889. Springer-Verlag, Berlin-New York, 1981.

[5] Bourgain, J. Subspaces of l_{N}^{∞}, arithmetical diameter and Sidon sets. Probability in Banach spaces, V (Medford, Mass., 1984), 96–127, Lecture Notes in Math., 1153, Springer, Berlin-New York, 1985.

[6] Bourgain, J. Bounded orthogonal systems and the Λ(p)-set problem. Acta Math. 162 (1989), no. 3-4, 227–245.

[7] Bourgain, J.; Kalton, N. J.; Tzafriri, L. Geometry of finite-dimensional subspaces and quotients of L_{p}. Geometric aspects of functional analysis (1987–88), 138–175, Lecture Notes in Math., 1376, Springer, Berlin-New York, 1989.

[8] Bourgain, J.; Lindenstrauss, J.; Milman, V. M. Approximation of zonoids by zonotopes Acta Math. series 162 (1989), 73–141.

[9] Bourgain, J.; Tzafriri, L. Complements of subspaces of l_{p}^{n}, p ≥ 1, which are uniquely determined. Geometrical aspects of functional analysis (1985/86), 39– 52, Lecture Notes in Math., 1267, Springer, Berlin-New York, 1987.

[10] Bourgain, J.; Tzafriri, L. Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis. Israel J. Math. 57 (1987), no. 2, 137–224.

[11] Bourgain, J.; Tzafriri, L. Restricted invertibility of matrices and applications. Analysis at Urbana, Vol. II (Urbana, IL, 1986–1987), 61–107, London Math. Soc. Lecture Note Ser., 138, Cambridge Univ. Press, Cambridge-New York, 1989.

[12] Bourgain, J.; Tzafriri, L. Embedding l_{p}^{k} in subspaces of L_{p} for p > 2. Israel J. Math. 72 (1990), no. 3, 321–340 (1991).

[13] Bourgain, J.; Tzafriri, L. On a problem of Kadison and Singer. J. Reine Angew. Math. 420 (1991), 1–43.

[14] Bretagnolle, Jean; Dacunha-Castelle, Didier. Application de l’étude de certaines formes linéaires aléatoires au plongement d’espaces de Banach dans des espaces L^{p}. (French) Ann. Sci. École Norm. Sup. (4) 2 1969 437–480.

[15] Carl, Bernd; Pajor, Alain. Gelfand numbers of operators with values in a Hilbert space. Invent. Math. 94 (1988), no. 3, 479–504.

[16] Davidson, K. R.; Szarek, S. J. Banach space theory and “local” operator theory. This handbook.

[17] Davis, W. J.; Milman, V. D.; Tomczak-Jaegermann, N. The distance between certain n-dimensional Banach spaces. Israel J. Math. 39 (1981), no. 1-2, 1–15.

[18] Diestel, Joe; Jarchow, Hans; Tonge, Andrew. Absolutely summing operators. Cambridge studies in advanced mathematics 43, Cambridge University Press, Cambridge-New York-Port Chester-Melbourne-Sydney, 1995.

[19] Dor, Leonard E. On projections in L_{1}. Ann. of Math. (2) 102 (1975), no. 3, 463–474.

[20] Figiel, Tadeusz; Kwapień, Stanisław; Pełczyński, Aleksander. Sharp estimates for the constants of local unconditional structure of Minkowski spaces. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 25 (1977), no. 12, 1221–1226.

[21] Figiel, T.; Johnson, W. B. Large subspaces of l_{∞}^{n} and estimates of the Gordon-Lewis constant. Israel J. Math. 37 (1980), no. 1-2, 92–112.

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

[23] Figiel, T.; Johnson, W. B.; Schechtman, G. Factorizations of natural embeddings of l_{p}^{n} into L_{r}. II. Pacific J. Math. 150 (1991), no. 2, 261–277.

[24] Giannopoulos, A. A.; Milman, V. M. Euclidean structure in finite dimensional normed spaces. This handbook.

[25] Gluskin, E. D.; Tomczak-Jaegermann, N.; Tzafriri, L. Subspaces of l_{p}^{N} of small codimension. Israel J. Math. 79 (1992), no. 2-3, 173–192.

[26] Gordon, Y.; Lewis, D. R. Absolutely summing operators and local unconditional structures. Acta Math. 133 (1974), 27–48.

[27] Johnson, W. B.; Jones, L. Every L_{p} operator is an L_{2} operator. Proc. Amer. Math. Soc. 72 (1978), no. 2, 309–312.

[28] Johnson, W. B.; Lindenstrauss, J. Basic concepts in the geometry of Banach spaces. This handbook.

[29] Johnson, W. B.; Maurey, B.; Schechtman, G.; Tzafriri, L. Symmetric structures in Banach spaces. Mem. Amer. Math. Soc. 19 (1979), no. 217

[30] Johnson, W. B.; Schechtman, G. On subspaces of L_{1} with maximal distances to Euclidean space. Proceedings of research workshop on Banach space theory (Iowa City, Iowa, 1981), 83–96, Univ. Iowa, Iowa City, Iowa, 1982.

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

[32] Johnson, W. B.; Schechtman, G. Remarks on Talagrand’s deviation inequality for Rademacher functions, in: Functional analysis (Austin, TX, 1987/1989) (Lecture Notes in Math., 1470, Springer, Berlin, 1991) 72–77.

[33] Johnson, W. B.; Schechtman, G. On the distance of subspaces of l_{p}^{n} to l_{p}^{k}. Trans. Amer. Math. Soc. 324 (1991), no. 1, 319–329.

[34] Johnson, W. B.; Schechtman, G. Computing p-summing norms with few vectors. Israel J. Math. 87 (1994), no. 1-3, 19–31.

[35] Kadison, Richard V.; Singer, I. M. Extensions of pure states. Amer. J. Math. 81 1959 383–400.

[36] Kalton, N. J. The endomorphisms of L_{p}(0 ≤ p ≤ i). Indiana Univ. Math. J. 27 (1978), no. 3, 353–381.

[37] Ketonen, Timo On unconditionality in L_{p} spaces. Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes No. 35 (1981).

[38] Koldobsky, A.; König, H.. Aspects of the isometric theory of Banach spaces. This handbook.

[39] Kwapień, Stanisław; Schütt, Carsten Some combinatorial and probabilistic inequalities and their application to Banach space theory. Studia Math. 82 (1985), no. 1, 91–106.

[40] Lacey, H. Elton. The isometric theory of classical Banach spaces. Die Grundlehren der mathematischen Wissenschaften, Band 208. Springer-Verlag, New York-Heidelberg, 1974. x+270 pp.

[41] Ledoux, M.; Talagrand, M.. Probability in Banach spaces, Isoperimetry and processes. Springer-Verlag, Berlin, (1991).

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

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

[44] Maurey, Bernard Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces L^{p}. (French) With an English summary. Astérisque, No.

11. Société Mathématique de France, Paris, 1974.

[45] Maurey, B. This handbook.

[46] Maurey, B.; Schechtman, G. Some remarks on symmetric basic sequences in L_{1}. Compositio Math. 38 (1979), no. 1, 67–76.

[47] Milman, V. D.; Schechtman, G. Asymptotic theory of finite–dimensional normed spaces. Lecture Notes in Mathematics, 1200. Springer-Verlag, Berlin-New York (1986).

[48] Pisier, G. Un thèorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert. (French) Ann. Sci. École Norm. Sup. (4) 13 (1980), no. 1, 23–43.

[49] Pisier, Gilles On the dimension of the l_{p}^{n}-subspaces of Banach spaces, for 1 ≤ p < 2. Trans. Amer. Math. Soc. 276 (1983), no. 1, 201–211.

[50] Pisier, Gilles Factorization of operators through L_{p∞} or L_{p1} and noncommutative generalizations. Math. Ann. 276 (1986), no. 1, 105–136.

[51] Rosenthal, Haskell P. On the subspaces of L^{p} (p > 2) spanned by sequences of independent random variables. Israel J. Math. 8 1970 273–303.

[52] Schechtman, G. Almost isometric L_{p} subspaces of L_{p}(0, 1). J. London Math. Soc. (2) 20 (1979), no. 3, 516–528.

[53] Schechtman, G. . More on embedding subspaces of L_{p} in l_{r}^{n}. Compositio Math. series 61 (1987), 159–169.

[54] Schechtman, G. This handbook.

[55] Schechtman, G.; Zvavitch, A. Embedding subspaces of L_{p} into ℓ_{p}^{N}, 0 < p < 1. Math. Nachr., to appear.

[56] Szarek, S. J. Computing summing norms and type constants on few vectors. Studia Math. 98 (1991), no. 2, 147–156.

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

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

[59] Tomczak-Jaegermann, Nicole Banach-Mazur distances and finite-dimensional operator ideals. Pitman Monographs and Surveys in Pure and Applied Mathematics, 38. Longman Scientific & Technical, Harlow, 1989.

[60] Tzafriri, L. Uniqueness of structure in Banach spaces. This handbook.

[61] Weis, L. Integral operators and changes of density. Indiana Univ. Math. J. 31 (1982), no. 1, 83–96.

[62] Wojtaszczyk, P. Banach spaces for analysts. Cambridge Studies in Advanced Mathematics, 25. Cambridge University Press, Cambridge, 1991