VERTICAL VERSUS HORIZONTAL POINCARÉ INEQUALITIES ON THE HEISENBERG GROUP

VINCENT LAFFORGUE AND ASSAF NAOR

Dedicated to Joram Lindenstrauss

Abstract. Let ℍ = ⟨a, b | a[a, b] = [a, b]a ∧ b[a, b] = [a, b]b⟩ be the discrete Heisenberg group, equipped with the left-invariant word metric d_{W} (·, ·) associated to the generating set {a, b, a^{−1}, b^{−1}}. Letting B_{n} = {x ∈ ℍ : d_{W} (x, e_{ℍ}) ⩽ n} denote the corresponding closed ball of radius n ∈ ℕ, and writing c = [a, b] = aba^{−1}b^{−1}, we prove that if (X, ∥·∥_{X}) is a Banach space whose modulus of uniform convexity has power type q ∈ [2, ∞) then there exists K ∈ (0, ∞) such that every f : ℍ → X satisfies

∑_{k=1}^{n^{2}} ∑_{x∈B_{n}} \frac{∥f(xc^{k}) − f(x)∥_{X}^{q}}{k^{1+q/2}}

⩽ K ∑_{x∈B_{21n}} (∥f(xa) − f(x)∥_{X}^{q} + ∥f(xb) − f(x)∥_{X}^{q}).

It follows that for every n ∈ ℕ the bi-Lipschitz distortion of every f : B_{n} → X is at least a constant multiple of (log n)^{1/q}, an asymptotically optimal estimate as n → ∞.

1. Introduction

The discrete Heisenberg group, denoted ℍ, is the group generated by two elements a, b ∈ ℍ, with the relations asserting that the commutator [a, b] = aba^{−1}b^{−1} is in the center of ℍ. Thus ℍ is given by the presentation ℍ = ⟨a, b | a[a, b] = [a, b]a ∧ b[a, b] = [a, b]b⟩. Write c = [a, b] and let e_{ℍ} denote the identity element of ℍ. The left-invariant word metric on ℍ induced by the symmetric generating set {a, b, a^{−1}, b^{−1}} is

2010 Mathematics Subject Classification. 46B85,20F65,42B25,35R03,68W25. Key words and phrases. Heisenberg group, bi-Lipschitz embeddings, Uniform

convexity, Littlewood-Paley inequality, Sparsest Cut Problem.

V. L. was supported in part by ANR grant KInd. A. N. was supported in part by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation. Part of this work was completed while A. N. was visiting Université de Paris Est Marne-la-Vallée.

denoted d_{W} (·, ·). For n ∈ ℕ let B_{n} = {x ∈ ℍ : d_{W} (x, e_{ℍ}) ⩽ n} denote the corresponding closed ball of radius n.

A Banach space (X, ∥ · ∥_{X}) is said to be uniformly convex if for every ε ∈ (0, 1) there exists δ ∈ (0, 1) such that every x, y ∈ X with ∥x∥_{X} = ∥y∥_{X} = 1 and ∥x − y∥_{X} ⩾ ε satisfy ∥x + y∥_{X} ⩽ 2(1 − δ). The supremum over those δ ∈ (0, 1) for which this holds true is denoted δ_{(X,∥·∥_{X})}(ε), and is called the modulus of uniform convexity of (X, ∥·∥_{X}). An important theorem of Pisier [Pis75] asserts that every uniformly convex Banach space (X, ∥ · ∥_{X}) admits an equivalent norm ∥ · ∥ for which there exist q ∈ [2, ∞) and η ∈ (0, 1) such that δ_{(X,∥·∥)}(ε) ⩾ (ηε)^{q} for all ε ∈ (0, 1). For concreteness we recall [Han56] that if p ∈ (1, ∞) then ℓ_{p} satisfies such an estimate with q = max{p, 2}.

Theorem 1.1 (Vertical versus horizontal Poincaré inequality). For every η ∈ (0, 1) and q ∈ [2, ∞) there exists K = K(η, q) ∈ (0, ∞) with the following property. Suppose that (X, ∥ · ∥_{X}) is a Banach space satisfying δ_{(X,∥·∥_{X})}(ε) ⩾ (ηε)^{q} for every ε ∈ (0, 1). Then for every n ∈ ℕ and every f : ℍ → X we have

∑_{k=1}^{n^{2}} ∑_{x∈B_{n}} \frac{∥f(xc^{k}) − f(x)∥_{X}^{q}}{k^{1+q/2}}

⩽ K ∑_{x∈B_{21n}} (∥f(xa) − f(x)∥_{X}^{q} + ∥f(xb) − f(x)∥_{X}^{q}). (1)

The constant 21 appearing in the range of the summation on the right hand side of (1) is an artifact of our proof and is not claimed to be sharp. The important point here is that the summation on the right hand side of (1) is over x ∈ B_{λn} for some universal constant λ ∈ ℕ. One can clearly make the same statement for word metrics induced by other finite symmetric generating sets of ℍ: the choice of generating set will only affect the value of λ.

An inspection of our proof of Theorem 1.1 reveals that K^{1/q} ≲ 1/η, but we will not explicitly track the value of such constants in the ensuing discussion. Here, and in what follows, we use A ≲ B and B ≳ A to denote the estimate A ⩽ CB for some absolute constant C ∈ (0, ∞). If we need C to depend on parameters, we indicate this by subscripts, thus e.g. A ≲_{α} B means that A ⩽ C_{α}B for some C_{α} ∈ (0, ∞) depending only on α. We shall also use the notation A ≍ B for A ≲ B ∧ B ≲ A, and similarly A ≍_{α} B stands for A ≲_{α} B ∧ B ≲_{α} A.

We call (1) a “vertical versus horizontal Poincaré inequality” for the following reason. The right hand side of (1) is the ℓ_{q} norm of the discrete horizontal gradient of f: it measures the “local” variation of f along the edges of the Cayley graph of ℍ (a.k.a. the horizontal edges in ℍ). The left hand side of (1) measures the “global” variation of f along the center of ℍ (a.k.a. the vertical direction in ℍ). Theorem 1.1 asserts that the global vertical variation of f is always bounded by its local horizontal variation. Thus, if the right hand side of (1) is small then f must collapse distances along the center of ℍ.

The (bi-Lipschitz) distortion of a finite metric space (M, d_{M}) in a Banach space (X, ∥ · ∥_{X}), denoted c_{X}(M, d_{M}) ∈ [1, ∞), is the infimum over those D ∈ [1, ∞) for which there exists an embedding f : M → X that satisfies d_{M}(x, y) ⩽ ∥f(x) − f(y)∥_{X} ⩽ Dd_{M}(x, y) for all x, y ∈ M. When X = ℓ_{p} for some p ∈ [1, ∞) it is customary to write c_{ℓ_{p}}(M, d_{M}) = c_{p}(M, d_{M}). The quantity c_{2}(M, d_{M}) is known as the Euclidean distortion of (M, d_{M}). Suppose that (X, ∥ · ∥_{X}) satisfies the assumption of Theorem 1.1 and that f : ℍ → X satisfies d_{W} (x, y) ⩽ ∥f(x) − f(y)∥_{X} ⩽ Dd_{W} (x, y) for all x, y ∈ B_{22n}. Since d_{W} (c^{k}, e_{ℍ}) ≍ \sqrt{k} for every k ∈ ℕ and |B_{m}| ≍ m^{4} for every m ∈ ℕ (see e.g. [Bla03]), Theorem 1.1 applied to f yields the following estimate.

n^{4} log n ≲ ∑_{k=1}^{n^{2}} n^{4} \frac{k^{q/2}}{k^{1+q/2}} ≲_{X} n^{4}D^{q}.  (2)

We therefore obtain the following corollary of Theorem 1.1.

Corollary 1.2 (Sharp nonembeddabilty of balls in ℍ). Fix η ∈ (0, 1) and q ∈ [2, ∞). Suppose that (X, ∥ · ∥_{X}) is a Banach space satisfying δ_{(X,∥·∥_{X})}(ε) ⩾ (ηε)^{q} for every ε ∈ (0, 1). Then for every n ∈ ℕ we have

c_{X} (B_{n}, d_{W}) ≳_{η} (log n)^{1/q}.

Corollary 1.2 yields an estimate on c_{X}(B_{n}, d_{W}) in terms of the modulus of uniform convexity of (X, ∥ · ∥_{X}) which is asymptotically best possible, up to constant factors that are independent of n. The following corollary states this explicitly for the case of special interest X = ℓ_{p}, though one could equally well state such results for a variety of concrete spaces for which the modulus of uniform convexity has been computed (e.g., the same conclusion holds true with ℓ_{p} replaced by the Schatten class S_{p}, due to the computation of its modulus of uniform convexity in [TJ74]).

Corollary 1.3. For every integer n ⩾ 2 we have

p ∈ (1, 2] ⟹ c_{p}(B_{n}, d_{W}) ≍_{p} \sqrt{log n},

and

p ∈ [2, ∞) ⟹ c_{p}(B_{n}, d_{W}) ≍_{p} (log n)^{1/p}.

The lower bounds on c_{p}(B_{n}, d_{W}) that appear in Corollary 1.3 are a special case of Corollary 1.2 (in this case q = max{p, 2}). There are several ways to establish the asymptotically matching upper bounds. Assouad proved in [Ass83] that there exists k ∈ ℕ and 1-Lipschitz functions {ϕ_{j} : ℍ → ℝ^{k}}_{j=1}^{∞} such that for every x, y ∈ ℍ and j ∈ ℕ,

d_{W} (x, y) ∈ [2^{j−1}, 2^{j}] ⟹ ∥ϕ_{j}(x) − ϕ_{j}(y)∥_{∞} ≳ d_{W} (x, y).

By concatenating ϕ_{1}, …, ϕ_{m} for m ≍ log n one sees that the distortion lower bounds of Corollary 1.3 are indeed asymptotically sharp. An alternative embedding of (B_{n}, d_{W}) into ℓ_{p} with the desired distortion bound was found by Tessera in [Tes08]. For p = 2 one can use the explicit closed-form embedding of ℍ into ℓ_{2} of [LN06], where for every ε ∈ (0, 1) a mapping f_{ε} : ℍ → ℓ_{2} is given with

∀ x, y ∈ ℍ, d_{W} (x, y)^{1−ε} ⩽ ∥f_{ε}(x) − f_{ε}(y)∥_{2} ≲ \frac{d_{W} (x, y)^{1−ε}}{\sqrt{ε}} .

Setting ε = 1/ log n shows that c_{2}(B_{n}, d_{W}) ≲ \sqrt{log n}.

The above distortion bounds complete a sequence of investigations of the (non)embeddability of the Heisenberg group into “nice” Banach spaces. A famous observation of Semmes [Sem96] shows that Pansu’s differentiation theorem for Carnot groups [Pan89] implies that ℍ does not admit a bi-Lipschitz embedding into ℝ^{n} for any n ∈ ℕ. Alternative proofs of this fact were obtained by Cheeger [Che99] and Pauls [Pau01]. The fact that the Pansu-Semmes argument can be extended to certain infinite dimensional targets, yielding in particular the bi-Lipschitz nonembeddability of ℍ into any uniformly convex Banach space, was obtained independently by [CK06] and [LN06] (via different arguments). In [CK10a] Cheeger and Kleiner proved that ℍ does not admit a bi-Lipschitz embedding into any L_{1}(μ) space, a result that is important for an application to theoretical computer science that will be mentioned in Section 4. Note that not all uniformly convex Banach spaces admit a bi-Lipschitz embedding into an L_{1}(μ) space (e.g. ℓ_{p} for p ∈ (2, ∞)), but the Cheeger-Kleiner theorem does yield a new proof of the nonembeddability of ℍ into some uniformly convex spaces of interest, such as L_{p} for p ∈ (1, 2], because they are isomorphic to subspaces of L_{1}. In [CK10b] Cheeger and Kleiner discovered a different proof of the nonembeddability of ℍ into an L_{1}(μ) space.

The results quoted above imply that lim_{n→∞} c_{X}(B_{n}, d_{W}) = ∞ for the respective target Banach spaces X, but they give no information on the rate at which c_{X}(B_{n}, d_{W}) tends to ∞ with n. In order to obtain such quantitative nonembeddability results one needs to overcome additional (conceptual and technical) issues. The first progress in this direction was due to [CKN11], where it is shown that c_{1}(B_{n}, d_{W}) ≳ (log n)^{κ} for some universal constant κ > 0. In [ANT10] it is shown that c_{2}(B_{n}, d_{W}) ≳ \sqrt{log n} and that if (X, ∥ · ∥_{X}) is a Banach space satisfying δ_{(X,∥·∥_{X})}(ε) ≳_{X} ε^{q} for every ε ∈ (0, 1) then c_{X}(B_{n}, d_{W}) ≳_{X} (log n/ log log n)^{1/q}. Recently, Li [Li13] obtained a quantitative version of Pansu’s differentiation theorem which yields the estimate c_{X}(B_{n}, d_{W}) ≳_{X} (log n)^{θ_{X}} for some θ_{X} > 0.

As explained above, except for the asymptotic evaluation of the Euclidean distortion c_{2}(B_{n}, d_{W}) that was obtained in [ANT10], computing c_{X}(B_{n}, d_{W}) up to constant factors that are independent of n remained open for all non-Hilbertian Banach spaces (the lower bound in [ANT10] was off by an iterated logarithm factor). Corollary 1.2 resolves this problem for uniformly convex Banach spaces. Other than yielding a complete result for an important class of Banach spaces, the significance of Corollary 1.2 is that its proof is different from the approaches that have been used thus far in the literature.

Specifically, all the above mentioned results first use a limiting argument that shows that it suffices to rule out low-distortion embeddings that belong to a certain “structured” subclass of all the possible embeddings (e.g. in the case of the Pansu-Semmes proof one argues that it suffices to deal with group homomorphisms). The proofs in [Pan89, Sem96, Che99, Pau01, CK06, LN06, CK10a, CK10b, CKN11, Li13] all apply this general “metric differentiation” strategy. The proof in [ANT10] uses a different but related approach: one first argues that it suffices to rule out embeddings that are 1-cocycles with respect to an isometric action of ℍ on X; when X is Hilbert space this is done via an argument of Aharoni, Maurey and Mityagin [AMM85] and Gromov [dCTV07], and for general uniformly convex X this is done via an argument of [NP11]. When X is a general uniformly convex Banach space one proceeds in [ANT10] via an algebraic argument and a quantitative version of a mean ergodic theorem, yielding a bound that is off by an iterated logarithm factor. This argument fails to yield a Poincaré inequality such as (1). The proof of the sharp estimate on the Euclidean distortion c_{2}(B_{n}, d_{W}) proceeds in [ANT10] by proving the Hilbertian case of the Poincaré inequality (1): this is done using a theorem of Guichardet [Gui72] that further reduces the problem to coboundaries, and since we are interested in an inequality that involves squares of Euclidean distances, one can use the available orthogonality to reduce to the case where the underlying unitary representation is irreducible. Co-boundaries with respect to irreducible representations may then be treated separately via a direct argument.

We do not know how to prove Theorem 1.1 using the above strategies: metric differentiation arguments seem to inherently lose (at least) an iterated logarithm factor, and in the only case where a sharp bound was proved the argument heavily uses the Hilbertian structure. Our approach is therefore entirely different: we prove the inequality (1) directly via an analytic argument that relies on generalized Littlewood-Paley g-function estimates. While our method does not yield an improved lower bound on c_{1}(B_{n}, d_{W}), it suggests a clean isoperimetrictype inequality that, if true, would yield the (at present still conjectural) sharp estimate c_{1}(B_{n}, d_{W}) ≳ \sqrt{log n}. This conjecture, whose investigation is deferred to future work, is discussed in Section 4.

1.1. Overview of the proof of Theorem 1.1. In Section 3 we prove that Theorem 1.1 follows from a certain global Poincaré-type inequality on the continuous Heisenberg group. Following the strategy of [ANT10], this is achieved through a localization step based on a variant of Kleiner’s local Poincaré inequality [Kle10], combined with a partition of unity argument. The heart of the matter is therefore a continuous analogue of Theorem 1.1, which is formulated as Theorem 2.1 below. In Section 2 we recall basic facts about the continuous Heisenberg group, and state as Proposition 2.2 the main new estimate that controls the left hand side of the desired Poincaré inequality (the “vertical variation”) in terms of the time-evolutes of the horizontal gradient of the given function under the time-derivative of the Poisson semigroup along the center. Once this is achieved, we conclude the proof using a vector-valued version of the Littlewood-Paley g-function inequality that was proved by Martinez, Torrea and Xu in [MTX06]. The proof of the key estimate that is stated as Proposition 2.2 consists of two steps. The first one follows the lines of a standard argument of Littlewood-Paley theory that relates the left hand side of the desired inequality to the evolutes of the given function under the Poisson semigroup along the center (here we modify appropriately the exposition in Stein’s book [Ste70]). The only part of our argument that uses the geometry of the Heisenberg group appears in Lemma 2.4 below. This limited use of Heisenberg geometry indicates that our arguments can be adapted in a straightforward manner so as to apply to more general nilpotent groups, but we did not attempt to carry out the proof in such generality since it is not needed for our purposes.

Acknowledgements. We are grateful to Artem Kozhevnikov, Pierre Pansu and Robert Young for enlightening discussions on the questions presented in Section 4, and for sharing their ongoing work on this topic.

2. Inequalities on the real Heisenberg group

We start by setting some (mostly standard) notation and terminology. The Heisenberg group ℍ can be identified with the following matrix group, equipped with matrix multiplication.

ℍ = \{( \begin{matrix}1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{matrix} ) : x, y, z ∈ ℤ\} .

Under this identification, we have

a = ( \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) and b = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) .

Thus

c = aba^{−1}b^{−1} = ( \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

We will reason below about the real Heisenberg group, denoted ℍ(ℝ), which is defined as

ℍ(ℝ) =^{def} \{( \begin{matrix}1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{matrix} ) : x, y, z ∈ ℝ\} .

We will use the following notation for every x, y, z ∈ ℝ.

a^{x} =^{def} ( \begin{matrix}1 & x & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) , b^{y} =^{def} ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & y \\ 0 & 0 & 1 \end{matrix} ) , c^{z} =^{def} ( \begin{matrix}1 & 0 & z \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

Thus,

c^{z}b^{y}a^{x} = ( \begin{matrix}1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{matrix} ) .

It is convenient to identify ℍ(ℝ) with ℝ^{3}. In particular, for a Banach space (X, ∥ · ∥_{X}) and a mapping f : ℍ(ℝ) → X, we identify f(x, y, z) with f(c^{z}b^{y}a^{x}). Under this identification, the Lebesgue measure on ℝ^{3} is a Haar measure on ℍ(ℝ); below we denote this measure on ℍ(ℝ) by μ. The spaces ℝ, ℝ^{2}, ℍ(ℝ) will always be understood to be endowed with the Lebesgue measure. Thus for p ∈ [1, ∞) the Lebesgue-Bochner spaces L_{p}(ℝ, X), L_{p}(ℝ^{2}, X), L_{p}(ℍ(ℝ), X) are defined unambiguously. For f ∈ L_{p}(ℍ(ℝ), X) define f^{c} : ℝ → L_{p}(ℝ^{2}, X) by

f^{c}(z)(x, y) = f(x, y, z).  (3)

Given ψ ∈ L_{1}(ℝ), we define the convolution ψ ∗ f ∈ L_{p}(ℍ(ℝ), X) by ψ ∗ f(x, y, z) = (ψ ∗ f^{c})(z)(x, y), i.e.,

ψ ∗ f(x, y, z) =^{def} ∫_{ℝ} ψ(u)f(x, y, z − u)du ∈ X.  (4)

Equivalently, ψ∗f is the usual group convolution of f with the measure supported on the center of ℍ(ℝ) whose density is ψ.

Suppose that f : ℍ(ℝ) → X is smooth. The identification of ℍ(ℝ) with ℝ^{3} gives meaning to the partial derivatives \frac{∂f}{∂x}, \frac{∂f}{∂y}. We define the left-invariant vector fields ∂_{a}f, ∂_{b}f : ℍ(ℝ) → X by

∂_{a}f(x, y, z) =^{def} \frac{∂f}{∂x}(x, y, z),  (5)

and

∂_{b}f(x, y, z) =^{def} \frac{∂f}{∂y} (x, y, z) + x\frac{∂f}{∂z} (x, y, z).  (6)

The horizontal gradient of f is then defined as

∇_{ℍ}f =^{def} (∂_{a}f, ∂_{b}f) : ℍ(ℝ) → X ⊕ X.  (7)

Thus for p ∈ [1, ∞) and x, y, z ∈ ℝ we have

∥∇_{ℍ}f(x, y, z)∥_{ℓ_{p}^{2}(X)}

= (∥\frac{∂f}{∂x}(x, y, z)∥_{X}^{p} + ∥\frac{∂f}{∂y} (x, y, z) + x\frac{∂f}{∂z} (x, y, z)∥_{X}^{p})^{1/p} .

Theorem 2.1 below, the case p = q of which establishes a continuous version of the Poincaré inequality of Theorem 1.1, is the main result of this section. Theorem 1.1 itself will be shown in Section 3 to follow from Theorem 2.1 via a partition of unity argument.

Theorem 2.1 (Real vertical versus horizontal Poincaré inequality). Suppose that q ∈ [2, ∞) and p ∈ (1, q]. Let (X, ∥·∥_{X}) be a Banach space satisfying δ_{(X,∥·∥_{X})}(ε) ⩾ (ηε)^{q} for every ε ∈ (0, 1) and some η ∈ (0, 1). Then every smooth and compactly supported f : ℍ(ℝ) → X satisfies

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥f(hc^{t}) − f(h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

≲_{η,p,q} (∫_{ℍ(ℝ)} ∥∇_{ℍ}f(h)∥_{ℓ_{p}^{2}(X)}^{p} dμ(h))^{1/p} . (8)

In preparation for the proof of Theorem 2.1, we first prove some preparatory lemmas. The Poisson kernel on ℝ is defined as usual for every t, x ∈ ℝ by

P_{t}(x) =^{def} \frac{t}{π(t^{2} + x^{2})}.

We also write

Q_{t}(x) =^{def} \frac{∂}{∂t}P_{t}(x) = \frac{x^{2} − t^{2}}{π(t^{2} + x^{2})^{2}} ,  (9)

and

R_{t}(x) =^{def} \frac{∂}{∂x}P_{t}(x) = \frac{−2tx}{π(t^{2} + x^{2})^{2}} .  (10)

We record for future use that for every t ∈ (0, ∞),

∫_{0}^{∞} \sqrt{x}P_{t}(x)dx = \frac{\sqrt{t}}{π} ∫_{0}^{∞} \frac{\sqrt{y}}{1 + y^{2}} dy = \sqrt{\frac{t}{2}},  (11)

∥Q_{t}∥_{L_{1}(ℝ)} = \frac{1}{πt} ∫_{ℝ} \frac{|1 − y^{2}|}{(1 + y^{2})^{2}} dy = \frac{2}{πt},  (12)

and

∥R_{t}∥_{L_{1}(ℝ)} = \frac{2}{πt} ∫_{ℝ} \frac{|y|}{(1 + y^{2})^{2}} dy = \frac{2}{πt}.  (13)

(The precise constants appearing in (11), (12) and (13) are not needed in the ensuing discussion: only the stated dependence on t up to constant factors will be used.)

The main step of the proof of Theorem 2.1 is Proposition 2.2 below.

Proposition 2.2. Fix p, q ∈ [1, ∞) and let (X, ∥ · ∥_{X}) be a Banach space. Every smooth and compactly supported f : ℍ(ℝ) → X satisfies

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥f(hc^{t}) − f(h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

≲ (∫_{0}^{∞} t^{q−1} ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}^{q} dt)^{1/q} .

Remark 2.3. Continuing with the notation of Proposition 2.2, for every t ∈ (0, ∞) denote τ_{t}f : ℍ(ℝ) → X by τ_{t}f(h) = f(hc^{t}). Write also S_{t} = \frac{π}{2}tQ_{t}. By (12) this yields the normalization ∥S_{t}∥_{L_{1}(ℝ)} = 1. The assertion of Proposition 2.2 can then be rewritten as

∥∥\frac{τ_{t}f − f}{\sqrt{t}} ∥_{L_{p}(ℍ(ℝ),X)}∥_{L_{q}(ℝ_{+}, \frac{dt}{t})} ≲ ∥∥S_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}∥_{L_{q}(ℝ_{+}, \frac{dt}{t})} .

Introducing S_{t} in this way helps explain the meaning of the powers of t that appear in the statement of Proposition 2.2, but it makes the ensuing proofs more cumbersome. We will therefore continue working with Q_{t} rather than S_{t} in what follows.

Assuming the validity of Proposition 2.2 for the moment, we now proceed to show how it implies Theorem 2.1.

Proof of Theorem 2.1. Given a Banach space space (𝔹, ∥ · ∥_{𝔹}), for every function ϕ ∈ L_{p}(ℝ, 𝔹) its generalized Littlewood-Paley g-function 𝔊_{q}(ϕ) : ℝ → [0, ∞] is defined as follows.

𝔊_{q}(ϕ)(x) =^{def} (∫_{0}^{∞} t^{q−1} ∥Q_{t} ∗ ϕ(x)∥_{𝔹}^{q} dt)^{1/q} .  (14)

A beautiful theorem of Martinez, Torrea and Xu [MTX06, Thm. 2.1] asserts that if δ_{(𝔹,∥·∥_{𝔹})}(ε) ⩾ (ξε)^{q} for every ε ∈ (0, 1) and some constant ξ ∈ (0, 1) then for every p ∈ (1, ∞),

ϕ ∈ L_{p}(ℝ, 𝔹) ⟹ ∥𝔊_{q}(ϕ)∥_{L_{p}(ℝ,𝔹)} ≲_{ξ,p,q} ∥ϕ∥_{L_{p}(ℝ,𝔹)}.  (15)

In fact, it is shown in [MTX06] that the validity of (15) for some p ∈ (1, ∞) (equivalently for all p ∈ (1, ∞)) is equivalent to 𝔹 admitting an equivalent norm whose modulus of uniform convexity is at least a constant multiple of ε^{q}. Note that Theorem 2.1 of [MTX06] asserts (15) under the assumption that (𝔹, ∥ · ∥_{𝔹}) has martingale cotype q, but this follows from our assumption on the modulus of uniform convexity of (𝔹, ∥ · ∥_{𝔹}) by important work of Pisier [Pis75].

We shall apply (15) to 𝔹 = L_{p}(ℝ^{2}, ℓ_{p}^{2}(X)). Since we are assuming in Theorem 2.1 that p ∈ (1, q], by a result of Figiel [Fig76] there exists ξ = ξ(η, p, q) ∈ (0, 1) such that δ_{(𝔹,∥·∥_{𝔹})}(ε) ⩾ (ξε)^{q} for every ε ∈ (0, 1) (see Corollary 6.4 in [MN12] for an explicit dependence of ξ on η, p, q). Recalling (3), consider the function ϕ = (∇_{ℍ}f)^{c} : ℝ → 𝔹. Then,

(∫_{0}^{∞} t^{q−1} ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}^{q} dt)^{1/q}

= (∫_{0}^{∞} (∫_{ℝ} (t ∥Q_{t} ∗ ϕ(z)∥_{𝔹})^{p} dz)^{q/p} \frac{dt}{t})^{1/q}  (16)

⩽ (∫_{ℝ} (∫_{0}^{∞} (t ∥Q_{t} ∗ ϕ(z)∥_{𝔹})^{q} \frac{dt}{t})^{p/q} dz)^{1/p}  (17)
= ∥𝔊_{q}(ϕ)∥_{L_{p}(ℝ,𝔹)} ≲_{η,p,q} ∥ϕ∥_{L_{p}(ℝ,𝔹)},  (18)

where in (16) we used the definitions of 𝔹 and ϕ, in (17) we used the fact that p ⩽ q, and in (18) we used (14) and (15). Noting that by the definition of ϕ we have ∥ϕ∥_{L_{p}(ℝ,𝔹)} = ∥∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}, the desired inequality (8) follows from Proposition 2.2. □

We now pass to the proof of Proposition 2.2.

Lemma 2.4. Suppose that p ∈ [1, ∞) and t ∈ (0, ∞). Then for every Banach space (X, ∥ · ∥_{X}) and every smooth and compactly supported f : ℍ(ℝ) → X we have

∥Q_{t} ∗ f − Q_{2t} ∗ f∥_{L_{p}(ℍ(ℝ),X)} ≲ \sqrt{t} · ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))} . (19)

Proof. The semigroup property of P_{t} implies that P_{2t} = P_{t} ∗ P_{t}. By differentiating this identity with respect to t we have Q_{2t} = P_{t} ∗ Q_{t}. Consequently, for every h ∈ ℍ(ℝ) we have

Q_{t} ∗ f(h) − Q_{2t} ∗ f(h) = Q_{t} ∗ f(h) − P_{t} ∗ Q_{t} ∗ f(h)

= ∫_{ℝ} P_{t}(u) (Q_{t} ∗ f(h) − Q_{t} ∗ f(hc^{−u})) du, (20)

where we used the fact that ∫_{ℝ} P_{t}(u)du = 1.

For every s ∈ [0, ∞) let γ_{s} : [0, 4\sqrt{s}] → ℍ(ℝ) be the commutator path joining e_{ℍ} and c^{s}, i.e.,

γ_{s}(θ) =^{def} \{ \begin{matrix}a^{θ} & if 0 ⩽ θ ⩽ \sqrt{s}, \\ a^{\sqrt{s}}b^{θ−\sqrt{s}} & if \sqrt{s} ⩽ θ ⩽ 2\sqrt{s}, \\ a^{\sqrt{s}}b^{\sqrt{s}}a^{−θ+2\sqrt{s}} & if 2\sqrt{s} ⩽ θ ⩽ 3\sqrt{s}, \\ a^{\sqrt{s}}b^{\sqrt{s}}a^{−\sqrt{s}}b^{−θ+3\sqrt{s}} & if 3\sqrt{s} ⩽ θ ⩽ 4\sqrt{s}. \end{matrix}

For every u ∈ [0, ∞) and h ∈ ℍ(ℝ) we then have

Q_{t} ∗ f(h) − Q_{t} ∗ f(hc^{−u}) = Q_{t} ∗ f(hc^{−u}γ_{u}(4\sqrt{u})) − Q_{t} ∗ f(hc^{−u})

= ∫_{0}^{4\sqrt{u}} \frac{d}{dθ}Q_{t} ∗ f(hc^{−u}γ_{u}(θ))dθ. (21)

Recalling (5) and (6), observe that for every θ ∈ [0, 4\sqrt{u}] we have

\frac{d}{dθ}Q_{t} ∗ f(hc^{−u}γ_{u}(θ)) ∈ \{∂_{a}Q_{t} ∗ f(hc^{−u}γ_{u}(θ)), ∂_{b}Q_{t} ∗ f(hc^{−u}γ_{u}(θ))\}

= {Q_{t} ∗ ∂_{a}f(hc^{−u}γ_{u}(θ)), Q_{t} ∗ ∂_{b}f(hc^{−u}γ_{u}(θ))} , (22) where we also used the fact that convolution with Q_{t} commutes with ∂_{a} and ∂_{b}. Recalling (7), we deduce from (21) and (22) that

(∫_{ℍ(ℝ)} ∥∫_{0}^{∞} P_{t}(u) (Q_{t} ∗ f(h) − Q_{t} ∗ f(hc^{−u})) du∥_{X}^{p} dμ(h))^{1/p}

⩽ ∫_{0}^{∞} ∫_{0}^{4\sqrt{u}} P_{t}(u) (∫_{ℍ(ℝ)} ∥Q_{t} ∗ ∇_{ℍ}f(hc^{−u}γ_{u}(θ))∥_{ℓ_{p}^{2}(X)}^{p} dμ(h))^{1/p} dθdu

= (∫_{0}^{∞} 4\sqrt{u}P_{t}(u)du) ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}  (23)
= 2\sqrt{2t} · ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))},  (24)

where in (23) we used the right-invariance of the Haar measure μ on ℍ(ℝ) and in (24) we used (11).

The analogue of (21) for u ∈ (−∞, 0] is the identity

Q_{t} ∗ f(h) − Q_{t} ∗ f(hc^{−u}) = − ∫_{0}^{4\sqrt{|u|}} \frac{d}{dθ}Q_{t} ∗ f(hγ_{−u}(θ))dθ.

This, combined with the above reasoning yields the estimate

(∫_{ℍ(ℝ)} ∥∫_{−∞}^{0} P_{t}(u) (Q_{t} ∗ f(h) − Q_{t} ∗ f(hc^{−u})) du∥_{X}^{p} dμ(h))^{1/p}

⩽ 2\sqrt{2t} · ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}. (25)

(24) and (25) combined with (20) yields the desired inequality (19). □

Lemma 2.5. Fix p, q ∈ [1, ∞). For every Banach space (X, ∥ · ∥_{X}), every smooth and compactly supported f : ℍ(ℝ) → X satisfies

(∫_{0}^{∞} t^{\frac{q}{2} −1} ∥Q_{t} ∗ f∥_{L_{p}(ℍ(ℝ),X)}^{q} dt)^{1/q}

≲ (∫_{0}^{∞} t^{q−1} ∥Q_{t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}^{q} dt)^{1/p} .

Proof. Observe that lim_{t→∞} Q_{t} ∗ f = 0 in L_{p}(ℍ(ℝ), X). Indeed, by Young’s inequality,

∥Q_{t} ∗ f∥_{L_{p}(ℍ(ℝ),X)} ⩽ ∥Q_{t}∥_{L_{1}(ℝ)} · ∥f∥_{L_{p}(ℍ(ℝ),X)} =^{(12)} \frac{2}{πt} · ∥f∥_{L_{p}(ℍ(ℝ),X)}.

We therefore have the identity

Q_{t} ∗ f = ∑_{m=1}^{∞} (Q_{2^{m−1}t} ∗ f − Q_{2^{m}t} ∗ f) ,

from which it follows that

(∫_{0}^{∞} t^{\frac{q}{2} −1} ∥Q_{t} ∗ f∥_{L_{p}(ℍ(ℝ),X)}^{q} dt)^{1/q}

⩽ ∑_{m=1}^{∞} (∫_{0}^{∞} t^{\frac{q}{2} −1} ∥Q_{2^{m−1}t} ∗ f − Q_{2^{m}t} ∗ f∥_{L_{p}(ℍ(ℝ),X)}^{q} dt)^{1/q}

≲ ∑_{m=1}^{∞} (∫_{0}^{∞} t^{\frac{q}{2} −1}(2^{m−1}t)^{q/2} ∥Q_{2^{m−1}t} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}^{q} dt)^{1/q} (26)

= (∑_{m=1}^{∞} \frac{1}{2^{(m−1)/2}} ) (∫_{0}^{∞} s^{q−1} ∥Q_{s} ∗ ∇_{ℍ}f∥_{L_{p}(ℍ(ℝ),ℓ_{p}^{2}(X))}^{q} ds)^{1/p} , (27)

where (26) uses Lemma 2.4, and (27) follows from the change of variable s = 2^{m−1}t in each of the summands of (26). □

Lemma 2.6 below is an analogue of a standard fact in Littlewood-Paley theory: it is commonly stated for real-valued functions defined on ℝ, while we need a statement for Banach space-valued functions defined on ℍ(ℝ). In the real-valued case this fact has several known proofs, and while we do not know how to extend all of them to the vectorvalued setting, the argument below is nothing more than the obvious modification of the corresponding proof in Stein’s book [Ste70].

Lemma 2.6. Fix p, q ∈ [1, ∞) and let (X, ∥ · ∥_{X}) be a Banach space. Every smooth and compactly supported f : ℍ(ℝ) → X satisfies

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥f(hc^{t}) − f(h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

≲ (∫_{0}^{∞} t^{\frac{q}{2} −1} ∥Q_{t} ∗ f∥_{L_{p}(ℍ(ℝ),X)}^{q} dt)^{1/q} . (28)

Proof. For every (h, t) ∈ ℍ(ℝ) × (0, ∞) write

f(hc^{t}) − f(h) = [f(hc^{t}) − P_{t} ∗ f(hc^{t})]

+ [P_{t} ∗ f(hc^{t}) − P_{t} ∗ f(h)] + [P_{t} ∗ f(h) − f(h)]. (29)

We proceed to bound each of the terms in the right hand side of (29) separately. Firstly,

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥f(hc^{t}) − P_{t} ∗ f(hc^{t})∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

= (∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥∫_{0}^{t} Q_{s} ∗ f(hc^{t})ds∥_{X}^{p} dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q} (30)

⩽ (∫_{0}^{∞} (∫_{0}^{t} ∥Q_{s} ∗ f∥_{L_{p}(ℍ(ℝ),X)} ds)^{q} \frac{dt}{t^{1+q/2}} )^{1/q}  (31)

⩽ 2 (∫_{0}^{∞} t^{\frac{q}{2} −1}∥Q_{t} ∗ f(x)∥_{L_{p}(ℍ(ℝ),X)}^{q}dt)^{1/q} ,  (32)

where for (30) recall that in (9) we defined Q_{t} as the time derivative of P_{t}, in (31) we used the triangle inequality in L_{p}(ℍ(ℝ), X) and the fact that the Haar measure μ is right-invariant, and in (32) we used Hardy’s inequality (see [Ste70, Sec. A.4]). The rightmost term in the right hand side of (29) is bounded using the same argument, yielding the following inequality.

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥P_{t} ∗ f(h) − f(h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

⩽ 2 (∫_{0}^{∞} t^{\frac{q}{2} −1}∥Q_{t} ∗ f(x)∥_{L_{p}(ℍ(ℝ),X)}^{q}dt)^{1/q} . (33)

To bound the middle term in the right hand side of (29) recall that by the semigroup property of the Poisson kernel, for every t ∈ (0, ∞) we have P_{t} = P_{t/2} ∗ P_{t/2}. As we have done in the proof of Lemma 2.4, differentiation of this identity with respect to t yields Q_{t} = P_{t/2} ∗ Q_{t/2}. Consequently, recalling the definition of R_{t} in (10),

\frac{∂}{∂t}R_{t} = \frac{∂}{∂x}Q_{t} = \frac{∂}{∂x} (P_{t/2} ∗ Q_{t/2}) = R_{t/2} ∗ Q_{t/2}.  (34)

Observe that lim_{t→∞} R_{t} ∗ f = 0 in L_{p}(ℍ(ℝ), X). Indeed,

∥R_{t} ∗ f∥_{L_{p}(ℍ(ℝ),X)} ⩽ ∥R_{t}∥_{L_{1}(ℝ)} · ∥f∥_{L_{p}(ℍ(ℝ),X)} =^{(13)} \frac{2}{πt} · ∥f∥_{L_{p}(ℍ(ℝ),X)}.

Consequently,

R_{t} ∗ f = − ∫_{t}^{∞} \frac{∂}{∂s}(R_{s} ∗ f)ds =^{(34)} − ∫_{t}^{∞} R_{s/2} ∗ (Q_{s/2} ∗ f)ds. (35)

The middle term in the right hand side of (29) can therefore be rewritten as follows.

P_{t} ∗ f(hc^{t}) − P_{t} ∗ f(h) = ∫_{0}^{t} R_{t} ∗ f(hc^{u})du

= − ∫_{0}^{t} ∫_{t}^{∞} R_{s/2} ∗ (Q_{s/2} ∗ f)(hc^{u})dsdu. (36)

Observe that for every t ∈ (0, ∞) we have

(∫_{ℍ(ℝ)} ∥∫_{0}^{t} ∫_{t}^{∞} R_{s/2} ∗ (Q_{s/2} ∗ f)(hc^{u})dsdu∥_{X}^{p} dμ(h))^{1/p}

⩽ ∫_{0}^{t} ∫_{t}^{∞} (∫_{ℍ(ℝ)} ∥R_{s/2} ∗ (Q_{s/2} ∗ f)(hc^{u})∥_{X}^{p} dμ(h))^{1/p} dsdu (37)
= t ∫_{t}^{∞} ∥R_{s/2} ∗ (Q_{s/2} ∗ f)∥_{L_{p}(ℍ(ℝ),X)} ds,  (38)

where (37) uses the triangle inequality in L_{p}(ℍ(ℝ), X) and (38) uses the right-invariance of the Haar measure μ . By combining (36) and (38) the middle term in the right hand side of (29) is bounded as follows.

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥P_{t} ∗ f(hc^{t}) − P_{t} ∗ f(x)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

⩽ (∫_{0}^{∞} t^{\frac{q}{2} −1} (∫_{t}^{∞} ∥R_{s/2} ∗ (Q_{s/2} ∗ f)∥_{L_{p}(ℍ(ℝ),X)} ds)^{q} dt)^{1/q}

⩽ 2 (∫_{0}^{∞} t^{\frac{3q}{2} −1} ∥R_{t/2} ∗ (Q_{t/2} ∗ f)∥_{L_{p}(ℍ(ℝ),X)}^{q} dt)^{1/q} ,  (39)

where (39) uses the second form of Hardy’s inequality (see [Ste70, Sec. A.4]). By Young’s inequality, for every t ∈ (0, ∞) we have

∥R_{t/2} ∗ Q_{t/2} ∗ f∥_{L_{p}(ℍ(ℝ),X)} ⩽ ∥R_{t/2}∥_{L_{1}(ℝ)} · ∥Q_{t/2} ∗ f∥_{L_{p}(ℍ(ℝ),X)}

=^{(13)} \frac{4}{πt} · ∥Q_{t/2} ∗ f∥_{L_{p}(ℍ(ℝ),X)}. (40)

A substitution of (40) into (39) yields the estimate

(∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥P_{t} ∗ f(hc^{t}) − P_{t} ∗ f(h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

⩽ \frac{8\sqrt{2}}{π} (∫_{0}^{∞} t^{\frac{q}{2} −1}∥Q_{t} ∗ f∥_{L_{p}(ℍ(ℝ),X)}^{q}dt)^{1/q} . (41)

The desired bound (28) now follows by applying the triangle inequality in L_{q}(t^{−1−q/2}dxdt, L_{p}(ℍ(ℝ), X)) to (29) while using (32), (33), (41). □

Proof of Proposition 2.2. Substitute Lemma 2.5 into Lemma 2.6. □

3. Proof of Theorem 1.1

Our goal here is to prove the following theorem, the case p = q of which is Theorem 1.1.

Theorem 3.1. For every η ∈ (0, 1), q ∈ [2, ∞) and p ∈ (1, q] there exists K = K(η, p, q) ∈ (0, ∞) with the following property. Suppose that (X, ∥ · ∥_{X}) is a Banach space satisfying δ_{(X,∥·∥_{X})}(ε) ⩾ (ηε)^{q} for every ε ∈ (0, 1). Then for every n ∈ ℕ and every f : ℍ → X we have

(∑_{k=1}^{n^{2}} \frac{1}{k^{1+q/2}} ( ∑_{x∈B_{n}} ∥f(xc^{k}) − f(x)∥_{X}^{p})^{q/p})^{1/q}

⩽ K ( ∑_{x∈B_{21n}} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} . (42)

Theorem 3.1 will be shown to follow from its continuous counterpart, i.e., Theorem 2.1. This deduction resembles the corresponding argument appearing in Section 7 of [ANT10], though there are some crucial differences. Other than dealing with an inequality of a different form, the main differences follow from the fact that [ANT10] argues about a different notion of horizontal gradient, namely a coarse counterpart of ∇_{ℍ}, and from the fact that [ANT10] uses a Euclidean version of Kleiner’s local Poincaré inequality [Kle10], while we need a similar statement for functions taking values in general Banach spaces.

3.1. A local Poincaré inequality on ℍ. Lemma 3.2 below extends the local Poincaré inequality of Kleiner [Kle10, Thm. 2.2], who proved the same statement for real-valued functions and p = 2. The simple argument below shows that the same result holds true for functions taking value in a general metric space, a fact that will be useful for us later. In [Kle10] the corresponding result is stated for arbitrary finitely generated groups, and while we state it for ℍ, the same argument works mutatis mutandis in the full generality of [Kle10].

Lemma 3.2. Fix p ∈ [1, ∞) and n ∈ ℕ. Let (M, d_{M}) be a metric space. For every f : ℍ → M,

∑_{x,y∈B_{n}} d_{M}(f(x), f(y))^{p}

≲ (2n)^{p+4} ∑_{x∈B_{3n}} (d_{M}(f(xa), f(x))^{p} + d_{M}(f(xb), f(x))^{p}). (43)

Proof. For every z ∈ B_{2n} choose s_{1}(z), …, s_{2n}(z) ∈ {a, b, a^{−1}, b^{−1}, e_{ℍ}} such that z = s_{1}(z) ⋯ s_{2n}(z). For i ∈ {1, …, 2n} write w_{i}(z) = s_{1}(z) ⋯ s_{i}(z) and set w_{0}(z) = e_{ℍ}. By the triangle inequality and Hölder’s inequality, for every x, y ∈ B_{n} we have

d_{M}(f(x), f(y))^{p}

⩽ (2n)^{p−1} ∑_{i=0}^{2n−1} d_{M} (f (xw_{i} (x^{−1}y)) , f (xw_{i} (x^{−1}y) s_{i+1} (x^{−1}y)))^{p} .

Consequently,

∑_{x,y∈B_{n}} d_{M}(f(x), f(y))^{p}

⩽ (2n)^{p−1} ∑_{z∈B_{2n}} ∑_{i=1}^{2n−1} ∑_{x∈B_{n}} d_{M} (f (xw_{i} (z)) , f (xw_{i} (z) s_{i+1} (z)))^{p}

= (2n)^{p−1} ∑_{z∈B_{2n}} ∑_{i=0}^{2n−1} ∑_{g∈B_{n}w_{i}(z)} d_{M} (f(g), f(gs_{i+1}(z)))^{p}

⩽ (2n)^{p−1} · |B_{2n}| · 2n ∑_{h∈B_{3n}} (d_{M}(f(ha), f(h))^{p} + d_{M}(f(hb), f(h))^{p}).

Since |B_{2n}| ≍ n^{4}, the desired inequality (51) follows. □

3.2. Localization of a discrete global inequality. Theorem 3.1 is a local vertical versus horizontal Poincaré inequality in the sense that it involves sums over balls in ℍ. While this form of the inequality is important for the deduction of lower bounds on bi-Lipschitz distortion of balls in ℍ, the natural discrete analogue of Theorem 2.1 is the following global vertical versus horizontal Poincaré inequality on ℍ.

Theorem 3.3. For every η ∈ (0, ∞), q ∈ [2, ∞) and p ∈ (1, q] there exists K = K(η, p, q) ∈ (0, ∞) with the following property. Suppose that (X, ∥ · ∥_{X}) is a Banach space satisfying δ_{(X,∥·∥_{X})}(ε) ⩾ (ηε)^{q} for every ε ∈ (0, 1). Then for every finitely supported f : ℍ → X we have

(∑_{k=1}^{∞} \frac{1}{k^{1+q/2}} (∑_{x∈ℍ} ∥f(xc^{k}) − f(x)∥_{X}^{p})^{q/p})^{1/q}

⩽ K (∑_{x∈ℍ} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} . (44)

Theorem 3.3 will be deduced from Theorem 2.1 via a partition of unity argument. This is done is Section 3.3 below. We shall now assume the validity of Theorem 3.3 and proceed, using Lemma 3.2, to conclude the proof of Theorem 3.1.

Proof of Theorem 3.1. The argument follows the proof of Claim 7.2 in [ANT10]. Fix n ∈ ℕ and a finitely supported f : ℍ → X. By translating f we may assume that ∑_{x∈B_{7n}} f(x) = 0. Due to Lemma 3.2, this implies that

( ∑_{x∈B_{7n}} ∥f(x)∥_{X}^{p})^{1/p}

= ( ∑_{x∈B_{7n}} ∥\frac{1}{|B_{7n}|} ∑_{y∈B_{7n}}(f(x) − f(y))∥_{X}^{p} )^{1/p}

⩽ (\frac{1}{|B_{7n}|} ∑_{x,y∈B_{7n}} ∥f(x) − f(y)∥_{X}^{p})^{1/p}

≲ n ( ∑_{x∈B_{21n}} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} . (45)

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

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

and let ϕ =^{def} ξf. Then ϕ is supported on B_{6n}. Since ξ is \frac{1}{n}-Lipschitz and takes values in [0, 1], for all s ∈ {a, b} and x ∈ ℍ we have

∥ϕ(x)−ϕ(xs)∥_{X} ⩽ |ξ(x)−ξ(xs)|·∥f(x)∥_{X} +|ξ(xs)|·∥f(x)−f(xs)∥_{X}

⩽ \frac{1}{n}∥f(x)∥_{X} + ∥f(x) − f(xs)∥_{X}. (46)

If k ∈ {1, …, n^{2}} then d_{W} (e_{ℍ}, c^{k}) ⩽ 4n (see [Bla03]). Consequently, for every x ∈ B_{n} we have xc^{k} ∈ B_{5n}, and therefore ϕ(x) = f(x) and ϕ(xc^{k}) = f(xc^{k}). Hence,

(∑_{k=1}^{n^{2}} \frac{1}{k^{1+q/2}} ( ∑_{x∈B_{n}} ∥f(xc^{k}) − f(x)∥_{X}^{p})^{q/p})^{1/q}

⩽ (∑_{k=1}^{∞} \frac{1}{k^{1+q/2}} (∑_{x∈ℍ} ∥ϕ(xc^{k}) − ϕ(x)∥_{X}^{p})^{q/p})^{1/q} . (47)

Moreover,

(∑_{x∈ℍ} (∥ϕ(xa) − ϕ(x)∥_{X}^{p} + ∥ϕ(xb) − ϕ(x)∥_{X}^{p}))^{1/p}

= ( ∑_{x∈B_{7n}} (∥ϕ(xa) − ϕ(x)∥_{X}^{p} + ∥ϕ(xb) − ϕ(x)∥_{X}^{p}))^{1/p}  (48)

⩽ \frac{2^{1/p}}{n} ( ∑_{x∈B_{7n}} ∥f(x)∥_{X}^{p})^{1/p}

+ ( ∑_{x∈B_{7n}} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} (49)

≲ ( ∑_{x∈B_{21n}} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} ,  (50)

where (48) holds true since ϕ is supported on B_{6n}, (49) uses (46), and (50) uses (45). The desired inequality (42) now follows from an application of Theorem 3.3 to ϕ, combined with (47) and (50). □

3.3. Discretization of Theorem 2.1. Here we prove Theorem 3.3, thus completing the proof of Theorem 3.1, and, as a special case, completing the proof of Theorem 1.1. The argument below is a variant of the proof of Claim 7.3 in [ANT10].

We will use the following simple lemma, whose proof is similar to the proof of Lemma 3.2. Below, a mapping f : ℍ → M is said to be finitely supported if there exists m_{0} ∈ M such that |f^{−1}(M ∖ {m_{0}})| < ∞.

Lemma 3.4. Fix p ∈ [1, ∞) and n ∈ ℕ. Let (M, d_{M}) be a metric space. For every finitely supported f : ℍ → M,

∑_{y∈ℍ} ∑_{z∈B_{n}} d_{M}(f(yz), f(y))^{p}

≲ n^{p+4} ∑_{x∈ℍ} (d_{M}(f(xa), f(x))^{p} + d_{M}(f(xb), f(x))^{p}). (51)

Proof. For every z ∈ B_{n} choose s_{1}(z), …, s_{n}(z) ∈ {a, b, a^{−1}, b^{−1}, e_{ℍ}} such that z = s_{1}(z) ⋯ s_{n}(z). Set w_{0}(z) = e_{ℍ} and for i ∈ {1, …, n} write w_{i}(z) = s_{1}(z) ⋯ s_{i}(z). By the triangle inequality and Hölder’s inequality, for every y ∈ ℍ we have

d_{M}(f(yz), f(y))^{p} ⩽ n^{p−1} ∑_{i=0}^{n−1} d_{M} (f (yw_{i} (z)) , f (yw_{i} (z) s_{i+1} (z)))^{p} .

Consequently,

∑_{y∈ℍ} ∑_{z∈B_{n}} d_{M}(f(yz), f(y))^{p}

⩽ n^{p}|B_{n}| ∑_{x∈ℍ} (d_{M}(f(xa), f(x))^{p} + d_{M}(f(xb), f(x))^{p}). □

Proof of Theorem 3.3. Since ℍ is a co-compact lattice in ℍ(ℝ), there exists a compactly supported smooth function χ : ℍ(ℝ) → [0, 1] with

∀ h ∈ ℍ(ℝ),  ∑_{x∈ℍ} χ_{x}(h) = 1,  (52)

where χ_{x} : ℍ(ℝ) → X is given by χ_{x}(h) = χ(x^{−1}h) for every x ∈ ℍ and h ∈ ℍ(ℝ). Let A ⊆ ℍ(ℝ) denote the support of χ. We may assume without loss of generality that A^{−1} = A. Note that due to (52) we have

⋃_{x∈ℍ} xA = ℍ(ℝ).  (53)

Since A is compact, we may fix m ∈ ℕ for which A ∩ ℍ ⊆ B_{m}. Let f : ℍ → X be finitely supported. Define F : ℍ(ℝ) → X by

F (h) =^{def} ∑_{x∈ℍ} χ_{x}(h)f(x).  (54)

Fix y ∈ ℍ and h ∈ yA. Note that it follows from (52) that

∑_{x∈ℍ} ∇_{ℍ}χ_{x}(h) = 0.  (55)

Observe that if x ∈ ℍ satisfies ∇_{ℍ}χ_{x}(h) ≠ 0 then necessarily x^{−1}h ∈ A. Since A^{−1} = A, this implies that x ∈ hA ⊆ (yA)A ⊆ yB_{2m}. Hence,

∥∇_{ℍ}F (h)∥_{ℓ_{p}^{2}(X)}

= ∥ ∑_{x∈yB_{2m}} (∂_{a}χ_{x}(h)(f(x) − f(y)), ∂_{b}χ_{x}(h)(f(x) − f(y)))∥_{ℓ_{p}^{2}(X)}

⩽ (max_{h∈A} ∥∇_{ℍ}χ(h)∥_{ℓ_{p}^{2}}) ∑_{z∈B_{2m}} ∥f(yz) − f(y)∥_{X}

≲ |B_{2m}|^{1−1/p} ( ∑_{z∈B_{2m}} ∥f(yz) − f(y)∥_{X}^{p})^{1/p} .  (56)

By integrating (56) over yA, we have

∫_{yA} ∥∇_{ℍ}F (h)∥_{ℓ_{p}^{2}(X)}^{p} dμ(h) ≲ ∑_{z∈B_{2m}} ∥f(yz) − f(y)∥_{X}^{p}.  (57)

By summing (57) over y ∈ ℍ and recalling (53), we conclude that

(∫_{ℍ(ℝ)} ∥∇_{ℍ}F (h)∥_{ℓ_{p}^{2}(X)}^{p} dμ(h))^{1/p} ≲ (∑_{y∈ℍ} ∑_{z∈B_{2m}} ∥f(yz) − f(y)∥_{X}^{p})^{1/p}

≲ (∑_{x∈ℍ} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} , (58)

where the final step of (58) uses Lemma 3.4.

Next, let U ⊆ ℍ(ℝ) be a bounded open set such that e_{ℍ} ∈ U yet U ∩ (xU) = ∅ for all x ∈ ℍ ∖ {e_{ℍ}}. Since c^{[0,1]} = {c^{s} : s ∈ [0, 1]} and U are bounded subsets of ℍ(ℝ), we can choose r ∈ ℕ such that (Uc^{[0,1]}A) ∩ ℍ ⊆ B_{r}. Fix x ∈ ℍ and h ∈ xU. Suppose that k ∈ ℕ and t ∈ [k, k + 1]. Recalling (52) and (54) we have

F (hc^{t}) − f(xc^{k}) = ∑_{w∈ℍ} χ_{w}(hc^{t})(f(w) − f(xc^{k})).  (59)

Observe that if w ∈ ℍ satisfies χ_{w}(hc^{t}) ≠ 0 then hc^{t} ∈ A, and since A = A^{−1} and c belongs to the center of ℍ(ℝ), this inclusion implies that w ∈ hc^{t}A ⊆ xc^{k}Uc^{[0,1]}A ⊆ xc^{k}B_{r}. (59) therefore implies that

∥F (hc^{t}) − f(xc^{k})∥_{X}^{p} ≲ ∑_{z∈B_{r}} ∥f(xc^{k}z) − f(xc^{k})∥_{X}^{p}.  (60)

Similar (simpler) reasoning shows that also

∥F (h) − f(x)∥_{X}^{p} ≲ ∑_{z∈B_{r}} ∥f(xz) − f(x)∥_{X}^{p}.  (61)

It follows from (60) and (61) that

∥f(xc^{k}) − f(x)∥_{X}^{p} ≲ ∥F (hc^{t}) − F (h)∥_{X}^{p}

+ ∑_{z∈B_{r}} (∥f(xc^{k}z) − f(xc^{k})∥_{X}^{p} + ∥f(xz) − f(x)∥_{X}^{p}). (62)

Integration of (62) over h ∈ xU therefore yields the estimate

∥f(xc^{k}) − f(x)∥_{X}^{p} ≲ ∫_{xU} ∥F (hc^{t}) − F (h)∥_{X}^{p}dμ(h)

+ ∑_{z∈B_{r}} (∥f(xc^{k}z) − f(xc^{k})∥_{X}^{p} + ∥f(xz) − f(x)∥_{X}^{p}). (63)

Since the sets {xU}_{x∈ℍ} are pairwise disjoint, summation of (63) over x ∈ ℍ, combined with an application of Lemma 3.4, shows that

(∑_{x∈ℍ} ∥f(xc^{k}) − f(x)∥_{X}^{p})^{1/p} ≲ (∫_{ℍ(ℝ)} ∥F (hc^{t}) − F (h)∥_{X}^{p}dμ(h))^{1/p}

+ (∑_{x∈ℍ} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} . (64)

Integration of (64) over t ∈ [k, k + 1] yields

\frac{1}{k^{1+q/2}} (∑_{x∈ℍ} ∥f(xc^{k}) − f(x)∥_{X}^{p})^{q/p}

⩽ C^{q} ∫_{k}^{k+1} (∫_{ℍ(ℝ)} ∥F (hc^{t}) − F (h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}}

+ \frac{C^{q}}{k^{1+q/2}} (∑_{x∈ℍ} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{q/p} , (65)

where C ∈ (0, ∞) is a universal constant. We may now sum (65) over k ∈ ℕ to get the bound

(∑_{k=1}^{∞} \frac{1}{k^{1+q/2}} (∑_{x∈ℍ} ∥f(xc^{k}) − f(x)∥_{X}^{p})^{q/p})^{1/q}

≲ (∫_{0}^{∞} (∫_{ℍ(ℝ)} ∥F (hc^{t}) − F (h)∥_{X}^{p}dμ(h))^{q/p} \frac{dt}{t^{1+q/2}} )^{1/q}

+ (∑_{x∈ℍ} (∥f(xa) − f(x)∥_{X}^{p} + ∥f(xb) − f(x)∥_{X}^{p}))^{1/p} .  (66)

The desired inequality (44) follows from an application of Theorem 2.1 to F, and substituting (58) and (66) into the resulting inequality. □

4. Vertical perimeter versus horizontal perimeter

The case X = ℝ and q = 2 of Theorem 2.1 shows that for every p ∈ (1, 2] and every smooth and compactly supported f : ℍ(ℝ) → ℝ,

(∫_{0}^{∞} (∫_{ℍ(ℝ)} |f(hc^{t}) − f(h)|^{p}dμ(h))^{2/p} \frac{dt}{t^{2}})^{1/2}

≲_{p} (∫_{ℍ(ℝ)} ∥∇_{ℍ}f(h)∥_{ℓ_{p}^{2}}^{p} dμ(h))^{1/p} . (67)

The implied constant in (67) that follows from our proof of Theorem 2.1 tends to ∞ as p → 1. However, we ask whether the endpoint case p = 1 of (67) does nevertheless hold true.

Question 4.1. Is it true that every smooth and compactly supported f : ℍ(ℝ) → ℝ satisfies

(∫_{0}^{∞} (∫_{ℍ(ℝ)} |f(hc^{t}) − f(h)|dμ(h))^{2} \frac{dt}{t^{2}})^{1/2}

≲ ∫_{ℍ(ℝ)} ∥∇_{ℍ}f(h)∥_{ℓ_{1}^{2}} dμ(h). (68)

A standard application of the co-area formula shows that it suffices to prove (68) when f is an indicator of a measurable set A ⊆ ℍ(ℝ). For such a choice of f the right hand side of (68) should be interpreted as the horizontal perimeter of A, denoted PER(A). Rather than defining the horizontal perimeter PER(A) here, we refer to [Amb01] and [CK10a, Sec. 2] for a detailed discussion of this notion.

Definition 4.2 (Vertical perimeter at scale t). Let A ⊆ ℍ(ℝ) be measurable and t ∈ (0, ∞). Recalling that μ is the Haar measure on ℍ(ℝ) (equivalently μ is the Lebesgue measure on ℝ^{3}), define the vertical perimeter of A at scale t, denoted v_{t}(A), to be the quantity

v_{t}(A) =^{def} μ ({h ∈ A : hc^{t} ∉ A or hc^{−t} ∉ A}) .  (69)

Thus v_{t}(A) measures the the size of those points of A from which a vertical movement of ±t lands outside A. Using this terminology, we have the following reformulation of Question 4.1 in terms of an isoperimetric-type inequality.

Question 4.3. Is it true that for every measurable A ⊆ ℍ(ℝ) one has

∫_{0}^{∞} \frac{v_{t}(A)^{2}}{t^{2}} dt ≲ PER(A)^{2}.  (70)

While we believe that Question 4.3 has a positive answer, at present we do not have sufficient evidence that would justify formulating this assertion as a conjecture. However, there is a weaker coarse variant of Question 4.3 for which there is significant partial positive evidence that will be published elsewhere; this evidence originates from ongoing work (including numerical experiments and proofs of nontrivial special cases) on our question by Artem Kozhevnikov and Pierre Pansu (personal communication). We shall now formulate this weaker conjecture, and proceed to explain an application of it to theoretical computer science.

Definition 4.4 (Coarse total vertical perimeter at resolution ε). Let A ⊆ ℍ(ℝ) be measurable and ε ∈ (0, 1). Define the coarse total vertical perimeter of A at resolution ε by

V^{(ε)}(A) =^{def} ∫_{ε}^{1} \frac{v_{t}(A)}{t^{3/2}}dt.  (71)

The following isoperimetric-type conjecture relates the coarse total vertical perimeter of A at resolution ε with its horizontal perimeter.

Conjecture 4.5. For every measurable A ⊆ ℍ(ℝ) and every ε ∈ (0, 1/2),

V^{(ε)}(A) ≲ \sqrt{log(1/ε)} · PER(A).  (72)

Note that if (70) holds true then by the Cauchy–Schwarz inequality,

V^{(ε)}(A) =^{(71)} ∫_{ε}^{1} \frac{1}{\sqrt{t}} · \frac{v_{t}(A)}{t}dt

⩽ \sqrt{∫_{ε}^{1} \frac{dt}{t}} · \sqrt{∫_{ε}^{1} \frac{v_{t}(A)^{2}}{t^{2}} dt} ≲^{(70)} \sqrt{log(1/ε)} · PER(A). (73)

This shows that a positive answer to Question 4.3 would imply a positive resolution of Conjecture 4.5.

By the co-area formula, Conjecture 4.5 has the following equivalent functional version: for every smooth and compactly supported f : ℍ(ℝ) → ℝ and every ε ∈ (0, 1/2),

∫_{ε}^{1} ∫_{ℍ(ℝ)} \frac{|f(hc^{t}) − f(h)|}{t^{3/2}}dμ(h)dt ≲ \sqrt{log(1/ε)} ∫_{ℍ(ℝ)} ∥∇_{ℍ}f(h)∥_{ℓ_{1}^{2}}dμ(h).

By re-scaling, this is equivalent to requiring that for every R ∈ (1, ∞),

∫_{1}^{R} ∫_{ℍ(ℝ)} \frac{|f(hc^{t}) − f(h)|}{t^{3/2}}dμ(h)dt

≲ \sqrt{log R} ∫_{ℍ(ℝ)} ∥∇_{ℍ}f(h)∥_{ℓ_{1}^{2}}dμ(h). (74)

Arguing as in Section 3, one sees that (74) implies that for every integer n ⩾ 2 and every f : ℍ → ℝ we have

∑_{k=1}^{n^{2}} ∑_{x∈B_{n}} \frac{|f(xc^{k}) − f(x)|}{k^{3/2}}

≲ \sqrt{log n} ∑_{x∈B_{21n}} (|f(xa) − f(x)| + |f(xb) − f(x)|). (75)

By summing (75) over coordinates we conclude that the conjectural inequality (75) implies that every f : ℍ → ℓ_{1} satisfies

∑_{k=1}^{n^{2}} ∑_{x∈B_{n}} \frac{∥f(xc^{k}) − f(x)∥_{1}}{k^{3/2}}

≲ \sqrt{log n} ∑_{x∈B_{21n}} (∥f(xa) − f(x)∥_{1} + ∥f(xb) − f(x)∥_{1}). (76)

The same computation as in (2) shows that if (76) does indeed hold true, then c_{1}(B_{n}, d_{W}) ≳ \sqrt{log n}, and therefore, as explained in the introduction, in fact c_{1}(B_{n}, d_{W}) ≍ \sqrt{log n}. We state this conclusion as a separate conjecture.

Conjecture 4.6. For every integer n ⩾ 2 we have c_{1}(B_{n}, d_{W}) ≍ \sqrt{log n}.

To summarize the above reasoning, a positive answer to Question 4.1 (or equivalently Question 4.3) implies the positive resolution of Conjecture 4.5, which in turn implies the positive resolution of Conjecture 4.6.

We recall that in [CKN11] it was shown that c_{1}(B_{n}, d_{W}) ≳ (log n)^{κ} for some universal constant κ > 0. While the proof of this result in [CKN11] is constructive, to the best of our knowledge there was no serious attempt to use that proof in order to give a good estimate on the value of κ, since it seems very unlikely that the methods of [CKN11] can yield the sharp bound κ ⩾ \frac{1}{2}. Suppose that for some p ∈ [1, ∞) the following variant of (70) holds true for every measurable A ⊆ ℍ(ℝ).

(∫_{0}^{∞} \frac{v_{t}(A)^{p}}{t^{1+p/2}} dt)^{1/p} ≲ PER(A).  (77)

Arguing as in (73), an application of Hölder’s inequality would yield the validity of (72) with the term \sqrt{log(1/ε)} replaced by (log(1/ε))^{1−1/p}. Reasoning identically to the discussion preceding Conjecture 4.6, it would follow that c_{1}(B_{n}, d_{W}) ≳ (log n)^{1/p}. Thus, proving an inequality such as (77) would yield a new proof of the lower bound on c_{1}(B_{n}, d_{W}) of [CKN11]. It is straightforward to check that (77) holds true when p = ∞, and it would be interesting to investigate whether the method of [CKN11] can potentially lead to a proof of (77) for some finite p.

Due to the fact that our conjectures lead to an asymptotically sharp lower bound on the ℓ_{1} distortion of balls in ℍ, it follows that the smallest possible p ∈ [1, ∞) for which (77) can hold true is p = 2. Correspondingly, (72) cannot be improved. The three known embeddings of (B_{n}, d_{W}) into ℓ_{1} with distortion O(\sqrt{log n}) that were mentioned in the introduction (first embed into ℓ_{2}, and then use the fact that finite subsets of ℓ_{2} embed isometrically into ℓ_{1}) lead to examples of sets A ⊆ ℍ(ℝ) for which (72) is sharp. A different explicit example of a set for which (72) is sharp was found by Robert Young (personal communication). This illuminating example will be published elsewhere.

4.1. Algorithmic implications. We shall now indicate an important consequence of the conjectures presented here to theoretical computer science. This topic is discussed at length in e.g. [CKN11, Nao10], so we will be brief here, and in particular we will mention only the best known results without describing the historical development.

In the Sparsest Cut problem one is given as input two symmetric functions C, D : {1, …, n} × {1, …, n} → [0, ∞) and the goal is to compute (or estimate) in polynomial time the quantity

Φ^{∗}(C, D) =^{def} min_{∅≠S⊊\{1,...,n\}} \frac{∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j) |1_{S}(i) − 1_{S}(j)|}{∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j) |1_{S}(i) − 1_{S}(j)|} .

This versatile optimization problem is of central algorithmic importance; see e.g. [Shm97] for examples of its applicability.

The best known approximation algorithm for the Sparsest Cut problem was proposed by Goemans and Linial [Goe97, Lin02]. In [ALN08] it is proved that the Goemans-Linial algorithm outputs a number which is guaranteed to be within a factor of O(\sqrt{log n} log log n) of Φ^{∗}(C, D). Goemans [Goe97] and Linial [Lin02] (see also [Mat02, pages 379–380]) actually conjectured that their algorithm outputs a number which is within a factor of O(1) of Φ^{∗}(C, D). The Goemans-Linial conjecture was disproved by Khot and Vishnoi [KV05], who proved that the Goemans-Linial algorithm makes an error of at least a constant power of log log n on some inputs. A link of the Sparsest Cut problem to the Heisenberg group was found in [LN06], where the Goemans-Linial algorithm was shown to make an error of at least a constant multiple of c_{1}(B_{n}, d_{W}) on some inputs. The lower bound c_{1}(B_{n}, d_{W}) ≳ (log n)^{κ} of [CKN11] consequently established that the Goemans-Linial algorithm makes an error of at least a constant multiple of (log n)^{κ} on some inputs. An affirmative solution of Conjecture 4.6 would improve this lower bound to a constant multiple of \sqrt{log n}, thus resolving (up to iterated logarithms) the problem of understanding the asymptotic performance of the Goemans-Linial algorithm.

References

[ALN08] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1–21 (electronic), 2008.

[Amb01] L. Ambrosio. Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces. Adv. Math., 159(1):51–67, 2001.

[AMM85] I. Aharoni, B. Maurey, and B. S. Mityagin. Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces. Israel J. Math., 52(3):251–265, 1985.

[ANT10] T. Austin, A. Naor, and R. Tessera. Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces, 2010. To appear in Groups Geom. Dyn., preprint available at

http://arxiv.org/abs/1007.4238.

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

[Bla03] S. Blachère. Word distance on the discrete Heisenberg group. Colloq. Math., 95(1):21–36, 2003.

[Che99] J. Cheeger. Differentiability of Lipschitz functions on metric measure spaces. Geom. Funct. Anal., 9(3):428–517, 1999.

[CK06] J. Cheeger and B. Kleiner. On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces. In Inspired by S. S. Chern, volume 11 of Nankai Tracts Math., pages 129–152. World Sci. Publ., Hackensack, NJ, 2006.

[CK10a] J. Cheeger and B. Kleiner. Differentiating maps into L^{1}, and the geometry of BV functions. Ann. of Math. (2), 171(2):1347–1385, 2010.

[CK10b] J. Cheeger and B. Kleiner. Metric differentiation, monotonicity and maps to L^{1}. Invent. Math., 182(2):335–370, 2010.

[CKN11] J. Cheeger, B. Kleiner, and A. Naor. Compression bounds for Lipschitz maps from the Heisenberg group to L_{1}. Acta Math., 207(2):291–373, 2011.

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

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

[Goe97] M. X. Goemans. Semidefinite programming in combinatorial optimization. Math. Programming, 79(1-3, Ser. B):143–161, 1997. Lectures on mathematical programming (ismp97) (Lausanne, 1997).

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

[Han56] O. Hanner. On the uniform convexity of L^{p} and l^{p}. Ark. Mat., 3:239–244, 1956.

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

[KV05] S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ_{1}. In Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science (FOCS 2005), pages 53–62. 2005.

[Li13] S. Li. Coarse differentiation and quantitative nonembeddability for Carnot groups, 2013. Preprint available at

http://arxiv.org/abs/1304.6633.

[Lin02] N. Linial. Finite metric-spaces—combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 573–586. Higher Ed. Press, Beijing, 2002.

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

[Mat02] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[MN12] M. Mendel and A. Naor. Nonlinear spectral calculus and superexpanders, 2012. To appear in Inst. Hautes Études Sci. Publ. Math.,

available at http://arxiv.org/abs/1207.4705.

[MTX06] T. Martínez, J. L. Torrea, and Q. Xu. Vector-valued Littlewood-Paley-Stein theory for semigroups. Adv. Math., 203(2):430–475, 2006.

[Nao10] A. Naor. L_{1} embeddings of the Heisenberg group and fast estimation of graph isoperimetry. In Proceedings of the International Congress of Mathematicians. Volume III, pages 1549–1575. Hindustan Book Agency, New Delhi, 2010.

[NP11] A. Naor and Y. Peres. L_{p} compression, traveling salesmen, and stable walks. Duke Math. J., 157(1):53–108, 2011.

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

[Pau01] S. D. Pauls. The large scale geometry of nilpotent Lie groups. Comm. Anal. Geom., 9(5):951–982, 2001.

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

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

[Shm97] D. B. Shmoys. Cut problems and their application to divide-and-conquer. In Approximation Algorithms for NP-hard Problems, (D.S. Hochbaum, ed.), pages 192–235. PWS, 1997.

[Ste70] E. M. Stein. Singular integrals and differentiability properties of functions. Princeton Mathematical Series, No. 30. Princeton University Press, Princeton, N.J., 1970.

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

[TJ74] N. Tomczak-Jaegermann. The moduli of smoothness and convexity and the Rademacher averages of trace classes S_{p}(1 ⩽ p < ∞). Studia Math., 50:163–182, 1974.

Laboratoire de Mathématiques - Analyse, Probabilités, Modélisation - Orléans (MAPMO) UMR CNRS 6628, Université d’Orléans Rue de Chartres, B.P. 6759 - 45067 Orléans cedex 2

E-mail address: vlafforg@math.jussieu.fr

Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York NY 10012, USA

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