Diamond graphs and super-reflexivity ^{∗}

William B. Johnson^{†}and Gideon Schechtman^{‡}

Abstract

The main result is that a Banach space X is not super-reflexive if and only if the diamond graphs D_{n} Lipschitz embed into X with distortions independent of n. One of the consequences of that and previously known results is that dimension reduction a-la Johnson–Lindenstrauss fails in any non super reflexive space with non trivial type.

We also introduce the concept of Lipschitz (p, r)-summing map and prove that every Lipschitz mapping is Lipschitz (p, r)-summing for every 1 ≤ r < p.

1 Introduction

In [BC] Brinkman and Charikar proved that the diamond graphs D_{n}, which were known ([GNRS]) to Lipschitz embed into ℓ_{1} with distortion independent of n, can be used to give a lower bound on dimension reduction in ℓ_{1}; precisely, for each n there are subsets A_{n} of ℓ_{1} of cardinality \overline{A_{n}} = n so that if α > 0 and f_{n} : A_{n} → ℓ_{1}^{⌈n^{α}⌉}, then Lip(f_{n})Lip(f_{n}^{−1}) ≥ cα^{−1} for some universal c > 0. Lee and Naor [LN] substantially simplified the proof of this fact. In Corollary 2 we give an even simpler proof, modelled on the proof of [LN] but substituting an easy inductive argument for the magical telescoping series inequality there.

Recall that a Banach space X is super reflexive iff whenever a Banach space Y is finitely represented in X (which means that for every ε > 0, every finite dimensional subspace E of Y linearly embeds into X with distortion less than 1 + ε), then Y is reflexive. Enflo [E] (see also [P]) proved that X is super reflexive iff X has an equivalent uniformly convex norm.

Our main focus in this paper is to show (in Theorem 1) that the diamond graphs give a metric characterization of super reflexivity; that is, a Banach space X is not super reflexive if and only if the diamond graphs D_{n} Lipschitz embed into X with distortion independent of n. The proof is, in our opinion, simpler than Bourgain’s proof [BOU2] that a Banach space X is not super reflexive if and only if the diadic trees T_{n} Lipschitz embed into X with distortion independent of n. As far as we see neither of these non linear characterizations of super reflexivity directly implies the other.

∗AMS subject classification: Primary: 52C99, Secondary: 46B10. Key words: Diamond graph, super reflexivity, (p, q) summing operator, dimension reduction.

†Supported in part by NSF DMS-0503688 and U.S.-Israel Binational Science Foundation.

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

As a by-product we get that dimension reduction as in Hilbert space (embedding any n points into a O(log n)-dimensional Euclidean space, [JL]) is not possible in any non super reflexive space with non trivial type.

In [FJ] an appropriate definition of Lipschitz p-summing map was introduced and there it was shown that the (linear) p-summing norm of a linear operator is the same as its Lipschitz p-summing norm. In section 5 we give an analogous definition of Lipschitz (p, r)-summing map (so that, e.g., the Lipschitz (p, p)-summing norm of a Lipschitz map is the same as its Lipschitz p-summing norm). However, it turns out that the (linear) (p, r)-summing norm of a linear operator can be much larger than its Lipschitz (p, r)- summing norm. In fact, the Lipschitz (p, r)-summing norm of any Lipschitz map is finite for every 1 ≤ r < p! An equivalent formulation of this is that every metric space satisfies a family of inequalities which look to us non trivial. This will be explained in detail in Section 5. As we shall also explain there we were led to this family of inequalities by an interpretation of Theorem 1 coming from the linear theory of Banach spaces.

In Section 6 we indicate the validity of the analog statement to Theorem 1 applied to the sequence of Laakso graphs. This is a family of graphs very similar to the diamond graphs but with the additional property that they are uniformly doubling.

2 Preliminaries

We begin by describing the inductive construction of the diamond graph D_{n} whose vertex set will be a subset of {0, 1}^{2^{n}} and the edge set will be a subset of the edge set of the Hamming cube {0, 1}^{2^{n}}. The exposition follows closely that in [BC] but there will be an important change in the way we index the vertices of the graph. D_{0} is the graph with two vertices, labelled 0 and 1 and one edge connecting them. Giving D_{i−1} whose vertex set is a subset of {0, 1}^{2^{i−1}} we replace each vertex (a_{1}, a_{2}, …, a_{2^{i−1}}) with (a_{1}, a_{1}, a_{2}, a_{2}, …, a_{2^{i−1}}, a_{2^{i−1}}) ∈ {0, 1}^{2^{i}} (this is where the indexing differs from that in [BC]; there the replacement would be (a_{1}, a_{2}, …, a_{2^{i−1}}, a_{1}, a_{2}, …, a_{2^{i−1}})). For each two new vertices whose Hamming distance is 2 (i.e, coming from an edge in D_{i−1}) we also add the two points in {0, 1}^{2^{i}} which are of Hamming distance 1 from each of these two vertices. If x′ = (x_{1}, …, x_{2^{i}}) is a vertex of D_{i} we say that x = (x_{1}, …, x_{1}, x_{2}, …, x_{2}, …, x_{2^{i}}, …, x_{2^{i}}) ∈ D_{n}, where each x_{j} repeats 2^{n−i} times, is the vertex developed from x′ by n − i doubling operations. If (x_{1}, …, x_{2^{i}}) is one of the new vertices of D_{i} (as opposed to one coming from doubling a vertex of D_{i−1}) we say that x = (x_{1}, …, x_{1}, x_{2}, …, x_{2}, …, x_{2^{i}}, …, x_{2^{i}}) ∈ D_{n} (the vertex developed from x′ by n − i doubling operations) is a vertex of level i.

Suppose that x′ and y′ are two vertices of D_{i} connected by an edge and x, y are the two vertices of D_{n} developed from them by n − i doubling operations, then (unless i = 0) exactly one of x or y is a vertex of level i. x and y differ exactly in one interval, (j − 1)2^{n−i}, j2^{n−i}, where one of them has all 1-s and the other all 0-s (these facts are easy to prove by induction). The set of vertices of D_{n} lying pointwise between x and y will be called a sub-diamond of level i. The one of x and y that has all ones on the said interval,i.e., x ∨ y, will be called the top vertex of this sub-diamond and the other the bottom vertex. The vertex which has ones in the left half of the said interval and zeros in the right half will be called the leftmost vertex of this sub-diamond and the vertex which has ones in the right half of the said interval and zeros in the left half will be called the rightmost vertex of this sub-diamond. The vertices of the sub-diamond whose distance to the bottom vertex is at most their distance to the top one will said to lie below the diagonal and the rest above the diagonal. The vertices of the sub-diamond whose distance to the leftmost vertex is at most their distance to the right most one will said to be on the left of the sub-diamond and the rest on the right.

Note that D_{n} has 4^{n} edges and 2 + 2 ∑_{i=0}^{n−1} 4^{i} = 2 + 2\frac{4^{n}−1}{3} vertices.

It is easy to prove, by induction, that, given two vertices of D_{n}, either both lie on a path connecting the top and bottom vertices of D_{n}, or one is on the left side and one is on the right side of some sub-diamond (possibly D_{n} itself).

3 Embedding the diamonds in non super reflexive spaces

Proposition 1 Let x_{1}, x_{2}, …, x_{2^{n}} be a sequence of norm one points in a Banach space X with the properties:

(i) ∥ ∑_{i∈A} x_{i}∥ ≥ a|A|, for any subset A ⊂ {1, 2, …, 2^{n}}

(ii) ∥ ∑_{i∈A} a_{i}x_{i}∥ ≤ b∥ ∑_{i=1}^{2^{n}} a_{i}x_{i}∥, for any interval A ⊂ {1, 2, …, 2^{n}} and any real coefficients a_{1}, …, a_{2^{n}}.

Define f : D_{n} → X by f(a_{1}, …, a_{2^{n}}) = ∑_{i=1}^{2^{n}} a_{i}x_{i}. Then f has distortion at most 4a^{−1}b.

Proof: If u and v lie on a path between the (images of the) original two vertices, (0, 0, …, 0) and (1, 1, …, 1) (such a path is a monotone sequence in {0, 1}^{2^{n}}) then f(u)− f(v) = ± ∑_{i∈A} x_{i} where |A| = d_{D_{n}}(u, v). By (i), ad_{D_{n}}(u, v) ≤ ∥f(u)−f(v)∥ ≤ d_{D_{n}}(u, v).

If u and v do not lie on such a path then there is some sub-diamond, say of level n−k, such that u is on the left side of it and v on the right (or vice versa). Denote the bottom and top vertices of this sub-diamond by v_{B} and v_{T}. This means that for some subinterval A ⊂ {1, 2, …, 2^{n}} of size 2^{k}, v_{T} restricted to A is the all 1-s vector, v_{B} restricted to A is the all 0-s vector, and v_{T} and v_{B} are identical on the complement of A. If u = (u_{1}, …, u_{2^{n}}) and v = (v_{1}, …, v_{2^{n}}) lie on the same side of the diagonal of this sub-diamond then their distance in D_{n} is min{d_{D_{n}}(u, v_{B}) + d_{D_{n}}(v_{B}, v), d_{D_{n}}(u, v_{T}) + d_{D_{n}}(v_{T} , v)}. Let us assume that they both lie on or below the diagonal (the treatment of the other case is similar). Write A = B ∪ C where B (resp. C) is the left (resp. right) half of A. Then u restricted to C is the all zero vector and v restricted to B is the all zero vector. u and v are equal (and equal to v_{T} and v_{B}) on the complement of A. Consequently, since the x_{i}-s are all norm one,

∥f(u) − f(v)∥ = ∥ ∑_{i∈B} u_{i}x_{i} − ∑_{i∈C} v_{i}x_{i}∥ ≤ ∥ ∑_{i∈B} u_{i}x_{i}∥ + ∥ ∑_{i∈C} v_{i}x_{i}∥
≤ d_{D_{n}}(u, v_{B}) + d_{D_{n}}(v_{B}, v).

On the other hand, by (ii) then (i),

∥f(u) − f(v)∥ ≥ b^{−1} max{∥ ∑_{i∈B} u_{i}x_{i}∥, ∥ ∑_{i∈C} v_{i}x_{i}∥} = ab^{−1} max{d_{D_{n}}(u, v_{B}), d_{D_{n}}(v_{B}, v)}
≥ \frac{a}{2b}(d_{D_{n}}(u, v_{B}) + d_{D_{n}}(v_{B}, v)).

If u and v are not on the same side of the diagonal of the sub-diamond determined by v_{T} and v_{B}, let us assume for example that u is above the diagonal (and on the left) and v below the diagonal (and on the right). In this case it is easy to see that the distance between u and v in D_{n} is between 2^{k−1} and 2^{k}. Also u restricted to B is the all 1-s vector (while v restricted to B is zero), so

2^{k} ≥ ∥f(u) − f(v)∥ = ∥ ∑_{i∈B} u_{i}x_{i} − ∑_{i∈C} v_{i}x_{i}∥ ≥ b^{−1}∥ ∑_{i∈B} x_{i}∥
≥ ab^{−1}2^{k−1}.

Remark 1 Note that we have only used assumption (ii) for ±1, 0 coefficients.

One of the characterization of super-reflexivity says that any non super reflexive Banach space contains for every a < 1 and b > 4 and any n a sequence as in Proposition 1. By the definition of super-reflexivity, it is enough to have this statement for any nonreflexive space. It is not easy to trace the origin of this statement. It explicitly appear in [Ja1, Theorem 8] and partially attributed there to Pełczyński. Vitali Milman told us that Ptak and Pełczyński are probably the origin and Milman and Milman also proved the same a bit earlier than James’ paper.

Corollary 1 For each λ > 1, each n ∈ ℕ and each non-super-reflexive space X, D_{n} Lipschitz embeds into X with distortion at most 16λ.

4 Non embedability of the diamonds in uniformly convex spaces

Recall that the modulus of uniform convexity of a normed space X is the function δ : (0, 2) → [0, 1] defined by

δ(ε) = δ_{X}(ε) = inf\{1 − ∥\frac{x + y}{2} ∥ ; ∥x∥, ∥y∥ ≤ 1, ∥x − y∥ ≥ ε\}.

Lemma 1 Let X be a normed space and f : D_{1} → X with Lip(f^{−1}) ≤ 1 and Lip(f) ≤ M. Then ∥f(1, 1) − f(0, 0)∥ ≤ 2M(1 − δ(\frac{2}{M}))

Proof: Without loss of generality we may assume f(0, 0) = 0. Denote x = f(1, 1) and x_{1} = x − f(1, 0), x_{2} = f(1, 0), x_{3} = x − f(0, 1), x_{4} = f(0, 1). Then, 1 ≤ ∥x_{i}∥ ≤ M for i = 1, 2, 3, 4. Since ∥\frac{x_{2}}{M} − \frac{x_{4}}{M} ∥ ≥ \frac{2}{M}, we get that

1 − \frac{∥x_{2} + x_{4}∥}{2M} ≥ δ(\frac{2}{M}).

Similarly,

1 − \frac{∥x_{1} + x_{3}∥}{2M} ≥ δ(\frac{2}{M}).

Consequently,

2(1 − δ(\frac{2}{M})) ≥ \frac{∥x_{1} + x_{2} + x_{3} + x_{4}∥}{2M} = \frac{∥x∥}{M}.

Applying the lemma we get that if M_{n} is the best constant M such that there is an embedding f of D_{n} into X with d_{D_{n}}(x, y) ≤ ∥f(x) − f(y)∥ ≤ Md_{D_{n}}(x, y), then M_{n−1} ≤ M_{n}(1 − δ_{X}(\frac{2}{M_{n}})). Indeed, by the Lemma the distance between the images of the top and the bottom vertices of any sub diamond of level n−1 is at most 2M_{n}(1−δ_{X}(\frac{2}{M_{n}})) (and at least 2). The collection of all top and bottom vertices of level n − 1 of D_{n} is isometric to D_{n−1}: The distance between any two points of that subset of D_{n} is exactly twice the distance of the vertices of D_{n−1} they developed from. This implies that M_{n−1} ≤ M_{n}(1 − δ_{X}(\frac{2}{M_{n}})).

Passing to the limit as n → ∞ we easily get that the D_{n} do not embed with a uniform distortion in any uniformly convex space. This fact was basically known, although we could not find an explicit reference. Its analog for the Laakso graphs (see Section 6) was proved in [La] (see also [Ty]). Also, [LN] (and [LMN] for the Laakso graphs) contains the result under the additional assumption that the modulus of convexity dominates cε^{2} for some c > 0. However, for some of the applications we shall need a finer estimate of the distortion. Notice that the exact dependence on the constant c will be important for us later. [MN] essentially contains this result with a different, more involved proof.

Proposition 2 Let X be a normed space whose modulus of uniform convexity is of power type p, for some 2 ≤ p < ∞; i.e, δ_{X}(ε) ≥ cε^{p}. Let M_{n} denote the best distortion of an embedding of D_{n} into X. Then M_{n} ≥ 2c^{1/p}n^{1/p}.

Proof: By the Lemma and the remark following it, for all k ≥ 1, M_{k} − M_{k−1} ≥ M_{k}c(\frac{2}{M_{k}})^{p} = \frac{c2^{p}}{M_{k}^{p−1}} . So,

M_{n} ≥ c2^{p} ∑_{k=1}^{n} M_{k}^{−p+1} + M_{0} ≥ c2^{p}nM_{n}^{−p+1},

implying M_{n} ≥ 2c^{1/p}n^{1/p}.

Since a Banach space is super reflexive if and only if it has an equivalent norm which is uniformly convex with modulus of uniform convexity of power type p for some 2 ≤ p < ∞ (see [P]), we get as a corollary of the last proposition and of Corollary 1 the following main theorem of this paper.

Theorem 1 A Banach space X is not super reflexive if and only if the diamond graphs D_{n} Lipschitz embed into X with distortions independent of n.

We now state some more corollaries of Proposition 2. The first is a proof of the main result of [BC] which combined with the above is even simpler than the simple proof in [LN]. The deduction of the result from Proposition 2 is identical to that in [LN].

Corollary 2 (BC) If D_{n} Lipschitz embeds into ℓ_{1}^{k} with distortion K then k ≥ \overline{D_{n}}^{β/K^{2}}, for a universal β > 0.

Proof: For any p > 1, the (Lipschitz) distance between ℓ_{1}^{k} and ℓ_{p}^{k} is at most k^{(p−1)/p}. δ_{L_{p}}(ε) ≥ α(p−1)ε^{2}, for all 1 < p < 2 and for a universal α > 0 (see e.g. [Fi] or [BCL]). It thus follows from Lemma 1 that K ≥ 2k^{−(p−1)/p}α^{1/2}(p − 1)^{1/2}n^{1/2}. Choosing p = 1 + \frac{1}{log k} we get log k ≥ βn/K^{2} for a universal β > 0.

There are non super reflexive spaces that have non trivial type ([Ja2]; see also [PX]). These provide interesting examples of spaces in which the Johnson–Lindenstrauss dimension reduction result cannot occur.

Corollary 3 If X is a non super reflexive space with non trivial type p then

(i) The D_{n}-s uniformly Lipschitz embed in X, but

(ii) for any sequence k_{n} with k_{n} = O(n), if X_{n} are subspaces of X of dimensions k_{n} then the distortion of embedding D_{n} into X_{n} tends to infinity.

Proof: (i) follows from Corollary 1. Since X has non trivial type, by [MW], d(Y, ℓ_{2}^{dim Y}) = o((dim Y)^{1/2}) for every subspace Y of X. If dim Y = k_{n} with k_{n} = O(n), and D_{n} embeds into Y with distortion D, then it embeds into ℓ_{2}^{k_{n}} with distortion Do(k_{n}^{1/2}) = Do(n^{1/2}). By the previous proposition, since δ_{ℓ_{2}}(ε) > ε^{2}/8, D ≥ 2^{−1/2}n^{1/2}/o(k_{n}^{1/2}) → ∞.

Remark 2 There are also non super reflexive spaces X in which d(Y, ℓ_{2}^{dim Y}) = O(log(dim Y)) for every subspace Y of X [PX]. In a similar way to the proof of the previous corollary we get that if D_{n} Lipschitz embeds into a k_{n}-dimensional subspace of X then k_{n} ≥ 2^{c(log \overline{D_{n}})^{1/2}/D}, for a universal c > 0.

Remark 3 The summing operator S : ℓ_{1} → ℓ_{∞} is defined to be the continuous linear extension of the mapping e_{n} ↦ ∑_{i=1}^{n} e_{i}, where {e_{n}}_{n=1}^{∞} is the unit vector basis. Lindenstrauss and Pełczyński [LiP] proved that a Banach space X is non reflexive iff S factors through X, which means that there are bounded linear operators A : ℓ_{1} → X and B : X → ℓ_{∞} so that S = BA. Moreover, if X is non reflexive then A and B can be chosen so that ∥A∥ · ∥B∥ < C for some absolute constant C. Now {e_{i}}_{i=1}^{2^{n}} in ℓ_{1} and {Se_{i}}_{i=1}^{2^{n}} in ℓ_{∞} both satisfy the conditions on {x_{i}}_{i=1}^{2^{n}} in Proposition 1 (with constants a, b independent of n), so there are mappings F_{n} of D_{n} into ℓ_{1} with uniformly bounded distortion so that SF_{n} have uniformly bounded distortion. This implies Theorem 1, in view of the result in [LiP].

5 (p, r)-summing Lipschitz maps

We begin with explaining our motivation for the main result of this section, Proposition 4. This motivation depends on some non trivial facts from the linear theory which the (unmotivated) reader may prefer to skip. Such a reader should skip to Definition 1 below.

Remark 3 says that the summing operator, S, preserves with bounded distortion a sequence of metric spaces that are fairly complicated. This led us to wonder whether or not S is finitely strictly singular, which means that S does not preserve with bounded distortion any sequence of finite dimensional subspaces of ℓ_{1} whose dimensions tend to infinity. It turned out that S is finitely strictly singular; in fact,

Proposition 3 There exists a constant C such that if E is an n-dimensional subspace of ℓ_{1}, then

α(S_{E}) := inf_{x∈E; ∥x∥_{1}=1} ∥Sx∥_{∞} ≤ Cn^{−1/2}.  (1)

Proof: This proposition is not really needed to understand the main result in this section, so we use without further reference tools that are standard in Banach space theory. The interested non expert can find everything we use in [MS] or [DJT].

Since there is a constant δ > 0 so that every n-dimensional subspace of ℓ_{1} contains a further subspace that has dimension at least δn and is 2-isomorphic to a Euclidean space, it is enough to verify (1) when E is 2-isomorphic to ℓ_{2}^{n}. Let Y be a non reflexive space that has type 2 (see [Ja2] or [PX]) and let A : ℓ_{1} → Y, B : Y → ℓ_{∞} be bounded linear operators so that S = BA and ∥B∥ = 1. Clearly α(A_{E}) ≥ α(S_{E}). That is, letting U be the inverse of the restriction of A to E, we have that ∥U∥ ≤ α(S_{E})^{−1}. Since U is mapping into a space that is 2-isomorphic to a Hilbert space, we have that U has an extension to a linear operator Ũ : X → E with ∥U∥ ≤ 2T_{2}(X)α(S_{E})^{−1} (here T_{2}(X) is the (gausian) type 2 constant of X). Thus ŨA is a projection from ℓ_{1} onto a 2-isomorph of ℓ_{2}^{n} and hence

(1/8)\sqrt{n} ≤ ∥ŨA∥ ≤ 2T_{2}(X)α(S_{E})^{−1}.

After we discovered Proposition 3, Pełczyński reminded us that he and Kwapień [KP] proved that S is (p, r)-summing for every p > r ≥ 1. This immediately implies that S is finitely strictly singular (but without the precise estimate given by Proposition 3). Now, one can modify the definition of (p, r)-summing to define a concept of Lipschitz (p, r)-summing in the same way that the definition of p-summing was modified in [Fa] to define the concept of Lipschitz p-summing. Since the summing operator preserves copies of of the diamond graphs, it follows that the identity operators on the diamond graphs D_{n} are Lipschitz (p, r)-summing, with constants independent of n, for all p > r ≥ 1. This means that the diamond graphs satisfy a family of inequalities that look non trivial. We were surprised when further investigation yielded that all metric spaces satisfy these inequalities.

We begin with the definition of Lipschitz (p, r)-summing function.

Definition 1 A function F from a metric spaces (M, d) into a metric space (N, ρ) is said to be Lipschitz (p, r)-summing with constant at most K if for all finite sequences of pairs of points {x_{i}, y_{i}}_{i=1}^{n} in M and all positive numbers {c_{i}}_{i=1}^{n}

(∑_{i=1}^{n} c_{i}^{p}ρ(F (x_{i}), F (y_{i}))^{p})^{1/p} ≤ K sup(∑_{i=1}^{n} c_{i}^{r}|f(x_{i}) − f(y_{i})|^{r})^{1/r},  (2)

where the sup is taken over all real Lipschitz functions f on M of Lipschitz constant 1. The smallest possible K is denoted π_{p,r}^{L}(F). (The superscript L stands for Lipschitz.)

For a linear operator F, the definition of (p, r)-summing is the same except that the supremum in the right side of (2) is taken over all linear functionals f whose norm is at most one. Of course, linearity of F allows the definition in the linear case to be written more succinctly.

The definition of Lipschitz (p, p)-summing is the same as the definition of Lipschitz p-summing given in J. Farmer’s 1992 dissertation [Fa] and repeated in [FJ]. π_{p,p}^{L}(F) is the same as the quantity π_{p}^{L}(F) defined there.

It is quite easy to show that if p ≥ r, q ≥ s and \frac{1}{s} − \frac{1}{q} ≤ \frac{1}{r} − \frac{1}{p} then any (q, s)-summing function F is also (p, r)-summing and π_{p,r}^{L}(F) ≤ π_{q,s}^{L}(F). (The proof is very similar to the simple proof in the linear setting; see e.g. page 198 in [DJT].)

We now state the main result in this section.

Proposition 4 For any p > 1, any Lipschitz function is (p, 1)-summing with constant at most its Lipschitz constant times a constant C_{p} which is O((p−1)^{−1}) for p → 1 and O(1) for p → ∞ . Consequently, it is also (p, r)-summing for any p > r > 1 with constant at most its Lipschitz constant times a constant depending only on p and r.

Proof: It is enough to prove the proposition for the identity map on (M, d). Let {x_{i}, y_{i}}_{i=1}^{n} be any points in the metric space (M, d) and let {c_{i}}_{i=1}^{n} be any positive numbers with ∑_{i=1}^{n} c_{i}^{p}d(x_{i}, y_{i})^{p} = 1. Put σ_{j} = {i; (c_{i}d(x_{i}, y_{i}))^{p−1} ∈ (2^{−j}, 2^{−j+1}]}, j = 1, 2, . . ..

As was mentioned in [FJ] (or, in view of [FJ, Theorem 1], in an equivalent form in [MR]), Bourgain [BOU1] really proved that π_{1}^{L}(I_{Z}) ≤ C log n for all n point metric spaces Z. This implies that for some universal C and for each j there is a real Lipschitz function f_{j} on M with Lipschitz constant 1 satisfying

∑_{i∈σ_{j}} c_{i}^{p}d(x_{i}, y_{i})^{p} ≤ C log \overline{σ_{j}} ∑_{i∈σ_{j}}(c_{i}d(x_{i}, y_{i}))^{p−1}c_{i}|f_{j}(x_{i}) − f_{j}(y_{i})|
≤ C2^{1−j} log \overline{σ_{j}} ∑_{i∈σ_{j}} c_{i}|f_{j}(x_{i}) − f_{j}(y_{i})|.  (3)

Given a sequence ε of ε_{j} = ±1, let f_{ε} = ∑_{j} ε_{j}2^{1−j} log \overline{σ_{j}}f_{j}.

Note that for each ε the Lipschitz constant of f_{ε} is at most ∑_{j} 2^{1−j} log \overline{σ_{j}}. To evaluate this sum note that \overline{σ_{j}}2^{−jp/(p−1)} ≤ 1 so that

∑_{j} 2^{1−j} log \overline{σ_{j}} ≤ \frac{p}{p − 1} ∑_{j=1}^{∞} j2^{1−j} ≤ C_{p}.

Where C_{p} = O((p − 1)^{−1}) when p approaches 1 and O(1) when p approaches infinity. Note also that for each i and j such that i ∈ σ_{j},

𝔼|f_{ε}(x_{i}) − f_{ε}(y_{i})| ≥ 2^{1−j} log \overline{σ_{j}}|f_{j}(x_{i}) − f_{j}(y_{i})|,

where the expectation 𝔼 is the average over all ε ∈ {−1, 1}^{n}. Consequently, using (3),

1 = ∑_{i=1}^{n} c_{i}^{p}d(x_{i}, y_{i})^{p} = ∑_{j} ∑_{i∈σ_{j}} c_{i}^{p}d(x_{i}, y_{i})^{p}
≤ C ∑_{j} ∑_{i∈σ_{j}} c_{i}2^{1−j} log \overline{σ_{j}}|f_{j}(x_{i}) − f_{j}(y_{i})|

≤ C𝔼 ∑_{i=1}^{n} c_{i}|f_{ε}(x_{i}) − f_{ε}(y_{i})|.  (4)

Remark 4 In [FJ] it was proved that π_{p}(T) = π_{p}^{L}(T), 1 ≤ p < ∞, for every linear operator T. Proposition 4 shows that there is no analogous result for the (p, r)-summing norms.

Remark 5 The order O((p − 1)^{−1}) for the constant C_{p} when p approaches 1 is best possible. This can be seen by considering the examples of n point metric spaces whose best embedding into a Hilbert space have distortion of order log n (see [LLR], expanders with a fix degree can serve as such examples). If (M, d) is such an n-point metric space then the identity on M satisfies π_{1}^{L}(I_{M}) ≥ c log n, for a universal c > 0 (see [FJ]). Also, in the definition of π_{p,1}^{L}(I_{M}) it is clearly enough to consider at most n^{2} couples of points (x_{i}, y_{i}) ∈ M^{2} (no repetitions are needed). Consequently, for all such couples of points and all coefficients c_{i},

∑ c_{i}d(x_{i}, y_{i}) ≤ n^{2(1−1/p)}(∑ c_{i}^{p}d(x_{i}, y_{i})^{p})^{1/p} ≤ n^{2(1−1/p)}π_{p,1}^{L}(I_{M}) sup ∑ c_{i}|f(x_{i}) − f(y_{i})|.

We thus get n^{2(1−1/p)}π_{p,1}^{L}(I_{M}) ≥ c log n. Given 1 < p < 2 choose n so that log n is of order (p − 1)^{−1} to get that π_{p,1}^{L}(I_{M}) is at least of order (p − 1)^{−1}.

Clearly, also the order O(1) for the constant C_{p} when p approaches ∞ is best possible.

We conclude this section with a possible measure of the complexity of a metric space. Saying that π_{1}^{L}(I_{X}) ≤ K is the same as saying that you can situate X isometrically in L_{∞}(μ) for some probability μ so that the L_{∞}(μ) and L_{1}(μ) norms are K-equivalent on X (see [FJ]). In some sense, then, π_{1}^{L}(I_{X}) < ∞ says that X is reasonably simple, and the size of π_{1}^{L}(I_{X}) for, say, a finite metric space X provides one measure of the simplicity of X. Perhaps here it is worth mentioning that π_{1}^{L}(I_{ℓ_{2}^{n}}) is of order \sqrt{n} and that if X is an infinite metric space such that the distance between any two distinct points is one, then π_{1}^{L}(I_{X}) = 2 (see [FJ]). When π_{1}^{L}(I_{X}) = ∞, a related measure of the complexity of X is provided by the asymptotics of π_{p,1}^{L}(I_{X}) as p ↓ 1.

6 The Laakso graphs

In this final section we indicate how to prove a theorem similar to Theorem 1 for another interesting sequence of graphs. These are graphs introduced by Laakso [La]. They have similar properties to those of the diamond graphs but in addition are doubling: every ball in each of these graphs can be covered by a union of 6 balls of half the radius of the original ball. See [LaP] for a simple proof of this fact, originally proved (with a different constant) in [La]. We prefer to introduce these graphs as subgraphs of the Hamming cubes, with all edges of length 1; consequently our distance function is a multiple of the ones used in [La], [LiP] and [LMN]. As for the diamond graphs, the actual embedding into the Hamming cubes will be important for us.

The vertex set of the graph L_{n} will be a subset of {0, 1}^{4^{n}} and the edge set will be a subset of the edge set of the Hamming cube {0, 1}^{4^{n}}. L_{0} is the graph with two vertices, labelled 0 and 1 and one edge connecting them. Given L_{i−1} whose vertex set is a subset of {0, 1}^{4^{i−1}} we replace each vertex (a_{1}, a_{2}, …, a_{2^{i−1}}) with

(a_{1}, a_{1}, a_{1}, a_{1}, a_{2}, a_{2}, a_{2}, a_{2}, …, a_{2^{i−1}}, a_{2^{i−1}}, a_{2^{i−1}}, a_{2^{i−1}}) ∈ {0, 1}^{4^{i}}.

For each two new vertices whose Hamming distance is 4 (i.e, coming from an edge in L_{i−1}) we now add four new vertices in the following way: the two new vertices differ only in four consecutive coordinates in which one of them has all ones and the other all zeros, the four additional new vertices will be identical to these two in all coordinates except these four, and the restriction of these four new vertices to these four coordinates will be: ((1, 1, 0, 1), (1, 1, 0, 0), (0, 1, 0, 1) and (0, 1, 0, 0). So, for example, L_{1} will be

(1, 1, 1, 1)
(1, 1, 0, 1)
(1, 1, 0, 0) (0, 1, 0, 1)
(0, 1, 0, 0)
(0, 0, 0, 0)

with an edge connecting any vertex to the one(s) immediately below it. We shall term these six vertices as: very top, top, leftmost, rightmost, bottom, and very bottom. In analogy to the notations of the diamond graphs, we can also talk about sub-Laakso graphs of level i, on top, very top, etc in sub-Laasko graphs and so on.

In a very similar way to the proofs presented, we can prove

Theorem 2 A Banach space X is not super reflexive if and only if the Laakso graphs L_{n} Lipschitz embed into X with distortions independent of n.

We only indicate briefly the outline of the proof. As we already indicated the fact that the Laakso graphs do not uniformly Lipschitz embed in a uniformly convex space was known ([La], [Ty] and [LMN] for a somewhat more restrictive statement). We shall however indicate the simple proof as it gives a somewhat more quantitative statement (the analog of Proposition 2). So to prove that L_{n} do not uniformly embed in a uniformly convex Banach space we first prove

Lemma 2 Let X be a normed space and f : L_{1} → X with Lip(f^{−1}) ≤ 1 and Lip(f) ≤ M. Then ∥f(1, 1, 1, 1) − f(0, 0, 0, 0)∥ ≤ 4M(1 − δ(\frac{2}{M}))

The proof of the lemma is almost identical with the proof of Lemma 1: Start with the assumption that f(0, 0, 0, 0) = 0 and put x = f(1, 1, 1, 1), x_{1} = x − f(1, 1, 0, 0), x_{2} = f(1, 1, 0, 0), x_{3} = x − f(0, 1, 0, 1), x_{4} = f(0, 1, 0, 1). Now continue as in the proof of Lemma 1 to get exactly the same statement as in Proposition 2 (for L_{n} instead of D_{n}).

To prove that the L_{n}-s uniformly embed in any non super reflexive space use an embedding similar to the one in the statement of Proposition 1: Let x_{1}, x_{2}, …, x_{4^{n}} be a sequence satisfying the assumptions of Proposition 1 (with 4^{n} replacing 2^{n}) and let f : L_{n} → X be defined by f(a_{1}, …, a_{4^{n}}) = ∑_{i=1}^{4^{n}} a_{i}x_{i}. If u, v ∈ L_{n} lie on a path from the very top to the very bottom then f acts as an isometry on them. If not, we look at the smallest sub-Laakso graph u and v belong to and then necessarily they both lie between the top and bottom (as opposed to the very top and the very bottom) vertices of this sub graph and they lie on opposite sides there. The rest of the argument is very similar to the one in the proof of Proposition 1 and we omit it.

Remark 6 In light of [BKL], It might very well be that Theorem 1 extends to any series parallel graph. We didn’t try to prove this.

References

[BCL] Ball, Keith; Carlen, Eric A.; Lieb, Elliott H., Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115 (1994), no. 3, 463–482.

[BL] Benyamini, Y.; Lindenstrauss, J., Geometric nonlinear functional analysis, Vol. 1, Colloquium Publications Vol 48, AMS 2000.

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

[BOU2] Bourgain, J., The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math. 56 (1986), no. 2, 222–230.

[BC] Brinkman, B.; Charikar, M., On the impossibility of dimension reduction in l_{1}. J. ACM 52 (2005), no. 5, 766–788

[BKL] Brinkman, B.; Karagiozova, A.; Lee, J. R., Vertex cuts, random walks, and dimension reduction in series-parallel graphs. STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 621–630, ACM, New York, 2007.

[DJT] Diestel, Joe; Jarchow, Hans; Tonge, Andrew, Absolutely summing operators. Cambridge Studies in Advanced Mathematics, 43. Cambridge University Press, Cambridge, 1995.

[E] Enflo, Per, Banach spaces which can be given an equivalent uniformly convex norm. Proceedings of the International Symposium on Partial Differential Equations and the Geometry of Normed Linear Spaces (Jerusalem, 1972). Israel J. Math. 13 (1972), 281–288 (1973).

[Fa] Farmer, Jeffrey D., Extensions and applications of infinite dimensional Banach space theory, PhD thesis, Texas A&M University, August, 1992.

[FJ] Farmer, Jeffrey D.; Johnson, William B., Lipschitz p-summing operators. (preprint)

[Fi] Figiel, T., On the moduli of convexity and smoothness. Studia Math. 56 (1976), no. 2, 121–155.

[GNRS] Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair, Cuts, trees and l_{1}-embeddings of graphs. Combinatorica 24 (2004), no. 2, 233–269.

[Ja1] James, R. C., Weak compactness and reflexivity. Israel J. Math. 2 1964 101–119.

[Ja2] James, R. C., Nonreflexive spaces of type 2. Israel J. Math. 30 (1978), nos. 1-2, 1–13.

[JL] Johnson, William B.; Lindenstrauss, Joram, Extensions of Lipschitz mappings into a Hilbert space. Conference in modern analysis and probability (New Haven, Conn., 1982), 189–206, Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984.

[KP] Kwapień, S.; Pełczyński, A., The main triangle projection in matrix spaces and its applications. Studia Math. 34 (1970), 43–68.

[La] Laakso, T. J., Ahlfors Q-regular spaces with arbitrary Q > 1 admitting weak Poincare inequality. Geom. Funct. Anal. 10 (2000), no. 1, 111–123.

[LLR] Linial, Nathan; London, Eran; Rabinovich, Yuri, The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), no. 2, 215–245.

[LMN] Lee, James R.; Mendel, Manor; Naor, Assaf, Metric structures in L_{1}: dimension, snowflakes, and average distortion. European J. Combin. 26 (2005), no. 8, 1180– 1190.

[LN] Lee, J. R.; Naor, A., Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal. 14 (2004), no. 4, 745–747.

[LaP] Lang, Urs; Plaut, Conrad, Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87 (2001), no. 1-3, 285–307.

[LiP] Lindenstrauss, J.; Pełczyński, A, Absolutely summing operators in L_{p}-spaces and their applications. Studia Math. 29 (1968), 275–326.

[MR] Matoušek, Jiři; Rabinovich, Yuri, On dominated l_{1} metrics. Israel J. Math. 123 (2001), 285–301.

[MN] Mendel, M.; Naor, A., Markov convexity and local rigidity of distorted metrics, Proceedings of the twenty-fourth annual symposium on Computational Geometry, (2008), 49–58.

[MS] Milman, V. D.; Schechtman, G., Asymptotic theory of finite dimensional normed spaces, Springer lecture notes in mathematics 1200, 1986.

[MW] Milman, V. D.; Wolfson, H., Minkowski spaces with extremal distance from the Euclidean space. Israel J. Math. 29 (1978), no. 2-3, 113–131.

[P] Pisier, Gilles, Martingales with values in uniformly convex spaces. Israel J. Math. 20 (1975), no. 3-4, 326–350.

[PX] Pisier, Gilles; Xu, Quan Hua, Random series in the real interpolation spaces between the spaces v_{p}. Geometrical aspects of functional analysis (1985/86), 185–209, Lecture Notes in Math., 1267, Springer, Berlin, 1987.

[Ty] Tyson, Jeremy T., Bi-Lipschitz embeddings of hyperspaces of compact sets. Fund. Math. 187 (2005), no. 3, 229–254.

W.B. Johnson  G. Schechtman
Department of Mathematics  Department of Mathematics
Texas A&M University  Weizmann Institute of Science
College Station, TX 77843 U.S.A. Rehovot, Israel

johnson@math.tamu.edu         gideon@weizmann.ac.il