Isomorphic embedding of ℓ_{p}^{n}, 1 < p < 2, into ℓ_{1}^{(1+ε)n}

Assaf Naor  Artem Zvavitch^{∗}

November 1, 2001

Abstract

In this paper we partially answer a question posed by V. Milman and G. Schechtman by proving that ℓ_{p}^{n}, (C log n)^{^{\frac{1}{q}}(1+ \frac{1}{ε})}-embeds into ℓ_{1}^{(1+ε)n}, where 1 < p < 2 and 1/p + 1/q = 1.

1 Introduction

In 1982 W.B Johnson and G. Schechtman [J-S1], [J-S2] proved that if 1 ≤ p ≤ 2 then for any positive ϵ there exists a constant C = C(ϵ) such that ℓ_{p}^{n}, (1 + ϵ)-embeds into ℓ_{1}^{Cn} ( A generalization of this result was obtained by G. Pisier [P] in 1983). The same result for p = 2 has been proved in 1977 by T. Figiel, J. Lindenstrauss and V. Milman [F-L-M] who published a detailed investigation on Dvoretzky’s theorem. In the same year, B.S. Kashin [K] proved that for any 0 < θ < 1 the space ℓ_{1}^{n} has a subspace of dimension θn which is C(θ) close to Euclidean space. An investigation of all large dimensional subspaces of ℓ_{1}^{n} was continued by G. Schechtman, J. Bourgain, J. Lindenstrauss, V. Milman, S.J. Szarek, M. Talagrand and others.

These results, together with the recent proofs of the isomorphic version of Dvoretzky theorem ([M-S,2], [M-S,3]) led to the following question posed by V. Milman and G. Schechtman : Does there exist a universal constant C(ε) such that ℓ_{p}^{n} can be C(ε) embedded into ℓ_{1}^{(1+ε)n}. In other words, can we replace the constant C in the Johnson-Schechtman result by 1 + ε for any ε > 0, at the expense of changing the constant 2 to some other (possibly large) universal constant (which depends on ε). In this paper we prove the following weaker version: Theorem There is a universal constant C such that for every ϵ > 0 and every n there is a subspace Y of ℓ_{1}^{(1+ε)n} with d(ℓ_{p}^{n}, Y) < (C log n)^{^{\frac{1}{q}}(1+ \frac{1}{ε})}, where 1/p + 1/q = 1 and d(·, ·) denotes the Banach-Mazur distance.

∗supported by ISF.

All the proofs of the result [J-S1] use random embeddings T: ℓ_{p}^{m} → ℓ_{1}^{n}. The main point is to prove a concentration result which states that if ||b||_{p} = 1 then P (|||T (b)||_{1} − 1| > a) is exponentially small with respect to n. Such a result yields, by standard arguments, that if n/m is large enough then with high probability T would be a \frac{1+a}{1−a}-embedding. If, however, we want n/m to be arbitrarily close to 1, we are forced to choose a large a. When a > 1, the estimate on P (1 − ||T (b)||_{1} > a) is clearly meaningless, and we don’t get any lower bound for ||T (b)||_{1}.

In our proof we present a different approach. We still have a random embedding T ( which is quite different from the embeddings used before), and we prove directly an estimate for P (||T (b)||_{1} < t||b||_{p}) - not via a concentration inequality. Unfortunately, we do not get a bound on P (||T (b)||_{1} > a||b||_{p}) which is exponential in n. We are therefore forced to use more complicated estimates than in the usual “net” argument, and this is the reason why the factor log n appears in the statement of the theorem.

2 The main lemmas

We will break the proof of the theorem into a few simple lemmas. The first lemma is an elementary probabilistic result.

Lemma 1 Let X_{1}, …, X_{n} be independent positive random variables with densities bounded by C. Then for every t > 0

P ( ∑_{k=1}^{n} X_{k} < t) ≤ \frac{(Ct)^{n}}{n!} .

Proof: Let ϕ_{k} be the density of X_{k}. Then :

ϕ_{∑_{k=1}^{n} X_{k}}(s) = (ϕ_{1} ∗ … ∗ ϕ_{n})(s) =

∫_{0}^{s} ∫_{0}^{s−u_{1}}… ∫_{0}^{s−u_{1}−...−u_{n−2}}ϕ_{1}(u_{1}) … ϕ_{n−1}(u_{n−1})ϕ_{n}(s−u_{1}−…−u_{n−1})du_{n−1} … du_{1}

≤ ∫_{0}^{s} ∫_{0}^{s−u_{1}} … ∫_{0}^{s−u_{1}−...−u_{n−2}} C^{n}du_{n−1} … du_{1} = \frac{C^{n}s^{n−1}}{(n − 1)!}.

Hence :

P ( ∑_{k=1}^{n} X_{k} < t) = ∫_{0}^{t} ϕ_{∑_{k=1}^{n} X_{k}}(s)ds ≤ ∫_{0}^{t} \frac{C^{n}s^{n−1}}{(n − 1)!}ds = \frac{(Ct)^{n}}{n!} .

Fix 1 < p < 2 and let g be a normalized symmetric p-stable random variable. We will fix also m < n and attempt to embed ℓ_{p}^{m} into ℓ_{1}^{n}.

Define a symmetric random variable X by :

P (X < t) = \{ \begin{matrix}0  if & t < −n^{1/p} \\ \frac{P (−n^{1/p}≤g≤t)}{P (|g|≤n^{1/p})} if & |t| ≤ n^{1/p} \\ 1  if & t > n^{1/p} \end{matrix}

Lemma 2 There exists a constant C = C_{p} such that for every (b_{1}, …, b_{m}) in the unit sphere of ℓ_{p}^{m} the density of |∑_{k=1}^{m} b_{k}X_{k}| is bounded pointwise by Cϕ_{|g|}, where X_{1}, …, X_{m} are i.i.d copies of X.

Proof: Put Y = ∑_{k=1}^{m} b_{k}X_{k}. Since ϕ_{|Y |} ≤ 2ϕ_{Y} it is enough to prove that Y has a bounded density. Notice that the density of X satisfies :

ϕ_{X} ≤ \frac{ϕ_{g}}{P (|g| ≤ n^{1/p})} ≤ \frac{ϕ_{g}}{1 − \frac{C}{n}} .

For some universal constant C = C_{p}. The last inequality follows from known estimates of the tail distribution of a p-stable (see [D]).

Hence :

ϕ_{Y} ≤ (\frac{ϕ_{X} (\frac{·}{|b_{1}|})}{|b_{1}|}) ∗ … ∗ (\frac{ϕ_{X} (\frac{·}{|b_{m}|})}{|b_{m}|}) ≤

≤ \frac{1}{(1 − \frac{C}{n} )^{m}} (\frac{ϕ_{g} (\frac{·}{|b_{1}|})}{|b_{1}|}) ∗ … ∗ (\frac{ϕ_{g} (\frac{·}{|b_{m}|})}{|b_{m}|}) ≤

≤ e^{2C}ϕ_{∑_{k=1}^{m} b_{k}g_{k}} = e^{2C}ϕ_{g}.

Where g_{1}, …, g_{m} are i.i.d. copies of g and the last inequality follows from the fact that ∑_{k=1}^{m} b_{k}g_{k} has the same distribution as g.

We will now define the random variables which will be the object of our study:

Z_{b} = \frac{1}{n} ∑_{i=1}^{n} |∑_{j=1}^{m} b_{j}X_{ij}| .

Where b = (b_{1}, …, b_{m}) ∈ ℓ_{p}^{m} and {X_{ij}}_{i=1,j=1}^{n,m} are i.i.d. copies of X.

Corollary 1 There is a universal constant C = C_{p} such that for every t > 0 and b ∈ ℓ_{p}^{m} :

P (Z_{b} < t) < (\frac{Ct}{||b||_{p}} )^{n} .

Proof: We can clearly assume that ||b||_{p} = 1. By inverting the Fourier transform of ϕ_{g} we see that ϕ_{g} ≤ C pointwise, for some universal constant C. Lemma 1 then implies that

P (Z_{b} < t) < \frac{(Cnt)^{n}}{n!} ≤ \frac{(Cnt)^{n}}{\sqrt{2πn}n^{n}e^{−n}} ≤ (C′t)^{n}.

We now pass to estimating P (Z_{b} ≥ a).

Lemma 3 For every t > 0 :

𝔼e^{tX} ≤ 1 + \frac{1}{n} (cosh(Cn^{1/p}t) − 1) ,

where C = C_{p} depends only on p.

Proof: Using the known tail estimates of a p-stable we get that for every k ≥ 1:

𝔼X^{2k} = ∫_{0}^{∞} 2kt^{2k−1}P (|X| > t)dt = ∫_{0}^{n^{1/p}} 2kt^{2k−1} \frac{P (|g| > t)}{P (|g| ≤ n^{1/p})}dt ≤

∫_{0}^{n^{1/p}} 2kt^{2k−1} \frac{1}{(1 − \frac{C}{n} )} \frac{C}{t^{p}} dt ≤ C′ \frac{n^{2k/p}}{n} .

Hence, since X is symmetric,

𝔼e^{tX} = ∑_{k=0}^{∞} \frac{t^{2k}}{(2k)!}𝔼X^{2k} ≤ 1 + \frac{1}{n} ∑_{k=1}^{∞} \frac{(Ctn^{1/p})^{2k}}{(2k)!} = 1 + \frac{1}{n} (cosh(Cn^{1/p}t) − 1) .

Lemma 4 Set Y_{i} = ∑_{j=1}^{m} b_{j}X_{ij}, where ||b||_{p} = 1, then for t > 0

𝔼e^{t|Y_{i}|} ≤ 1 + Ct + 2 (exp (\frac{||b||_{1}}{n||b||_{∞}} (cosh(Cn^{1/p}||b||_{∞}t) − 1)) − 1) ,

where C = C_{p} depends only on p.

Proof: By lemma 2 ϕ_{|Y_{i}|} ≤ Cϕ_{|g|}, which implies that 𝔼|Y_{i}| ≤ C. Using the elementary inequality

e^{a} ≤ 1 + a + 2(cosh a − 1)

we get that

𝔼e^{t|Y_{i}|} ≤ 1 + Ct + 2(𝔼e^{tY_{i}} − 1) = 1 + Ct + 2 (∏_{j=1}^{m} 𝔼e^{t|b_{j}|X} − 1) ≤

≤ 1 + Ct + 2 (∏_{j=1}^{m} (1 + \frac{1}{n} (cosh(Cn^{1/p}|b_{j}|t) − 1)) − 1) .

Now, by convexity, for every j:

cosh(Cn^{1/p}|b_{j}|t) − 1 ≤ \frac{|b_{j}|}{||b||_{∞}} (cosh(Cn^{1/p}||b||_{∞}t) − 1)

Hence

∏_{j=1}^{m} (1 + \frac{1}{n} (cosh(Cn^{1/p}|b_{j}|t) − 1)) ≤ exp (\frac{1}{n} ∑_{j=1}^{m}(cosh(Cn^{1/p}|b_{j}|t) − 1))

≤ exp (\frac{||b||_{1}}{n||b||_{∞}} (cosh(Cn^{1/p}||b||_{∞}t) − 1))

Lemma 5 There is a universal constant C such that for all a > C and ||b||_{p} = 1

P (Z_{b} > a) ≤ e^{−Ca \frac{n^{1/q}}{||b||∞}} .

Proof: For every t > 0 we have

P (Z_{b} > a) = P (e^{tZ_{b}−ta} > 1) ≤ e^{−ta}𝔼e^{tZ_{b}} = e^{−ta} (𝔼e^{tY_{1}/n})^{n}

≤ e^{−ta} [1 + C \frac{t}{n} + 2 (exp (\frac{||b||_{1}}{n||b||_{∞}} (cosh(Cn^{1/p}||b||_{∞} \frac{t}{n}) − 1)) − 1)]^{n}

≤ e^{−ta} exp [Ct + 2n (exp (\frac{||b||_{1}}{n||b||_{∞}} exp(C \frac{||b||_{∞}t}{n^{1/q}})) − 1)] .

Take t = \frac{n^{1/q}}{C||b||_{∞}}. Notice that then

\frac{||b||_{1}}{n||b||_{∞}} exp(C \frac{||b||_{∞}t}{n^{1/q}}) = \frac{e||b||_{1}}{n||b||_{∞}} ≤ e.

Since for all 0 ≤ x ≤ e, e^{x} − 1 ≤ 6x we get that

P (Z_{b} > a) ≤ exp [−ta + Ct + 12\frac{||b||_{1}}{||b||_{∞}} exp(C \frac{||b||_{∞}t}{n^{1/q}})]

= exp [−(a − C)\frac{n^{1/q}}{C||b||_{∞}} + \frac{12e||b||_{1}}{||b||_{∞}} ]

≤ exp [−(a − C)\frac{n^{1/q}}{C||b||_{∞}} + \frac{36n^{1/q}}{||b||_{∞}} ] ≤ e^{−Ca \frac{n^{1/q}}{||b||∞}} ,

for a big enough.

We will now prove a standard geometric result, the proof of which we include for the sake of completeness. Define a special set of points on the unit sphere of ℓ_{p}^{m}:

F = \{\frac{ϵ1_{A}}{|A|^{1/p}} ; A ⊆ \{1, …, m\}, A ≠ ∅ and ϵ ∈ \{−1, 1\}^{m}\} ,

where the multiplication ϵ1_{A} is pointwise. Lemma 6 There is a constant C = C_{p} such that for all m

conv(F) ⊇ \frac{C}{(log m)^{1/q}} B(ℓ_{p}^{m}).

Proof: Fix b ∈ S(ℓ_{p}^{m}) and assume that b_{1} ≥ b_{2} ≥ … ≥ b_{m} ≥ 0. Define

α(b) = ∑_{k=1}^{m} [k^{1/p} − (k − 1)^{1/p}] b_{k}

and put λ_{m} = \frac{b_{m}}{α(b)}m^{1/p} and λ_{k} = \frac{b_{k}−b_{k+1}}{α(b)} k^{1/p}, for 1 ≤ k < m.

Clearly λ_{k} ≥ 0, ∑_{k=1}^{m} λ_{k} = 1 and

b = α(b) ∑_{k=1}^{m} \frac{λ_{k}}{k^{1/p}} ∑_{i=1}^{k} e_{i}.

Holder’s inequality gives :

α(b) ≤ (∑_{k=1}^{m} [k^{1/p} − (k − 1)^{1/p}]^{q})^{1/q} (∑_{k=1}^{m} |b_{k}|^{p})^{1/p}

≤ (1 + ∑_{k=2}^{m} (\frac{1}{p(k − 1)^{1/q}} )^{q})^{1/q} = (1 + \frac{1}{p^{q}} ∑_{r=1}^{m−1} \frac{1}{r})^{1/q} ≤ C_{p}(log m)^{1/q}.

We proved that if b_{1} ≥ b_{2} ≥ … ≥ b_{m} ≥ 0 there exist α(b) > 0 and v ∈conv(F) such that b = α(b)v and α(b) ≤ C(log m)^{1/q}. Since F is invariant under permutations and changes of sign, this shows that

B(ℓ_{p}^{m}) ⊆ c(log m)^{1/q}conv(F).

3 Proof of the theorem

We will first estimate:

P (∃v ∈ F, Z_{v} > a) ≤ ∑_{v∈F} P (Z_{v} > a) ≤ ∑_{v∈F} e^{− \frac{Can^{1/q}}{||v||∞}}

= ∑_{k=1}^{m} \binom{m}{k}2^{k}e^{−Can^{1/q}k^{1/p}} ≤ ∑_{k=1}^{m} \binom{m}{k}2^{k}e^{−Cam^{1/q}k^{1/p}}

≤ ∑_{k=1}^{m} \binom{m}{k}e^{−C′am^{1/q}k^{1/p}},

for a big enough.

If k ≥ m/2 then

\binom{m}{k}e^{−C′am^{1/q}k^{1/p}} ≤ \binom{m}{[m/2]}e^{−C′am^{1/q}(m/2)^{1/p}} ≤ 4^{−m}e^{−C′am} ≤ e^{−C′′am},

for a big enough.

When k < m/2 put x = \frac{k}{m}. Stirling’s formula gives that

\binom{m}{xm} ≤ 2 (x^{x}(1 − x)^{(1−x)})^{−m} .

Hence

\binom{m}{k}e^{−C′am^{1/q}k^{1/p}} ≤ 2e^{−m(x log x+(1−x) log x+Cax^{1/p})}.

Let f(x) = x log x + (1 − x) log(1 − x) + Cax^{1/p}. Using the elementary inequality x^{1/q} log(1/x) ≤ q/e we get that :

x^{1/q}f′(x) = −x^{1/q} log (\frac{1}{x} − 1) + \frac{Ca}{p} ≥ −x^{1/q} log (\frac{1}{x}) + \frac{Ca}{p} ≥ −\frac{q}{e} + \frac{ca}{p}.

This shows that when a is big enough, f(x) is increasing, hence

\binom{m}{k}e^{−C′am^{1/q}k^{1/p}} ≤ 2e^{−m( \frac{1}{m} log \frac{1}{m} +(1− \frac{1}{m}) log(1− \frac{1}{m})+Ca \frac{1}{(m)^{1/p}})}

≤ 2e^{log m+(m−1) log(1+ \frac{1}{m−1})−Ca(m)^{1/q}} ≤ e^{−C′am^{1/q}}.

Which gives

P (∃v ∈ F, Z_{v} > a) ≤ me^{−Cam^{1/q}}.

Let N be a δ-net in S(ℓ_{p}^{m}). Then |N | ≤ (\frac{3}{δ})^{m}. We get that for every t > 0

P (∃b ∈ N , Z_{b} < t) ≤ (\frac{3}{δ})^{m} (Ct)^{n} < \frac{1}{2},

for δ = Ct^{n/m}, where C is some fixed universal constant. This shows that for a big enough, with positive probability there is an ω in our probability space such that for all v ∈ F, Z_{v}(ω) ≤ a and for all b ∈ N, Z_{b}(ω) ≥ t. Fix such an ω and define T: ℓ_{p}^{m} → ℓ_{1}^{n} by :

T (b) = \frac{1}{n} ∑_{i=1}^{n} (∑_{j=1}^{m} b_{j}X_{ij}(ω)) e_{i}.

Then ||T (b)||_{1} = Z_{b}(ω) and the above remarks show that :

sup \{||T (b)||_{1}; b ∈ \frac{C}{(log(m))^{1/q}} B(ℓ_{p}^{m})\} ≤ sup \{||T (b)||_{1}; b ∈ conv(F)\} ≤ a.

In other words, ||T || ≤ Ca(log m)^{1/q}. Now, for any x ∈ S(ℓ_{p}^{m}) we can find some b ∈ N with ||x − b||_{p} ≤ δ = Ct^{n/m}. Hence :

||T (x)||_{1} ≥ ||T (b)||_{1} − ||T ||δ = Z_{b}(ω) − ||T ||δ ≥ t − Ca(log m)^{1/q}t^{n/m}.

Optimizing over t choose t = (Ca log m)^{− \frac{1}{q}(\frac{1}{n/m−1})}. We deduce that :

||T^{−1}|| ≤ (K log m)^{\frac{1}{q} \frac{1}{n/m−1}} ,

for some universal constant K, and this is the required result.

4 Remarks

In this section we would like to explain some of the inherent difficulties in our approach. Assume that for every b ∈ ℓ_{p}^{m} we have a random variable of the form :

Z′_{b} = \frac{1}{n} ∑_{i=1}^{n} |∑_{j=1}^{m} b_{j}X′_{ij}| ,

where {X′_{ij}}_{i=1,j=1}^{n,m} are i.i.d. copies of some symmetric random variable X′. If we somehow (for instance via lemma 1) get an estimate of the form P (Z′_{b} < t) < (Ct)^{n} for ||b||_{p} = 1 it follows that :

𝔼 |∑_{j=1}^{m} b_{j}X′_{1j}| = 𝔼Z′_{b} ≥ \frac{C}{2} P (Z′_{b} ≥ \frac{C}{2} ) ≥ \frac{C}{2} (1 − \frac{1}{2^{n}} ) ≥ C′.

Now,

C ≤ 𝔼 |∑_{j=1}^{m} b_{j}X′_{1j}| ≤ (𝔼 |∑_{j=1}^{m} b_{j}X′_{1j}|^{2})^{1/2} = ||b||_{2}(𝔼|X′|^{2})^{1/2}.

Since this is true for all ||b||_{p} = 1, it follows that 𝔼|X′|^{2} ≥ Cn^{2/p−1}. Hence, for all k, 𝔼|X′|^{k} ≥ C^{k}n^{k/p−k/2}. Now, by symmetry :

𝔼e^{t|∑_{j=1}^{m} b_{j}X′_{1j}|} ≥ 𝔼e^{t ∑_{j=1}^{m} |b_{j}|X′_{1j}} = ∏_{j=1}^{m} 𝔼e^{t|b_{j}|X′}

≥ ∏_{j=1}^{m} cosh (Cn^{1/p−1/2}|b_{j}|t) .

If for instance b = (1, 0, …, 0) then we deduce that : 𝔼e^{tZ′_{b}} ≥ e^{Cn^{1/p−1/2}t}, so that the tails of Z′_{b} cannot be exponential in n and a, and the usual “net” argument isn’t applicable. This is the reason why we are forced to introduce concrete nets such as the family F. Moreover, for our specific Z_{b}, it is possible to show that if b = (1, 0, …, 0) then the estimate in lemma 5 is best possible, up to a log n factor in the exponent.

References

[D] R. Durrett Probability theory and examples, Duxbury Press, (1996).

[J-S1] W. B. Johnson and G. Schechtman, Embedding ℓ_{p}^{m} into ℓ_{1}^{n}, Acta Math., 149 (1982), 71-85.

[F-L-M] T. Figiel, J. Lindenstrauss and V. Milman, The dimension of almost spherical sections of convex bodies, Acta Math., 129 (1977), 53-94.

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

[K] B.S. Kashin, Sections of some finite-dimensional sets and classes of smooth functions (in Russian), Izv. Akad. Nauk. SSSR Ser. Mat. 41, 334-351.

[M-S,1] V. D. Milman and G. Schechtman, Asymptotic theory of finite dimensional normed spaces, Lect. Notes in Math. 1200 (1986), Springer-Verlag, Berlin.

[M-S,2] V. D. Milman and G. Schechtman, An “isomorphic” version of Dvoretzky’s theorem, C.R. Acad. Sci. Paris Ser. I 321 (1995), 541-544.

[M-S,3] V. D. Milman and G Schechtman, An “isomorphic” version of Dvoretzky’s theorem, II, Convex geometric analysis (Berkeley, CA, 1996), 159-164, Math. Sci. Res. Inst. Publ., 34, Cambridge Univ. Press, Cambridge, 1999. 46Bxx (52A21) 34.

[P] G. Pisier, On the dimension of the ℓ_{p}^{n} subspaces of Banach spaces, for 1 ≤ p < 2, Trans. Amer. Math. Soc. 276, 201-211.