L_{p} metrics on the Heisenberg group and the Goemans-Linial conjecture

James R. Lee^{∗}  Assaf Naor ^{†}

Abstract

We prove that the function d : ℝ^{3} × ℝ^{3} → [0, ∞) given by

d((x, y, z), (t, u, v))

= ([((t − x)^{2} + (u − y)^{2})^{2} + (v − z + 2xu − 2yt)^{2}]^{\frac{1}{2}} + (t − x)^{2} + (u − y)^{2})^{\frac{1}{2}} .

is a metric on ℝ^{3} such that (ℝ^{3}, \sqrt{d}) is isometric to a subset of Hilbert space, yet (ℝ^{3}, d) does not admit a bi-Lipschitz embedding into L_{1}. This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the semidefinite relaxation of the Sparsest Cut problem. The metric above is doubling, and hence has a padded stochastic decomposition at every scale. We also study the L_{p} version of this problem, and obtain a counter example to a natural generalization of a classical theorem of Bretagnolle, Dacunha-Castelle and Krivine (of which the Goemans-Linial conjecture is a particular case). Our methods involve Fourier analytic techniques, and a recent breakthrough of Cheeger and Kleiner, together with classical results of Pansu on the differentiability of Lipschitz functions on the Heisenberg group.

1 Introduction

Let G = (V, E) be a graph, with a capacity C(e) ≥ 0 associated to every edge e ∈ E. Assume that we are given k pairs of vertices (s_{1}, t_{1}), ..., (s_{k}, t_{k}) ∈ V × V and D_{1}, …, D_{k} ≥ 1. We think of the s_{i} as sources, the t_{i} as targets, and the value D_{i} as the demand of the terminal pair (s_{i}, t_{i}) for some commodity κ_{i}. The problem is said to have uniform demands if every pair u, v ∈ V occurs as some (s_{i}, t_{i}) pair with D_{i} = 1. Given a non-empty subset S ⫋ V, we write

Φ(S) = \frac{∑_{uv∈E} C(uv) · |1_{S}(u) − 1_{S}(v)|}{∑_{i=1}^{k} D_{i} · |1_{S}(s_{i}) − 1_{S}(t_{i})|},

where 1_{S} is the characteristic function of S. The value Φ^{∗} = min_{∅≠S⫋V} Φ(S) is the minimum over all cuts (partitions) of V, of the ratio between the total capacity crossing the cut and the total demand crossing the cut. In the case of uniform demands Φ^{∗} is simply the edge expansion of the graph G.

∗School of Mathematics, Institute for Advanced Study, Princeton, NJ. This material is based on work supported by the National Science Foundation under agreement No. DMS-0111298 and NSF grant CCR-0324906. Email:

jrl@math.ias.edu.

†Theory Group, Microsoft Research, Redmond WA. Email: anaor@microsoft.com.

Computing Φ^{∗} is NP-hard [40]. Moreover, finding a cut for which Φ^{∗} is (approximately) attained is a basic step in approximation algorithms for several NP-hard problems [34, 1, 47]. The problem of approximating Φ^{∗} in polynomial time is known as the Sparsest Cut problem with general demands, and is a famous open problem in the field of approximation algorithms. The best known algorithm for this problem is based on the following classical semidefinite relaxation (see [19, 2] for the motivation for this relaxation).

SDP relaxtion for Sparsest Cut

min ∑_{uv∈E} C(uv) ∥x_{u} − x_{v}∥_{2}^{2}
s.t. x_{u} ∈ ℝ^{n}  ∀u ∈ V

∑_{u,v∈V} D(u, v) ∥x_{u} − x_{v}∥_{2}^{2} = 1

∥x_{u} − x_{v}∥_{2}^{2} ≤ ∥x_{u} − x_{w}∥_{2}^{2} + ∥x_{w} − x_{v}∥_{2}^{2}

∀u, v, w ∈ V

Goemans and Linial (see [19, 36]) observed that this SDP produces a metric space (X, d) such that (X, \sqrt{d}) is isometric to a subset of Hilbert space. Such metrics are known in the literature as negative type metrics or squared L_{2} metrics. Moreover, following the approach of London, Linial and Rabinovich [39] (see also the work of Aumann and Rabani [5]), they noted that the cut-cone characterization of subsets of L_{1} (see [17]) implies that the integrality gap of this SDP can be bounded by the least distortion with which (X, d) embeds into L_{1}, i.e. the smallest L > 0 for which there is an embedding f : X → L_{1} satisfying for all x, y ∈ X, d(x, y) ≤ ∥f(x) − f(y)∥_{1} ≤ L d(x, y). We will denote the smallest such L by c_{1}(X) in what follows. In fact it is known that the worst-case integrality gap of the SDP over all instances of graphs with n nodes is precisely the largest value of c_{1}(X) as X ranges over all n-point metric spaces of negative type. Goemans and Linial therefore made the following conjecture (see [19, 38]), which would imply that there exists a polynomial time algorithm which approximates Φ^{∗} to within a constant factor.

The Goemans-Linial conjecture: Every metric space of negative type embeds with O(1) distortion into L_{1}.

In a recent remarkable paper [26] Khot and Vishnoi proved that this conjecture does not hold true. In other words, there exist arbitrarily large n-point metric spaces of negative type X_{n} such that lim_{n→∞} c_{1}(X_{n}) = ∞. Their construction is motivated by considerations from complexity theory, as it is based on a hardness result that will be discussed later. In particular, the Khot-Vishnoi spaces are quite complicated to describe. The purpose of the present paper is to give a different simple counter-example to the Goemans-Linial conjecture which is based on a classical and well-understood metric space— the Heisenberg group. Moreover, our example has several additional properties which lead to a solution of related problems. We will describe the Heisenberg group geometry later, but for concreteness we first state explicitly our counter-example.

Theorem 1.1. Define d : ℝ^{3} × ℝ^{3} → [0, ∞) by

d((x, y, z), (t, u, v)) = ([((t − x)^{2} + (u − y)^{2})^{2} + (v − z + 2xu − 2yt)^{2}]^{\frac{1}{2}} + (t − x)^{2} + (u − y)^{2})^{\frac{1}{2}} .

Then d is a metric on ℝ^{3} and (ℝ^{3}, \sqrt{d}) is isometric to a subset of Hilbert space (i.e. (ℝ^{3}, d) is a metric space of negative type). But, (ℝ^{3}, d) does not embed bi-Lipschitzly into L_{1}. Thus

lim_{n→∞} c_{1} ({0, …, n}^{3}, d) = ∞.  (1)

Our approach can be used to answer additional questions to which the Khot-Vishnoi method does not apply. In order to motivate them we recall some background which explains why the Goemans-Linial conjecture is a natural question. A classical theorem of Schoenberg [45] (see also [50]) states that a metric space (X, d) is isometric to a subset of L_{2} if and only if d^{2} is a negative definite kernel on X, i.e. for every x_{1}, …, x_{n} ∈ X and every c_{1}, …, c_{n} ∈ ℂ with ∑_{j=1}^{n} c_{j} = 0 we have ∑_{j,k=1}^{n} d(x_{j}, x_{k})^{2}c_{j}\overline{c_{k}} ≤ 0. Thus (X, d) is of negative type if and only if d is negative definite on X. More generally Schoenberg proved that for 1 ≤ p ≤ 2 the function ∥x − y∥_{p}^{p} is negative definite on L_{p}. It follows that L_{1} is of negative type (this corollary of Schoenberg’s theorem is easy to prove directly). It also follows that for 1 ≤ p ≤ 2 the space L_{p} equipped with the metric ∥x − y∥_{p}^{p/2} is isometric to a subset of L_{2}. Bretagnolle, Dacunha-Castelle and Krivine [7] proved the following beautiful converse to this result of Schoenberg in the case of normed spaces: If (X, ∥ · ∥) is a normed space and ∥x − y∥^{p} is negative definite then X is linearly isometric to a subset of L_{p}. Stated differently, X equipped with the metric ∥x − y∥^{p/2} is isometric to a subset of L_{2} if and only if (X, ∥ · ∥) is isometric to a subset of L_{p}.

Specializing the above discussion to the case p = 1 we see that the Goemans-Linial conjecture is true for normed spaces. It is thus natural to ask if this phenomenon holds for arbitrary metric spaces. Moreover, from a computational viewpoint, since optimization problems over L_{1} metrics are so important for the analysis of the cut structure of graphs, but are intractable computationally (see [17]), one might hope that the negative type property of L_{1} metrics characterizes L_{1} embeddability. This would reduce optimization problems over cuts to the Euclidean case, where we have efficient techniques, such as semidefinite programming, at our disposal. As we have seen, this hope fails. But as a motivation for the Goemans-Linial conjecture, the theorem of Bretagnolle, Dacunha-Castelle and Krivine is true for all 1 < p < 2, and it is thus just as natural to ask if it holds for general metrics. In other words, if (X, d) is a metric space such that (X, d^{p/2}) is isometric to a subset of L_{2}, does X embed into L_{p}? The following theorem shows that the answer to this question is negative.

Theorem 1.2. Fix 1 ≤ p < 2 and define d : ℝ^{3} × ℝ^{3} → [0, ∞) by

d((x, y, z), (t, u, v)) = [((t − x)^{2} + (u − y)^{2})^{2} + (v − z + 2xu − 2yt)^{2}]^{\frac{1}{4}}

· \{cos [\frac{p}{2} arccos (\frac{(t − x)^{2} + (u − y)^{2}}{[((t − x)^{2} + (u − y)^{2})^{2} + (v − z + 2xu − 2yt)^{2}]^{\frac{1}{2}}} )]\}^{1/p} .

Then d is a metric on ℝ^{3} and (ℝ^{3}, d^{p/2}) is isometric to a subset of Hilbert space. But, (ℝ^{3}, d) does not embed bi-Lipschitzly into L_{p}.

Note that when p = 1 the metric in Theorem 2.2 is proportional to the metric in Theorem 1.1. Moreover, for all 1 ≤ p < 2 the metric in Theorem 1.2 is easily seen to be bi-Lipschitz equivalent to the metric in Theorem 2.2 (we will prove this later). Thus the fact that it does not embed into L_{p} follows from Theorem 1.1, since L_{p} is isometric to a subset of L_{1}. Nevertheless, the proof of the non-embeddability result in the case 1 < p < 2 is significantly easier, and is based on more classical results.

An additional novel aspect of Theorem 1.1 is that the metric constructed there is decomposable. Recall that the modulus of padded decomposability of X is the smallest α > 0 such that for every Δ > 0 there exists a distribution over partitions of X into sets of diameter at most Δ, such that for every x ∈ X with probability at least \frac{1}{2} the entire ball of radius Δ/α centered at x is contained in the element of the partition to which x belongs (we refer to [33, 28] for a general discussion of this notion). We will see that the spaces (ℝ^{3}, d) in Theorem 1.1 and Theorem 1.2 are doubling (see [23] for more information on the doubling condition), so that by the results of [21] they have a finite modulus of padded decomposability. It is a folklore problem, stated explicitly in [49], whether decomposable spaces embed into L_{1}. Theorem 1.1 shows that the answer to this question is negative. On the other hand the Khot-Vishnoi spaces are easily seen not to have a uniformly bounded modulus of padded decomposability.

Padded decomposability is a central tool in metric embeddings which is used in numerous contexts. In particular, a theorem of Klein, Plotkin and Rao [27] states that planar graphs, or more generally graphs which exclude a fixed minor, are decomposable. It is a famous conjecture (stated in [37, 22]) that such metrics embed into L_{1}. Our results show that if true, the proof of this conjecture will have to use more information than just the fact that such graph families are decomposable. This contrasts the fact that all known bi-Lipschitz embedding theorems for these spaces only use the fact that they are decomposable.

In the next subsections of this introduction we describe in greater detail the Heisenberg groups, and the ingredients of the proof of Theorem 1.1 and Theorem 1.2.

1.1 Heisenberg groups and the Koranyi norm

Let G be a group with identity element e. A function N : G → [0, ∞) is called a group semi-norm on G if N(e) = 0, every g ∈ G satisfies N(g^{−1}) = N(g), and every g, h ∈ G satisfy N(gh) ≤ N(g) + N(h). If, in addition, N(g) = 0 implies that g = e, then N is called a group norm on G. Observe that every group norm N on G induces a right-invariant metric ρ_{N} on G given by ρ_{N}(g, h) = N(gh^{−1}).

Fix an integer n ≥ 1. For z = (z_{1}, …, z_{n}) ∈ ℂ^{n} denote |z| = \sqrt{|z_{1}|^{2} + … + |z_{n}|^{2}}. Additionally, we will use the standard symplectic form on ℂ^{n}, defined for z, w ∈ ℂ^{n} as:

[z, w] = ∑_{j=1}^{n} ℑ(z_{j}\overline{w_{j}}),

where here and in what follows, ℑ(ζ) and ℜ(ζ) denote the imaginary part and real part of the complex number ζ, respectively.

The 2n+1 dimensional Heisenberg group ℍ^{2n+1} is defined via the following (non-commutative) group operation on ℂ^{n} × ℝ:

(z, s) · (w, t) = (z + w, t + s + 2[z, w]).

The Koranyi norm N_{0} on ℍ^{2n+1} is defined as

N_{0}(z, t) = (|z|^{4} + t^{2})^{1/4} .

It is a classical fact (see [15, 48]) that N_{0} is indeed a group norm on ℍ^{2n+1}.

Remark 1.1. The Heisenberg groups are examples of the more general class of Carnot groups, which are themselves particular cases of a class of path metrics known as sub-Riemannian geometries. In particular, there is an important intrinsic geodesic metric on ℍ^{2n+1}, which is known as the Carnot-Carathéodory metric. We will not need to define this metric here, and it suffices to say that it is bi-Lipschitz equivalent the the metric induced by the Koranyi norm. However, understanding the proofs of the results that we will use requires familiarity with the Carnot-Carathéodory structure on ℍ^{2n+1}. Moreover, some of the results stated here carry over to general Carnot groups. We refer the interested reader to [20, 41] for more information about the fascinating world of sub-Riemannian geometries and Carnot groups.

Define N : ℍ^{2n+1} → [0, ∞) by

N(z, t) = \sqrt{\sqrt{|z|^{4} + t^{2}} + |z|^{2}} = \sqrt{[N_{0}(z, t)]^{2} + |z|^{2}}.  (2)

Since for any two group semi-norms N_{1}, N_{2} on a group G, \sqrt{N_{1}^{2} + N_{2}^{2}} is also a group semi-norm on G, it follows that N is a group norm on ℍ^{2n+1}. Note that the metric d in Theorem 1.1 is precisely the metric induced on ℍ^{3} by the group norm N. This proves that d is indeed a metric. The heart of Theorem 1.1 is the proof that (ℍ^{2n+1}, \sqrt{ρ_{N}}) is isometric to a subset of Hilbert space, and the non-embeddability of ℍ^{2n+1} into L_{1}. We remark that it is easy to check that (ℍ^{2n+1}, ρ_{N_{0}}) is not of negative type. Our proof that (ℍ^{2n+1}, ρ_{N}) is of negative type is naturally based on Schoenberg’s theorem [45] quoted above, and is contained in Section 2. The fact that ℍ^{2n+1} does not embed into L_{1} follows from a recent result of Cheeger and Kleiner— this is explained in Section 1.3 below.

In order to prove Theorem 1.2 fix p ∈ [1, 2) and define M : ℍ^{2n+1} → [0, ∞) by

M(z, t) = (|z|^{4} + t^{2})^{1/4} \{cos [\frac{p}{2} arccos (\frac{|z|^{2}}{\sqrt{|z|^{4} + t^{2}}} )]\}^{1/p} .  (3)

The following lemma implies that the metric d in Theorem 1.2 is indeed a metric, since it is precisely the metric on ℍ^{3} induced by the group norm M.

Lemma 1.3. M is a group norm on ℍ^{2n+1} which satisfies for all g ∈ ℍ^{2n+1},

\sqrt{1 − \frac{p}{2}} · N_{0}(g) ≤ [cos (\frac{πp}{4})]^{1/p} · N_{0}(g) ≤ M(g) ≤ N_{0}(g).  (4)

Lemma 1.3 is proved in Section 3, as well as the fact that (ℍ^{2n+1}, M^{p/2}) is isometric to a subset of L_{2} (the proof of which uses Schoenberg’s theorem once more). The non-embeddability of ℍ^{2n+1} into L_{p} when p > 1 follows from a simple extension of a differentiability theorem of Pansu [42] to the case of functions with values in Banach spaces with the Radon-Nikodým property, and an elegant observation of Semmes [46]. This is described in Section 1.2 below.

Remark 1.2. It is well known (see [23]) that (ℍ^{2n+1}, N_{0}) is doubling with constant O(1)^{n}. By a theorem of Assouad [4, 23] we know that for every ε ∈ (0, 1) the metric space (ℍ^{2n+1}, N_{0}^{1−ε}) is bi-Lipschitz equivalent to a subset of L_{2} (with distortion depending on n and ε). Thus the main issue in Theorem 1.2 is to pass to an equivalent metric on ℍ^{2n+1} for which the embedding is isometric.

As a by product we see from the bounds in (3) that (ℍ^{2n+1}, N_{0}^{1−ε}) embeds into Hilbert space with distortion independent of n. This distortion is O (\frac{1}{\sqrt{ε}}), which coincides with the general bound for doubling spaces proved in [31].

1.2 Pansu differentiability and the Radon-Nikodým property

For every θ ∈ ℝ define the dilation operator δ_{θ} : ℍ^{2n+1} → ℍ^{2n+1} by δ_{θ}(z, t) = (θz, θ^{2}t). Observe that for every g, h ∈ ℍ^{2n+1}, δ_{θ}(gh) = (δ_{θ}g)(δ_{θ}h) and ρ_{N_{0}}(δ_{θ}(g), δ_{θ}(h)) = |θ|ρ_{N_{0}}(g, h). Let X be a Banach space and F : ℍ^{2n+1} → X be a Lipschitz mapping. We shall say that F has a Pansu derivative at g ∈ ℍ^{2n+1} if for every h ∈ ℍ^{2n+1} the limit

D_{F}^{g} (h) ≡ lim_{θ→0} \frac{F (δ_{θ}(h)g) − F (g)}{θ}

exists, and D_{F}^{g} is a homomorphism, i.e. for all h_{1}, h_{2} ∈ ℍ^{2n+1}, D_{F}^{g} (h_{1}h_{2}^{−1}) = D_{F}^{g} (h_{1}) − D_{F}^{g} (h_{2}).

Pansu [42] proved that if X is finite dimensional then every Lipschitz mapping F : ℍ^{2n+1} → X is Pansu-differentiable (Lebesgue) almost everywhere. We remark that Pansu’s proof of this theorem extends almost verbatim to the case when X has the Radon-Nikodým property. A Banach space X is said to have the Radon-Nikodým property (RNP) if every Lipschitz function f : ℝ → X is differentiable almost everywhere. This is not the original definition of the Radon-Nikodým property, but it is equivalent to it and is most convenient for our purposes. We refer to Chapter 3 in [6] for more details. Examples of spaces without the RNP are L_{1}, c_{0} and C(0, 1). On the other hand, separable conjugate Banach spaces and reflexive Banach spaces are known to have the RNP [6]. For example, since ℓ_{1} = c_{0}^{∗} and ℓ_{1} is separable, it has the RNP.

Since Pansu’s proof of his differentiability theorem into finite dimensional spaces uses only the differentiability of Lipschitz functions along geodesics, it extends to the case when X has the RNP (the modification of Pansu’s argument is straightforward, and will not be included here). In fact, a very simple proof which is particularly convenient to extend to the Heisenberg case is the Preiss-Zajíček theorem [43] on the differentiability outside a σ-porous set of Lipschitz functions on ℝ^{n} with values in RNP spaces (see also the second proof of Proposition 6.41 in [6]). Recall that for a metric space (Z, d) a set A ⊆ M is called porous if there exists a number 0 < λ < 1 such that for every x ∈ A and every ε > 0 there is y ∈ Z such that 0 < d(x, y) < ε and A ∩ B(y, λd(x, y)) = ∅. A countable union of porous sets is called σ-porous. Clearly porous sets are nowhere dense, so that σ-porous sets are of the first category. The Lebesgue density theorem implies that σ-porous sets on ℍ^{2n+1} also have measure zero. Thus a slight strengthening of Pansu’s differentiability theorem is that if X has the RNP then every Lipschitz function F : ℍ^{2n+1} → X is Pansu-differentiable outside a σ-porous set.

As noted by Semmes in [46], these observations imply that ℍ^{2n+1} does not embed bi-Lipschitzly into any Banach space with the RNP. Indeed, if F : ℍ^{2n+1} → X were such an embedding then let g ∈ ℍ^{2n+1} be a point of Pansu differentiability of F. For every h, k ∈ ℍ^{2n+1} we have D_{F}^{g} (hk) = D_{F}^{g} (h) + D_{F}^{g} (k) = D_{F}^{g} (kh). Thus

0 = lim_{θ→0} ∥\frac{F (δ_{θ}(hk)g) − F (g)}{θ} − \frac{F (δ_{θ}(kh)g) − F (g)}{θ}∥_{X}

≥ \frac{1}{∥F^{−1}∥_{Lip}} · lim inf_{θ→0} \frac{ρ_{N_{0}}(δ_{θ}(hk)g, δ_{θ}(kh)g)}{θ} ≥ \frac{ρ_{N_{0}}(hk, kh)}{∥F^{−1}∥_{Lip}},

and this is a contradiction since ℍ^{2n+1} is not commutative.

Since for p > 1, L_{p} has the RNP, it follows that ℍ^{2n+1} does not embed bi-Lipschitzly in L_{p}, proving the last part of Theorem 1.2.

Remark 1.3. Since ℓ_{1} has the RNP, it follows from the above discussion that ℍ^{2n+1} does not embed into ℓ_{1}. But this does not suffice to deduce the discretization statement in (1), since it is not true that if a metric space does not embed into ℓ_{1} then its finite subsets cannot embed into ℓ_{1} with uniformly bounded distortion. Indeed, ℓ_{2} does not embed into ℓ_{1} (see [35]), but all its finite subsets embed isometrically into ℓ_{1}. Another such example is L_{1} itself. For the Goemans-Linial conjecture (and hence also for the integrality gap of the Sparsest Cut SDP), which originally deals with finite metrics, it is crucial, and sufficient, to prove non-embeddability into L_{1}, since L_{1} has the property that if all the finite subsets of a separable metric space embed into it with uniformly bounded distortion, then so does the entire space (see [24]).

Remark 1.4. In [13] Cheeger and Kleiner extend Pansu’s theorem in a different direction by generalizing Cheeger’s theory of metric differentiation [10] to the case of mappings from certain metric measure spaces to a separable dual Banach space. The fact that ℍ^{2n+1} does not embed into L_{p}, p > 1, follows from their results as well. In [12] they use this theory to give an example of a doubling metric space which embeds into L_{1} but does not embed into ℓ_{1}. This result can be viewed as an extreme infinite version of the results [8, 32, 31] that there is no dimension reduction in L_{1} in the spirit of the Johnson-Lindenstrauss dimension reduction lemma [25].

1.3 The Cheeger-Kleiner theorem on collapse towards the center

The crucial non-embeddability result in Theorem 1.1 does not follow from a differentiation statement, since L_{1} does not have the RNP, and thus even Lipschitz mappings from the real line into L_{1} might not have a point of differentiability (consider for example the mapping t ↦ 1_{[0,t]}). Moreover, differentiability theorems cannot hold for mappings into general Banach spaces since ℍ^{2n+1} is isometric to a subset of L_{∞}, and this isometry cannot have a derivative in any reasonable sense. This problem is a long standing major obstacle to proving L_{1} non-embeddability. In a beautiful tour-de-force paper [11] Cheeger and Kleiner proved that in a certain sense there is a weak notion of differentiability for mappings from ℍ^{2n+1} into L_{1}. This notion is strong enough to prove that ℍ^{2n+1} does not embed into L_{1}. We will not state here the exact (somewhat complicated) formulation of the Cheeger-Kleiner L_{1} differentiation result— instead we will state its main corollary. They show that if U ⊆ ℍ^{2n+1} is an open subset, and F : U → L_{1} is a Lipschitz function, then for almost every (z, t) ∈ U we have

lim_{ε→0^{+}} \frac{∥F (z, t + ε) − F (z, t)∥_{1}}{\sqrt{ε}} = 0.  (5)

This implies that F is not bi-Lipschitz. Indeed, otherwise we would have for every (z, t) ∈ U and ε > 0,

∥F (z, t + ε) − F (z, t)∥_{1} ≥ \frac{1}{∥F^{−1}∥_{Lip}} · ρ_{N_{0}}((z, t + ε), (z, t)) = \frac{1}{∥F^{−1}∥_{Lip}} · \sqrt{ε}.

The statement in (5) says that Lipschitz maps on ℍ^{2n+1} “collapse” in the direction of the center of ℍ^{2n+1} at almost every point, and thus they cannot be bi-Lipschitz. This in itself can be viewed as a weak differentiation result. The proof of (5) is quite remarkable. Cheeger and Kleiner start by using the cut decomposition on the image of F to induce a family of cuts on ℍ^{2n+1}. They observe that in a certain sense most of these cuts are given by subsets of ℍ^{2n+1} with finite perimeter. They then apply recent results in geometric measure theory on the fine structure of subsets of ℍ^{2n+1} with finite perimeter, and use this structural information to prove (5). This geometric investigation of the type of cuts that can appear in the cut decomposition of certain spaces is a novel approach to L_{1} non-embeddability and L_{1} differentiation, and we expect that it will have additional applications in the future.

Remark 1.5. A natural question that occurs is what is the rate with which the distortion tends to infinity in (1). It is not difficult to see that explicit rates would follow from a version of (5) with an explicit rate of convergence to 0. We discuss this below in Remark 1.6. This rate at which (5) tends to 0 is the topic of a work in progress of Cheeger, Kleiner and the second named author [14]. Heuristic considerations suggest that the rate in (1) might be c_{1} ({0, …, n}^{3}, d) ≥ (log n)^{Ω(1)}. This should follow from a technical (albeit tedious) “quantification” of the arguments in [11]. It is clearly of interest to find a simpler and shorter argument— this is intended to be the main focus of [14]. We do not report a specific exponent here since the quantitative version of (5) is quite long and involved, and it is not clear at this point what are the precise rates that are obtained. One of the reasons for this complication is that a quantitative version of (5) involves proving effective versions of the results from geometric measure theory that were used in [11]. Such effective versions were not previously known, and they are of independent interest.

We remark that the Khot-Vishnoi example in [26] gives an n-point metric space X_{n} of negative type such that c_{1}(X_{n}) ≥ (log log n)^{\frac{1}{6} −o(1)}. This was improved recently by Krauthgamer and Rabani [29] to a lower bound of Ω(log log n). The best known upper bounds for the Euclidean distortion (and, hence, L_{1} distortion) of n-point negative type metrics are due to Arora, Lee, and Naor [2], who proved that such metrics embed into L_{2} with distortion O (\sqrt{log n} · log log n). A recent paper of the first named author yields a small improvement to O (\sqrt{log n log log n}) [30]. The result of Khot and Vishnoi is based on the analysis of a hardness result which they proved (in the same paper) for the Sparsest Cut problem with general demands, assuming the unique games conjecture (such a hardness result was also obtained in [9]). Improving this (conditional) hardness lower bound to (log n)^{Ω(1)} remains an important challenge.

The best known integrality gap for the Goemans-Linial semidefinite relaxation of Sparsest Cut with uniform demands, due to Arora, Rao and Vazirani [3], is O (\sqrt{log n}). Very recently Devanur, Khot, Saket and Vishnoi [16] showed that this integrality gap also tends to infinity with the number of vertices of the graph. We remark that doubling metrics, and more generally decomposable metrics, cannot yield an integrality gap for the SDP relaxation of uniform Sparsest Cut due to the results of Rabinovich [44].

Remark 1.6. We now show the relationship between the rate of convergence in (5) and quantitative lower bounds on c_{1}(X) for finite subsets X ⊆ ℍ^{3}. Let B(0, r) denote the open ball of radius r centered at 0 in (ℍ^{3}, ρ_{N_{0}}). Fix δ ∈ (0, \frac{1}{2}) and let X ⊆ B(0, 1) be a δ-net in B(0, 1). It is easily checked that |X| ≤ (4/δ)^{4}.

Assume that for some non-decreasing function R : (0, \frac{1}{4}) → [0, 1] with 1 ≥ R(ε) ≥ \sqrt{ε} for every ε ∈ (0, \frac{1}{4}), the following assertion holds true: For every 1-Lipschitz map F : B(0, 1) → L_{1} there exists a point (z, t) ∈ B(0, \frac{1}{2}) such that

∥F (z, t + ε) − F (z, t)∥_{1} ≤ R(ε)\sqrt{ε}.  (6)

We claim that by choosing δ = \frac{1}{4} \sqrt{ε} · R(ε) one has

c_{1}(X) ≥ \frac{c}{R (16 |X|^{−1/4})},  (7)

where c > 0 is a universal constant.

Indeed, let f : X → L_{1} be a bi-Lipschitz map with ∥f∥_{Lip} ≤ 1. Since ℍ^{3} is doubling, by [33, Th. 1.6] there exists a universal constant K ≥ 1 (independent of f) and a map f̃: ℍ^{3} → L_{1} for which ∥f̃∥_{Lip} ≤ K and f̃|_{X} = f. Let F = \frac{1}{K} f̃, so that ∥F ∥_{Lip} ≤ 1. Let (z, t) ∈ B(0, \frac{1}{2}) be the point which results from applying (6) to F, and let (z_{1}, t_{1}), (z_{2}, t_{2}) ∈ X be such that ρ_{N_{0}}((z_{1}, t_{1}), (z, t)) ≤ δ and ρ_{N_{0}}((z_{2}, t_{2}), (z, t + ε)) ≤ δ. Then

R(ε)\sqrt{ε} ≥ ∥F (z, t + ε) − F (z, t)∥_{1} ≥ ∥F (z_{1}, t_{1}) − F (z_{2}, t_{2})∥_{1} − 2δ
≥ \frac{ρ_{N_{0}}((z_{1}, t_{1}), (z_{2}, t_{2}))}{K · ∥f^{−1}∥_{Lip}} − 2δ ≥ \frac{\sqrt{ε} − 2δ}{K · ∥f^{−1}∥_{Lip}} − 2δ.

Equivalently,

∥f^{−1}∥_{Lip} ≥ \frac{1}{K} · \frac{\sqrt{ε} − 2δ}{R(ε)\sqrt{ε} + 2δ} ≥ \frac{1}{3K · R(ε)}.

Since |X| ≤ (4/δ)^{4} ≤ (16/ε)^{4}, we conclude that (7) holds. Thus one obtains a bound of the form c_{1}(X) ≥ (log |X|)^{Ω(1)} as long as R(ε)^{−1} ≥ (log(\frac{1}{ε}))^{Ω(1)} holds in (6).

2 A metric of negative type on the Heisenberg group

Let G be a group with identity element e. A a complex valued function K : G × G → ℂ is called a Hermitian kernel on G if every g, h ∈ G satisfy K(g, h) = \overline{K(h, g)}. A Hermitian kernel K on G is said to be positive definite if

∑_{ℓ,m=1}^{n} K(g_{ℓ}, g_{m})c_{ℓ}\overline{c_{m}} ≥ 0

for all g_{1}, …, g_{n} ∈ G and for all complex scalars c_{1}, …, c_{n} ∈ ℂ. A Hermitian kernel K on G is called negative definite if

∑_{ℓ,m=1}^{n} K(g_{ℓ}, g_{m})c_{ℓ}\overline{c_{m}} ≤ 0

for all g_{1}, …, g_{n} ∈ G and for all complex scalars c_{1}, …, c_{n} ∈ ℂ satisfying ∑_{j=1}^{n} c_{j} = 0.

Let F : G → ℂ be a function such that every g ∈ G satisfies F (g^{−1}) = \overline{F (g)}. The Hermitian kernel on G induced by F, denoted K_{F}, is defined by K_{F} (g, h) = F (gh^{−1}). F is said to be positive definite (resp. negative definite) if K_{F} is positive definite (resp. negative definite).

We will use the following classical fact, due to Scoenberg [45] (see also the book [50] and Proposition 8.5 in [6]).

Proposition 2.1. Let K : G×G → ℝ be a real-valued kernel on G satisfying K(g, g) = 0 for every g ∈ G. Then K is negative definite if and only if there exists a Hilbert space H and a function T : G → H such that for all g, h ∈ G,

K(g, h) = ∥T (g) − T (h)∥^{2}.

The main result of this section is:

Theorem 2.2. Let N be as in (2). Then (ℍ^{2n+1}, ρ_{N}) is a metric space of negative type, i.e. (ℍ^{2n+1}, ρ_{N}) is a metric space and (ℍ^{2n+1}, \sqrt{ρ_{N}}) embeds isometrically in Hilbert space.

By Proposition 2.1 all that remains is to show that N is a negative definite function on ℍ^{2n+1}, and the remainder of this section is devoted to the proof of this fact. We remark that it is easy to verify that the Koranyi norm itself in not negative definite on ℍ^{2n+1}.

Lemma 2.3. For every λ ∈ ℂ define Φ_{λ} : ℍ^{2n+1} → ℝ by

Φ_{λ}(z, t) = e^{−|λ|·|z|^{2}+iλt}.

Then Φ_{λ} is a positive definite function on ℍ^{2n+1}.

Proof. We have

K_{Φ_{λ}}((z, s), (w, t)) = Φ_{λ}((z, s) · (−w, −t))
= exp [−|λ| ∑_{j=1}^{n} |z_{j} − w_{j}|^{2} + iλ(s − t − 2 ∑_{j−1}^{n} ℑ(z_{j}\overline{w_{j}}))]

= (∏_{j=1}^{n} e^{−|λ|(|z_{j}|^{2}+|w_{j}|^{2})}) · e^{iλ(s−t)} · (∏_{j=1}^{n} e^{2|λ|(ℜ(z_{j} \overline{w_{j}})−i·sign(λ)ℑ(z_{j} \overline{w_{j}}))}) .

Since the point-wise product of positive definite kernels is positive definite (see [6], Proposition 8.2), it suffices to show that each term in the above product is a positive definite kernel on ℍ^{2n+1}. The fact that e^{iλ(s−t)} and e^{−|λ|(|z_{j}|^{2}+|w_{j}|^{2})} are positive definite follows the fact that for all complex scalars c_{1}, …, c_{k} ∈ ℂ, the matrix (c_{ℓ}\overline{c_{m}})_{ℓ,m} is positive semidefinite. It remains to check that e^{2|λ|(ℜ(z_{j} \overline{w_{j}})−i·sign(λ)ℑ(z_{j} \overline{w_{j}}))} is positive definite. Since, for any positive definite kernel K, the kernel e^{K} is also positive definite (see [6], Proposition 8.2), it is enough to show that

ℜ(z_{j}\overline{w_{j}}) − i · sign(λ)ℑ(z_{j}\overline{w_{j}})

is positive definite. This equals z_{j}\overline{w_{j}} if λ < 0 and \overline{z_{j}\overline{w_{j}}} = \overline{z_{j}}w_{j} if λ ≥ 0. In both cases, the kernel is positive definite.

Proof of Theorem 2.2. Our goal is to show that N is a negative definite function on ℍ^{2n+1}. In what follows, we use some notions from Fourier analysis. For a function f : ℝ → ℝ, we denote its Fourier transform by f̂(t) = ∫_{ℝ} e^{itx}f(x)dx. The convolution of two functions f, g : ℝ → ℝ is defined as (f ∗ g)(t) = ∫_{ℝ} f(t − x)g(x)dx, so that { \atop f ∗ g} = f̂· ĝ.

Fix ε > 0. The existence of symmetric \frac{1}{2}-stable distributions (see [18]) implies that there exits a non-negative integrable function φ_{ε} : ℝ → [0, ∞) such that, for all t ∈ ℝ, φ̂_{ε}(t) = e^{−ε\sqrt{|t|}}. Lemma 2.3 shows that the function F_{ε} : ℍ^{2n+1} → ℂ given by

F_{ε}(z, t) = ∫_{ℝ} e^{−|λ|·|z|^{2}+iλt}φ_{ε}(λ) dλ

is positive definite on ℍ^{2n+1}. For every a > 0, denote

h_{a}(x) = \frac{a}{π} · \frac{1}{a^{2} + x^{2}} .

Then ∫_{ℝ} ĥ_{a}(x)dx = 1 and ĥ_{a}(t) = e^{−a|t|} for all t ∈ ℝ (see, e.g. [18]). Denoting f_{ε}(t) = e^{−ε\sqrt{|t|}}, the inversion formula for the Fourier transform implies that φ_{ε} = \frac{1}{2π} f̂_{ε}. Another application of the inversion formula gives

F_{ε}(z, t) = \frac{1}{2π} ∫_{ℝ} e^{iλt}ĥ_{|z|^{2}}(λ)f̂_{ε}(λ)dλ = \frac{1}{2π} ∫_{ℝ} e^{iλt}{ \atop (h_{|z|^{2}} ∗ f_{ε})}(λ)dλ = (h_{|z|^{2}} ∗ f_{ε})(t).

Since F_{ε} is positive definite on ℍ^{2n+1}, the function \frac{1−F_{ε}}{ε} is negative definite on ℍ^{2n+1}, and

lim_{ε→0} \frac{1 − F_{ε}(z, t)}{ε} = lim_{ε→0} [h_{|z|^{2}} ∗ (\frac{1 − f_{ε}}{ε} )] (t)

= lim_{ε→0} ∫_{ℝ} \frac{1 − e^{−ε\sqrt{|x|}}}{ε} h_{|z|^{2}}(t − x) dx
= \frac{|z|^{2}}{π} ∫_{ℝ} \frac{\sqrt{|x|}}{|z|^{4} + (t − x)^{2}} dx.

The next lemma shows that the latter expression is equal to N(z, t), completing the proof.

Lemma 2.4. For every r, t ∈ ℝ

\frac{r^{2}}{π} ∫_{ℝ} \frac{\sqrt{|x|}}{r^{4} + (t − x)^{2}} dx = \sqrt{\sqrt{r^{4} + t^{2}} + r^{2}}.

Proof. Making the change of variable x = r^{2}v and s = t/r^{2}, our goal is to prove that

∫_{0}^{∞} (\frac{1}{1 + (s − v)^{2}} + \frac{1}{1 + (s + v)^{2}} ) \sqrt{v} dv = π\sqrt{\sqrt{1 + s^{2}} + 1}.  (8)

By continuity, we may assume that s ≠ 0. Consider the function ψ : {ζ : ℑ(ζ) > 0} → ℂ given by ψ(ζ) = (\frac{1}{1+(s−ζ)^{2}} + \frac{1}{1+(s+ζ)^{2}} ) \sqrt{ζ}. We take here the principle branch of the square root, i.e. if

ζ = ρe^{iθ} where ρ > 0 and θ ∈ (0, π) then \sqrt{ζ} = \sqrt{ρ}e^{iθ/2}. The poles of ψ are at i ± s, so that, by the residue theorem, the left-hand side of (8) equals ℜ [2πiRes_{i+s}(ψ) + 2πiRes_{i−s}(ψ)]. Since the poles of ψ are simple, a direct computation gives that the required integral equals

ℜ [2πi (\frac{\sqrt{i + s}}{2i} + \frac{\sqrt{i − s}}{2i})] = π (\sqrt{\frac{\sqrt{s^{2} + 1} + s}{2}} + \sqrt{\frac{\sqrt{s^{2} + 1} − s}{2}}) = π\sqrt{\sqrt{1 + s^{2}} + 1},

which is the required identity.

3 The L_{p} case

We now generalize the argument of Section 2.2 to prove Theorem 1.2. The idea of the proof is the same, and we will therefore use the same notation and be sketchy at some places. In what follows we fix 1 ≤ p < 2.

Fix ε > 0 and let φ_{ε} : ℝ → [0, ∞) satisfy for all t ∈ ℝ, φ̂_{ε}(t) = e^{−ε|t|^{p/2}}. The existence of φ_{ε} follows from the existence of a symmetric \frac{p}{2}-stable distribution [18]. Define F_{ε} : ℍ^{2n+1} → ℂ by

F_{ε}(z, t) = ∫_{ℝ} e^{−|λ|·|z|^{2}+iλt}φ_{ε}(λ) dλ,

which is a positive definite function on ℍ^{2n+1} by Lemma 2.3. As before, we write h_{a}(x) = \frac{a}{π} · \frac{1}{a^{2}+x^{2}} and f_{ε}(t) = e^{−ε|t|^{p/2}}. Arguing as in the proof of Theorem 2.2 we obtain the identity

lim_{ε→0} \frac{1 − F_{ε}(z, t)}{ε} = \frac{|z|^{2}}{π} ∫_{ℝ} \frac{|x|^{p/2}}{|z|^{4} + (t − x)^{2}} dx.

Thus the mapping

(z, t) ↦ \frac{|z|^{2}}{π} ∫_{ℝ} \frac{|x|^{p/2}}{|z|^{4} + (t − x)^{2}} dx  (9)

is negative definite on ℍ^{2n+1}. This integral is calculated in the following lemma.

Lemma 3.1. For every r, t ∈ ℝ

\frac{r^{2}}{π} ∫_{ℝ} \frac{|x|^{p/2}}{r^{4} + (t − x)^{2}} dx = 2 cos (\frac{pπ}{4} ) · (r^{4} + t^{2})^{p/4} · cos [\frac{p}{2} arccos (\frac{r^{2}}{\sqrt{r^{4} + t^{2}}} )] .

Proof. Making the change of variable x = r^{2}v and s = t/r^{2} we find that:

\frac{r^{2}}{π} ∫_{ℝ} \frac{|x|^{p/2}}{r^{4} + (t − x)^{2}} dx = \frac{r^{p}}{π} ∫_{0}^{∞} (\frac{1}{1 + (s − v)^{2}} + \frac{1}{1 + (s + v)^{2}} ) v^{p/2}dv.

As in Lemma 2.4 we define ψ : \{ζ : ℑ(ζ) > 0\} → ℂ by ψ(ζ) = (\frac{1}{1+(s−ζ)^{2}} + \frac{1}{1+(s+ζ)^{2}} ) ζ^{p/2}, where if

ζ = ρe^{iθ} for ρ > 0 and θ ∈ (0, π) then ζ^{p/2} = ρ^{p/2}e^{ipθ/2}. By the residue theorem,

∫_{0}^{∞} (\frac{1}{1 + (s − v)^{2}} + \frac{1}{1 + (s + v)^{2}} ) v^{p/2}dv = ℜ [2πi (\frac{(i + s)^{p/2}}{2i} + \frac{(i − s)^{p/2}}{2i} )]

= 2π cos (\frac{pπ}{4} ) · (1 + s^{2})^{p/4} · cos [\frac{p}{2} arccos (\frac{1}{\sqrt{1 + s^{2}}} )] .

This implies the required identity.

We have thus shown that if M is as in (3) then (ℍ^{2n+1}, M^{p/2}) is isometric to a subset of L_{p} (since the integral in (9) equals M^{p}). In order to prove Theorem 1.2 it remains to prove Lemma 1.3. We begin with the following standard lemma, whose simple proof we include for the sake of completeness.

Lemma 3.2. Denote C = {(a, b) ∈ ℝ^{2}\{0} : a ≥ b ≥ 0}. Assume that 1 < β and γ : [1, β] → [0, ∞] is continuously differentiable, concave, γ(1) = 1, γ(β) = 0, and γ′(1) < 0. Then for every (a, b) ∈ C there is a unique μ = μ(a, b) ∈ [a/β, a] such that \frac{b}{μ} = γ (\frac{a}{μ}). Moreover, μ : C → [0, ∞) satisfies for every x, y ∈ C, μ(x + y) ≤ μ(x) + μ(y), and if x ≤ y coordinate-wise then μ(x) ≤ μ(y).

Proof. The assumptions imply that γ is strictly decreasing. To prove the existence of μ take (a, b) ∈ C and for μ ∈ [a/β, a] let f(μ) = μγ (\frac{a}{μ}). Direct differentiation shows that γ is strictly

increasing. Moreover f (\frac{a}{β} ) = \frac{a}{β} γ(β) = 0 ≤ b and f(a) = aγ (1) = a. Thus there exists a unique μ for which f(μ) = b.

If x, y ∈ C write x = (x_{1}, x_{2}), y = (y_{1}, y_{2}) and denote A = μ(x) + μ(y). Then by the concavity of γ,

γ (\frac{x_{1} + y_{1}}{μ(x) + μ(y)}) ≥ \frac{μ(x)}{μ(x) + μ(y)}γ (\frac{x_{1}}{μ(x)}) + \frac{μ(y)}{μ(x) + μ(y)}γ (\frac{y_{1}}{μ(y)}) = \frac{x_{2} + y_{2}}{μ(x) + μ(y)},

and from the above reasoning we deduce that μ(x) + μ(y) ≥ μ(x + y). Assume now that x_{1} ≤ y_{1} and x_{2} ≤ y_{2}. Then denoting g(t) = tγ (\frac{x_{1}}{t} ) for t ∈ [x_{1}/β, x_{1}], we know that g is increasing and g (μ(x_{1}, x_{2})) = x_{2} ≤ y_{2} = g (μ(x_{1}, y_{2})). Thus μ(x_{1}, x_{2}) ≤ μ(x_{1}, y_{2}). Assume for the sake of contradiction that μ(y_{1}, y_{2}) < μ(x_{1}, y_{2}). Then γ (\frac{x_{1}}{μ(x_{1},y_{2})}) = \frac{y_{2}}{μ(x_{1},y_{2})} < \frac{y_{2}}{μ(y_{1},y_{2})} = γ (\frac{y_{1}}{μ(y_{1},y_{2})}). Since γ is decreasing we deduce that \frac{y_{1}}{μ(x_{1},y_{2})} ≥ \frac{x_{1}}{μ(x_{1},y_{2})} > \frac{y_{1}}{μ(y_{1},y_{2})}, which is a contradiction.

The following lemma is the crucial step in proving that M is indeed a group norm on ℍ^{2n+1}.

Lemma 3.3. Define γ : [1, [cos (\frac{πp}{4})]^{−1/p}] → [0, ∞) by

γ(a) = a\sqrt{cos (\frac{2}{p} arccos (\frac{1}{a^{p}} )) .}

Then γ satisfies the conditions of Lemma 3.2.

Before proving Lemma 3.3 we use it to prove Lemma 1.3.

Proof of Lemma 1.3. Let μ : C → [0, ∞) be the function from Lemma 3.2 which corresponds to the function γ in Lemma 3.3. Then for (a, b) ∈ C we have

\frac{b}{μ(a, b)} = γ (\frac{a}{μ(a, b)}) = \frac{a}{μ(a, b)}\sqrt{cos (\frac{2}{p} arccos (\frac{μ(a, b)^{p}}{a^{p}} ))}.

Solving this equation we see that

μ(a, b) = |a| \{cos [\frac{p}{2} arccos (\frac{b^{2}}{a^{2}} )]\}^{1/p} .

Thus M(z, t) = μ(N_{0}(z, t), |z|). It follows that for every (z, t), (ζ, τ) ∈ ℍ^{2n+1} we have

M ((z, t) · (ζ, τ)) = μ (N_{0} ((z, t) · (ζ, τ)) , |z + ζ|)
≤ μ (N_{0} (z, t) + N_{0}(ζ, τ), |z| + |ζ|)
≤ μ(N_{0}(z, t), |z|) + μ(N_{0}(ζ, τ), |ζ|)
= M(z, t) + M(ζ, τ).

The right-hand inequality in (4) follows from the fact that arccos (\frac{|z|^{2}}{\sqrt{|z|^{4}+t^{2}}} ) ∈ [0, π/2], and the

left-hand inequality in (4) is an easy elementary numerical inequality which we do not prove here (actually we just care about the asymptotic behavior as p tend to 2, which is obvious).

Before passing to the proof of Lemma 3.3 we record some elementary numerical inequalities that will be used in the ensuing argument.

Lemma 3.4 (Auxiliary numerical inequalities that will be used later). The following numerical inequalities hold true in the specified ranges

1. tan(λt) ≥ λ tan t for λ ∈ [1, ∞) and t ∈ [0, \frac{π}{2λ}).

2. \frac{4x}{π} ≤ max \{1, 3 sin^{2} x\} for x ∈ [0, 1].

3. 2 sin u − u cos u − u ≥ 0 for u ∈ [0, π].

4. sin(4x) − 4x + 12x sin^{2} x ≥ 0 for 0 ≤ x ≤ arcsin (\frac{1}{\sqrt{3}}).

Proof. The first inequality is simply a consequence of the convexity of the function tan(·) on [0, π/2). To prove the second inequality note that if \frac{4x}{π} ≤ 1 then there is nothing to prove, so assume that x ∈ [π/4, 1]. We must show that in this range 3 sin^{2} x ≥ \frac{4x}{π}. Using the elementary inequality

sin x ≥ x − \frac{x^{3}}{6} we see that it is enough to prove the inequality x (1 − \frac{x^{2}}{6} )^{2} ≥ \frac{4π}{3} , which is valid for x ∈ [π/4, 1]. To prove the third inequality write ψ(u) = 2 sin u − u cos u − u. Then ψ′′(u) = u cos u. So ψ′ is increasing on [0, π/2] and decreasing on [π/2, π]. But ψ′(0) = 0, so that ψ′ is either always non-negative or first non-negative and then negative. Thus ψ is either increasing or first increasing and then decreasing. In both cases the minimum of ψ is attained at one of the endpoints {0, π}, where its value is 0.

It remains to prove the fourth inequality. To this end let s = sin x, so that 0 ≤ s ≤ \frac{1}{\sqrt{3}}. Note that sin(4x) = 4 sin x cos x (1 − 2 sin^{2} x) = 4s(1 − 2s^{2})\sqrt{1 − s^{2}}. Thus the required inequality becomes 4s(1 − 2s^{2})\sqrt{1 − s^{2}} − 4x (1 − 3s^{2}) ≥ 0, or

arcsin s ≤ \frac{s(1 − 2s^{2})\sqrt{1 − s^{2}}}{1 − 3s^{2}} .  (10)

To prove (10) define θ(s) = ^{\frac{s(1−2s^{2})\sqrt{1−s^{2}}}{1−3s^{2}}} − arcsin s. Direct (but tedious) differentiation gives

θ′(s) = \frac{s^{2}(1 + 5s^{2} − 12s^{4})}{(1 − 3s^{2})^{2}\sqrt{1 − s^{2}}}.

Since 1 + 5s^{2} − 12s^{4} ≥ 0 when 0 ≤ s ≤ \frac{1}{\sqrt{3}} it follows that θ′(s) ≥ 0. Thus θ(s) ≥ θ(0) = 0, which proves (10).

Proof of Lemma 3.3. If g = γ^{2} satisfies the conditions of Lemma 3.3 then so does γ. One checks that g′(1) = 2 − \frac{4}{p} < 0, so that it is enough to show that g′′ ≤ 0. Direct differentiation yields

g′′(a) = \frac{2(a^{2p} − 3)}{a^{2p} − 1} cos (\frac{2}{p} arccos (\frac{1}{a^{p}} )) + \frac{2[a^{2p}(p − 3) + 3]}{(a^{2p} − 1)^{3/2}} sin (\frac{2}{p} arccos (\frac{1}{a^{p}} )) .

Note that in the range 1 ≤ a ≤ [cos (\frac{πp}{4})]^{−1/p} we have cos (\frac{2}{p} arccos (\frac{1}{a^{p}} )) ≥ 0. Thus the inequality g′′(a) ≤ 0 is equivalent to

[a^{2p}(3 − p) − 3] tan (\frac{2}{p} arccos (\frac{1}{a^{p}} )) ≥ (a^{2p} − 3)\sqrt{a^{2p} − 1}.  (11)

We distinguish between two cases. If a^{2p}(3 − p) − 3 > 0 then we must show that

tan (\frac{2}{p} arccos (\frac{1}{a^{p}} )) ≥ \frac{(a^{2p} − 3)\sqrt{a^{2p} − 1}}{a^{2p}(3 − p) − 3}.  (12)

Observe that we are assuming that \frac{2}{p} arccos (\frac{1}{a^{p}} ) ≤ \frac{π}{2} . Hence by the first inequality in Lemma 3.4 (with λ = \frac{2}{p} ≥ 1) we see that

tan (\frac{2}{p} arccos (\frac{1}{a^{p}} )) ≥ \frac{2}{p} tan (arccos (\frac{1}{a^{p}} )) = \frac{2}{p} · \frac{\sqrt{1 − a^{−2p}}}{a^{−p}} = \frac{2}{p} · \sqrt{a^{2p} − 1}.

Thus (12) is equivalent to a^{2p} ≥ 1, as required.

It remains to deal with the case a^{2p}(3 − p) − 3 < 0, which is equivalent to a^{2p} < \frac{3}{3−p}. In this case we need to show that

tan (\frac{2}{p} arccos (\frac{1}{a^{p}} )) ≤ \frac{(3 − a^{2p})\sqrt{a^{2p} − 1}}{3 − a^{2p}(3 − p)}.  (13)

Write x = arccos (\frac{1}{a^{p}} ), so that by our assumption x ≤ \frac{πp}{4}. Then the required inequality becomes

tan (\frac{2x}{p}) ≤ \frac{2 − 3 sin^{2} x}{p − 3 sin^{2} x} · tan x,  (14)

where the condition a^{2p} < \frac{3}{3−p} translates to p > 3 sin^{2} x. For fixed x the range of p for which (14) should hold is 2 ≥ p ≥ max \{1, \frac{4x}{π}, 3 sin^{2} x\}. If this range is non-empty then 3 sin^{2} x ≤ 2, i.e. x ≤ arcsin (\sqrt{2/3}) < 1. We will therefore assume from now on that this upper bound on x is satisfied, in which case the second inequality in Lemma 3.4 implies that (14) should hold for 2 ≥ p ≥ max {1, 3 sin^{2} x}.

Denote A(p) = (p − 3 sin^{2} x) tan (\frac{2x}{p}). We want to show that A(p) ≤ A(2). Now,

A′(p) = tan (\frac{2x}{p}) − \frac{2x(p − 3 sin^{2} x)}{p^{2} cos^{2} (\frac{2x}{p})}.

It is enough to show that A′(p) ≥ 0. Clearing the denominator and simplifying we see that it is enough to prove that

B(p) = \frac{p^{2}}{2} sin (\frac{4x}{p}) − 2x(p − 3 sin^{2} x) ≥ 0.  (15)

Now,

B′(p) = p sin (\frac{4x}{p}) − 2x cos (\frac{4x}{p}) − 2x.

We claim that B′(p) ≥ 0. Denoting u = \frac{4x}{p} ≤ π we see that this reduces to the third inequality in Lemma 3.4. So B′(p) ≥ 0 and hence B(p) ≥ B (p_{0}), where p_{0} = max{1, 3 sin^{2} x} and we are assured that 2 ≥ p_{0} ≥ \frac{4x}{π}. If p_{0} = 3 sin^{2} x then B(p_{0}) = \frac{p_{0}^{2}}{2} sin (\frac{4x}{p_{0}}) ≥ 0, since \frac{4x}{p_{0}} ≤ π. We

therefore assume that p_{0} = 1, in which case we know that 0 ≤ x ≤ arcsin (\frac{1}{\sqrt{3}}). But B(p_{0}) =

B(1) = \frac{1}{2} sin(4x) − 2x + 6x sin^{2} x ≥ 0, by the fourth inequality in Lemma 3.4. This concludes the proof of (15), and completes the proof of Lemma 3.3.

References

[1] A. Agrawal, P. Klein, R. Ravi, and S. Rao. Approximation through multicommodity flow. In 31st Annual Symposium on Foundations of Computer Science, pages 726–737. IEEE Computer Soc., Los Alamitos, CA, 1990.

[2] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut [extended abstract]. In STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 553–562, New York, 2005. ACM.

[3] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 222–231 (electronic), New York, 2004. ACM.

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

[5] Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291–301, 1998.

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

[7] J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine. Lois stables et espaces L^{p}. Ann. Inst. H. Poincaré Sect. B (N.S.), 2:231–259, 1965/1966.

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

[9] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. In 20th Annual IEEE Conference on Computational Complexity, pages 144–153, 2005.

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

[11] J. Cheeger and B. Kleiner. Differentiating maps into L^{1} and the geometry of BV functions. Preprint, 2006.

[12] J. Cheeger and B. Kleiner. Embedding Laakso spaces into L^{1}. Preprint, 2006.

[13] J. Cheeger and B. Kleiner. On the differentiation of Lipschitz maps from metric measure spaces to Banach spaces. Preprint, 2006.

[14] J. Cheeger, B. Kleiner, and A. Naor. Quantitative bounds on the rate of central collapse of Lipschitz maps on the Heisenberg group. In preparation, 2006.

[15] J. Cygan. Subadditivity of homogeneous norms on certain nilpotent Lie groups. Proc. Amer. Math. Soc., 83(1):69–70, 1981.

[16] N. Devanur, S. Khot, R. Saket, and N. Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 537–546, 2006.

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

[18] R. Durrett. Probability: theory and examples. Duxbury Press, Belmont, CA, second edition, 1996.

[19] M. X. Goemans. Semidefinite programming in combinatorial optimization. Mathematical Programming, 79:143–161, 1997.

[20] M. Gromov. Carnot-Carathéodory spaces seen from within. In Sub-Riemannian geometry, volume 144 of Progr. Math., pages 79–323. Birkhäuser, Basel, 1996.

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

[22] A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and l_{1}-embeddings of graphs. Combinatorica, 24(2):233–269, 2004.

[23] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[24] S. Heinrich. Ultraproducts in Banach space theory. J. Reine Angew. Math., 313:72–104, 1980.

[25] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[26] S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ_{1}. In 46th Annual Symposium on Foundations of Computer Science, pages 53–62. IEEE Computer Soc., Los Alamitos, CA, 2005.

[27] P. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In 25th Annual ACM Symposium on Theory of Computing, pages 682–690, May 1993.

[28] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839–858, 2005.

[29] R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into L_{1}. In SODA ’06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1010–1017, New York, NY, USA, 2006. ACM Press.

[30] J. R. Lee. Improved distortion estimates for negative type metrics. Preprint, 2006.

[31] J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: dimension, snowflakes, and average distortion. European J. Combin., 26(8):1180–1190, 2005.

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

[33] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[34] T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999.

[35] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. I. Springer-Verlag, Berlin, 1977. Sequence spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 92.

[36] N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III, pages 573–586, 2002.

[37] N. Linial. Planar graph metrics into ℓ_{1}. In J. Matoušek, editor, Open Problems, Workshop on Discrete Metric Spaces and their Algorithmic Applications. Haifa, March 2002.

[38] N. Linial. Squared ℓ_{2} metrics into ℓ_{1}. In J. Matoušek, editor, Open Problems, Workshop on Discrete Metric Spaces and their Algorithmic Applications. Haifa, March 2002.

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

[40] D. W. Matula and F. Shahrokhi. The maximum concurrent flow problem. J. Assoc. Comput. Mach., 37(2):318–334, 1990.

[41] R. Montgomery. A tour of subriemannian geometries, their geodesics and applications, volume 91 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2002.

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

[43] D. Preiss and L. Zajíček. Sigma-porous sets in products of metric spaces and sigmadirectionally porous sets in Banach spaces. Real Anal. Exchange, 24(1):295–313, 1998/99.

[44] Y. Rabinovich. On average distortion of embedding metrics into the line and into l_{1}. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pages 456– 462 (electronic), New York, 2003. ACM.

[45] I. J. Schoenberg. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 44(3):522–536, 1938.

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

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

[48] E. M. Stein. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 43 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1993. With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III.

[49] K. Talwar. Decomposability of metrics. In J. Matoušek, editor, Open Problems, Workshop on Discrete Metric Spaces and their Algorithmic Applications. Haifa, March 2002.

[50] J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.