Very tight embeddings of subspaces of L_{p}, 1 ≤ p < 2, into ℓ_{p}^{n}

William B. Johnson^{∗}  Gideon Schechtman^{†}

Abstract

We prove that for 1 ≤ p < r < 2, every n-dimensional subspace E of L_{r}, in particular ℓ_{r}^{n}, well-embeds into ℓ_{p}^{m} for some m ≤ (1 + ϵ)n, where “well” depends on p, r, and the arbitrary ϵ > 0, but not on n.

1 Introduction

Given two normed spaces X and Y we say that X K-embeds into Y provided there exists a subspace X̄ of Y and an isomorphism T from X onto X̄ with ∥T ∥∥T^{−1}∥ ≤ K. Starting with Dvoretzky’s Theorem [D], a lot of attention was given to the question of what is the smallest dimension of a space, out of a certain family, into which ℓ_{2}^{d} Kembeds. For example, it is shown in [FLM] that, for every ϵ > 0, ℓ_{2}^{d} (1 + ϵ)-embeds into ℓ_{p}^{n} whenever d ≤ c(ϵ)n, for 1 ≤ p < 2, and whenever d ≤ c(p, ϵ)n^{2/p}, for 2 < p < ∞. The proofs in [FLM] are based on concentration inequalities, following Milman’s [Mi] method for proving Dvoretzky-like theorems. As such the proofs do not give better results (i.e., smaller n) for ϵ > 1 than what they give for ϵ = 1, say. There is however a different method of Kashin [K], based on volume considerations, which only works in some restricted class of spaces but gives better results for large K: For every μ > 1 and 1 ≤ p < 2 there is a K = K(p, μ) such that for every d ℓ_{2}^{d}, K-embeds into ℓ_{p}^{μd}.

Concerning embeddings of other classical spaces, the first result not involving Euclidean spaces is contained in [JS1], where it was proved that for all ϵ > 0 and 1 < p < 2, ℓ_{p}^{d} (1 + ϵ)-embeds into ℓ_{1}^{n} whenever d ≤ c(p, ϵ)n. This was extended by replacing ℓ_{p}^{d} with more general subspaces of L_{1}, in [BLM] and [T], using the random sampling method introduced in [S]. There is an extensive literature on this subject with more extensions and refinements. We refer the reader to [JS3] for a survey of this topic.

∗Supported in part by NSF DMS-0200690, Texas Advanced Research Program 010366-0033-20013, U.S.-Israel Binational Science Foundation, and a Weston Visiting Professorship at The Weizmann Institute of Science.

†Supported in part by Israel Science Foundation and U.S.-Israel Binational Science Foundation; participant, NSF Workshop in Linear Analysis and Probability, Texas A&M University.

All these results were proved by using some kind of concentration results and as such did not give better estimates, in terms of the dimension of the containing space, when the constant of the embedding was allowed to be large. The exception is a result of Naor and Zvavitch [NZ]. They proved that for every μ > 1 and 1 < p < 2, ℓ_{p}^{d} K(d, p, μ)-embeds into ℓ_{1}^{μd} where K(d, p, μ) is a power of log d depending only on p and μ.

Our purpose here is to strengthen this to the status of Kashin’s theorem and show that for every μ > 1 and 1 < p < 2 there is a K = K(p, μ) such that for every d, ℓ_{p}^{d} K-embeds into ℓ_{1}^{μd}. The critical reader may notice that at first glance this may look contradictory: Since any two d-dimensional subspaces of a μd dimensional space have a (2 − μ)d-dimensional common subspace, it follows that any two ℓ_{p_{i}}^{d} spaces, 1 < p_{1}, p_{2} < 2 have (2 − μ)d-dimensional subspaces which are 2K-isomorphic (and (2 − μ) < 1 is arbitrarily close to 1). Of course there is no contradiction here, the common subspace can be an Euclidean space, by Kashin’s theorem (or any ℓ_{r}^{(2−μ)d}, max{p_{1}, p_{2}} < r < 2 by ours).

In Theorem 2 below we actually show more.

Main Result For every 1 ≤ p < q ≤ 2 and every μ > 1 there is a constant K = K(p, q, μ) such that if X is a d-dimensional subspace of L_{q} then X K-embeds into ℓ_{p}^{n} for n = [μd].

Theorem 2 also contains information about general subspaces of L_{p}; i.e., subspaces which do not necessarily embed into L_{q} for some q > p.

2 The main result

We begin by stating a theorem from [BKT] which will be our main tool. The case p = 1 of this theorem was known earlier; as was mentioned in [BKT], it appears implicitly in [CP]. We denote by {e_{i}}_{i=1}^{n} the canonical basis of ℓ_{p}^{n} and by [e_{i}]_{i∈σ} the subspace of ℓ_{p}^{n} spanned by {e_{i}}_{i∈σ}. Given an operator Q from ℓ_{p}^{n}, Q_{|[e_{i}]_{i∈σ}} denotes the operator Q restricted to [e_{i}]_{i∈σ}.

Theorem 1 ([BKT]) There is a constant 1 ≥ c > 0 such that if 1 ≤ p < 2, Q : ℓ_{p}^{n} → Y is a quotient map and a dimY ≥ n for some a > 1, then there is a subset σ of {1, 2, …, n} of cardinality at least c^{a}n so that Q_{|[e_{i}]_{i∈σ}} is a c^{−a} isomorphism.

The proof is contained in the proof of Theorem 2.1 in [BKT] using the estimates in Elton’s theorem [E] (see [MV] for the best estimates, but they are not needed here).

Corollary 1 Let X be a d-dimensional subspace of ℓ_{p}^{n}, 1 ≤ p < 2 and put a = n/(n−d). Then X is 1 + c^{−a} isomorphic to a subspace of ℓ_{p}^{[(1−c^{a})n]}.

Proof: Put Y = ℓ_{p}^{n}/X and denote by Q the quotient map from ℓ_{p}^{n} onto Y with kernel X. Let σ be the set from the conclusion of Theorem 1 and let P : ℓ_{p}^{n} → [e_{i}]_{i∈σ̃} be the natural restriction map, where σ̃ is the complementary set to σ. For x ∈ X,

∥P x∥ = ∥x − (I − P)x∥ ≥ ∥Q(I − P)x∥ ≥ c^{a}∥(I − P)x∥

and thus

∥x∥ ≤ ∥P x∥ + ∥(I − P)x∥ ≤ (1 + c^{−a})∥P x∥.

This means that X is 1+c^{−a} isomorphic to a subspace of [e_{i}]_{i∈σ̃} which in turn is isometric to ℓ_{p}^{k} with k ≤ n − c^{a}n.

Proposition 1 For every λ > 0 there is a K < ∞ such that if X is a subspace of ℓ_{p}^{n}, 1 ≤ p < 2, then X is K isomorphic to a subspace of ℓ_{p}^{m} with m ≤ dimX + λn.

Proof: Put d = dimX. Note that if n ≥ k > d + λn, then \frac{k}{k−d} ≤ \frac{1}{λ} and thus c^{\frac{k}{k−d}} ≥ c^{\frac{1}{λ}}. (Recall that c is the constant from Theorem 1 and thus satisfies 0 < c ≤ 1.) Consequently, if n ≥ k ≥ d + λn and X is C isomorphic to a subspace of ℓ_{p}^{k}, then, by Corollary 1, X is

C(1 + c^{− \frac{1}{λ}}) isomorphic to a subspace of ℓ_{p}^{(1−c^{\frac{1}{λ}})k}.

By iterating we see that if s is the first integer for which m ≡ (1 − c^{\frac{1}{λ}})^{s}n < d + λn, then X is (1 + c^{− \frac{1}{λ}})^{s} isomorphic to a subspace of ℓ_{p}^{m}.

Since s can be estimated as a function of λ, the proposition is proved.

Recall that the type q constant of a normed space X is the smallest T for which for all n and all choices of {x_{i}}_{i=1}^{n} ⊂ X

(Ave∥ ∑_{i=1}^{n} ϵ_{i}x_{i}∥^{2})^{1/2} ≤ T (∑_{i=1}^{n} ∥x_{i}∥^{q})^{1/q}

where Ave denotes the average over all choices of signs {ϵ_{i}} ∈ {−1, 1}^{n}. Recall that for 1 ≤ q ≤ 2 the type q constant of L_{q} over any measure space is finite and bounded by a constant depending only on q. Consequently, the result stated in the abstract follows from the following theorem, which is the main result of this paper.

Theorem 2 (a) For every 1 ≤ p < q ≤ 2, T < ∞, and every μ > 1 there is a constant K = K(p, q, T, μ) such that if X is a d-dimensional subspace of L_{p} whose type q constant is at most T, then X K-embeds into ℓ_{p}^{n} for n = [μd].

(b) For every 1 ≤ p < 2, and every μ > 1 there is a constant K = K(p, μ) such that if X is a d-dimensional subspace of L_{p}, then X K(log(d + 2))^{1/p}-embeds into ℓ_{p}^{n} for n = [μd].

Proof: (a) follows from Proposition 1 and the fact, first proved in [BLM], that the conclusion of (a) holds for some μ = μ(p, q, T) and K = 2 (say).

(b) Using Proposition 1, it is enough to prove the claim for some μ, depending only on p. We first 2-embed X into ℓ_{1/2}^{μd} for some μ (or into any other ℓ_{r}^{μd} for some r < p). The possibility of doing that is essentially contained in [BLM], although, for p = 1, it is first stated and proved in [JS2]. [JS3] contains a proof for the whole range which is probably the shortest available one. We are assuming, as we may, that μd is an integer. We denote the image of X under this embedding by Y. Now there are two ways to proceed, both via some change of density argument. We shall describe one way based on a change of density due to Pisier and remark about the other one, based on a result of Maurey, later.

It follows from Theorem 1.1 in [P] that there is a probability measure ν on {1, 2, …, μd} such that

∥x∥_{p,∞} ≤ C∥x∥_{1/2}

for all x in the the image Z of Y under the natural isometry between ℓ_{1/2}^{μd} and the space L_{1/2}({1, 2, …, μd}, ν). Here C is an absolute constant, ∥x∥_{1/2} denotes the norm of x in L_{1/2}({1, 2, …, μd}, ν) and ∥x∥_{p,∞} = max_{t>0} t(ν({i; ∥x(i)∥ > t}))^{1/p}. Since ν is a probability measure we also have that ∥x∥_{p,∞} ≥ c∥x∥_{1/2} for all x and some absolute c > 0. In particular Z C/c-embeds into L_{p,∞}(ν).

Let A be a subset of {1, 2, …, μd} of positive measure. Applying the inequality ∥x∥_{p,∞} ≥ c∥x∥_{1/2} in the probability space (A, \frac{ν_{|A}}{ν(A)}) we get that

∥x_{|A}∥_{1/2} ≤ c^{−1}ν(A)^{2−1/p}∥x_{|A}∥_{p,∞} ≤ (C/c)ν(A)^{2−1/p}∥x∥_{1/2}

for all x ∈ Z. It follows that if (C/c)ν(A)^{2−1/p} < 1/2 then the restriction to Ã, the complement of A, is a 2-isomorphism on Z. Note also that the equivalence of the L_{1/2} norm with the L_{p,∞} norm on this restriction remains valid, although we have to change the constants to some other absolute constants. Since the total measure of A = {i; ν(i) < 1/(Mμd)} is at most 1/M we may assume, by restricting to Ã, that, for an appropriate absolute M, ν(i) ≥ 1/(Mμd).

The reason for eliminating the small atoms is that now one can easily deduce that the (natural) distance between L_{p,∞}(ν) and L_{p}(ν) is an absolute constant multiple of (log(μd))^{1/p}. This concludes the proof.

As we remarked before, instead of using Pisier’s result one can use a much earlier result of Maurey [Ma] which is similar in nature and ensures, for every ϵ > 0, an embedding of Y into L_{p−ϵ} with constant depending only on ϵ. Computing the exact dependence on ϵ in this result and optimizing the product of this constant with the distance between L_{p−ϵ}^{μd} and L_{p}^{μd}, one gets the same result.

Remarks 1. Let p, q, T and X be as in the statement of Theorem 2a. Applying the theorem with μ = 2 we get a good embedding of X into ℓ_{p}^{2d}. Call the image of this embedding Y. Perturbing Y a bit we may assume that the restriction P_{1} (resp. P_{2}) to the first (resp. last) d coordinates is an isomorphism on Y (i.e., these restrictions are of rank d when considered as operators on Y. We do not assume anything about the constant of isomorphism). Note that for x ∈ Y, ∥x∥ is well equivalent to max{∥P_{1}x∥_{p}, ∥P_{2}x∥_{p}}. Geometrically this means that the unit ball of Y (and thus of X) is well approximated by the intersection of two linear images of the ball of ℓ_{p}^{d}. More precisely, there are two invertible linear operators T_{1} and T_{2} such that

T_{1}(B_{ℓ_{1}^{d}}) ∩ T_{2}(B_{ℓ_{1}^{d}}) ⊂ B_{X} ⊂ K(T_{1}(B_{ℓ_{1}^{d}}) ∩ T_{2}(B_{ℓ_{1}^{d}}))  (1)

where K = K(p, q, T).

Recall that for q = 2, i.e., when X = ℓ_{2}^{d}, a somewhat stronger assertion (where the linear maps involved are multiples of orthogonal transformations) is a well known theorem of Kashin [K], the proof of which is similar to the proof of the the result of Kashin stated in the introduction.

Without the assumption on type, (1) holds with K replaced with K(p)(log(2d+2))^{1/p}.

2. We do not know if the statement Theorem 2 also holds for 0 < p < 1. The missing part is a variant of Theorem 1 to this range. The problem of extending the proof of this theorem for the range 0 < p < 1 is that the natural extension of Elton’s theorem for p-normed spaces is false; this follows easily from the fact observed in [Po] that L_{p,∞} is a p-normed space. We would like to thank Nigel Kalton for bringing this to our attention.

References

[BKT] 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, 1989.

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

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

[D] Dvoretzky, A., Some results on convex bodies and Banach spaces. 1961 Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960) pp. 123–160 Jerusalem Academic Press, Jerusalem; Pergamon, Oxford

[E] Elton, J., Sign-embeddings of l_{1}^{n}. Trans. Amer. Math. Soc. 279 (1983), no. 1, 113– 124.

[FLM] Figiel, T.; Lindenstrauss, J.; Milman, V. D., The dimension of almost spherical sections of convex bodies. Acta Math. 139 (1977), no. 1-2, 53–94.

[K] Kashin, B., Section of some finite-dimensional sets and classes of smooth functions. Izv. Acad. Nauk. SSSR 41 (1977), 334–351. (Russian).

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

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

[JS3] Johnson, W. B.; Schechtman, G., Finite dimensional subspaces of L_{p}. Handbook of the geometry of Banach spaces, Vol. I, 837–870, North-Holland, Amsterdam, 2001.

[Mi] Milman, V. D. A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies. (Russian) Funkcional. Anal. i Priložen. 5 (1971), no. 4, 28–37.

[Ma] Maurey, B., Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces L_{p}. (French) With an English summary. Asterisque, No. 11. Societe Mathematique de France, Paris, 1974.

[MV] Mendelson, S.; Vershynin, R., Entropy, dimension and the Elton–Pajor theorem. Preprint.

[NZ] Naor, A.; Zvavitch, A., Isomorphic embedding of l_{p}^{n}, 1 < p < 2, into l_{1}^{(1+ϵ)n}. Israel J. Math. 122 (2001), 371–380.

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

[Po] Popa, N., Uniqueness of the symmetric structure in L_{p}(μ) for 0 < p < 1. Rev. Roumaine Math. Pures Appl. 27 (1982), no. 10, 1061–1089.

[S] Schechtman, G., More on embedding subspaces of L_{p} into l_{r}^{n}. Comp. Math. 61 (1987), 159–170.

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

William B. Johnson Department Mathematics Texas A&M University College Station, TX, USA E-mail: johnson@math.tamu.edu

Gideon Schechtman Department of Mathematics Weizmann Institute of Science Rehovot, Israel E-mail: gideon@wisdom.weizmann.ac.il