Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces

Tim Austin^{∗} ; Brown

Assaf Naor^{†} Courant Institute Romain Tessera E.N.S. Lyon

Abstract Let ℍ denote the discrete Heisenberg group, equipped with a word metric d_{W} associated to some finite symmetric generating set. We show that if (X, ∥ · ∥) is a p-convex Banach space then for any Lipschitz function f : ℍ → X there exist x, y ∈ ℍ with d_{W} (x, y) arbitrarily large and

\frac{∥f(x) − f(y)∥}{d_{W} (x, y)} ≲ (\frac{log log d_{W} (x, y)}{log d_{W} (x, y)})^{1/p} .  (1)

We also show that any embedding into X of a ball of radius R ⩾ 4 in ℍ incurs bi-Lipschitz distortion that grows at least as a constant multiple of

(\frac{log R}{log log R})^{1/p} .  (2)

Both (1) and (2) are sharp up to the iterated logarithm terms. When X is Hilbert space we obtain a representation-theoretic proof yielding bounds corresponding to (1) and (2) which are sharp up to a universal constant.

1 Introduction

Let ℍ =^{def} ⟨a, b| aba^{−1}b^{−1} is central⟩ denote the discrete Heisenberg group, with canonical generators a, b ∈ ℍ. We let d_{W} (·, ·) denote the left-invariant word metric on ℍ associated to the symmetric generating set S =^{def} {a, b, a^{−1}, b^{−1}}.

A Banach space (X, ∥ · ∥_{X}) is superreflexive if it admits an equivalent uniformly convex norm, i.e., a norm ∥ · ∥ satisfying α∥x∥_{X} ⩽ ∥x∥ ⩽ β∥x∥_{X} for some α, β > 0 and all x ∈ X, such that for all ε ∈ (0, 1) there exists δ > 0 for which we have

∥x∥ = ∥y∥ = 1 ∧ ∥x − y∥ = ε ⟹ ∥x + y∥ ⩽ 2 − δ.  (3)

Here we prove the following result:

Theorem 1.1. Let (X, ∥ · ∥_{X}) be a superreflexive Banach space. Then there exist c, C > 0 such that for every f : ℍ → X which is 1-Lipschitz with respect to the metric d_{W}, there are x, y ∈ X with d_{W} (x, y) arbitrarily large and

\frac{∥f(x) − f(y)∥_{X}}{d_{W} (x, y)} ⩽ \frac{C}{(log d_{W} (x, y))^{c}} .

∗Partially supported by a fellowship from Microsoft Corporation.

†Supported by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

The fact that ℍ does not admit a bi-Lipschitz embedding into any superreflexive Banach space was proved in [18, 7]. These proofs use an argument of Semmes [25], based on a natural extension of Pansu’s differentiability theorem [22].

A natural way to quantify the extent to which ℍ does not admit a bi-Lipschitz embedding into (X, ∥ · ∥_{X}) is via Gromov’s notion [13, Sec. 7.3] of compression rate, defined for a Lipschitz function f : ℍ → X as the largest function ω_{f} : (0, ∞) → [0, ∞) such that for all x, y ∈ ℍ we have ∥f(x) − f(y)∥_{X} ⩾ ω_{f} (d_{W} (x, y)). The fact that ℍ does not admit a bi-Lipschitz embedding into a superreflexive Banach space X means that lim inf_{t→∞} ω_{f}(t)/t = 0 for all Lipschitz functions f : ℍ → X. The differentiability-based proof of this nonembeddability result involves a limiting argument that does not give information on the rate at which ω_{f}(t)/t vanishes. Theorem 1.1 supplies such information, via an approach which is different from the arguments in [18, 7].

Cheeger and Kleiner proved [6] that ℍ does not admit a bi-Lipschitz embedding into L_{1}. In [8] it was shown that there exists c > 0 such that for any Lipschitz function f : ℍ → L_{1} we have ω_{f}(t)/t ⩽ 1/(log t)^{c} for arbitrarily large t. This result covers Theorem 1.1 when the superreflexive Banach space X admits a bi-Lipschitz embedding into L_{1}: such spaces include L_{p} for p ∈ (1, 2]. Theorem 1.1 is new even for spaces such as L_{p} for p ∈ (2, ∞), which do not admit a bi-Lipschitz embedding into L_{1} (see [3]). Moreover, our method yields sharp results, while the constant c obtained in [8] is far from sharp.

In order to state our sharp version of Theorem 1.1, we recall the following important theorem of Pisier [23, Thm. 3.1]: if X is superreflexive then it admits an equivalent norm ∥ · ∥ for which there exist p ⩾ 2 and K > 0 satisfying the following improvement of (3):

∀x, y ∈ X, ∥\frac{x + y}{2} ∥^{p} ⩽ \frac{∥x∥^{p} + ∥y∥^{p}}{2} − \frac{1}{K^{p}} ∥\frac{x − y}{2} ∥^{p} .  (4)

A Banach space admitting an equivalent norm satisfying (4) is said to be p-convex. If (X, ∥ · ∥) satisfies (4) then the infimum over those K > 0 satisfying (4) is denoted K_{p}(X). For concreteness, when p ∈ (1, 2] we have K_{2}(L_{p}) ⩽ 1/\sqrt{p − 1} and for p ⩾ 2 we have K_{p}(L_{p}) ⩽ 1 (see [2]).

The following theorem is a refinement of Theorem 1.1.

Theorem 1.2. Assume that the Banach space (X, ∥·∥) satisfies (4). Let f : ℍ → X be a 1-Lipschitz function. Then for every t ⩾ 3 there exists an integer t ⩽ n ⩽ t^{2} such that^{1}

\frac{ω_{f}(n)}{n} ≲ K_{p}(X) (\frac{log log n}{log n})^{1/p} .  (5)

The estimate (5) is sharp up to the iterated logarithm term. Indeed, L_{p} is p-convex when p ∈ [2, ∞), and in [26, 27] it was shown that there exists f : ℍ → L_{p} satisfying

\frac{ω_{f}(n)}{n} ≳ \frac{1}{(log n)^{1/p} log log n}

for all n ⩾ 3 (we refer to [27] for a more refined result of this type).

Our proof of Theorem 1.2 circumvents the difficulties involved with proving quantitative variants of differentiability results by avoiding the need to reason about arbitrary Lipschitz mappings.

1In (5), and in the rest of this paper, the notation ≲, ≳ denotes the corresponding inequalities up to a universal multiplicative factor. The notation A ≍ B stands for A ≲ B ∧ B ≲ A.

Instead, we start by using a simple result from [21] which reduces the problem to equivariant mappings. Specifically, in [21, Thm. 9.1] it is shown that if X satisfies (4) and f : ℍ → X is 1-Lipschitz, then there exists a Banach space Y that also satisfies (4), with K_{p}(Y) = K_{p}(X) (in fact, Y is finitely representable in ℓ_{p}(X)), an action π of ℍ on Y by linear isometric automorphisms, and a 1-cocycle F : ℍ → Y (i.e., F (xy) = π(x)F (y)+F (x) for all x, y ∈ ℍ) with ω_{F} = ω_{f}. Thus, in proving Theorem 1.2 it suffices to assume that f itself is a 1-cocycle. We note that if X is Hilbert space then Y is also Hilbert space; this is an older result of Gromov (see [10]). More generally, when X = L_{p} then it is shown in [21] that we can take Y = L_{p}.

Having reduced the problem to 1-cocycles, our starting point is a (non-quantitative) proof, explained in Section 2, showing that if X is an ergodic Banach space, then for every 1-cocycle f : ℍ → X we have lim inf_{t→∞} ω_{f}(t)/t = 0. It turns out that the ideas of this proof, which crucially use the fact that f is a 1-cocycle, can be (nontrivially) adapted to yield Theorem 1.2.

Recall that X is ergodic if for every linear isometry T : X → X and every x ∈ X the sequence \{\frac{1}{n} ∑_{j=0}^{n−1} T^{j}x\}_{n=1}^{∞} converges in norm. Reflexive spaces, and hence also superreflexive spaces, are ergodic (see [11, p. 662]). If a Banach space X has the property that all Banach spaces that are finitely representable in X are ergodic, then X must be superreflexive [4]. Thus, when using the reduction to 1-cocyles based on the result of [21], the class of Banach spaces to which it naturally applies is the class of superreflexive spaces.

1.1 Bi-Lipschitz distortion of balls

For R ⩾ 1 let B_{R} = {x ∈ ℍ : d_{W} (e, x) ⩽ R} denote the ball of radius R centered at the identity element e ∈ ℍ. The bi-Lipschitz distortion of (B_{R}, d_{W}) in (X, ∥·∥), denoted c_{X}(B_{R}), is the infimum over those D ⩾ 1 such that there exists f : B_{R} → X satisfying

∀ x, y ∈ B_{R}, d_{W} (x, y) ⩽ ∥f(x) − f(y)∥ ⩽ Dd_{W} (x, y).  (6)

Another way to measure the extent to which ℍ does not admit a bi-Lipschitz embedding into X is via the rate at which c_{X}(B_{R}) grows to ∞ with R. In [8] it was shown that

c_{L_{1}}(B_{R}) ≳ (log R)^{c}  (7)

for some universal constant c > 0. This result is of importance due to an application to theoretical computer science; see [9, 8, 20] for a detailed discussion. Evaluating the supremum over those c > 0 satisfying (7) remains an important open problem. Theorem 1.2 implies the following sharp bound on the bi-Lipschitz distortion of B_{R} into a p-convex Banach space:

Theorem 1.3. If a Banach space (X, ∥ · ∥) satisfies (4) then for every R ⩾ 4 we have

c_{X}(B_{R}) ≳ \frac{1}{K_{p}(X)} (\frac{log R}{log log R})^{1/p} .

Thus in particular for p ∈ (1, 2] we have c_{L_{p}}(B_{R}) ≳ \sqrt{p − 1} · (log R)^{\frac{1}{2} −o(1)} and for p ⩾ 2 we have c_{L_{p}}(B_{R}) ≳ (log R)^{\frac{1}{p} −o(1)}. Theorem 1.3 is a formal consequence of Theorem 1.2. The simple deduction of Theorem 1.3 from Theorem 1.2 is presented in Section 6. It follows from the results of [1, 24] (see the explanation in [15, 27]) that for every p ⩾ 2 we have c_{L_{p}}(B_{R}) ≲ (log R)^{1/p}. Thus Theorem 1.3 is sharp up to iterated logarithms.

1.2 The case of Hilbert space

In section 7 we prove the following Poincaré-type inequality for functions on ℍ taking value in Hilbert space:

Theorem 1.4. For every f : ℍ → L_{2} and every R ∈ ℕ we have

∑_{x∈B_{R}} ∑_{k=1}^{R^{2}} \frac{∥f(xc^{k}) − f(x)∥_{2}^{2}}{k^{2}} ≲ ∑_{x∈B_{22R}} (∥f(xa) − f(x)∥_{2}^{2} + ∥f(xb) − f(x)∥_{2}^{2}) .  (8)

This result has the following two sharp consequences. First, assume that θ : (0, ∞) → [0, ∞) is nondecreasing, and that θ ⩽ ω_{f} for some 1-Lipschitz f : ℍ → L_{2}. Then since |B_{22R}| ≍ |B_{R}| and d_{W} (c^{k}, e) ≍ \sqrt{k} for all k ∈ ℕ, inequality (8) implies that

\frac{1}{2} ∫_{1}^{∞} \frac{θ (t)^{2}}{t^{3}} dt = ∫_{1}^{∞} \frac{θ (\sqrt{s})^{2}}{s^{2}} ds ≲ ∑_{k=1}^{∞} \frac{θ (\sqrt{k})^{2}}{k^{2}} ≲ 1.  (9)

Combined with [26, Theorem 1], we obtain

Corollary 1.5. A nondecreasing function θ : (0, ∞) → [0, ∞) satisfies θ ⩽ ω_{f} for some Lipschitz function f : ℍ → L_{2} if and only if

∫_{1}^{∞} (\frac{θ(t)}{t})^{2} \frac{dt}{t} < ∞.  (10)

A second corollary of Theorem 1.4 yields a sharp bound (up to universal constants) on c_{L_{2}}(B_{R}). Indeed, fix R ⩾ 2 and assume that f : B_{R} → L_{2} satisfies d_{W} (x, y) ⩽ ∥f(x)−f(y)∥ ⩽ Dd_{W} (x, y) for all x, y ∈ B_{R}. Let f^{∗} : ℍ → L_{2} have Lipschitz constant at most 2D and coincide with f on B_{R/2} (see equation (41) for an explicit formula defining such an extension f^{∗}). It follows from (8) applied to f^{∗} that D^{2} ≳ ∑_{k=1}^{R} \frac{1}{k} ≳ log R. Thus c_{L_{2}}(B_{R}) ≳ \sqrt{log R}. In conjunction with the previously quoted upper bound on c_{L_{2}}(B_{R}), we have

Corollary 1.6. For every R ⩾ 2 we have c_{L_{2}}(B_{R}) ≍ \sqrt{log R}.

Roughly speaking, the proof of Theorem 1.4 proceeds via a reduction to the case of 1-cocycles corresponding to the irreducible representations of ℍ (see Section 7). But actually, since the representation theory of the continuous Heisenberg group is simpler than the representation theory of the discrete Heisenberg group ℍ, we first apply a discretization argument which reduces Theorem 1.4 to an inequality on the real Heisenberg group. Then an averaging argument reduces the proof to an inequality on cocycles. Every unitary representation of the continuous Heisenberg group decomposes as a direct integral of irreducibles, and cocycles themselves can be decomposed accordingly. Since the desired inequality involves a sum of squares of norms, it suffices to prove it for cocycles corresponding to irreducible representations (that is, for each direct integrand separately). The computation for irreducible representations is carried out in Section 7.1.

2 Sublinear growth of Heisenberg cocycles in ergodic spaces

Write c =^{def} [a, b] = aba^{−1}b^{−1}. Thus c lies in the center of ℍ and for every n ∈ ℕ we have d_{W} (c^{n^{2}}, e_{ℍ}) = 4n (in fact c^{n^{2}} = [a^{n}, b^{n}] = a^{n}b^{n}a^{−n}b^{−n}).

Let (X, ∥·∥) be a Banach space and π : G → Aut(X) be an action of ℍ on X by linear isometric automorphisms. In addition let f ∈ Z^{1}(π) be a 1-cocycle, so f : ℍ → X and for all x, y ∈ ℍ we have f(xy) = π(x)f(y) + f(x). We assume in what follows that f is 1-Lipschitz, or equivalently that max{∥f(a)∥, ∥f(b)∥} = 1.

In this section we quickly show that if X is an ergodic Banach space then lim inf_{t→∞} ω_{f}(t)/t = 0, but without obtaining any quantitative bounds.

If X is ergodic then the operator on X defined by

P x =^{def} lim_{N→∞} \frac{1}{N} ∑_{n=0}^{N−1} π(c)^{n}x

is a contraction onto the subspace X_{0} ⊆ X of π(c)-invariant vectors, and since P x = x for any x ∈ X_{0} it follows at once that P is idempotent. Also, since c is central in ℍ, the projection P commutes with π(g) for all g ∈ ℍ, and hence the maps g ↦ P f(g) and g ↦ (I − P)f(g) are both still members of Z^{1}(π). Since P and I − P are bounded, these cocycles are both still Lipschitz functions from ℍ to X.

We complete the proof by showing that for any ε > 0 we have

∥f (c^{N^{2}})∥ ⩽ 2εd_{W} (e_{ℍ}, c^{N^{2}}) ⩽ 8εN  (11)

for all sufficiently large N. To prove this we consider the two cocycles P f and (I − P)f separately. On the one hand, P f takes values among the π(c)-invariant vectors, and hence the cocycle identity implies that

P f (c^{N}) = ∑_{n=0}^{N−1} π(c)^{n}P f(c) = NP f(c),

and therefore ∥P f (c^{N})∥ = N∥P f(c)∥. However, ∥P f (c^{N})∥ ⩽ d_{W} (e_{ℍ}, c^{N}) ≲ \sqrt{N}, so these relations are compatible only if P f(c) = 0.

On the other hand, let f̃ =^{def} (I − P)f and for each K ⩾ 1,

v_{K} =^{def} −\frac{1}{K} ∑_{k=1}^{K} f (c^{k}) .

Observe from the cocycle identity and the centrality of c that

− π(g)v_{K} + f̃(g) = \frac{1}{K} ∑_{k=1}^{K} (π(g)f̃(c^{k}) + f̃(g)) = \frac{1}{K} ∑_{k=1}^{K} f̃(gc^{k})

= \frac{1}{K} ∑_{k=1}^{K} f̃(c^{k}g) = \frac{1}{K} ∑_{k=1}^{K} π (c^{k}) f̃(g) − v_{K}. (12)

Re-arranging (12) gives

f̃(g) = π(g)v_{K} − v_{K} + \frac{1}{K} ∑_{k=1}^{K} π(c)^{k}f̃(g).  (13)

For any fixed g ∈ ℍ the last term of this right-hand side of (13) converges to P (I − P)f(g) = 0 (using again that X is ergodic), and so in particular once K is sufficiently large we obtain that for all g ∈ ℍ we have,

max {∥f̃(a^{±1}) − (π (a^{±1}) v_{K} − v_{K})∥ , ∥f̃(b^{±1}) − (π (b^{±1}) v_{K} − v_{K})∥} ⩽ ε.

Having obtained this approximation to f̃ by a coboundary, let c^{N^{2}} = s_{1}s_{2} ⋯ s_{4N} be an expression for c^{N^{2}} as a word in S, and observe from another appeal to the cocycle identity that

f̃(c^{N^{2}}) = ∑_{i=0}^{4N−1} π (s_{1}s_{2} ⋯ s_{i}) f̃(s_{i+1}) = ∑_{i=0}^{4N−1} π (s_{1}s_{2} ⋯ s_{i}) (π (s_{i+1}) v_{K} − v_{K}) + R_{N}

= π(s_{1}s_{2} ⋯ s_{4N})v_{K} − v_{K} + R_{N}

for some remainder R_{N} which is a sum of 4N terms all of norm at most ε. Since the action π is isometric and we may let N grow independently of K we obtain

∥f̃(c^{N^{2}})∥ ⩽ 2∥v_{K}∥ + ∥R_{N}∥ ⩽ 8εN

for all sufficiently large N. Since ε was arbitrary and f̃(c^{N^{2}}) = f (c^{N^{2}}) by our analysis of P f above, this completes the proof of (11).

3 A uniform convexity lemma for ergodic averages

We prove here a simple lemma on the behavior of ergodic averages in p-convex Banach spaces.

Lemma 3.1. Assume that (X, ∥ · ∥) satisfies (4). Fix z ∈ X and an operator T : X → X with ∥T ∥ ⩽ 1. For every integer n ⩾ 0 denote

s_{n} =^{def} \frac{1}{2^{n}} ∑_{j=0}^{2^{n}−1} T^{j}z.

Then for every ℓ ∈ ℕ we have:

∑_{i=0}^{∞} \frac{1}{2^{ℓ}} ∑_{j=0}^{2^{ℓ}−1} ∥s_{(i+1)ℓ} − T^{j2^{iℓ}}s_{iℓ}∥^{p} ⩽ (2K)^{p}∥z∥^{p}.  (14)

Proof. A consequence of (4) is that for every x_{1}, …, x_{n} ∈ X we have:

\frac{1}{n} ∑_{i=1}^{n} ∥x_{i} − \frac{1}{n} ∑_{j=1}^{n} x_{j}∥^{p} ⩽ (2K)^{p} (\frac{1}{n} ∑_{i=1}^{n} ∥x_{i}∥^{p} − ∥\frac{1}{n} ∑_{i=1}^{n} x_{i}∥^{p}) .  (15)

For the derivation of (15) from (4) see [19, Lem. 3.1].

Due to the identity

s_{(i+1)ℓ} = \frac{1}{2^{ℓ}} ∑_{j=0}^{2^{ℓ}−1} T^{j2^{iℓ}}s_{iℓ},

inequality (15) implies that:

\frac{1}{2^{ℓ}} ∑_{j=0}^{2^{ℓ}−1} ∥T^{j2^{iℓ}}s_{iℓ} − s_{(i+1)ℓ}∥^{p} ⩽ (2K)^{p} (\frac{1}{2^{ℓ}} ∑_{j=0}^{2^{ℓ}−1} ∥T^{j2^{iℓ}}s_{iℓ}∥^{p} − ∥s_{(i+1)ℓ}∥^{p})

⩽ (2K)^{p} (∥s_{iℓ}∥^{p} − ∥s_{(i+1)ℓ}∥^{p}) . (16)

The desired inequality (14) now follows by summing (16) over i ∈ {0, 1, …}.

4 Estimates for Heisenberg cocycles

Let π : ℍ → Aut(X) and f ∈ Z^{1}(π) be as in Section 2. For every n ∈ ℕ define a linear operator P_{n} : X → X by

P_{n} =^{def} \frac{1}{2^{n}} ∑_{j=0}^{2^{n}−1} π(c)^{j}.

Thus ∥P_{n}∥ ⩽ 1.

Lemma 4.1. Assume that (X, ∥ · ∥) satisfies (4). Then for every ℓ, k, m ∈ ℕ there exist integers i ∈ [k + 1, k + m] and j ∈ [0, 2^{ℓ} − 1] satisfying for all n ∈ ℕ,

∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (c^{n^{2}}) − P_{iℓ}f (c^{n^{2}})∥ ⩽ \frac{16Kn}{m^{1/p}}.  (17)

Proof. Consider the Banach space Y = X ⊕ X, equipped with the norm

∥(x, y)∥_{Y} = (∥x∥^{p} + ∥y∥^{p})^{1/p} .

We also define T : Y → Y by T (x, y) = (π(c)x, π(c)y). Then ∥T ∥ ⩽ 1. Since (Y, ∥ · ∥_{Y}) satisfies (4) we may apply Lemma 3.1 to z = (f(a), f(b)) ∈ Y, obtaining the following estimate:

(4K)^{p} ⩾ ∑_{i=k+1}^{k+m} \frac{1}{2^{ℓ}} ∑_{j=0}^{2^{ℓ}−1} (∥P_{(i+1)ℓ}f (a) − π (c^{j2^{iℓ}}) P_{iℓ}f (a)∥^{p} + ∥P_{(i+1)ℓ}f (b) − π (c^{j2^{iℓ}}) P_{iℓ}f (b)∥^{p})

= ∑_{i=k+1}^{k+m} \frac{1}{2^{ℓ}} ∑_{j=0}^{2^{ℓ}−1} (∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (a) − P_{iℓ}f (a)∥^{p} + ∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (b) − P_{iℓ}f (b)∥^{p})
⩾ m min_{\begin{matrix}k+1⩽i⩽k+m \\ 0⩽j⩽2^{ℓ}−1 \end{matrix}} (∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (a) − P_{iℓ}f (a)∥^{p} + ∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (b) − P_{iℓ}f (b)∥^{p}) .

It follows that there exist integers i ∈ [k + 1, k + m], j ∈ [0, 2^{ℓ} − 1] such that

max \{∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (a) − P_{iℓ}f (a)∥ , ∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (b) − P_{iℓ}f (b)∥\} ⩽ \frac{4K}{m^{1/p}} . (18)

Consider the operator

Q_{n} =^{def} \frac{1}{n} ∑_{i=0}^{n−1} π(a)^{i}.

The cocycle identity implies that f(a^{n}) = nQ_{n}f(a). Thus

π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f(a^{n}) − P_{iℓ}f(a^{n}) = n (π (c^{−j2^{iℓ}}) P_{(i+1)ℓ} − P_{iℓ}) Q_{n}f(a)

= nQ_{n} (π (c^{−j2^{iℓ}}) P_{(i+1)ℓ} − P_{iℓ}) f(a), (19)

where the last equality in (19) holds since c is in the center of ℍ, and therefore Q_{n} commutes with all of {P_{r}}_{r=0}^{∞}. Since ∥Q_{n}∥ ⩽ 1, it follows from (19) and (18) that

∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f(a^{n}) − P_{iℓ}f(a^{n})∥ ⩽ \frac{4Kn}{m^{1/p}} .  (20)

Since f(a^{−n}) = −π(a)^{−n}f(a^{n}), and π(a) commutes with π(c), and hence with all of {P_{r}}_{r=0}^{∞}, it follows that also

∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f(a^{−n}) − P_{iℓ}f(a^{−n})∥ ⩽ \frac{4Kn}{m^{1/p}} .  (21)

An identical argument implies the analogous bounds with a replaced by b:

∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f(b^{n}) − P_{iℓ}f(b^{n})∥ ⩽ \frac{4Kn}{m^{1/p}}  (22)

and

∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f(b^{−n}) − P_{iℓ}f(b^{−n})∥ ⩽ \frac{4Kn}{m^{1/p}} .  (23)

The cocycle identity implies that for all n ∈ ℕ,

f (c^{n^{2}}) = f ([a^{n}, b^{n}]) = π(a^{n}b^{n}a^{−n})f(b^{−n}) + π(a^{n}b^{n})f(a^{−n}) + π(a^{n})f(b^{n}) + f(a^{n}).

Thus, using (20), (21), (22) and (23), we conclude the validity of (17).

Lemma 4.2. For every m, n ∈ ℕ we have

∥P_{m}f (c^{n^{2}})∥ ≲ \frac{n^{5/3}}{2^{m/3}} .  (24)

Proof. Note that for every k ∈ ℕ we have

P_{m} − π (c^{k}) P_{m} = \frac{1}{2^{m}} ∑_{j=0}^{k−1} π(c)^{j} − \frac{1}{2^{m}} ∑_{j=2^{m}}^{2^{m}+k−1} π(c)^{j}.

Thus,

∥P_{m} − π (c^{k}) P_{m}∥ ⩽ \frac{2k}{2^{m}} .  (25)

The cocycle identity implies that

f (c^{(kn)^{2}}) = ∑_{j=0}^{k^{2}−1} π (c^{jn^{2}}) f (c^{n^{2}}) .  (26)

Using the fact that f is 1-Lipschitz, ∥P_{m}∥ ⩽ 1 and d_{W} (e_{ℍ}, c^{(kn)^{2}}) ⩽ 4kn, we deduce from (26) that

4kn ⩾ ∥P_{m}f (c^{(kn)^{2}})∥ ⩾ ∑_{j=0}^{k^{2}−1} (∥P_{m}f (c^{n^{2}})∥ − ∥P_{m} − π (c^{jn^{2}}) P_{m}∥ · ∥f (c^{n^{2}})∥)

⩾^{(25)} k^{2} ∥P_{m}f (c^{n^{2}})∥ − ∑_{j=0}^{k^{2}−1} \frac{2jn^{2}}{2^{m}} · 4n ⩾ k^{2} ∥P_{m}f (c^{n^{2}})∥ − \frac{4n^{3}k^{4}}{2^{m}} .

Thus,

∥P_{m}f (c^{n^{2}})∥ ⩽ \frac{4n}{k} + \frac{4n^{3}k^{2}}{2^{m}} .  (27)

Choosing k = ⌈(2^{m−1}/n^{2})^{1/3}⌉ in (27) (roughly the optimal choice of k), we obtain (24).

Lemma 4.3. For every m, n ∈ ℕ we have:

∥f (c^{n^{2}}) − P_{m}f (c^{n^{2}})∥ ⩽ 2^{m/3}n^{1/3}.  (28)

Proof. In this proof the relation to Section 2 becomes clear. Define f̃: ℍ → X by

f̃(h) =^{def} f (h) − P_{m}f (h) = (I − P_{m})f(h).

Note that f̃ ∈ Z^{1}(π). Fix an integer k ⩾ 1 that will be determined later. Consider the vector v ∈ X defined by

v =^{def} −\frac{1}{k} ∑_{j=0}^{k−1} f̃(c^{j}) .

Then

∥v∥ ≲ \frac{1}{k} ∑_{j=0}^{k−1} \sqrt{j} ≲ \sqrt{k}.  (29)

Since c is in the center of ℍ, we have the following identity for every h ∈ ℍ:

− π(h)v + f̃(h) = \frac{1}{k} ∑_{j=0}^{k−1} (π(h)f̃(c^{j}) + f̃(h)) = \frac{1}{k} ∑_{j=0}^{k−1} f̃(hc^{j}) = \frac{1}{k} ∑_{j=0}^{k−1} f̃(c^{j}h)

= \frac{1}{k} ∑_{j=0}^{k−1} (π (c^{j}) f̃(h) + f̃(c^{j})) = \frac{1}{k} ∑_{j=0}^{k−1} π (c^{j}) f̃(h) − v. (30)

Note that

\frac{1}{k} ∑_{j=0}^{k−1} π (c^{j}) f̃(h) = \frac{1}{k} ∑_{j=0}^{k−1} (π (c^{j}) f(h) − \frac{1}{2^{m}} ∑_{i=0}^{2^{m}−1} π (c^{j+i}) f(h))

= \frac{1}{2^{m}} ∑_{i=0}^{2^{m}−1} (\frac{1}{k} ∑_{j=0}^{k−1} π (c^{j}) − \frac{1}{k} ∑_{j=i}^{i+k−1} π (c^{j})) f(h).

Hence,

∥\frac{1}{k} ∑_{j=0}^{k−1} π (c^{j}) f̃(h)∥ ⩽ \frac{d_{W} (h, e_{ℍ})}{2^{m}} ∑_{i=0}^{2^{m}−1} \frac{2i}{k} ⩽ \frac{2^{m}}{k} d_{W} (h, e_{ℍ}).  (31)

Combining (30) and (31), we see that f̃ is close to a coboundary in the following sense:

∥f̃(h) − (π(h)v − v)∥ ⩽ \frac{2^{m}}{k} d_{W} (h, e_{ℍ}).  (32)

If we now write c^{n^{2}} = h_{1}h_{2} ⋯ h_{4n} for h_{1}, …, h_{4n} ∈ {a, a^{−1}, b, b^{−1}}, then the cocycle identity for f̃ implies the following bound:

∥f̃(c^{n^{2}})∥ = ∥ ∑_{i=0}^{4n−1} π(h_{1} ⋯ h_{4n−i−1})f̃(h_{4n−i})∥

⩽^{(32)} ∥ ∑_{i=0}^{4n−1} π(h_{1} ⋯ h_{4n−i−1})(π(h_{4n−i})v − v)∥ + \frac{4n2^{m}}{k}
= ∥π (c^{n^{2}}) v − v∥ + \frac{4n2^{m}}{k}
≲^{(29)} \sqrt{k} + \frac{n2^{m}}{k} .  (33)

The optimal choice for k in (33) is k ≍ n^{2/3}2^{2m/3}. For this choice of k, (33) becomes the desired bound (28).

5 Proof of Theorem 1.2

As explained in the introduction, using [21, Thm. 9.1] we may assume without loss of generality that f ∈ Z^{1}(π) for some action π of ℍ on X by linear isometric automorphisms. We may also assume that t ⩾ 8^{p}. Let m be the largest integer such that

m^{m} ⩽ (\frac{t}{4})^{p/3} .  (34)

Having defined m, let k be the smallest integer such that

m^{\frac{3}{2p} + \frac{3(k+1)}{p}} ⩾ t,  (35)

and set

ℓ =^{def} ⌈\frac{6}{p} log_{2} m⌉ .  (36)

By Lemma 4.1 there exist integers i ∈ [k + 1, k + m] and j ∈ [0, 2^{ℓ} − 1] satisfying for all n ∈ ℕ,

∥π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (c^{n^{2}}) − P_{iℓ}f (c^{n^{2}})∥ ⩽ \frac{16Kn}{m^{1/p}}.  (37)

Choose

n =^{def} \frac{1}{4} ⌈m^{\frac{3}{2p}} 2^{\frac{iℓ}{2}} ⌉ ,  (38)

We may write

f (c^{n^{2}}) = π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (c^{n^{2}}) + (P_{iℓ}f (c^{n^{2}}) − π (c^{−j2^{iℓ}}) P_{(i+1)ℓ}f (c^{n^{2}}))

+ (f (c^{n^{2}}) − P_{iℓ}f (c^{n^{2}})) .

Hence, by Lemma 4.2, inequality (37), and Lemma 4.3, we obtain the following bound:

ω_{f}(4n) = ω_{f} (d_{W} (c^{n^{2}}, e_{ℍ})) ⩽ ∥f (c^{n^{2}})∥ ≲ \frac{n^{5/3}}{2^{(i+1)ℓ/3}} + \frac{8Kn}{m^{1/p}} + 2^{iℓ/3}n^{1/3} ≲^{(38)∧(36)} \frac{Kn}{m^{1/p}} . (39)

Observe that

4n ⩾^{(38)} m^{\frac{3}{2p}} 2^{\frac{iℓ}{2}} ⩾ m^{\frac{3}{2p}} 2^{\frac{(k+1)ℓ}{2}} ⩾^{(36)} m^{\frac{3}{2p} + \frac{3(k+1)}{p}} ⩾^{(35)} t.

At the same time,

4n ⩽^{(38)} 2m^{\frac{3}{2p}} 2^{\frac{iℓ}{2}} ⩽ 2m^{\frac{3}{2p}} 2^{\frac{(k+m)ℓ}{2}} ⩽^{(36)} 4m^{\frac{3}{2p} + \frac{3k}{p}} · m^{\frac{3m}{p}} <^{(35)} 4tm^{\frac{3m}{p}} ⩽^{(34)} t^{2}.

Hence t ⩽ 4n ⩽ t^{2}. The definition of m implies that m ≳ \frac{p}{3} \frac{log n}{log log n}, and therefore (39) becomes:

\frac{ω_{f}(4n)}{n} ≲ K (\frac{log log n}{log n})^{1/p} .

The proof of Theorem 1.2 is complete.

6 Deduction of Theorem 1.3 from Theorem 1.2

Fix R ⩾ 4 and a function f : B_{R} → X satisfying

∀ x, y ∈ B_{R}, d_{W} (x, y) ⩽ ∥f(x) − f(y)∥ ⩽ Dd_{W} (x, y).  (40)

Our goal is to bound D from below. Without loss of generality assume that f(e) = 0. Define f^{∗} : ℍ → X by

f^{∗}(x) = \{ \begin{matrix}f(x) & x ∈ B_{R/2}, \\ 2 (1 − \frac{d_{W} (x,e)}{R}) f(x) & x ∈ B_{R} ∖ B_{R/2}, \\ 0 & x ∈ ℍ ∖ B_{R}. \end{matrix}  (41)

Then f^{∗} is 2D-Lipschitz and coincides with f on B_{R/2}. Let N ⊆ ℍ be a maximal 3R-separated

subset of ℍ. Thus the function f^{∗∗} : ℍ → X given by f^{∗∗}(x) =^{def} ∑_{y∈N} f^{∗}(y^{−1}x) (only one summand is nonzero for any given x) is also 2D-Lipschitz.

Fix a free ultrafilter 𝒰 on ℕ. Consider the semi-normed space Y = (ℓ_{∞}(ℍ, X), ∥ · ∥_{Y}), where

∥ψ∥_{Y} =^{def} lim_{M→𝒰} (\frac{1}{|B_{M}|} ∑_{z∈B_{M}} ∥ψ(z)∥^{p})^{1/p} .

Note that since X satisfies (4), so does Y. Y is a semi-normed space rather than a normed space, so we should formally deal below with the quotient Y/{f ∈ ℓ_{∞}(ℍ, X) : ∥f∥_{Y} = 0}, but we will ignore this inessential formality in what follows. (Complete details are as in the proof of Theorem 9.1 in [21]. Alternatively one can note that our proof of Theorem 1.2 carries over without change to the class of semi-normed spaces.)

Define F : ℍ → Y by F (x)(z) =^{def} f^{∗∗}(zx) − f^{∗∗}(z). This is well defined since the metric d_{W} is left-invariant, and therefore ∥F (x)∥_{Y} ⩽ 2Dd_{W} (x, e_{ℍ}) for all x ∈ ℍ. Moreover, by leftinvariance, F is 2D-Lipschitz. Theorem 1.2 therefore implies that there exist x, y ∈ ℍ such that \sqrt{R/4} ⩽ d_{W} (x, y) ⩽ R/4 and

lim_{M→𝒰} (\frac{1}{|B_{M}|} ∑_{z∈B_{M}} (\frac{∥f^{∗∗}(zx) − f^{∗∗}(zy)∥}{d_{W} (x, y)})^{p})^{1/p} ≲ DK_{p}(X) (\frac{log log R}{log R})^{1/p} .  (42)

Fix an integer M > 2d_{W} (x, e) + 4R and write m = M − 2d_{W} (x, e) − 4R. Since N is a maximal 3R-separated subset of ℍ, we have B_{m}x ⊆ ⋃_{w∈M} wB_{3R}, where M =^{def} {w ∈ N : wB_{3R} ∩ B_{m}x ≠ ∅}. Hence, since for r ⩾ 1 we have |B_{r}| ≍ r^{4}, we can bound the cardinality of M as follows:

|M| ≳ (\frac{M − 2d_{W} (x, e) − 4R}{3R})^{4} .  (43)

If w ∈ M then there exists z ∈ B_{m} and g ∈ B_{3R} such that zx = wg. Hence, for every h ∈ B_{R/4} we have

d_{W} (whx^{−1}, e) = d_{W} (zxg^{−1}hx^{−1}, e) ⩽ d_{W} (z, e) + 2d_{W} (x, e) + d_{W} (g, e) + d_{W} (h, e) < M.

Thus the sets {wB_{R/4}x^{−1}}_{w∈M} are disjoint and contained in B_{M}. Moreover, if w ∈ M and z ∈ wB_{R/4}x^{−1} then d_{W} (zx, w) ⩽ R/4, and hence also d_{W} (zy, w) ⩽ d_{W} (zy, zx) + d_{W} (zx, w) ⩽ R/2. By the definition of f^{∗∗}, this implies that f^{∗∗}(zx) = f(w^{−1}zx) and f^{∗∗}(zy) = f(w^{−1}zy). Hence,

∑_{z∈B_{M}} (\frac{∥f^{∗∗}(zx) − f^{∗∗}(zy)∥}{d_{W} (x, y)})^{p} ⩾ ∑_{w∈M} ∑_{z∈wB_{R/4}x^{−1}} (\frac{∥f(w^{−1}zx) − (w^{−1}zy)∥}{d_{W} (x, y)})^{p}

⩾^{(40)} |M| · |B_{R/4}| ≳^{(43)} (1 − \frac{2d_{W} (x, e) + 4R}{M})^{4} |B_{M}|. (44)

Theorem 1.3 now follows from (42) and (44).

7 Embeddings into Hilbert space

In this section, we prove Theorem 1.4. We will deduce it from an inequality on cocycles for the real Heisenberg group. We switch to the real Heisenberg group because its representation theory is simpler. However, this comes at the cost of adding a (straightforward) discretization step to the proof. The upshot is that we obtain as a byproduct a smooth Poincaré inequality on ℍ(ℝ) of independent interest; see Theorem 7.5.

The real Heisenberg group ℍ(ℝ) is defined as the matrix group

ℍ(ℝ) =^{def} \{( \begin{matrix}1 & u & w \\ 0 & 1 & v \\ 0 & 0 & 1 \end{matrix} ) : u, v, w ∈ ℝ\} .

The discrete Heisenberg group ℍ sits inside ℍ(ℝ) as the cocompact discrete subgroup consisting of unipotent matrices with integer coefficients. We equip the group ℍ(ℝ) with the word metric d_{S_{ℝ}} associated with the compact symmetric generating set S_{ℝ} = {a^{u}, b^{v}, c^{w}; |u|, |v|, |w| ⩽ 1}, where

a^{u} = ( \begin{matrix}1 & u & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) , b^{v} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & v \\ 0 & 0 & 1 \end{matrix} ) , c^{w} = ( \begin{matrix}1 & 0 & w \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

Let μ denote a Haar measure on ℍ(ℝ), which coincides with Lebesgue measure under the natural identification of ℍ(ℝ) with ℝ^{3}.

Theorem 7.1. For every continuous unitary representation π of ℍ(ℝ), any continuous cocycle γ ∈ Z^{1}(π) satisfies the inequality

∫_{1}^{∞} \frac{∥γ (c^{t})∥^{2}}{t^{2}} dt ≲ ∫_{−1}^{1} (∥γ(a^{u})∥^{2} + ∥γ(b^{u})∥^{2}) du.  (45)

Section 7.1 is devoted to the proof of Theorem 7.1. It is clearly enough to check inequality (45) when the representation π is irreducible. The proof therefore boils down to a quantitative study of 1-cocycles with values in an irreducible representation of ℍ(ℝ). In the next three subsections we deduce Theorem 1.4 from Theorem 7.1 by a succession of reductions. Finally, in the last subsection, we state a smooth Poincaré inequality on the real Heisenberg group, whose proof, being very similar to the discrete one, is explained in a few sentences.

7.1 Proof of Theorem 7.1

By the Stone-von Neumann theorem (see for example [12, Ch. 2]), irreducible representations of ℍ(ℝ) are of two types: those that factor through the center, and, for every λ ∈ ℝ ∖ {0}, the representation π_{λ} on L_{2}(ℝ) satisfying

∀ h ∈ L_{2}(ℝ), π_{λ}(a^{u}b^{v}c^{w})(h)(x) =^{def} e^{2πiλvx}h(x + u)e^{2πiλw}.  (46)

Note that if a nontrivial irreducible representation π factors through the center then any 1cocycle γ ∈ Z^{1}(π) must vanish on the center. Indeed, γ(c^{w}) is invariant under π(ℍ) for every w ∈ ℝ, which, since the representation is supposed to be irreducible and nontrivial, implies that γ(c^{w}) = 0. Therefore, in proving Theorem 7.1 we may assume that π = π_{λ} for some λ ≠ 0.

By [14, Thm. 7] all 1-cocycles γ ∈ Z^{1}(π_{λ}) can be approximated uniformly on compact sets by coboundaries. Hence, it is enough to consider the case where γ is of the form γ(x) = π_{λ}(x)h − h, for some h ∈ L_{2}(ℝ). We may assume that ∥h∥ = 1. By the definition (46), for every w ∈ ℝ we have ∥γ(c^{w})∥^{2} = 4 sin^{2}(πλw), from which we deduce that

∫_{1}^{∞} \frac{∥γ(c^{w})∥^{2}}{w^{2}} dw ≲ ∫_{1}^{∞} \frac{sin^{2}(πλw)}{w^{2}}dw = |λ| ∫_{|λ|}^{∞} \frac{sin^{2}(πw)}{w^{2}}dw ≲ min\{|λ|, 1\}.  (47)

Also,

∫_{−1}^{1} (∥γ(a^{u})∥^{2} + ∥γ(b^{u})∥^{2}) du = ∫_{−1}^{1} ∫_{ℝ} (|h(x + u) − h(x)|^{2} + 2|h(x)|^{2} (1 − cos(2πλux))) dxdu

≍ ∫_{−1}^{1} ∫_{ℝ} |h(x + u) − h(x)|^{2}dxdu + ∫_{ℝ} |h(x)|^{2} min{λ^{2}x^{2}, 1}dx. (48)

Since ℝ = (ℝ ∖ [−|u|, |u|]) ∪ (u + (ℝ ∖ [−|u|, |u|])) ∪ (−u + (ℝ ∖ [−|u|, |u|])) for every u ∈ ℝ, we can bound ∥h∥^{2} = 1 from above as follows.

1 ⩽ ∫_{ℝ∖[−|u|,|u|]} (|h(x + u)|^{2} + |h(x − u)|^{2} + |h(x)|^{2}) dx
≲ ∫_{ℝ} (|h(x + u) − h(x)|^{2} + |h(x) − h(x − u)|^{2}) dx + ∫_{ℝ∖[−|u|,|u|]} |h(x)|^{2}dx
⩽ ∫_{ℝ} (|h(x + u) − h(x)|^{2} + |h(x) − h(x − u)|^{2}) dx
+\frac{1}{min\{λ^{2}u^{2}, 1\}} ∫_{ℝ} |h(x)|^{2} min\{λ^{2}x^{2}, 1\}dx.  (49)

Write k = ⌈1/\sqrt{|λ|}⌉. By applying (49) with u = kv, and integrating over v ∈ [−1, −1/2] ∪ [1/2, 1], we see that

∫_{1}^{∞} \frac{∥γ(c^{w})∥^{2}}{w^{2}} dw ≲^{(47)} min\{|λ|, 1\}
≲^{(49)} min{|λ|, 1} ∫_{−1}^{1} ∫_{ℝ} |h(x + kv) − h(x)|^{2}dxdv

+\frac{min\{|λ|, 1\}}{min \{λ^{2} ⌈1/\sqrt{|λ|}⌉^{2} , 1\}} ∫_{ℝ} |h(x)|^{2} min\{λ^{2}x^{2}, 1\}dx

≲ min{|λ|, 1}k ∑_{j=1}^{k} ∫_{−1}^{1} ∫_{ℝ} |h(x + jv) − h(x + (j − 1)v)|^{2}dxdv

+ ∫_{ℝ} |h(x)|^{2} min{λ^{2}x^{2}, 1}dx

= min{|λ|, 1}k^{2} ∫_{−1}^{1} ∫_{ℝ} |h(x + u) − h(x)|^{2}dxdu + ∫_{ℝ} |h(x)|^{2} min{λ^{2}x^{2}, 1}dx
≲^{(48)} ∫_{−1}^{1} (∥γ(a^{u})∥^{2} + ∥γ(b^{u})∥^{2}) du.

The proof of Theorem 7.1 is complete.

7.2 Reduction to finitely supported functions

Claim 7.2. Inequality (8) is a consequence of the following statement. For every finitely supported ϕ : ℍ → L_{2}, we have

∑_{x∈ℍ} ∑_{k=1}^{∞} \frac{∥ϕ(xc^{k}) − ϕ(x)∥_{2}^{2}}{k^{2}} ≲ ∑_{x∈ℍ} (∥ϕ(xa) − ϕ(x)∥_{2}^{2} + ∥ϕ(xb) − ϕ(x)∥_{2}^{2}) .  (50)

Proof. Fix R ∈ ℕ and f : ℍ → L_{2}. Note that since (8) is not sensitive to adding a constant to the function f, we can assume without loss of generality that the average of f over B_{7R} is zero.

Define a cutoff function ξ : ℍ → [0, 1] by

ξ(x) =^{def} \{ \begin{matrix}1 & x ∈ B_{5R}, \\ 6 − \frac{d_{W} (x,e)}{R} & x ∈ B_{6R} ∖ B_{5R}, \\ 0 & x ∈ ℍ ∖ B_{6R}, \end{matrix}

and let ϕ =^{def} ξf. Then ϕ is supported on B_{6R}. Since ξ is 1/R-Lipschitz and takes values in [0, 1], for all x ∈ ℍ and s ∈ S,

∥ϕ(x) − ϕ(xs)∥_{2}^{2} ≲ |ξ(x) − ξ(xs)|^{2} · ∥f(x)∥_{2}^{2} + |ξ(xs)|^{2} · ∥f(x) − f(xs)∥_{2}^{2}

⩽ \frac{1}{R^{2}} ∥f(x)∥^{2} + ∥f(x) − f(xs)∥_{2}^{2}. (51)

Note that if k ∈ {1, …, R^{2}} then d_{W} (e, c^{k}) ⩽ 4R, and hence for x ∈ B_{R} we have xc^{k} ∈ B_{5R}. Therefore, an application of (50) to ϕ yields the estimate

∑_{x∈B_{R}} ∑_{k=1}^{R^{2}} \frac{∥f(xc^{k}) − f(x)∥_{2}^{2}}{k^{2}} ⩽ ∑_{x∈ℍ} ∑_{k=1}^{∞} \frac{∥ϕ(xc^{k}) − ϕ(x)∥_{2}^{2}}{k^{2}} ≲ ∑_{x∈ℍ} max_{s∈S} ∥ϕ(xs) − ϕ(x)∥_{2}^{2}

= ∑_{x∈B_{7R}} max_{s∈S} ∥ϕ(xs) − ϕ(x)∥_{2}^{2} ⩽^{(51)} \frac{1}{R^{2}} ∑_{x∈B_{7R}} ∥f(x)∥_{2}^{2} + ∑_{x∈B_{7R}} max_{s∈S} ∥f(xs) − f(x)∥_{2}^{2}. (52)

By [17, Thm. 2.2] (a discrete version of the classical Heisenberg local Poincaré inequality [16]),

\frac{1}{R^{2}} ∑_{x∈B_{7R}} ∥f(x)∥_{2}^{2} ≲ ∑_{x∈B_{22R}} (∥f(xa) − f(x)∥_{2}^{2} + ∥f(xb) − f(x)∥_{2}^{2}) ,  (53)

where we used the fact that the average of f on B_{7R} vanishes. The desired inequality (8) is now a consequence of (52) and (53).

7.3 Reduction to an inequality on the real Heisenberg group

Claim 7.3. Inequality (50) is a consequence of the following statement. For every continuous and compactly supported function ψ : ℍ(ℝ) → L_{2}, we have

∫_{ℍ(ℝ)} ∫_{1}^{∞} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dtdμ(x) ≲ ∫_{ℍ(ℝ)} ( sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2}) dμ(x).  (54)

Proof. For r > 0 let B_{r}^{ℝ} ⊆ ℍ(ℝ) denote the ball of radius r with respect to the metric d_{S_{ℝ}}. Note that ℍ(ℝ) = ⋃_{g∈ℍ} gB_{2}^{ℝ}. Let σ : ℍ(ℝ) → [0, 1] be a continuous nonnegative function, which equals 1 on B_{2}^{ℝ} and 0 outside of B_{3}^{ℝ}. Let σ̃ = ∑_{g∈ℍ} σ_{g}, where σ_{g}(x) = σ(g^{−1}x). For all x ∈ ℍ(ℝ) we have 1 ⩽ σ̃(x) ⩽ C for some C ∈ (0, ∞). Writing β = σ/σ̃ and β_{g}(x) = β(g^{−1}x), we see that {β_{g}}_{g∈ℍ} is a continuous partition of unity for ℍ(ℝ) satisfying

sup_{x∈ℍ(ℝ)} ∑_{g∈ℍ} sup_{s∈S_{ℝ}} |β_{g}(xs) − β_{g}(x)| < ∞.  (55)

Throughout the ensuing argument we will use repeatedly the fact that for every x ∈ ℍ(ℝ) the number of elements g ∈ ℍ for which β_{g}(x) > 0 is bounded by a constant independent of x, and that ∑_{g∈ℍ} 1_{gB_{2}} ≍ 1_{ℍ(ℝ)}.

Let ϕ : ℍ → L_{2} be a finitely supported function on the discrete Heisenberg group ℍ. Define a function on the real Heisenberg group ℍ(ℝ) by

ψ(x) = ∑_{g∈ℍ} ϕ(g)β_{g}(x).

Then ψ is compactly supported. We will eventually apply (54) to ψ, but before doing so we will need some preparatory estimates.

The metric d_{S_{ℝ}} restricted to ℍ ⊆ ℍ(ℝ) is bi-Lipschitz equivalent to d_{W} [5, Thm. 8.3.19]. It follows that for all g_{0} ∈ ℍ, if x ∈ g_{0}B_{3}^{ℝ} then the sum ψ(x) − ϕ(g_{0}) = ∑_{g∈ℍ} β_{g}(x)(ϕ(g) − ϕ(g_{0})) is supported on elements of the form g = g_{0}h, with d_{W} (h, e) ⩽ K, for some universal constant K ∈ ℕ. Thus, using (55) we see that for all x ∈ g_{0}B_{2}^{ℝ},

sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2} ≲ ∑_{h∈B_{K}} ∥ϕ(g_{0}h) − ϕ(g_{0})∥_{2}^{2}.  (56)

Integrating (56) over g_{0}B_{2}^{ℝ} gives the following inequality:

∫_{g_{0}B_{2}^{ℝ}} ( sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2}) dμ(x) ≲ ∑_{h∈B_{K}} ∥ϕ(g_{0}h) − ϕ(g_{0})∥_{2}^{2}.  (57)

By summing (57) over g_{0} ∈ ℍ we see that

∫_{ℍ(ℝ)} ( sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2}) dμ(x) ≲ ∑_{g∈ℍ} max_{s∈S} ∥ϕ(g) − ϕ(gs)∥_{2}^{2},  (58)

where we used the bound

∑_{g_{0}∈ℍ} ∑_{h∈B_{K}} ∥ϕ(g_{0}h) − ϕ(g_{0})∥_{2}^{2} ≲ ∑_{g∈ℍ} max_{s∈S} ∥ϕ(g) − ϕ(gs)∥_{2}^{2},  (59)

which follows by writing each h ∈ B_{K} as a product of at most K elements of S, and using the triangle inequality.

In order to deduce from (54) a corresponding bound on ϕ, we need to bound ϕ in terms of ψ. To this end, note that for all g_{0} ∈ ℍ,

ψ(g_{0}) = ϕ(g_{0}) + ∑_{g∈ℍ} β(g^{−1}g_{0})(ϕ(g) − ϕ(g_{0})) = ϕ(g_{0}) + ∑_{h∈B_{K}} β(h^{−1})(ϕ(g_{0}h) − ϕ(g_{0})).

It follows that for all g_{0}, g_{1} ∈ ℍ we have

∥ϕ(g_{0}) − ϕ(g_{1})∥_{2}^{2} ≲ ∥ψ(g_{0}) − ψ(g_{1})∥_{2}^{2} + ∑_{h∈B_{K}} (∥ϕ(g_{0}) − ϕ(g_{0}h)∥_{2}^{2} + ∥ϕ(g_{1}) − ϕ(g_{1}h)∥_{2}^{2}) . (60)

If x, y ∈ ℍ(ℝ) satisfy max{d_{S_{ℝ}}(x, g_{0}), d_{S_{ℝ}}(y, g_{1})} ⩽ 2, then using (56) we deduce from (60) that

∥ϕ(g_{0}) − ϕ(g_{1})∥_{2}^{2} ≲ ∥ψ(x) − ψ(y)∥_{2}^{2} + ∑_{h∈B_{K}} (∥ϕ(g_{0}) − ϕ(g_{0}h)∥_{2}^{2} + ∥ϕ(g_{1}) − ϕ(g_{1}h)∥_{2}^{2}) . (61)

Fix g_{0} ∈ ℍ, x ∈ g_{0}B_{1}^{ℝ}, k ∈ ℕ and t ∈ [k, k+1]. Writing g_{1} = g_{0}c^{k} and y = xc^{t}, we have d_{S_{ℝ}}(x, g_{0}) ⩽ 1 and d_{S_{ℝ}}(y, g_{1}) = d_{S_{ℝ}}(c^{−k}g_{0}^{−1}xc^{t}, e) = d_{S_{ℝ}}(g_{0}^{−1}xc^{t−k}, e) ⩽ d_{S_{ℝ}}(g_{0}^{−1}x, e) + d_{S_{ℝ}}(c^{t−k}, e) ⩽ 2. We may therefore apply (61) and deduce that for all g_{0} ∈ ℍ, x ∈ g_{0}B_{1}^{ℝ} and k ∈ ℕ,

∥ϕ(g_{0}c^{k})−ϕ(g_{0})∥_{2}^{2} ≲ ∥ψ(xc^{t})−ψ(x)∥_{2}^{2} + ∑_{h∈B_{K}} (∥ϕ(g_{0}) − ϕ(g_{0}h)∥_{2}^{2} + ∥ϕ(g_{0}c^{k}) − ϕ(g_{0}c^{k}h)∥_{2}^{2}) . (62)

Integrating (62) over x ∈ g_{0}B_{1}^{ℝ} and t ∈ [k, k + 1], we see that

\frac{∥ϕ(g_{0}c^{k}) − ϕ(g_{0})∥_{2}^{2}}{k^{2}} ≲ ∫_{g_{0}B_{1}^{ℝ}} ∫_{k}^{k+1} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dtdμ(x)

+ \frac{1}{k^{2}} ∑_{h∈B_{K}} (∥ϕ(g_{0}) − ϕ(g_{0}h)∥_{2}^{2} + ∥ϕ(g_{0}c^{k}) − ϕ(g_{0}c^{k}h)∥_{2}^{2}) . (63)

Since g_{0}B_{1}^{ℝ} and g′_{0}B_{1}^{ℝ} intersect at a set of measure zero if g_{0} ≠ g′_{0}, by summing (63) over g_{0} ∈ ℍ and k ∈ ℕ, we see that

∑_{g_{0}∈ℍ} ∑_{k=1}^{∞} \frac{∥ϕ(g_{0}c^{k}) − ϕ(g_{0})∥_{2}^{2}}{k^{2}}

≲ ∫_{ℍ(ℝ)} ∫_{1}^{∞} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dtdμ(x) + ∑_{g_{0}∈ℍ} ∑_{h∈B_{K}} ∥ϕ(g_{0}) − ϕ(g_{0}h)∥_{2}^{2}

≲^{(59)} ∫_{ℍ(ℝ)} ∫_{1}^{∞} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dtdμ(x) + ∑_{g∈ℍ} max_{s∈S} ∥ϕ(g) − ϕ(gs)∥_{2}^{2}

≲^{(54)} ∫_{ℍ(ℝ)} ( sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2}) dμ(x) + ∑_{g∈ℍ} max_{s∈S} ∥ϕ(g) − ϕ(gs)∥_{2}^{2}

≲^{(58)} ∑_{g∈ℍ} max_{s∈S} ∥ϕ(g) − ϕ(gs)∥_{2}^{2}.

7.4 Reduction to a 1-cocycle on ℍ(ℝ)

Claim 7.4. Inequality (54) follows from Theorem 7.1.

Proof. Let ψ : ℍ(ℝ) → L_{2} be continuous and supported in B_{r}^{ℝ} for some r ⩾ 1. Take a maximal family {x_{i}B_{10r}^{ℝ}}_{i=1}^{∞} of disjoint balls of radius 10r. Define φ : ℍ(ℝ) → L_{2} by φ(g) = ∑_{i=1}^{∞} ψ(x_{i}^{−1}g). Note that since d_{S_{ℝ}}(c^{r^{2}}, e) ⩽ 4r, for each i ∈ ℕ we have

∫_{ℍ(ℝ)} ∫_{1}^{∞} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dtdμ(x) = ∫_{x_{i}B_{5r}^{ℝ}} ∫_{1}^{r^{2}} \frac{∥φ(xc^{t}) − φ(x)∥_{2}^{2}}{t^{2}} dtdμ(x).  (64)

Similarly,

∫_{ℍ(ℝ)} ( sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2}) dμ(x) = ∫_{x_{i}B_{2r}^{ℝ}} ( sup_{s∈S_{ℝ}} ∥φ(xs) − φ(x)∥_{2}^{2}) dμ(x).  (65)

Let X be the space of all finitely supported complex-valued functions on ℍ(ℝ). We denote by π the action of ℍ(ℝ) on X given by π(x)δ_{y} =^{def} δ_{xy}, where δ_{z} : ℍ(ℝ) → ℂ denotes the function which equals 1 at z ∈ ℍ(ℝ) and equals 0 elsewhere. Let 𝒰 be a free ultrafilter on ℕ. Define a scalar product [·, ·] on X by:

[δ_{x}, δ_{y}] =^{def} lim_{n→𝒰} \frac{1}{μ(B_{n}^{ℝ})} ∫_{B_{n}^{ℝ}}⟨φ(zx), φ(zy)⟩dμ(z),  (66)

where ⟨·, ·⟩ denotes the scalar product on L_{2}.

Since {B_{n}}_{n=1}^{∞} is a Følner sequence for ℍ(ℝ), a limit along a free ultrafilter of averages over B_{n} when n → ∞ is an invariant mean on ℍ(ℝ). It follows that the scalar product defined in (66) is π(ℍ(ℝ))-invariant. Thus π is a unitary representation of ℍ(ℝ) (formally we should first pass to the completion of the quotient of X by the subspace consisting of norm-zero elements, but we will ignore this inessential point in what follows). We note that π is also continuous in the strong operator topology. Indeed, since ψ is continuous and compactly supported, φ is uniformly continuous. Thus, writing ∥f∥_{X}^{2} =^{def} [f, f] for f ∈ X, we have for every y ∈ ℍ(ℝ),

lim_{x→e} ∥π(x)δ_{y} − δ_{y}∥_{X}^{2} = lim_{x→e} lim_{n→𝒰} \frac{1}{μ(B_{n}^{ℝ})} ∫_{B_{n}^{ℝ}} ∥φ(gxy) − φ(gy)∥_{2}^{2}dμ(g)

⩽ lim_{x→e} sup_{g∈ℍ(ℝ)} ∥φ(gxy) − φ(gy)∥_{2}^{2} = 0, (67)

implying the strong continuity of π.

Let γ : ℍ(ℝ) → X be given by γ(x) = δ_{x} − δ_{e}. Then π ∈ Z^{1}(π) and for all x ∈ X,

∥γ(x)∥_{X}^{2} = lim_{n→𝒰} \frac{1}{μ(B_{n}^{ℝ})} ∫_{B_{n}^{ℝ}} ∥φ(gx) − φ(g)∥_{2}^{2}dμ(g).  (68)

Arguing as in (67), the uniform continuity of φ and (68) imply that γ is a continuous 1-cocycle.

Fix n > 100r large enough so as to ensure that we have μ(B_{n} ∖ B_{n−100r}) ⩽ μ(B_{n})/2. Define I = {i ∈ ℕ : x_{i}B_{5r}^{ℝ} ⊆ B_{n}} and write Ω = ⋃_{i∈I} x_{i}B_{5r}^{ℝ} and Ω′ = ⋃_{i∈I} x_{i}B_{10r}^{ℝ}. By the maximality of {x_{i}B_{10r}^{ℝ}}_{i=1}^{∞} we have Ω′ ⊇ B_{n−100r}. Hence μ(Ω′) ⩾ μ(B_{n})/2. Since ℍ(ℝ) is doubling, μ(Ω′) ≲ μ(Ω), and therefore |I|μ(B_{5r}^{ℝ}) ⩾ μ(Ω) ≳ μ(B_{n}). Note that if g ∈ x_{i}B_{5r}^{ℝ} for some i ∈ ℕ then for every t ∈ [1, r^{2}] we have gc^{t} ∈ x_{i}B_{10r}. Hence,

\frac{1}{μ(B_{n}^{ℝ})} ∫_{B_{n}^{ℝ}} ∥φ(gc^{t}) − φ(g)∥_{2}^{2}dμ(g) ⩾ \frac{1}{μ(B_{n}^{ℝ})} ∑_{i∈I} ∫_{x_{i}B_{5r}^{ℝ}} ∥φ(gc^{t}) − φ(g)∥_{2}^{2}dμ(g)

= \frac{|I|}{μ(B_{n}^{ℝ})} ∫_{B_{5r}^{ℝ}} ∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}dμ(x) ≳ \frac{1}{μ(B_{5r}^{ℝ})} ∫_{B_{5r}^{ℝ}} ∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}dμ(x). (69)

It follows from (68) and (69) that

\frac{1}{μ(B_{5r}^{ℝ})} ∫_{B_{5r}^{ℝ}} ∫_{1}^{r^{2}} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dμ(x) ≲ ∫_{1}^{r^{2}} \frac{∥γ(c^{t})∥_{X}^{2}}{t^{2}} dt ≲^{(45)} sup_{s∈S_{ℝ}} ∥γ(s)∥_{X}^{2}

=^{(68)} sup_{s∈S_{ℝ}} lim_{n→𝒰} \frac{1}{μ(B_{n}^{ℝ})} ∫_{B_{n}^{ℝ}} ∥φ(gs) − φ(g)∥_{2}^{2}dμ(g). (70)

Let J ⊆ ℕ denote the set of i ∈ ℕ such that B_{n} ∩ x_{i}B_{2r} ≠ ∅. Then |J|μ(B_{2r}^{ℝ}) ⩽ μ(B_{n+4r}^{ℝ}). It follows that for all s ∈ S_{ℝ},

∫_{B_{n}^{ℝ}} ∥φ(gs) − φ(g)∥_{2}^{2}dμ(g) ⩽ ∑_{i∈J} ∫_{x_{i}B_{2r}} ∥φ(gs) − φ(g)∥_{2}^{2}dμ(g)

= |J| ∫_{B_{2r}} ∥ψ(xs) − ψ(x)∥_{2}^{2}dμ(x) ⩽ \frac{μ(B_{n+4r}^{ℝ})}{μ(B_{2r}^{ℝ})} ∫_{B_{2r}} ∥ψ(xs) − ψ(x)∥_{2}^{2}dμ(x). (71)

Substituting (71) into (70) we conclude that

∫_{ℍ(ℝ)} ∫_{1}^{∞} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dtdμ(x) =^{(64)} ∫_{B_{5r}^{ℝ}} ∫_{1}^{r^{2}} \frac{∥ψ(xc^{t}) − ψ(x)∥_{2}^{2}}{t^{2}} dμ(x)

≲^{(70)∧(71)} \frac{μ(B_{5r}^{ℝ})}{μ(B_{2r}^{ℝ})} sup_{s∈S_{ℝ}} lim_{n→𝒰} \frac{μ(B_{n+4r}^{ℝ})}{μ(B_{n}^{ℝ})} ∫_{B_{2r}} ∥ψ(xs) − ψ(x)∥_{2}^{2}dμ(x)

≲^{(65)} ∫_{ℍ(ℝ)} ( sup_{s∈S_{ℝ}} ∥ψ(xs) − ψ(x)∥_{2}^{2}) dμ(x)

This completes the proof of Claim 7.4, and therefore also the proof of Theorem 1.4.

7.5 A smooth Poincaré inequality on ℍ(ℝ)

Equip ℍ(ℝ) with the left-invariant Riemannian metric given by du^{2} + dv^{2} + (dw − udv)^{2}. In what follows, given a smooth function f : ℍ(ℝ) → ℝ we let ∇_{ℍ}f denote its gradient with respect to this Riemannian structure.

Theorem 7.5. For every smooth function f : ℍ(ℝ) → ℝ, and all R > 0,

∫_{B_{R}^{ℝ}} ∫_{1}^{R^{2}} \frac{|f(xc^{t}) − f(x)|^{2}}{t^{2}} dtdμ(x) ≲ ∫_{B_{CR}^{ℝ}} |∇_{ℍ}f(x)|^{2} dμ(x),

where C > 0 is a universal constant.

The proof of this Poincaré inequality can be obtained from Theorem 7.1 in a way similar, and actually even shorter than its discrete counterpart. Indeed, the discretization step of Claim 7.3 is not needed here. The other difference lies in the first step, where instead of the discrete Poincaré inequality (53), we use the following smooth version, which is due to [16]. For all R > 0, and for all smooth functions f : ℍ(ℝ) → ℝ whose integral over B_{R}^{ℝ} is zero,

\frac{1}{R^{2}} ∫_{B_{R}^{ℝ}} |f(g)|^{2}dμ(g) ≲ ∫_{B_{cR}^{ℝ}} |∇_{ℍ}f(g)|^{2}dμ(g),

where c > 0 is a universal constant.

References

[1] P. Assouad. Plongements Lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

[2] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[3] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[4] A. Brunel and L. Sucheston. Sur quelques conditions équivalentes à la super-réflexivité dans les espaces de Banach. C. R. Acad. Sci. Paris Sér. A-B, 275:A993–A994, 1972.

[5] D. Burago, Y. Burago, and S. Ivanov. A course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001.

[6] J. Cheeger and B. Kleiner. Differentiating maps into L^{1} and the geometry of BV functions. To appear in Ann. Math., preprint available at http://arxiv.org/abs/math/0611954, 2006.

[7] J. Cheeger and B. Kleiner. On the differentiability of Lipschtz maps from metric measure spaces into banach spaces. In Inspired by S.S. Chern, A Memorial volume in honor of a great mathematician, volume 11 of Nankai tracts in Mathematics, pages 129–152. World Scientific, Singapore, 2006.

[8] J. Cheeger, B. Kleiner, and A. Naor. Compression bounds for Lipschitz maps from the Heisen-

berg group to L_{1}. Preprint, 2009. http://arxiv.org/abs/0910.2026.

[9] J. Cheeger, B. Kleiner, and A. Naor. A (log n)^{Ω(1)} integrality gap for the Sparsest Cut SDP. In Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pages 555–564, 2009.

[10] Y. de Cornulier, R. Tessera, and A. Valette. Isometric group actions on Hilbert spaces: growth of cocycles. Geom. Funct. Anal., 17(3):770–792, 2007.

[11] N. Dunford and J. T. Schwartz. Linear operators. Part I. Wiley Classics Library. John Wiley & Sons Inc., New York, 1988. General theory, With the assistance of William G. Bade and Robert G. Bartle, Reprint of the 1958 original, A Wiley-Interscience Publication.

[12] G. B. Folland. Harmonic analysis in phase space, volume 122 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 1989.

[13] M. Gromov. Asymptotic invariants of infinite groups. In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.

[14] A. Guichardet. Sur la cohomologie des groupes topologiques. II. Bull. Sci. Math. (2), 96:305– 332, 1972.

[15] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 534–543. IEEE Computer Society, 2003.

[16] D. Jerison. The Poincaré inequality for vector fields satisfying Hörmander’s condition. Duke Math. J., 53(2):503–523, 1986.

[17] B. Kleiner. A new proof of Gromov’s theorem on groups of polynomial growth. J. Amer. Math. Soc., 23(4):815–829 (electronic), 2010.

[18] J. R. Lee and A. Naor. L_{p} metrics on the Heisenberg group and the Goemans-Linial conjecture. In Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 99–108, 2006. Available at

http://www.cims.nyu.edu/~naor/homepage%20files/L_pHGL.pdf.

[19] 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.

Available at http://arxiv.org/PS_cache/arxiv/pdf/0910/0910.2041v1.pdf.

[20] A. Naor. L_{1} embeddings of the Heisenberg group and fast estimation of graph isoperimetry. To appear in Proceedings of the International Congress of Mathematicians, (Hyderabad, 2010), 2010.

[21] A. Naor and Y. Peres. L_{p} compression, traveling salesmen, and stable walks. To appear in Duke Math. J., preprint available at http://arxiv.org/abs/0904.4728, 2009.

[22] P. Pansu. Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. of Math. (2), 129(1):1–60, 1989.

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

[24] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pages 300–306 (electronic), New York, 1999. ACM.

[25] S. Semmes. On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A_{∞}-weights. Rev. Mat. Iberoamericana, 12(2):337–410, 1996.

[26] R. Tessera. Asymptotic isoperimetry on groups and uniform embeddings into Banach spaces. To appear in Comment. Math. Helv., preprint available at

http://arxiv.org/abs/math/0603138, 2006.

[27] R. Tessera. Quantitative property A, Poincaré inequalities, L^{p}-compression and L^{p}-distortion for metric measure spaces. Geom. Dedicata, 136:203–220, 2008.