Remarks on Non Linear Type and Pisier’s Inequality

Assaf Naor^{∗}  Gideon Schechtman^{†}

Abstract We prove that for the class of UMD Banach spaces, the log n term in Pisier’s inequality [17] can be replaced by a constant independent of n. This is applied to show that for UMD Banach spaces, various non-linear notions of type p are implied by (Rademacher) type p.

1 Introduction

In [17], Pisier proved an elegant inequality for normed space valued functions on the discrete cube {1, −1}^{n}. He showed that for any such function f, for any 1 ≤ p ≤ ∞ and for any positive integer n

(∫{1,−1}^{n} ∥f − ∫_{{1,−1}^{n}} fdP_{n}∥^{p} dP_{n})^{1/p} ≤

≤ 2e log n (∫_{{1,−1}^{n}} ∫_{{1,−1}^{n}} ∥∑_{i=1}^{n} ω′_{i}∂_{i}f(ω)∥^{p} dP_{n}(ω)dP_{n}(ω′))^{1/p} .  (1)

Here

∂_{i}f(ω) = \frac{f(ω) − f(S_{i}(ω))}{2},

where S_{i}(ω) is obtained from ω by changing the sign of the i’th coordinate and P_{n} is the normalized counting measure on {1, −1}^{n}. This inequality is important in the non-linear theory of Banach spaces as we shall explain below and also has a harmonic analytic flavor. It has also been shown by Talagrand [18] that the log n factor in the inequality above is needed in general. Our initial motivation here was to try and remove the log n factor for a wide class of normed spaces. As we shall see we managed to do it for the class of UMD spaces (i.e., Banach spaces in which martingale differences are unconditional. We shall say more about this notion at the end of this introduction). We begin with reviewing some notions from the linear and then non-linear theory of Banach spaces.

The concept of (Rademacher) type of a Banach space has proved to be central to the modern theory of Banach spaces, both in its analytic and its geometric aspects. A Banach space X is said to have type p for some 1 ≤ p ≤ 2 if there is a constant T > 0 such that for every n and for every x_{1}, …, x_{n} ∈ X the following inequality holds:

(𝔼 ∥∑_{i=1}^{n} r_{i}x_{i}∥^{2})^{1/2} ≤ T (∑_{i=1}^{n} ∥x_{i}∥^{p})^{1/p} .

Here r_{1}, …, r_{n} are i.i.d. random variables which take the values ±1 with probability \frac{1}{2}. Every Banach space has type 1, and X is said to have non-trivial type if it has type p for some p > 1. Type has proved to be useful in many ways, and in the past thirty years the study of this concept has developed into a deep, and rich theory. Since a subspace of a space with type trivially has the same type (with the same constant), type is instrumental in trying to decide if a given space isomorphically embeds into another.

∗Supported in part by the Binational Science Foundation Israel-USA and the Clore Foundation. This work is part of a Ph.D. thesis being prepared under the supervision of Professor Joram Lindenstrauss.

†Supported in part by ISF.

As is seen in the definition of type, it is clearly a linear concept. When trying to decide Lipschitz embedability of one normed (or more generally metric) space in another one is led to some non-linear analogs of this concept. The first such concept, to the best of our knowledge (which actually predates the definition of linear type), was introduced by Enflo in his study of the infinite dimensional version of Hilbert’s 5’th problem [6],[7]. Enflo introduced the notion of roundness of a metric space, and proved that under some additional technical assumptions, when a Banach space has non-trivial roundness, this problem has a positive solution (see [2] chapter 17 for more details). A metric space (M, d) is said to have roundness 1 ≤ p < ∞ if for every a_{1}, a_{2}, a_{3}, a_{4} ∈ M:

d(a_{1}, a_{3})^{p} + d(a_{2}, a_{4})^{p} ≤ d(a_{1}, a_{2})^{p} + d(a_{2}, a_{3})^{p} + d(a_{3}, a_{4})^{p} + d(a_{4}, a_{1})^{p}.

This inequality easily tensorizes to an inequality for n-dimensional cubes in M. An n-dimensional cube in M is a subset {x_{ϵ}}_{ϵ∈{1,−1}^{n}} ⊂ M. If C is an n-dimensional cube in M, the set of diagonals of C is defined to be the set of unordered pairs diag(C) = {{x_{ϵ}, x_{−ϵ}}; ϵ ∈ {1, −1}^{n}}. An edge in C is an unordered pair {x_{ϵ}, x_{ϵ′}} such that ϵ and ϵ′ differ in only one coordinate. The set of all edges of C is denoted by edge(C). It is easy to verify that if (M, d) has roundness p then for every n dimensional cube C ⊂ M:

∑_{{a,b}∈diag(C)} d(a, b)^{p} ≤ ∑_{{α,β}∈edge(C)} d(α, β)^{p}.

In [8], Enflo generalized this concept to what is known today as Enflo type (or E-type). A metric space (M, d) is said to have Enflo type p if there is a constant K > 0 such that for every n and for every n-dimensional cube C ⊂ M,

∑_{{a,b}∈diag(C)} d(a, b)^{p} ≤ K ∑_{{α,β}∈edge(C)} d(α, β)^{p}.  (2)

It is obvious that for Banach spaces, Enflo type p implies type p. In [8] Enflo asked whether for Banach spaces this non-linear concept is actually equivalent to type. In Theorem 6 below we solve this problem positively for UMD Banach spaces. In particular, inequality (2) for X = L_{q}, q > 2 and p = 2 seems to be new.

Another notion of type for metric spaces is the so called non-linear type, which was introduced by Bourgain, Milman and Wolfson [3]. A metric space (M, d) is said to have non-linear type p if there is a constant K such that for every n and for every n-dimensional cube C ⊂ M,

( ∑_{\{a,b\}∈diag(C)} d(a, b)^{2})^{1/2} ≤ Kn^{\frac{1}{p} − \frac{1}{2}} ( ∑_{\{α,β\}∈edge(C)} d(α, β)^{2})^{1/2} .  (3)

Bourgain, Milman and Wolfson proved that a metric space has non trivial non-linear type (i.e. non-linear type p > 1) if and only if it does not contain uniformly Lipschitz images of n-dimensional Hamming cubes. (This is a nonlinear analogue of the previously known fact ([14] or see [13]) that a Banach space has non-trivial (linear) type if and only if it doesn’t contain ℓ_{1}^{n}’s uniformly; i.e., the smallest isomorphism constant between ℓ_{1}^{n} and an n-dimensional subspace of X must tend to infinity with n). They also proved that if a Banach space has type p > 1 then it also has non-linear type p_{1} for every 1 ≤ p_{1} < p. This, combined with results from the linear theory, implies the following striking geometric result: if a Banach space contains n-dimensional Hamming cubes uniformly then it also contains ℓ_{1}^{n}’s uniformly. Bourgain, Milman and Wolfson posed the question whether for Banach spaces type p implies non-linear type p. In this paper we prove that the answer is positive for UMD Banach spaces (in this case, inequality (3) seems to be new also for L_{p}, 1 < p < 2). In [17] Pisier proved that if a Banach space X has type p > 1 then it has Enflo type p_{1} for every p_{1} < p, and asked what is the precise relation between Enflo type and non-linear type. We show in Theorem 6 below that for UMD Banach spaces Enflo type p implies non-linear type p.

As remarked above, the non-linear type of a metric space (M, d) is related to the embedability of Hamming cubes (i.e. the cubes {1, −1}^{n} equipped with the ℓ_{1} metric) in M. We denote by c_{M}({1, −1}^{n}) the infimum over all constants L such that there is an embedding f : {1, −1}^{n} → M with distortion less than L, i.e.

sup_{ω,ω′∈\{1,−1\}^{n}} \frac{d(f(ω), f(ω′))}{∥ω − ω′∥_{1}} · sup_{ω,ω′∈\{1,−1\}^{n}} \frac{∥ω − ω′∥_{1}}{d(f(ω), f(ω′))} ≤ L.

As was noted by Matoušek [11] the results of Bourgain, Milman and Wolfson imply that for every p > 2 and for every ϵ > 0 there is a constant C(p, ϵ) > 0 such that for every n, c_{L_{p}}(\{1, −1\}^{n}) ≥ C(p, ϵ)n^{\frac{1}{2} −ϵ}. The validity of the more natural estimate c_{L_{p}}(\{1, −1\}^{n}) = Ω(\sqrt{n}) was left open. Our results imply a positive answer to this problem. In fact, for any UMD Banach space X of type p, c_{X}({1, −1}^{n}) = Ω(n^{1− \frac{1}{p}}) (and L_{p}, p > 2 is a UMD space of type 2).

In [17] Pisier re-proved the main results of Bourgain, Milman and Wolfson via an important Poincaré type inequality for functions on the discrete cube stated above as (1). Talagrand [18] proved that the log n factor in Pisier’s inequality is best possible for general Banach spaces, but that it may be replaced by an absolute constant (depending on p) when X is the real line. When p = ∞, Wagner [19] proved that the log n term can be removed when X is an arbitrary Banach space. In the present paper we prove that when X is UMD, the log n term can be replaced by a constant (depending on X). This is the main technical result here, the results concerning the non-linear theory of Banach spaces explained above are corollaries of this result.

Pisier’s inequality for UMD Banach spaces (with the log n term removed) is proved in Section 2. The martingale approach to Pisier’s inequality which we present is different from Pisier’s proof of (1). Section 2 also contain some related results including, in Theorem 2, a scale of inequalities, holding in any Banach space, which include Pisier’s inequality (1). These inequalities involve the discrete Laplacian which is defined by Δ = ∑_{i=1}^{n} ∂_{i}^{2} = ∑_{i=1}^{n} ∂_{i}, and we also use this operator to prove a reverse form of Pisier’s inequality. Section 3 studies the connection between the boundedness of Δ^{−α} on L_{p}({1, −1}^{n}, X), α > 0, 1 < p < ∞, and the property of K-convexity of X (by a deep theorem of Pisier [16] this property is equivalent to non trivial type). In Section 4 we apply the main inequality to prove the results, concerning the non-linear theory of Banach spaces, described at the beginning of this introduction. In Section 5 we discuss related problems concerning non-linear notions of type.

We conclude this introduction by reviewing some facts concerning the class of UMD spaces. Let X be a Banach space, (Ω, F, P) a probability space and {F_{n}}_{n=0}^{∞} a non-decreasing sequence of sub-σ-algebras of F. A sequence {d_{n}}_{n=0}^{∞} of integrable X-valued functions is said to be a martingale difference sequence relative to the filtration {F_{n}}_{n=0}^{∞} if for every n ≥ 0, d_{n} is F_{n}-measurable and 𝔼(d_{n+1}|F_{n}) = 0. The space X is said to be UMD if for some 1 < p < ∞ there is a constant β > 0 such that for every X-valued martingale difference sequence {d_{n}}_{n=0}^{∞} and every ω_{1}, …, ω_{n} ∈ {−1, 1}:

𝔼 ∥∑_{k=0}^{n} ω_{k}d_{k}∥^{p} ≤ β^{p}𝔼 ∥∑_{k=0}^{n} d_{k}∥^{p} .  (4)

The least such β is denoted by β_{p}(X). Pisier proved (see [12]) that if (4) holds for some 1 < p < ∞ then it holds for all 1 < p < ∞.

UMD spaces are known to be superreflexive (i.e. they admit an equivalent uniformly convex norm). There are however superreflexive spaces which are not UMD (see [15]). Examples of UMD spaces include all the classical reflexive spaces, in particular L_{p}, 1 < p < ∞.

2 Pisier’s Inequality Revisited

In this section we will prove our main result, i.e. that for UMD Banach spaces the log n term in (1) can be replaced by a constant (depending on the UMD constant of the space, but not on n). Our approach is based on martingale techniques, and is different from Pisier’s proof of (1). We will then return to the original technique introduced by Pisier, and prove a scale of inequalities which include (1) as a limiting case, and which hold in arbitrary Banach spaces. We will also prove a reverse form of these inequalities which hold for K-convex Banach spaces.

We begin with some background and notation concerning harmonic analysis on the discrete cube. Fix an integer n and let Ω_{n} = {1, −1}^{n}. We will denote by P_{n} the uniform probability measure on Ω_{n}, i.e. P_{n}(A) = |A|/2^{n} for every A ⊂ Ω_{n}. For every Banach space X and q ≥ 1 we denote by L_{q}(Ω_{n}, X) the space of all functions f : Ω_{n} → X equipped with the norm:

∥f∥_{L_{q}(Ω_{n},X)} = (∫_{Ω_{n}} ∥f(ω)∥^{q}dP_{n}(ω))^{1/q} .

For every A ⊂ {1, …, n} the Walsh function W_{A} : Ω_{n} → ℝ is defined by:

W_{A}(ω) = ∏_{i∈A} ω_{i}.

We also write W_{∅} = 1. Any f : Ω_{n} → X can be decomposed as follows:

f(ω) = ∑_{A⊂{1,...,n}} f̂(A)W_{A}(ω),

where

f̂(A) = ∫_{Ω_{n}} f(ω)W_{A}(ω)dP_{n}(ω).

For every f : Ω_{n} → X and λ, μ > 0 define f_{λ,μ} : Ω_{n} × Ω_{n} → X by:

f_{λ,μ}(ω, ω′) = ∑_{A⊂{1,...,n}} f̂(A) ∏_{i∈A}(λω_{i} + μω′_{i}).

As was noted in [17], if X is a Banach space then for every f : Ω_{n} → X, 0 ≤ t ≤ 1 and p ≥ 1, ∥f_{t,1−t}∥_{L_{p}(Ω_{n}×Ω_{n},X)} ≤ ∥f∥_{L_{p}(Ω_{n},X)}. We recall for the sake of completeness the simple convexity argument which proves this. For n = 1, we have to show that for every x, y ∈ X:

\frac{∥x + y∥^{p} + ∥x − y∥^{p} + ∥x + (2t − 1)y∥^{p} + ∥x − (2t − 1)y∥^{p}}{4} ≤

≤ \frac{∥x + y∥^{p} + ∥x − y∥^{p}}{2} ,

and this is indeed true since the function s ↦ ∥x + sy∥^{p} + ∥x − sy∥^{p} is convex and even, and hence non-decreasing on [0, ∞). We pass to general n by induction as follows: for every ω_{n}, ω′_{n} ∈ {1, −1} define g^{ω_{n},ω′_{n}} : Ω_{n−1} → X by:

g^{ω_{n},ω′_{n}} = ∑_{A⊂{1,...,n−1}} f̂(A)W_{A} + (tω_{n} + (1 − t)ω′_{n}) ∑_{A⊂{1,...,n−1}} f̂(A ∪ {n})W_{A}.

It is obvious that for every ω, ω′ ∈ Ω_{n}:

f_{t,1−t}(ω, ω′) = g_{t,1−t}^{ω_{n},ω′_{n}}((ω_{1}, …, ω_{n−1}), (ω′_{1}, …, ω′_{n−1},)).

Applying the induction hypothesis we get:

∥f_{t,1−t} ∥ _{L_{p}(Ω_{n}×Ω_{n},X)}^{q} =
= ∫_{Ω_{1}×Ω_{1}} ∫_{Ω_{n−1}×Ω_{n−1}} ∥g_{t,1−t}^{ω_{n},ω′_{n}}((ω_{1}, …, ω_{n−1}), (ω′_{1}, …, ω′_{n−1}))∥^{q}
dP_{n−1}(ω_{1}, …, ω_{n−1})dP_{n−1}(ω′_{1}, …, ω′_{n−1})dP_{1}(ω_{n})dP_{1}(ω′_{n})
= ∫_{Ω_{1}×Ω_{1}} ∥g_{t,1−t}^{ω_{n},ω′_{n}} ∥_{L_{q}(Ω_{n−1}×Ω_{n−1},X)}^{q} dP_{1}(ω_{n})dP_{1}(ω′_{n})
≤ ∫_{Ω_{1}×Ω_{1}} ∥g^{ω_{n},ω′_{n}} ∥_{L_{q}(Ω_{n−1},X)}^{q} dP_{1}(ω_{n})dP_{1}(ω′_{n}).

If we denote for ω ∈ Ω_{n−1}:

x(ω) = ∑_{A⊂{1,...,n−1}} f̂(A)W_{A}(ω),

and

y(ω) = ∑_{A⊂{1,...,n−1}} f̂(A ∪ {n})W_{A}(ω),

then:

∫_{Ω_{1}×Ω_{1}} ∥g^{ω_{n},ω′_{n}} ∥_{L_{q}(Ω_{n−1},X)}^{q} dP_{1}(ω_{n})dP_{1}(ω′_{n}) =

= ∫_{Ω_{n−1}} ∫_{Ω_{1}×Ω_{1}} ∥x(ω) + (tω_{n−1} + (1 − t)ω′_{n−1})y(ω)∥^{q} dP_{1}(ω_{n})dP_{1}(ω′_{n})dP_{n−1}(ω)
= ∫_{Ω_{n−1}} [\frac{∥x(ω) + y(ω)∥^{q}}{4} + \frac{∥x(ω) − y(ω)∥^{q}}{4}

+\frac{∥x(ω) + (2t − 1)y(ω)∥^{q}}{4} + \frac{∥x(ω) − (2t − 1)y(ω)∥^{q}}{4} ] dP_{n−1}(ω)

≤ ∫_{Ω_{n−1}} (\frac{∥x(ω) + y(ω)∥^{q}}{2} + \frac{∥x(ω) − y(ω)∥^{q}}{2} ) dP_{n−1} = ∥f∥_{L_{q}(Ω_{n},X)}^{q}.

For every i ∈ {1, …, n} we denote by D_{i} the so called annihilation operator on L_{2}(Ω_{n}, ℝ), which is defined for every A ⊂ {1, …, n} by:

D_{i}W_{A} = \begin{cases}W_{A\\{i\}} & i ∈ A \\ 0 & i ∉ A \end{cases}

It is easy to verify that D_{i}^{∗}, the so called creation operator, is given by:

D_{i}^{∗}W_{A} = \begin{cases}W_{A∪\{i\}} & i ∉ A \\ 0 & i ∈ A \end{cases}

The discrete Laplacian is defined by ΔW_{A} = |A|W_{A}. For any power α we also denote by Δ^{α} the linear extension of the operator defined by Δ^{α}W_{A} = |A|^{α}W_{A} (with Δ^{α}W_{∅} = 0 also for negative α). It is easy to check that Δ = ∑_{i=1}^{n} D_{i}^{∗}D_{i}. For every ϵ > 0 the diagonal operators T_{ϵ}, S_{ϵ} and T′_{ϵ} are defined by T_{ϵ}W_{A} = ϵ^{|A|}W_{A}, S_{ϵ}W_{A} = ϵ^{|A|−1}W_{A} and T′_{ϵ}W_{A} = |A|ϵ^{|A|−1}W_{A}. These operators can be interpreted as follows:

T_{ϵ}f = (∏_{i=1}^{n}(1 + ϵW_{{i}})) ∗ f,

and

S_{ϵ}f − ∫_{Ω_{n}} fdP_{n} = \frac{∏_{i=1}^{n}(1 + ϵW_{\{i\}}) − 1}{ϵ} ∗ f.

In particular it easily follows that T_{ϵ} is a contraction on L_{p}(Ω_{n}, X) for every 1 ≤ p ≤ ∞ and 0 ≤ ϵ ≤ 1. The following simple identity is fundamental:

∑_{i=1}^{n} D_{i}^{∗}T_{ϵ}D_{i} = T′_{ϵ}.

All the above operators extend to operators on L_{2}(Ω_{n}, X) by taking D_{i} ⊗ I_{X}, D_{i}^{∗} ⊗ I_{X} and Δ ⊗ I_{X}. By a slight abuse of notations, we will still denote these operators by D_{i}, D_{i}^{∗} and Δ, respectively.

For every f : Ω_{n} → X we clearly have:

D_{i}f(ω) = \frac{f(ω_{1}, …, ω_{i−1}, 1, ω_{i+1}, …, ω_{n}) − f(ω_{1}, …, ω_{i−1}, −1, ω_{i+1}, …, ω_{n})}{2}.

We will also use the related partial differentiation operator:

∂_{i}f(ω) = \frac{f(ω) − f(S_{i}(ω))}{2} = ω_{i}D_{i}f(ω),

where S_{i}(ω) is obtained from ω by changing the sign of the i’th coordinate.

Our main theorem is:

Theorem 1 Let X be a UMD Banach space and 1 < p < ∞. Then for every f ∈ L_{p}(Ω_{n}, X):

∥f − ∫_{Ω_{n}} fdP_{n}∥_{L_{p}(Ω_{n},X)} ≤ β_{p}(X) ∥∑_{i=1}^{n} ω′_{i}∂_{i}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} .

Proof: For k ≥ 1 denote by F_{k} the σ-algebra generated by ω_{1}, …, ω_{k}, i.e. the σ-algebra of sets which depend only on the first k coordinates. We also denote by F_{0} the trivial σ-algebra. Fix some ω′_{1}, …, ω′_{n} ∈ {−1, 1}. Since:

∑_{i=1}^{n} ω′_{i}∂_{i}f = ∑_{∅≠A⊂{1,...,n}} (∑_{i∈A} ω′_{i}) f̂(A)W_{A},

we have that:

𝔼 (∑_{i=1}^{n} ω′_{i}∂_{i}f| F_{k}) = ∑_{max A≤k} (∑_{i∈A} ω′_{i}) f̂(A)W_{A}.

and

𝔼 (∑_{i=1}^{n} ω′_{i}∂_{i}f| F_{0}) = 0.

Hence:

d_{k} := 𝔼 (∑_{i=1}^{n} ω′_{i}∂_{i}f| F_{k}) − 𝔼 (∑_{i=1}^{n} ω′_{i}∂_{i}f| F_{k−1})

= ∑_{max A=k} (∑_{i∈A} ω′_{i}) f̂(A)W_{A}.

By the UMD property of X, for any fixed ω′_{1}, …, ω′_{n} ∈ {−1, 1}:

∥∑_{i=1}^{n} ω′_{i}∂_{i}f(ω)∥_{L_{p}(Ω_{n},X)} = ∥∑_{k=1}^{n} d_{k}(ω)∥_{L_{p}(Ω_{n},X)}

≥ \frac{1}{β_{p}(X)} ∥∑_{k=1}^{n} ω′_{k} ∑_{max A=k} (∑_{i∈A} ω′_{i}) f̂(A)W_{A}(ω)∥_{L_{p}(Ω_{n},X)} .

Taking expectation with respect to ω′ we get:

∥∑_{i=1}^{n} ω′_{i}∂_{i}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} =

= (∫_{Ω_{n}} ∥∑_{i=1}^{n} ω′_{i}∂_{i}f(ω)∥_{L_{p}(Ω_{n},X)}^{p} dP_{n}(ω′))^{1/p}

≥ \frac{1}{β_{p}(X)} (∫_{Ω_{n}} ∥∑_{k=1}^{n} ω′_{k} ∑_{max A=k} (∑_{i∈A} ω′_{i}) f̂(A)W_{A}(ω)∥_{L_{p}(Ω_{n},X)}^{p} dP_{n}(ω′))^{1/p}

≥ \frac{1}{β_{p}(X)} ∥∑_{k=1}^{n} ∑_{max A=k} [∫_{Ω_{n}} ω′_{k} (∑_{i∈A} ω′_{i}) dP_{n}(ω′)] f̂(A)W_{A}(ω)∥_{L_{p}(Ω_{n},X)}

= \frac{1}{β_{p}(X)} ∥∑_{k=1}^{n} ∑_{max A=k} f̂(A)W_{A}(ω)∥_{L_{p}(Ω_{n},X)}

= \frac{1}{β_{p}(X)} ∥f − ∫ fdP_{n}∥_{L_{p}(Ω_{n},X)} .

We now elaborate on the methods of [17] to prove a family of inequalities which include Pisier’s inequality as an extreme case. The following identity is essentially contained in [17].

Lemma 1 Let X be a Banach space, f ∈ L_{p}(Ω_{n}, X), g ∈ L_{q}(Ω_{n}, X^{∗}), λ, μ > 0 and γ ∈ ℝ. Then:

\frac{1}{μ} · ∫_{Ω_{n}×Ω_{n}} ⟨g_{λ,μ}(ω, ω′), ∑_{i=1}^{n} ω′_{i}D_{i}Δ^{γ}f(ω)⟩ dP_{n}(ω)dP_{n}(ω′) =
= ∑_{A⊂{1,...,n}} λ^{|A|−1}|A|^{1+γ} ⟨ĝ(A), f̂(A)⟩ .

Proof: Since the Walsh system {W_{A}}_{A⊂{1,...,n}} forms an orthonormal basis of L_{2}(Ω, ℝ), expanding the products in the definition of g_{λ,μ} gives:

∫_{Ω_{n}×Ω_{n}} ⟨g_{λ,μ}(ω, ω′), ∑_{i=1}^{n} ω′_{i}D_{i}Δ^{γ}f(ω)⟩ dP_{n}(ω)dP_{n}(ω′) =

= μ ∑_{i=1}^{n} ⟨  ∑_{A⊂{1,...,n},i∈A} λ^{|A|−1}ĝ(A)W_{A\{i}}, D_{i}Δ^{γ}f⟩

= μ ∑_{i=1}^{n} ⟨T_{λ}D_{i}g, D_{i}Δ^{γ}f⟩

= μ ⟨∑_{i=1}^{n} D_{i}^{∗}T_{λ}D_{i}g, Δ^{γ}f⟩
= μ ⟨T′_{λ}g, Δ^{γ}f⟩ = μ ∑_{A⊂{1,...,n}} λ^{|A|−1}|A|^{1+γ} ⟨ĝ(A), f̂(A)⟩ .

Theorem 2 let X be a Banach space, 1 ≤ p ≤ ∞ and γ > 0. Then for every integer n and for every f ∈ L_{p}(Ω_{n}, X):

∥f − ∫_{Ω_{n}} f dP_{n}∥_{L_{p}(Ω_{n},X)} ≤

≤ 20 [1 + \frac{1}{γ} (1 − \frac{1}{(n + 1)^{γ}} )] ∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{γ}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} .

In particular, taking γ → 0 we recover Pisier’s inequality.

Proof: We may assume that f̂(∅) = 0. Fix some 1/2 < λ ≤ 1. A simple change of variable shows that for every u > 0:

\frac{λ^{u}}{u^{γ+1}} = \frac{1}{Γ(1 + γ)} ∫_{0}^{λ} t^{u−1} [log (\frac{λ}{t})]^{γ} dt.  (5)

Put q = \frac{p}{p−1}, and let g ∈ L_{q}(Ω_{n}, X^{∗}) be such that ∥g∥_{L_{q}(Ω_{n},X^{∗})} = 1 and ⟨g, T_{λ}f⟩ = ∥T_{λ}f∥_{L_{p}(Ω_{n},X)}. Now, using the fact that ∥T_{λ}f∥_{L_{p}(Ω_{n},X)} ≥ λ^{n}∥f∥_{L_{p}(Ω_{n},X)} we get:

λ^{n} ∥f ∥_{L_{p}(Ω_{n},X)} ≤ ⟨g, T_{λ}f⟩
= ∑_{∅≠A⊂{1,...,n}} λ^{|A|} ⟨ĝ(A), f̂(A)⟩

= \frac{1}{Γ(1 + γ)} ∫_{0}^{λ} ( ∑_{∅≠A⊂\{1,...,n\}} t^{|A|−1}|A|^{1+γ} ⟨ĝ(A), f̂(A)⟩) [log (\frac{λ}{t})]^{γ} dt

= \frac{1}{Γ(1 + γ)} ∫_{0}^{λ} \frac{1}{1 − t} ⟨g_{t,1−t}(ω, ω′), ∑_{i=1}^{n} ω′_{i}D_{i}Δ^{γ}f(ω)⟩ [log (\frac{λ}{t})]^{γ} dt

≤ \frac{1}{Γ(1 + γ)} (∫_{0}^{λ} \frac{1}{1 − t} [log (\frac{λ}{t})]^{γ} dt) ∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{γ}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} .

Assume first that 0 < γ ≤ 2. Then:

∫_{0}^{λ} \frac{1}{1 − t} [log (\frac{λ}{t})]^{γ} dt ≤
≤ 2 ∫_{0}^{1/2} [log (\frac{λ}{t})]^{γ} dt + ∫_{1/2}^{λ} \frac{(λ − t)^{γ}}{t^{γ}(1 − t)}dt

≤ 2 ∫_{0}^{1} [log (\frac{1}{t})]^{γ} dt + 2^{γ} ∫_{0}^{λ}(1 − t)^{γ−1}dt
= 2Γ(1 + γ) + \frac{2^{γ}}{γ} [1 − (1 − λ)^{γ}]
≤ 4 + \frac{4}{γ} [1 − (1 − λ)^{γ}] .

Taking λ = 1 − \frac{1}{n+1} gives the required result. If γ ≥ 2 take λ = 1 and use the estimate:

∫_{0}^{1} \frac{1}{1 − t} [log (\frac{1}{t})]^{γ} dt = ∫_{0}^{1} ∑_{k=1}^{∞} t^{k−1} [log (\frac{1}{t})]^{γ} dt

= Γ(γ + 1) ∑_{k=1}^{∞} \frac{1}{k^{γ+1}} ≤ 3Γ(1 + γ).

We now prove a reverse inequality. Before stating it, we recall some facts concerning K-convexity that will be used in the proof. The Rademacher projection on L_{2}(Ω_{n}, ℝ) is defined by:

Rad(W_{A}) = \begin{cases}W_{A} & if |A| = 1 \\ 0 & if |A| ≠ 1 \end{cases}

When X is a Banach space, Rad extends to a projection on L_{2}(Ω_{n}, X): Rad ⊗ I_{X}. Again, we will slightly abuse the notation and continue to denote this projection by Rad. The K-convexity constant of a Banach space X is defined by:

K(X) = sup_{n} ∥Rad∥_{L_{2}(Ω_{n},X)→L_{2}(Ω_{n},X)} .

X is called K-convex if K(X) < ∞. By a deep theorem of Pisier [16] (or see [13]), which we will refer to in the sequel as the K-convexity theorem, X is K-convex if and only if X doesn’t contain ℓ_{1}^{n}’s uniformly. It follows in particular that superreflexive spaces, and hence also UMD spaces are K-convex.

When f(ω, ω′) is a function defined on Ω_{n} × Ω_{n}, with values in a Banach space X, we denote by Rad_{ω′}(f) the Rademacher projection applied only to the variable ω′.

Theorem 3 Let X be a K-convex Banach space, 1 ≤ p ≤ ∞ and γ > 1. Then for every integer n and for every f ∈ L_{p}(Ω_{n}, X):

∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{−γ}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} ≤

≤ 20K(X) [1 + \frac{1}{γ − 1} (1 − \frac{1}{(n + 1)^{γ−1}} )] ∥f − ∫_{Ω_{n}} fdP_{n}∥_{L_{p}(Ω_{n},X)} .

In particular, when γ → 1:

∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{−1}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} ≤ 20K(X) log n ∥f − ∫_{Ω_{n}} fdP_{n}∥_{L_{p}(Ω_{n},X)} .

Proof: Assume that f̂(∅) = 0 and 1/2 ≤ λ ≤ 1. It is easy to verify that:

Rad_{ω′} (\frac{f_{t,1−t}}{1 − t} ) = ∑_{∅≠A⊂\{1,...,n\}} f̂(A) ∑_{i=1}^{n} t^{|A|−1}ω′_{i}W_{A\\{i\}}

= ∑_{i=1}^{n} ω′_{i} ∑_{A⊂{1,...,n}} f̂(A)t^{|A|−1}D_{i}W_{A}.  (6)

Using (5) and the identity (6), applied to T_{1/λ}f we get:

∑_{i=1}^{n} ω′_{i}D_{i}Δ^{−γ}f =

= \frac{1}{Γ(γ)} ∫_{0}^{λ} (∑_{i=1}^{n} ω′_{i} ∑_{A⊂\{1,...,n\}} (\frac{1}{λ})^{|A|} f̂(A)t^{|A|−1}D_{i}W_{A}) [log (\frac{λ}{t})]^{γ−1} dt

= \frac{1}{Γ(γ)} ∫_{0}^{λ} (∑_{i=1}^{n} ω′_{i} ∑_{A⊂\{1,...,n\}}(T_{1/λ}f)^{∧}(A)t^{|A|−1}D_{i}W_{A}) [log (\frac{λ}{t})]^{γ−1} dt

= \frac{1}{Γ(γ)} ∫_{0}^{λ} Rad_{ω′}[(T_{1/λ}f)_{t,1−t}]\frac{1}{1 − t} [log (\frac{λ}{t})]^{γ−1} dt.

Since ∥T_{1/λ}f∥_{L_{p}(Ω_{n},X)} ≤ λ^{−n}∥f∥_{L_{p}(Ω_{n},X)}, it follows that:

∥∑_{i=1}^{n} ω′_{i} D_{i} Δ^{−γ}f∥_{L_{p}(Ω_{n}×Ω_{n},X)} ≤

≤ \frac{K(X)}{λ^{n}Γ(γ)} (∫_{0}^{λ} \frac{1}{1 − t} [log (\frac{λ}{t})]^{γ−1} dt) ∥f∥_{L_{p}(Ω_{n},X)},

and the inequality follows just as in the proof of Theorem 2.

It is no coincidence that K-convexity appeared in the conditions of Theorem 3. We have in fact the following simple characterization of K-convexity:

Theorem 4 Let X be a Banach space, and assume that for some integer n, β ∈ ℝ, 1 ≤ p < ∞ and C > 0, for every f ∈ L_{p}(Ω_{n}, X),

∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{β}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} ≤ K ∥f − ∫_{Ω_{n}} fdP_{n}∥_{L_{p}(Ω_{n},X)} .

Then:

Rad_{n}(X) ≤ CK,

where C is an absolute constant (C = 100 will work).

Proof: Fix some α > 1 and f ∈ L_{p}(Ω_{n}, X) with f̂(∅) = 0. By Theorem 2,

\frac{1}{40}∥Δ^{β−α}f∥_{L_{p}(Ω_{n},X)} ≤
≤ ∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{α}Δ^{β−α}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)}

= ∥∑_{i=1}^{n} ω′_{i}D_{i}Δ^{β}f(ω)∥_{L_{p}(Ω_{n}×Ω_{n},X)} ≤ K∥f∥_{L_{p}(Ω_{n},X)}.

Clearly lim_{α→∞} Δ^{β−α}f = Rad(f). It follows that:

\frac{1}{\sqrt{2}}Rad_{n}(X) ≤ ∥Rad∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} ≤ 40K.

The left hand inequality follows from Kahane’s inequality (with best constant) when 1 ≤ p ≤ 2, and by duality when p > 2.

Remark: Going through the estimates in the proof of Theorem 2 and Theorem 4, we actually get the estimate: Rad_{n}(X) ≤ \sqrt{2}K.

3 The Operator Δ^{−α} and K-Convexity

In the proof of Theorem 4 we have used the fact that lim_{α→∞} Δ^{−α} = Rad. We have in fact the following stronger characterization of K-convexity:

Theorem 5 Let X be a Banach space. Then the following are equivalent:

1) X is K-convex.

2) For every α > 0 and 1 < p < ∞,

sup_{n} ∥Δ^{−α}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} < ∞.

3) There exist α > 0 and 1 < p ≤ ∞ such that

sup_{n} ∥Δ^{−α}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} < ∞.

Proof:

1)⟹2) Assume that X is K-convex and fix α > 0, 1 ≤ p < ∞. For every k = 0, 1, …, n, denote by R_{k} the projection:

R_{k}f = ∑_{|A|=k} f̂(A)W_{A}.

In particular R_{0}f = f̂(∅) and R_{1} = Rad. We first bound ∥R_{k}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)}. This part is a repetition of an argument from [16], in which it is stated for p = 2. Since 1 < p < ∞, L_{p}(Ω_{n}, X) is also K-convex. Pisier’s K-convexity theorem ([16] or see [13]) implies that there are ϕ, M > 0 such that if we define:

V = {z ∈ ℂ; Rez ≥ 0, |arg z| < ϕ},

and:

S_{z} = ∑_{k=0}^{n} e^{kz}R_{k},

then sup_{z∈V} ∥S_{z}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} ≤ M for all n (where X now denotes the complexification of the original X). Put a = \frac{π}{tanϕ}, since for all −π ≤ b ≤ π, a + ib ∈ V, we have for all k = 1, …, n:

∥R_{k}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} =
= ∥\frac{e^{ka}}{2π} ∫_{−π}^{π} S_{a+ib}e^{ib}db∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} ≤ Me^{ka}.

Since by (5):

Δ^{−α} = \frac{1}{Γ(α)} ∫_{0}^{1} t^{Δ−I}(I − R_{0}) (log \frac{1}{t})^{α−1} dt,

we get:

∥Δ^{−α}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} ≤

≤ \frac{1}{Γ(α)} ∥∫_{0}^{e^{−a}/2} t^{Δ−I}(I − R_{0}) (log \frac{1}{t})^{α−1} dt∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)}

+\frac{1}{Γ(α)} ∥∫_{e^{−a}/2}^{1} t^{Δ−I}(I − R_{0}) (log \frac{1}{t})^{α−1} dt∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)}

≤ \frac{2}{Γ(α)} ∫_{0}^{e^{−a}/2} ∥∑_{k=1}^{n} t^{k−1}R_{k}∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} (log \frac{1}{t})^{α−1} dt

+\frac{2}{Γ(α)} ∫_{e^{−a}/2}^{1} ∥\frac{T_{t}}{t} ∥_{L_{p}(Ω_{n},X)→L_{p}(Ω_{n},X)} (log \frac{1}{t})^{α−1} dt

≤ \frac{2}{Γ(α)} ∫_{0}^{e^{−a}/2} (∑_{k=1}^{n} t^{k−1}Me^{ka}) (log \frac{1}{t})^{α−1} dt

+\frac{2}{Γ(α)} ∫_{e^{−a}/2}^{1} \frac{1}{t} (log \frac{1}{t})^{α−1} dt

≤ \frac{2Me^{a}}{Γ(α)} ∫_{0}^{e^{−a}/2} \frac{1}{1 − te^{a}} (log \frac{1}{t})^{α−1} dt + \frac{4e^{a}}{Γ(α)} ∫_{0}^{1} (log \frac{1}{t})^{α−1} dt

≤ \frac{4Me^{a}}{Γ(α)} ∫_{0}^{1} (log \frac{1}{t})^{α−1} dt + 4e^{a} ≤ 4(M + 1)e^{a},

which is the required result.

3)⟹1) Another application of Pisier’s K-convexity theorem shows that if X is not K-convex then it contains ℓ_{1}^{n}’s uniformly. It is therefore enough to show that for every α > 0,

{∥Δ^{−α}∥_{L_{p}(Ω_{n},L_{1}(Ω_{n},ℝ))→L_{p}(Ω_{n},L_{1}(Ω_{n},ℝ))}|}_{n=1}^{∞}

is an unbounded sequence.

Define f ∈ L_{p}(Ω_{n}, L_{1}(Ω_{n}, ℝ)) by:

f(ω)(ω′) = 2^{n}1_{(1,...,1)}(ωω′) = ∑_{A⊂{1,...,n}} W_{A}(ω)W_{A}(ω′).

Then ∥f∥_{L_{p}(Ω_{n},L_{1}(Ω_{n},ℝ))} = 1 and:

Δ^{−α} f (ω)(ω′) =
= ∑_{∅≠A⊂\{1,...,n\}} \frac{1}{|A|^{α}} W_{A}(ω)W_{A}(ω′)

= \frac{1}{Γ(α)} ∫_{0}^{1} ( ∑_{∅≠A⊂\{1,...,n\}} t^{|A|−1}W_{A}(ω)W_{A}(ω′)) (log \frac{1}{t})^{α−1} dt

= \frac{1}{Γ(α)} ∫_{0}^{1} \frac{∏_{i=1}^{n}(1 + ω_{i}ω′_{i}t) − 1}{t} (log \frac{1}{t})^{α−1} dt.

Hence:

Γ(α)^{p}∥Δ^{−α}f∥_{L_{p}(Ω_{n},L_{1}(Ω_{n},ℝ))}^{p} =

= ∫_{Ω_{n}} (∫_{Ω_{n}} |∫_{0}^{1} \frac{∏_{i=1}^{n}(1 + ω_{i}ω′_{i}t) − 1}{t} (log \frac{1}{t})^{α−1} dt| dP_{n}(ω′))^{p} dP_{n}(ω)

= (∫_{Ω_{n}} |∫_{0}^{1} \frac{∏_{i=1}^{n}(1 + ω′_{i}t) − 1}{t} (log \frac{1}{t})^{α−1} dt| dP_{n}(ω′))^{p} .

For every ω ∈ Ω_{n} define:

N (ω) = |{1 ≤ i ≤ n; ω_{i} = −1}| .

By symmetry, P_{n} (N (ω) ≥ \frac{n}{2}) ≥ \frac{1}{2}. Hence, for n large enough:

∥Δ^{−α}f∥_{L_{p}(Ω_{n},L_{1}(Ω_{n},ℝ))}^{p} =
= \frac{1}{Γ(α)} ∫_{Ω_{n}} |∫_{0}^{1} \frac{(1 − t^{2})^{N (ω)}(1 + t)^{n−2N (ω)} − 1}{t} (log \frac{1}{t})^{α−1} dt| dP_{n}(ω)

≥ \frac{1}{2Γ(α)} ∫_{1/\sqrt{n}}^{1} \frac{1 − (1 − t^{2})^{n/2}}{t} (log \frac{1}{t})^{α−1} dt

≥ \frac{1}{2Γ(α)} (1 − \frac{1}{e}) ∫_{1/\sqrt{n}}^{1} \frac{(log \frac{1}{t})^{α−1}}{t}
= \frac{1}{2Γ(α)} (1 − \frac{1}{e}) \frac{log \sqrt{n}}{α}.

Remark: It follows that for K-convex spaces, the right hand side of the inequality in the statement of Theorem 2 is larger than the right hand side of the inequality in the statement of Theorem 1.

4 Applications to the Geometry of Banach Spaces

In this section we apply Theorem 1 to prove the geometric results that were announced in the introduction. Recall that a subset C = {x_{ϵ}}_{ϵ∈Ω_{n}} of a Banach space X is called an n-dimensional cube. As in the introduction, we denote by edge(C) and diag(C) the set of edges and diagonals of an n-dimensional cube C ⊂ X, respectively. For every u, v ∈ Ω_{n} we write u ∼ v if u and v differ in exactly one coordinate.

Theorem 6 Let X be a UMD Banach space and p > 1. Then the following are equivalent:

1) X has type p.

2) For every 1 < q < ∞ there is a constant K > 0 such that for every n-dimensional cube C ⊂ X:

∑_{{a,b}∈diag(C)} ∥a − b∥^{q} ≤ K ∑_{u∈C} (∑_{v∼u} ∥u − v∥^{p})^{q/p} .

3) There is some 1 < q < ∞ and K > 0 such that for every n-dimensional cube C ⊂ X:

∑_{{a,b}∈diag(C)} ∥a − b∥^{q} ≤ K ∑_{u∈C} (∑_{v∼u} ∥u − v∥^{p})^{q/p} .

Proof:

1) ⟹ 2) By Theorem 1 for every 1 < q < ∞ there is a constant K > 0 such that for every n and for every f ∈ L_{q}(Ω_{n}, X):

∥f − ∫_{Ω_{n}} fdP_{n}∥_{L_{q}(Ω_{n},X)} ≤ K ∥∑_{i=1}^{n} ω′_{i}D_{i}f(ω)∥_{L_{q}(Ω_{n}×Ω_{n},X)} .

Recall that by Kahane’s inequality, the fact that X has type p implies that for every 1 ≤ q < ∞ there is a constant T_{q} such that for every x_{1}, …, x_{n} ∈ X,

∫_{Ω_{n}} ∥∑_{i=1}^{n} ω′_{i}x_{i}∥^{q} dP_{n}(ω′) ≤ T_{q} (∑_{i=1}^{n} ∥x_{i}∥^{p})^{q/p} .

If C = {x_{ω}}_{ω∈Ω_{n}} is a cube in X define f : Ω_{n} → X by f(ω) = x_{ω}. Now:

∑_{{a,b}∈diag(C)} ∥ a − b∥^{q} =

= 2^{n} ∫_{Ω_{n}} ∥f(ω) − f(−ω)∥^{q} dP_{n}
≤ 2^{n} · 2^{q−1} ∫_{Ω_{n}} ∥f − ∫_{Ω_{n}} fdP_{n}∥^{q} dP_{n}

≤ 2^{n+q−1}K^{q} ∫_{Ω_{n}×Ω_{n}} ∥∑_{i=1}^{n} ω′_{i}D_{i}f(ω)∥^{q} dP_{n}(ω′)dP_{n}(ω)

≤ 2^{n+q−1}K^{q}T_{q} ∫_{Ω_{n}} (∑_{i=1}^{n} ∥D_{i}f(ω)∥^{p})^{q/p} dP_{n}(ω)

= \frac{K^{q}T_{q}}{2} ∑_{u∈C} (∑_{v∼u} ∥u − v∥^{p})^{q/p} .

3) ⟹ 1) Fix x_{1}, …, x_{n} ∈ X. Define a cube C = {z_{ϵ}}_{ϵ∈Ω_{n}} by:

z_{ϵ} = ∑_{i=1}^{n} ϵ_{i}x_{i}.

Then, by Kahane’s inequality :

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

≤ C_{q} (𝔼 ∥∑_{i=1}^{n} ϵ_{i}x_{i}∥^{q})^{1/q}

= \frac{C_{q}}{2} (\frac{1}{2^{n}} ∑_{\{a,b\}∈diag(C)} ∥a − b∥^{q})^{1/q}

≤ \frac{KC_{q}}{2} [\frac{1}{2^{n}} ∑_{u∈C} (∑_{v∼u} ∥u − v∥^{p})^{q/p}]^{1/q}

= \frac{KC_{q}}{2} (∑_{i=1}^{n} ∥x_{i}∥^{p})^{1/p} ,

so that X has type p.

Remark: The case q = p in Theorem 6 shows that for UMD Banach spaces, Enflo type is equivalent to type. The question whether this holds for a general Banach space was raised in [8]. Unfortunately, there are examples of Banach spaces with non trivial type which are not UMD [15] (although we can safely say that these can’t be found among “common” Banach spaces).

Remark: A simple application of Theorem 6 shows that for UMD spaces both type and Enflo type imply non-linear type. This answers, for the class of UMD spaces, questions posed by Bourgain, Milman and Wolfson [3] and Pisier [17]. Indeed, if X is UMD and has either type p or Enflo type p then, since necessarily p ≤ 2, by Theorem 6 there is a constant K > 0 such that for every n-dimensional cube C ⊂ X:

∑_{{a,b}∈diag(C)} ∥a − b∥^{2} ≤

≤ K ∑_{u∈C} (∑_{v∼u} ∥u − v∥^{p})^{2/p}
≤ Kn^{\frac{2}{p} −1} ∑_{\{u,v\}∈edge(C)} ∥u − v∥^{2}.

We now prove a non-linear analogue of the fact that “equal norm type 2” implies type 2.

Theorem 7 Let X be a UMD Banach space and 1 < p, q < ∞. Then the following are equivalent:

1) There is a constant K > 0 such that for every n-dimensional cube C ⊂ X:

∑_{{a,b}∈diag(C)} ∥a − b∥^{p} ≤ K ∑_{u∈C} (∑_{v∼u} ∥u − v∥^{2})^{p/2} .

2) There is a constant K > 0 such that for every n-dimensional cube C ⊂ X with the property that for every {u, v} ∈ edge(C), ∥u − v∥ = 1:

∑_{{a,b}∈diag(C)} ∥a − b∥^{q} ≤ K2^{n}n^{q/2}.

Proof: The implication 1) ⟹ 2) is an application of Theorem 6. In the other direction, repeating the argument that appeared in the proof of Theorem 6 we get that for every x_{1}, …, x_{n} ∈ X such that for every i = 1, …, n, ∥x_{i}∥ = 1,

(𝔼 ∥∑_{i=1}^{n} ϵ_{i}x_{i}∥^{2})^{1/2} ≤ K′\sqrt{n}.

Hence, X has “equal norm type” 2, which implies that X has type 2 ( This is a well known observation of Pisier. See [9]). Another application of Theorem 6 gives the required result.

Finally, we settle the gap noticed by Matoušek [11] concerning lower bounds on the distortion required to embed Hamming cubes in L_{p}, p > 2 (or more generally, in UMD spaces of type p):

Theorem 8 Let X be a UMD Banach space with type p. Then there is a constant c > 0 such that for every n, c_{X}(Ω_{n}, ∥ · ∥_{1})) ≥ cn^{1− \frac{1}{p}}.

Proof: Let f : Ω_{n} → X be an embedding such that for every ω, ω′ ∈ Ω_{n},

∥ω − ω′∥_{1} ≤ ∥f(ω) − f(ω′)∥ ≤ L∥ω − ω′∥_{1}.

Now, C = {f(ω)}_{ω∈Ω_{n}} defines a cube in X. Clearly |diag(C)| = 2^{n} and |edge(C)| = n2^{n}. Since by Theorem 6, X has Enflo type p, there is a constant K > 0 such that:

2^{n}n^{p} ≤
≤ ∑_{{a,b}∈diag(C)} d(a, b)^{p}
≤ K ∑_{{u,v}∈edge(C)} d(u, v)^{p} ≤ Kn2^{n}L^{p}.

Hence L ≥ \frac{1}{K^{1/p}} · n^{1− \frac{1}{p}}.

5 Concluding Remarks

Our original motivation for studying non-linear type, came from a problem concerning the notion of Markov type. Let (M, d) be a metric space. A stochastic process {Z_{k}}_{k=0}^{∞} is called a symmetric Markov chain on M if it is a stationary Markov chain whose state space is a finite subset of M with a symmetric transition matrix and such that Z_{0} is uniformly distributed. In other words, there are x_{1}, …, x_{m} ∈ M and a symmetric stochastic m × m matrix A, such that for every k, P (Z_{k+1} = x_{j}|Z_{k} = x_{i}) = a_{ij} and P (Z_{0} = x_{i}) = \frac{1}{m} for every 1 ≤ i, j ≤ m. The space M is said to have Markov type p > 0 if there is a constant K > 0 such that for every symmetric Markov chain on M, {Z_{k}}_{k=0}^{∞}, and for every n, 𝔼d(Z_{n}, Z_{0})^{p} ≤ K^{p}n𝔼d(Z_{1}, Z_{0})^{p}. The least such K is denoted by M_{p}(M). This notion was introduce by K. Ball in [1] in connection with extension problems for Lipschitz maps. As is the case with other non-linear notions of type, Markov type proved itself useful in Lipschitz embedding problems (see [10]). In [1], Ball posed the problem whether L_{p}, 2 < p < ∞, has Markov type 2. Apart from the intrinsic geometric and probabilistic interest in this question, a positive solution would imply results concerning extensions of Lipschitz function between L_{p} spaces and give lower bound on the distortion required to embed graphs with large girth in L_{p}, p > 2 (see [1],[10] for more details). Our starting point was the following

Proposition 1 Let (M, d) be a metric space with Markov type p ≥ 1. Then M also has Enflo type p. To be more precise, for every n-dimensional cube C ⊂ M:

∑_{{a,b}∈diag(C)} d(a, b)^{p} ≤ 24 · 6^{p}M_{p}(M)^{p} ∑_{{α,β}∈edge(C)} d(α, β)^{p}.

Having realized that a positive solution to the Markov type 2 problem would imply that L_{p}, 2 < p < ∞ has Enflo type 2, it was somewhat discouraging that the only space that was known to have Enflo type 2 was Hilbert space. The purpose of this article was to remedy this. The class of spaces with Enflo type 2 is now known to include UMD spaces with linear type 2 (particularly L_{p}, 2 < p < ∞), and as we shall see below, metric trees also have Enflo type 2. Unfortunately, we are unable to prove a result in the reverse direction of Proposition 1.

In this section we will prove Proposition 1, and then proceed to study the Markov type of trees. Denote by H the Hamming metric on Ω_{n}:

H(ω, τ) = |{1 ≤ i ≤ n; ω_{i} ≠ τ_{i}}|.

We will begin with the following technical lemma:

Lemma 2 Let (M, d) be a metric space and f : Ω_{n} → M. For every p ≥ 1 and every integer \frac{n}{3} ≤ k ≤ n the following inequality holds:

∑_{H(u,v)=n} d(f(u) , f(v))^{p} ≤

≤ \frac{6^{p}}{2\binom{n}{k}} ∑_{H(u,v)=k} d(f(u), f(v))^{p} + \frac{2^{p−1}}{n} ∑_{H(u,v)=1} d(f(u), f(v))^{p}.

Proof: For every u, v ∈ Ω_{n} define:

A(u, v) = {(a, b) ∈ Ω_{n} × Ω_{n}; H(u, a) = H(a, b) = H(b, v) = k}.

Assume first that n − k is even. In this case, whenever H(u, v) = n, A(u, v) ≠ ∅. Indeed, let a be any element of Ω_{n} which is obtained from u by flipping k coordinated, and b be any vector which is obtained from a by flipping \frac{3k−n}{2} of those k coordinates, and \frac{n−k}{2} of the remaining n − k coordinates. It is easy to check that in this case (a, b) ∈ A(u, v) (the conditions k ≥ n/3 and n − k even ensure that (n − k)/2 and (3k − n)/2 are integers). By symmetry, the size of A(u, v) does not depend on the choice of u, v with H(u, v) = n. Denote this size by N. Again, the symmetry of the cube implies that if we consider the union of all the (3 · 2^{n})-tuples ((u, a_{uv}), (a_{uv}, b_{uv}), (b_{uv}, v))_{H(u,v)=n} over all possible choices of (a_{uv}, b_{uv}) ∈ A(u, v) for each u, v ∈ Ω_{n} with H(u, v) = n, then each pair (x, y) ∈ Ω_{n} × Ω_{n} with H(x, y) = k appears in it with the same multiplicity, say M. The total number of these (3 · 2^{n})-tuples is N^{2^{n}}, since there are 2^{n} pairs (u, v) ∈ Ω_{n} × Ω_{n} with H(u, v) = n. On the other hand, since there are 2^{n}\binom{n}{k} pairs (x, y) ∈ Ω_{n} × Ω_{n} with H(x, y) = k, it follows that

3 · 2^{n} · N^{2^{n}} = M · 2^{n} · \binom{n}{k}.

For every (u, v) ∈ Ω_{n} × Ω_{n} choose (a_{uv}, b_{uv}) ∈ A(u, v). Then:

∑_{H(u,v)=n} d (f(u), f(v))^{p} ≤
≤ ∑_{H(u,v)=n}[d(f(u), f(a_{uv})) + d(f(a_{uv}), f(b_{uv})) + d(f(b_{uv}), f(v))]^{p}
≤ 3^{p−1} ∑_{H(u,v)=n}[d(f(u), f(a_{uv})^{p} + d(f(a_{uv}, b_{uv}))^{p} + d(f(b_{uv}), f(v))^{p}].

Summing up over all possible choices of (a_{uv}, b_{uv}) we get that:

N^{2^{n}} ∑_{H(u,v)=n} d(f(u), f(v))^{p} ≤ 3^{p−1}M ∑_{H(u,v)=k} d(f(u), f(v))^{p},

so that:

∑_{H(u,v)=n} d(f(u), f(v))^{p} ≤ \frac{3^{p}}{\binom{n}{k}} ∑_{H(u,v)=k} d(f(u), f(v))^{p}.

This proves the required result (when n − k is even).

When n−k is odd the proof is similar, with an added complication since in this case A(u, v) = ∅ when H(u, v) = n. We proceed as follows. Similar to the above reasoning, A(u, v) ≠ ∅ whenever H(u, v) = n − 1. In this case denote the size of A(u, v) by N_{1}. Let M_{1} be the multiplicity of each pair of points with Hamming distance k in the union of all the (3n2^{n})-tuples ((u, a_{uv}), (a_{uv}, b_{uv}), (b_{uv}, v))_{H(u,v)=n−1} over all possible choices of (a_{uv}, b_{uv}) ∈ A(u, v) for each u, v ∈ Ω_{n} with H(u, v) = n − 1. We get that:

3n2^{n}N_{1}^{n2^{n}} = M_{1}2^{n}\binom{n}{k}.

Applying the triangle inequality as before we get:

N_{1}^{n2^{n}} ∑_{H(u,v)=n−1} d(f(u), f(v))^{p} ≤ 3^{p−1}M_{1} ∑_{H(u,v)=k} d(f(u), f(v))^{p},

so that:

∑_{H(u,v)=n−1} d(f(u), f(v))^{p} ≤ \frac{3^{p}n}{\binom{n}{k}} ∑_{H(u,v)=k} d(f(u), f(v))^{p}.

For every E ⊂ {1, … n} and x ∈ Ω_{n} denote by S_{E}(x) the vector obtained from x by flipping the coordinates in E. Now:

∑_{H(u,v)=n} d(f(u), f(v))^{p} ≤

≤ \frac{1}{n} ∑_{|E|=n−1} ∑_{H(u,v)=n}[d(f(u), f(S_{E}(u))) + d(f(S_{E}(u)), f(v))]^{p}

≤ \frac{2^{p−1}}{n} ∑_{|E|=n−1} ∑_{H(u,v)=n}[d(f(u), f(S_{E}(u)))^{p} + d(f(S_{E}(u)), f(v))^{p}]

= \frac{2^{p−1}}{n} ∑_{H(u,v)=n−1} d(f(u), f(v))^{p} + \frac{2^{p−1}}{n} ∑_{H(u,v)=1} d(f(u), f(v))^{p}

≤ \frac{6^{p}}{2\binom{n}{k}} ∑_{H(u,v)=k} d(f(u), f(v))^{p} + \frac{2^{p−1}}{n} ∑_{H(u,v)=1} d(f(u), f(v))^{p}.

Proof of Proposition 1 Fix an integer n. Let {Z_{k}}_{k=0}^{∞} be the standard random walk on Ω_{n}, i.e. Z_{0} is uniformly distributed on Ω_{n} and Z_{k+1} flips each coordinate of Z_{k} with probability \frac{1}{n}. Clearly,

𝔼(H(Z_{k+1} , Z_{0})|H(Z_{k}, Z_{0})) =
= [H(Z_{k}, Z_{0}) + 1]\frac{n − H(Z_{k}, Z_{0})}{n} + [H(Z_{k}, Z_{0}) − 1]\frac{H(Z_{k}, Z_{0})}{n}
= (1 − \frac{2}{n}) H(Z_{k}, Z_{0}) + 1.

Hence:

𝔼H(Z_{k+1}, Z_{0}) = 𝔼[𝔼(H(Z_{k+1}, Z_{0})|H(Z_{k}, Z_{0}))] = (1 − \frac{2}{n}) 𝔼H(Z_{k}, Z_{0}) + 1.

Solving the recursion we get that:

𝔼H(Z_{k}, Z_{0}) = \frac{n}{2} [1 − (1 − \frac{2}{n})^{k}] .

Now, 𝔼H(Z_{n}, Z_{0}) ≥ \frac{n}{2} (1 − \frac{1}{e^{2}} ) ≥ \frac{3n}{8}. Hence:

\frac{3n}{8} ≤ 𝔼H(Z_{n}, Z_{0}) ≤ \frac{n}{3} + nP (H(Z_{n}, Z_{0}) ≥ \frac{n}{3}) ,

so that P (H(Z_{n}, Z_{0}) ≥ \frac{n}{3}) ≥ \frac{1}{24}.

Now, fix a function f : Ω_{n} → M. Using the the Markov type p condition for the symmetric Markov chain {f(Z_{k})}_{k=0}^{∞} we get:

𝔼d(f(Z_{n}), f(Z_{0}))^{p} ≤ M_{p}(M)^{p}n𝔼d(f(Z_{1}), f(Z_{0}))^{p}
= \frac{M_{p}(M)^{p}}{2^{n}} ∑_{H(u,v)=1} d(f(u), f(v))^{p}.

On the other hand, applying Lemma 2 we get that:

𝔼 d (f(Z_{n}), f(Z_{0}))^{p} ≥
≥ ∑_{k≥n/3} P (H(Z_{n}, Z_{0}) = k)𝔼(d(f(Z_{n}), f(Z_{0}))^{p}|H(Z_{n}, Z_{0}) = k)

= ∑_{k≥n/3} P (H(Z_{n}, Z_{0}) = k)\frac{1}{2^{n}\binom{n}{k}} ∑_{H(u,v)=k} d(f(u), f(v))^{p}

≥ \frac{P (H(Z_{n}, Z_{0}) ≥ n/3)}{6^{p}2^{n−1}} [ ∑_{H(u,v)=n} d(f(u), f(v))^{p}

−\frac{2^{p−1}}{n} ∑_{H(u,v)=1} d(f(u), f(v))^{p}] ,

and this implies the required result.

We end by adding one more family of metric spaces to the class of spaces with non-linear type 2, namely we will prove that metric trees have type 2. This fact was noticed by the first named author in collaboration with Nathan Linial. We thank him for his kind permission to include the proof here.

A metric space X is a metric tree provided it is metrically convex and there is a unique arc joining each pair of points in X. Note that metric convexity implies that the unique arc joining a pair of points in a metric tree must be a geodesic arc. For more information on metric trees we refer to the book [5].

Proposition 2 Let T be a metric tree. Then T has roundness 2 (i.e. Enflo type 2 with constant 1).

Proof: As remarked in the introduction, a simple tenzorization argument shows that it is enough to prove the roundness 2 condition for 2 dimensional cubes in T . Any four point in T must be in the following “double fork” configuration:

Hence, depending on whether {x, w}, {x, y} or {x, z} are taken to be diagonals, our claim reduces to the following three inequalities which should hold for every a, b, c, d, e ≥ 0:

(a + c + e)^{2} + (b + c + d)^{2} ≤ (a + b)^{2} + (d + e)^{2} + (a + c + d)^{2} + (b + c + e)^{2},

(a + b)^{2} + (d + e)^{2} ≤ (a + c + d)^{2} + (a + c + e)^{2} + (b + c + e)^{2} + (b + c + d)^{2},
(a + c + d)^{2} + (b + c + e)^{2} ≤ (a + b)^{2} + (d + e)^{2} + (a + c + e)^{2} + (b + c + d)^{2}.

Expanding the squares, these inequalities are easy to verify.

Remark: Proposition 2 shows that in the non-linear setting, even ℓ_{1} objects such as metric trees can have type 2. Since metric trees contain line segments, they cannot have Enflo type greater than 2. We do not know whether metric trees have Markov type 2.

References

[1] Ball K., Markov Chains, Riesz Transforms and Lipschitz Maps. Geometric and Functional Analysis 2, 137–172 (1992).

[2] Benyamini, Y; Lindenstrauss, J. Geometric nonlinear functional analysis. Vol. 1. American Mathematical Society Colloquium Publications, 48. American Mathematical Society, Providence, RI, 2000.

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

[4] Burkholder D.L. Martingales and Singular Integrals in Banach Spaces. Handbook of the Geometry of Banach Spaces, volume 1, 233-269, edited by W.B. Johnson and J. Lindenstrauss, Elsevier, Amsterdam 2001.

[5] Deza, M.; Laurent, M. Geometry of cuts and metrics. Algorithms and Combinatorics, 15. Springer-Verlag, Berlin, 1997.

[6] Enflo, P. Topological groups in which multiplication on one side is differentiable or linear. Math. Scand. 24 1969 195–207 (1970).

[7] Enflo, P. Uniform structures and square roots in topological groups. I, II. Israel J. Math. 8 (1970), 230-252; ibid. 8 1970 253–272.

[8] Enflo, P. On infinite-dimensional topological groups. Seminaire sur la Geometrie des Espaces de Banach (1977–1978), Exp. No. 10–11, 11 pp., Ecole Polytech., Palaiseau, 1978.

[9] James R. Nonreflexive spaces of type 2. Israel Journ. Math. 30 (1978), 1–13.

[10] Linial, N.; Magen, A.; Naor, A.; Girth and Euclidean Distortion. To appear in Geometric and Functional Analysis.

[11] Matoušek J. Embedding expanders into ℓ_{p}, Israel Journ. Math. 102 (1997), 189–197.

[12] Maurey B. Système de Haar, Séminaire Maurey-Schwartz, 1974-1975, École Polytechnique, Paris (1975)

[13] Milman, V. D.; Schechtman, G. Asymptotic theory of finite-dimensional normed spaces. With an appendix by M. Gromov. Lecture Notes in Mathematics, 1200. Springer-Verlag, Berlin, 1986.

[14] Pisier, G. Sur les espaces qui ne contiennent pas de l_{n}^{1} uniformement. Seminaire Maurey-Schwartz (1973–1974), Espaces L^{p}, applications radonifiantes et geometrie des espaces de Banach, Exp. No. 7, 19 pp. (errata, p. E.1) Centre de Math., Ecole Polytech., Paris, 1974.

[15] Pisier, G. Un exemple concernant la super-réflexivité. Séminaire Maurey-Schwartz, 1974-1975, École Polytechnique, Paris (1975).

[16] Pisier, G. Holomorphic semigroups and the geometry of Banach spaces. Ann. of Math. (2) 115 (1982), no. 2, 375–392.

[17] Pisier, G. Probabilistic methods in the geometry of Banach spaces. Probability and analysis (Varenna, 1985), 167–241, Lecture Notes in Math., 1206, Springer, Berlin, 1986.

[18] Talagrand, M. Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. Geom. Funct. Anal. 3 (1993), no. 3, 295–314.

[19] Wagner, R. Notes on an inequality by Pisier for functions on the discrete cube. Geometric aspects of functional analysis, 263–268, Lecture Notes in Math., 1745, Springer, Berlin, 2000.

Mathematics Subject Classification (2000): Primary: 46B07, 46B20; Secondary: 54E35.

Assaf Naor Institute of Mathematics Hebrew University Jerusalem 91904, Israel E-mail: naor@math.huji.ac.il

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