.

A NOTE ON DICHOTOMIES FOR METRIC TRANSFORMS

MANOR MENDEL AND ASSAF NAOR

Abstract. We show that for every nondecreasing concave function ω : [0, ∞) → [0, ∞) with ω(0) = 0, either every finite metric space embeds with distortion arbitrarily close to 1 into a metric space of the form (X, ω∘d) for some metric d on X, or there exists α = α(ω) > 0 and n_{0} = n_{0}(ω) ∈ ℕ such that for all n ⩾ n_{0}, any embedding of {0, …, n} ⊆ ℝ into a metric space of the form (X, ω ∘ d) incurs distortion at least n^{α}.

1. Introduction

The distortion of a bi-Lipschitz embedding f : X → Y of metric spaces (X, d_{X}) and (Y, d_{Y}) is defined as

dist(f) =^{def} ( sup_{x≠y^{x,y∈X}} \frac{d_{Y} (f(x), f(y))}{d_{X}(x, y)}) · ( sup_{x≠y^{x,y∈X}} \frac{d_{X}(x, y)}{d_{Y} (f(x), f(y))}) = ∥f∥_{Lip} · ∥f^{−1}∥_{Lip}.

If (X, d_{X}) admits a bi-Lipschitz embedding into (Y, d_{Y}), then the least distortion of such an embedding is denoted

c_{Y} (X) =^{def} inf {dist(f) : f : X → Y } .

If F is a family of metric spaces then the distortion of (X, d_{X}) in F is defined as

c_{F}(X) =^{def} inf {c_{Y} (X) : Y ∈ F} .

Let ω : [0, ∞) → [0, ∞) be a nondecreasing concave function with ω(0) = 0. Then (X, ω ∘ d_{X}) is a metric space for any metric space (X, d_{X}), known as the ω-metric transform of (X, d_{X}). When ω(t) = t^{θ} for some θ ∈ (0, 1], the metric space (X, d_{X}^{θ}) is known as the θ-snowflake of (X, d_{X}). In what follows we denote the class of all finite metric spaces by MET, and the class of all ω-metric transforms by

ω(MET) =^{def} {(X, ω ∘ d_{X}) : (X, d_{X}) ∈ MET}.

Let P_{n} = {0, 1, …, n} ⊆ ℝ be the (n + 1)-point path, equipped with the metric inherited from the real line. The main purpose of this note is to prove the following dichotomy theorem for metric transforms:

Theorem 1. For every nondecreasing concave function ω : [0, ∞) → [0, ∞) with ω(0) = 0, one of the following two dichotomic possibilities must hold true:

• either for every X ∈ MET we have c_{ω(MET)}(X) = 1,

• or there exists α = α(ω) > 0 and n_{0} = n_{0}(ω) ∈ ℕ such that for all n ⩾ n_{0} we have

c_{ω(MET)}(P_{n}) ⩾ n^{α}.

M.M. was supported by ISF grant 221/07, BSF grant 2006009, and a gift from Cisco Research Center.

A.N. was supported by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

Theorem 1 is sharp due to the following fact:

Proposition 2. For every 0 < α < 1 there exists a nondecreasing and concave function ω : [0, ∞) → [0, ∞) with ω(0) = 0 such that c_{ω(MET)}(X) ⩽ (|X| − 1)^{α} for every finite metric space X, and c_{ω(MET)}(P_{n}) = n^{α} for every n ∈ ℕ.

The metric cotype dichotomy problem. Our motivation for proving Theorem 1 is one of the main questions left open in our investigation of metric cotype [14]. To explain it, we recall the following theorem^{1} from [14, Thm. 1.6]. Given two classes of metric spaces E, F and an integer n ∈ ℕ, denote

𝒟_{n}(E ↪ F) =^{def} sup_{\begin{matrix}X∈E \\ |X|⩽n \end{matrix}} c_{F}(X).

When E = MET we write

𝒟_{n}(F) =^{def} 𝒟_{n}(MET ↪ F) = sup_{\begin{matrix}X∈MET \\ |X|⩽n \end{matrix}} c_{F}(X).

Theorem 3 (Metric cotype dichotomy [14]). For any class of metric spaces F, one of the following two dichotomic possibilities must hold true:

• either 𝒟_{n}(F) = 1 for all n ∈ ℕ,

• or there exists α = α(F) > 0 and n_{0} = n_{0}(F) ∈ ℕ such that for all n ⩾ n_{0} we have

𝒟_{n}(F) ⩾ (log n)^{α}.

We call Theorem 3 a “metric cotype dichotomy” since the parameter α = α(F) is related in [14] to a numerical invariant of the class F called the metric cotype of F; we refer to [14] for more details since we will not use the notion of metric cotype here.

A consequence of Theorem 3 is that if we were told that 𝒟_{n}(F) = (log n)^{o(1)} then we would immediately deduce that actually 𝒟_{n}(F) = 1 for all n ∈ ℕ. The theory of metric dichotomies studies such dichotomic behavior (if it exists) of the rate of growth of {𝒟_{n}(E ↪ F)}_{n=1}^{∞}. For example, we have the following classical result of Bourgain, Milman and Wolfson [4], corresponding to the case when E consists of all Hamming hypercubes, and F consists of a single metric space.

Theorem 4 (Bourgain-Milman-Wolfson cube dichotomy [4]). For any metric space (X, d_{X}) one of the following two dichotomic possibilities must hold true:

• either for all n ∈ ℕ we have c_{X} ({0, 1}^{n}, ∥ · ∥_{1}) = 1,

• or there exists α = α(X) and c = c(X) > 0 such that for all n ∈ ℕ we have c_{X} ({0, 1}^{n}, ∥ · ∥_{1}) ⩾ cn^{α}.

For more information on the theory of metric dichotomies see [15, Sec. 1.1], the survey paper [12], and the references therein. The most fundamental open question in this area concerns the sharpness of the metric cotype dichotomy (Theorem 3), or even more generally, the possible rates of growth of {𝒟_{n}(F)}_{n=1}^{∞}. Bourgain’s embedding theorem [3] (combined with Dvoretzky’s theorem [5]) says that 𝒟_{n}(X) ≲ log n for every infinite dimensional Banach space X. Linial, London and Rabinovich [8] proved that 𝒟_{n}(L_{1}) ≍ log n. This was extended by Matoušek [11] to all L_{p} spaces p ∈ [1, ∞), by showing that 𝒟_{n}(L_{p}) ≍ 1 + \frac{1}{p} log n. The work of Ozawa [18] and Pisier [20, 21] shows that 𝒟_{n}(X) ≍_{X} log n for X in a class Banach spaces satisfying certain geometric conditions; this class includes all Banach lattices with finite Rademacher cotype. Lafforgue’s work [6] shows that 𝒟_{n}(X) ≍_{X} log n whenever X is a K-convex Banach space (see also [7, 16]). Additional results along these lines (when X is not necessarily a Banach space) follow from [17].

1This phenomenon was first conjectured to hold true by Arora, Lovász, Newman, Rabani, Rabinovich and Vempala in [1].

In light of Theorem 3 and the above quoted results, we recall the following natural open question from [14].

Question 5 (Metric cotype dichotomy problem). Does there exist a class of metrics spaces F for which lim_{n→∞} 𝒟_{n}(F) = ∞ yet 𝒟_{n}(F) = o(log n)? If so, for which α ∈ (0, 1) there exists a class of metric spaces F = F_{α} such that 𝒟_{n}(F) ≍_{F} (log n)^{α}? What happens if we insist in these questions that F consists of a single Banach space X?

Theorem 1 shows that a judicious choice of metric transform ω cannot show that ω(MET) solves the metric cotype dichotomy problem. Furthermore, Proposition 8 shows that for every θ ∈ (0, 1] we can have 𝒟_{n}(X) = n^{θ} for some metric space X. Previously it was shown by Matoušek [9] that when d is even integer, 𝒟_{n} (ℓ_{2}^{d}) behaves roughly like n^{2/d} (up to polylogarithmic multiplicative factors). It is unknown what are the possible rates of growth of sequences such as {𝒟_{n}(F)}_{n=1}^{∞}; the only currently known restriction, from Theorem 3, is that such sequences cannot be larger than 1 yet behave like (log n)^{o(1)}.

2. A dichotomy theorem for line metrics

The following simple result will be used in the proof of Theorem 1. It implies that either every metric space X contains arbitrarily large “almost geodesics”, or any embedding of the path P_{n} into X incurs very large distortion. Without quantitative estimates on the rate of growth of c_{X}(P_{n}), such a result has been previously proved by Matoušek in [10] via a metric differentiation argument.

Proposition 6. For any class of metric spaces F one of the following two dichotomic possibilities must hold true:

• for every L ⊆ ℝ we have c_{F}(L) = 1,

• or there exists α = α(F) > 0 and n_{0} = n_{0}(F) ∈ ℕ such that for all n ⩾ n_{0} we have

c_{F}(P_{n}) ⩾ n^{α}.

Proposition 6 is a simple consequence of the following lemma, taken from [15, Prop. 5.1]. The proof of this lemma in [15] is a “baby version” of the sub-multiplicativity method that is commonly used in Banach space theory; see Pisier’s characterization of trivial Rademacher type [19] as an early example of many such arguments. A thorough discussion of the submultiplicativity method in the context of metric dichotomies in contained in [12].

Lemma 7. Fix δ ∈ (0, 1), D ⩾ 2 and t, n ∈ ℕ satisfying n ⩾ D^{(4t log t)/δ}. If (X, d_{X}) is a metric space and f : P_{n} → X satisfies dist(f) ⩽ D, then there exists ϕ : P_{t} → P_{n} which is a rescaled isometry, i.e., dist(ϕ) = 1, such that dist(f ∘ ϕ) ⩽ 1 + δ.

Proof of Proposition 6. If the first assertion of Proposition 6 fails then there exists some δ ∈ (0, 1) and a finite L_{0} ⊆ ℝ such that c_{F}(L_{0}) > 1 + δ. Using dilation and rounding, there exists t ∈ ℕ for which c_{P_{t}}(L_{0}) ⩽ 1 + δ/3, and therefore c_{F}(P_{t}) > 1 + δ/2. Define D = n^{δ/(8t log t)} and assume that n is large enough so that D ⩾ 2. By Lemma 7 we obtain

c_{F}(P_{n}) ⩾ n^{δ/8t log t}.  □

Proposition 6 is sharp due to the following fact:

Proposition 8. For every θ ∈ (0, 1] there exists a metric space X such that for every finite subset of the real line L ⊆ ℝ we have c_{X}(L) ⩽ (|L| − 1)^{θ}, and c_{X}(P_{n}) = n^{θ} for all n ∈ ℕ.

Proof. Assume first that θ < 1. The metric space X will be the snowflaked real line (ℝ, |x − y|^{1−θ})

We first observe that any (n + 1)-point subset L ⊂ ℝ embeds in X with distortion n^{θ} distortion. Indeed, write L = {y_{0}, …, y_{n}} where y_{0} < y_{1} < … < y_{n}, and define z_{0} = 0 and for i ∈ {1, …, n},

z_{i} = ∑_{k=0}^{i−1}(y_{k+1} − y_{k})^{1/(1−θ)}.

If n ⩾ j > i ⩾ 0 then,

|z_{j} − z_{i}|^{1−θ} = (∑_{k=i}^{j−1}(y_{k+1} − y_{k})^{1/(1−θ)})^{1−θ} ∈ [y_{j} − y_{i}, \frac{y_{j} − y_{i}}{(j − i)^{θ}} ] .

thus the embedding of L into X which maps y_{i} to z_{i} has distortion at most n^{θ}.

The fact that c_{X}(P_{n}) ⩾ n^{θ} is simple. We briefly recall the standard computation. For a bijection f : P_{n} → X we have,

\frac{n}{∥f^{−1}∥_{Lip}} ⩽ |f(0)−f(n)|^{1−θ} ⩽ (∑_{i=0}^{n−1} |f(i + 1) − f(i)|)^{1−θ} ⩽ (n∥f∥_{Lip}^{1/(1−θ)})^{1−θ} = n^{1−θ}∥f∥_{Lip}.

Therefore dist(f) ⩾ n^{θ}.

For θ = 1 let 𝒰 be the class of all finite ultrametrics of diameter 1. Let X be the disjoint union of the elements of 𝒰 , equipped with the following metric: if x, y ∈ X then let U_{1}, U_{2} ∈ 𝒰 be finite ultrametics such that x ∈ U_{1} and y ∈ U_{2}. Define d_{X}(x, y) = 1 if U_{1} ≠ U_{2} and d_{X}(x, y) = d_{U}(x, y) if U_{1} = U_{2} = U. Then (X, d_{X}) is an ultrametric. It is a standard and easy fact (see for example [13, Lem. 2.4] that any embedding of P_{n} into an ultrametric incurs distortion at least n. Thus c_{X}(P_{n}) ⩾ n. Furthermore, it is well known (via a Cantor set-type construction; see for example [2, Lem. 3.6]) that any (n + 1)-point metric space embeds into some ultrametric U ∈ 𝒰 with distortion at most n. Since U is isometric to a subset of X, we have c_{X}(P_{n}) = n. □

3. Proof of Theorem 1

We will deduce Theorem 1 from Proposition 6 via the following lemma.

Lemma 9. Let ω : [0, ∞) → [0, ∞) be a nondecreasing concave function with ω(0) = 0. Then for every n ∈ ℕ we have

𝒟_{n^{2}} (2^{ℝ} ↪ ω(MET)) ⩾ 𝒟_{n} (ω(MET)) .  (1)

Here 2^{ℝ} denotes the class of metric spaces consisting of all nonempty subsets of the real line.

Proof. Fix an n-point metric space (X, d) and consider the subset L of the real line defined by L = {d(x, y)}_{x,y∈X}. Then |L| ⩽ n^{2}. Therefore, if D > 𝒟_{n^{2}} (2^{ℝ} ↪ ω(MET)) we know that there exists a metric ρ on L, and a scaling factor λ > 0, such that for every x, y, z, w ∈ X,

λ|d(x, y) − d(w, z)| ⩽ ω(ρ(d(x, y), d(w, z))) ⩽ Dλ|d(x, y) − d(w, z)|.

For every z ∈ X define a semi-metric ρ_{z} on X by ρ_{z}(x, y) = ρ(d(x, z), d(y, z)). Then δ = max_{z∈X} ρ_{z} is also a semi-metric on X. Using the monotonicity of ω (and the triangle inequality), for every x, y ∈ X we have

d(x, y) = max_{z∈X} |d(x, z) − d(y, z)| ⩽ \frac{1}{λ} max_{z∈X} ω(ρ(d(x, z), d(y, z)))

= \frac{1}{λ}ω (max_{z∈X} ρ(d(x, z), d(y, z))) = \frac{1}{λ}ω(δ(x, y)).

Similarly,

d(x, y) ⩾ \frac{1}{Dλ}ω(δ(x, y)).

Thus the identity mapping between (X, d) and (X, ω ∘δ) ∈ ω(MET) has distortion at most D. Since D was an arbitrary number bigger than 𝒟_{n^{2}} (2^{ℝ} ↪ ω(MET)), the proof is complete. □

Proof of Theorem 1. Failure of the first statement of Theorem 1 implies the existence of n_{0} ∈ ℕ such that 𝒟_{n_{0}}(ω(MET)) > 1. By Lemma 9 it follows that 𝒟_{n_{0}^{2}} (2^{ℝ} ↪ ω(MET)) > 1. Thus the first dichotomic possibility of Proposition 6 fails, forcing the conclusion that the second dichotomic possibility of Proposition 6 holds, as required. □

4. Snowflakes

The quadratic dependence on n in (1) can be removed when ω corresponds to a snowflake, leading to sharp bounds in this case. The appropriate variant of Lemma 9 is as follows.

Lemma 10. For every θ ∈ (0, 1) and every n ∈ ℕ we have,

𝒟_{n} (2^{ℝ} ↪ (MET)^{θ}) = 𝒟_{n} ((MET)^{θ}) .  (2)

Proof. We need to show that 𝒟_{n} (2^{ℝ} ↪ (MET)^{θ}) ⩾ 𝒟_{n} ((MET)^{θ}) (the reverse inequality is trivial). Fix an n-point metric space (X, d) and D > 𝒟_{n} (2^{ℝ} ↪ (MET)^{θ}). For every z ∈ X consider the subset of the real line given by L_{z} = {d(x, z)}_{x∈X}. Since |L_{z}| ⩽ n, there exists a metric ρ_{z} on L_{z} and a scaling factor λ_{z} > 0 such that for every x, y ∈ X we have

λ_{z}|d(x, z) − d(y, z)| ⩽ ρ_{z}(d(x, z), d(y, z))^{θ} ⩽ Dλ_{z}|d(x, z) − d(y, z)|.

Define a semi-metric δ on X by

δ(x, y) = max_{z∈X} \frac{ρ_{z}(d(x, z), d(y, z))}{λ_{z}^{1/θ}}.

Then for all x, y ∈ X,

d(x, y) = max_{z∈X} |d(x, z) − d(y, z)| ∈ [\frac{δ(x, y)^{θ}}{D} , δ(x, y)^{θ}] .

This means that (X, d) is bi-Lipschitz equivalent with distortion at most D to the θ-snowflake of (X, δ). □

We can now state and prove a concrete version of Proposition 2.

Corollary 11. For every θ ∈ (0, 1) and every n ∈ ℕ we have 𝒟_{n} ((MET)^{θ}) = (n − 1)^{1−θ}.

Proof. We have seen in the proof of Proposition 8 that any n-point subset of the real line embeds into the θ-snowflake of ℝ with distortion at most (n − 1)^{1−θ}, and that this bound is attained for P_{n}. Now apply Lemma 10. □

Remark 12. An inspection of the proof of Lemma 10 shows that if ω : [0, ∞) → [0, ∞) is increasing, concave, and ω(0) = 0, then the improvement (2) over (1) holds provided the class of metric spaces ω(MET) is closed under dilation, i.e., if d ∈ ω(MET) and λ > 0 then also λd ∈ ω(MET). Equivalently, ω^{−1}(λω(d)) is a metric for every λ > 0 and every metric d. This is the same as requiring that the function t ↦ ω^{−1}(λω(t)) is subadditive. We do not know the possible moduli ω satisfying this requirement, but we believe that it is quite stringent, and possibly it characterizes snowflakes. Here we note that if ω is smooth on (0, ∞) and lim_{t→∞} ω(t) = ∞ (in addition to being increasing, concave, and ω(0) = 0) and t ↦ ω^{−1}(λω(t)) is concave for all λ > 0, then there exist a > 0 and b ∈ (0, 1] such that ω(t) = at^{b} for all t ⩾ 0. To see this, denote f_{λ}(t) = ω^{−1}(λω(t)). Then f′_{λ}(t) = λω′(t)/ω′ (ω^{−1}(λω(t))), and therefore the concavity of f_{λ} is equivalent to the requirement

∀t > 0, 0 ⩾ \frac{f′′_{λ}(t)}{λ} = \frac{ω′′(t)ω′ (ω^{−1}(λω(t))) − \frac{λ[ω′(t)]^{2}ω′′(ω^{−1}(λω(t)))}{ω′(ω^{−1}(λω(t)))}}{[ω′ (ω^{−1}(λω(t)))]^{2}} .  (3)

Assuming the validity of (3), we know that for all λ, t > 0,

ω′′(t)ω′ (ω^{−1}(λω(t))) ⩽ \frac{λ[ω′(t)]^{2}ω′′ (ω^{−1}(λω(t)))}{ω′ (ω^{−1}(λω(t)))}.  (4)

Denoting s = ω^{−1}(λω(t)), we see that since w′ > 0, inequality (4) implies that for all s, t > 0 we have,

\frac{ω(s)ω′′(s)}{[ω′(s)]^{2}} ⩾ \frac{ω(t)ω′′(t)}{[ω′(t)]^{2}}.

Thus there exists c ∈ ℝ such that for all t > 0 we have ω(t)ω′′(t) = c[ω′(t)]^{2}. Equivalently, (log ω′)′ = c(log ω)′. Thus for some K ∈ ℝ we have log ω′ − c log ω = K, or ω′/ω^{c} = e^{K}. If c ≠ 1 then since ω(0) = 0, it follows that c < 1 and ω(t) = (1−c)^{1/(1−c)}e^{K/(1−c)}t^{1/(1−c)}. Since ω is concave, necessarily 1/(1 − c) ∈ (0, 1], as required. The case c = 1 is ruled out since the equation ω′/ω = e^{K} cannot be satisfied by a concave function. □

Remark 13. The shortest path metrics on certain (in some cases any) constant degree expander graphs have been the only tool used so far to rule out intermediate behavior in the metric cotype dichotomy problem, i.e., to exhibit that for certain classes of metric spaces F, the sequence {𝒟_{n}(F)}_{n=1}^{∞} cannot have asymptotic growth to infinity of (log n)^{α} (up to constant factors) for some α ∈ (0, 1). A simple consequence of Corollary 11 is that expanders are not always the “worst case” spaces for metric dichotomy problems. Indeed, if G = (V, E) is an n-vertex constant degree expander, then c_{(MET)^{θ}}(G) grows like (log n)^{1−θ} rather than the required n^{1−θ}. More generally (since constant degree expanders have logarithmic diameter), if G = (V, E) is an n-vertex unweighted graph and d_{G} is its shortest path metric, then c_{(MET)^{θ}}(V, d_{G}) = Δ^{1−θ}, where Δ is the diameter of G. This is true since (V, d_{G}) contains P_{Δ+1} isometrically, and therefore by Proposition 8 we have c_{(MET)^{θ}}(V, d_{G}) ⩾ Δ^{1−θ}. In the reverse direction, the identity mapping (V, d_{G}) ↦ (V, d_{G}^{θ}) has distortion at most Δ^{1−θ}.

References

[1] S. Arora, L. Lovász, I. Newman, Y. Rabani, Y. Rabinovich, and S. Vempala. Local versus global properties of metric spaces (extended abstract). In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41–50, New York, 2006. ACM.

[2] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric ramsey-type phenomena. Annals of Mathematics, 162(2):643–709, 2005.

[3] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[4] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295– 317, 1986.

[5] A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123–160. Jerusalem Academic Press, Jerusalem, 1961.

[6] V. Lafforgue. Un renforcement de la propriété (T). Duke Math. J., 143(3):559–602, 2008.

[7] V. Lafforgue. Propriété (T) renforcée banachique et transformation de Fourier rapide. J. Topol. Anal., 1(3):191–206, 2009.

[8] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[9] J. Matoušek. Bi-Lipschitz embeddings into low-dimensional euclidean spaces. Comment. Math. Univ. Carolinae, 31:589–600, 1990.

[10] J. Matoušek. Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces. Comment. Math. Univ. Carolin, 33(3):451–463, 1992.

[11] J. Matoušek. On embedding expanders into ℓ_{p} spaces. Israel J. Math., 102:189–197, 1997.

[12] M. Mendel. Metric dichotomies. In Limits of graphs in group theory and computer science, pages 59–76. EPFL Press, Lausanne, 2009.

[13] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

[14] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247–298, 2008.

[15] M. Mendel and A. Naor. Markov convexity and local rigidity of distorted metrics. Preprint available at

http://arxiv.org/abs/0803.1697, 2010.

[16] M. Mendel and A. Naor. Towards a calculus for non-linear spectral gaps. In SODA ’10: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.

[17] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Preprint available at

http://arxiv.org/abs/1005.4084, 2010.

[18] N. Ozawa. A note on non-amenability of ℬ(l_{p}) for p = 1, 2. Internat. J. Math., 15(6):557–565, 2004.

[19] G. Pisier. Sur les espaces de Banach qui ne contiennent pas uniformément de l_{n}^{1}. C. R. Acad. Sci. Paris Sér. A-B, 277:A991–A994, 1973.

[20] G. Pisier. Some applications of the complex interpolation method to Banach lattices. J. Analyse Math., 35:264–281, 1979.

[21] G. Pisier. Complex interpolation between Hilbert, Banach and operator spaces. Preprint available at

http://arxiv.org/abs/0802.0476, 2008.

Mathematics and Computer Science Department, The Open University of Israel

E-mail address: manorme@openu.ac.il

Courant Institute, New York University

E-mail address: naor@cims.nyu.edu