A DOUBLING SUBSET OF L_{p} FOR p > 2 THAT IS INHERENTLY INFINITE DIMENSIONAL

VINCENT LAFFORGUE AND ASSAF NAOR

Abstract. It is shown that for every p ∈ (2, ∞) there exists a doubling subset of L_{p} that does not admit a bi-Lipschitz embedding into ℝ^{k} for any k ∈ ℕ.

1. Introduction

Given K ∈ [1, ∞), a metric space X is said to be K-doubling if every ball in X can be covered by at most K balls of half its radius. X is said to be doubling if it is K-doubling for some K ∈ (0, ∞).

Lang and Plaut [LP01] asked whether or not every doubling subset of Hilbert space admits a bi-Lipschitz embedding into ℝ^{k} for some k ∈ ℕ. We refer to [NN12, Sec. 1.1] for further discussion on the ramifications of this question, as well as a construction of a doubling subset of Hilbert space that conceivably does not to admit a bi-Lipschitz embedding into ℝ^{k} for any k ∈ ℕ. While the validity of this suggestion of [NN12] remains open, and hence also the Lang–Plaut question remains open, here we show that a variant of the method that was proposed in [NN12] can be used to prove that the analogue of the Lang–Plaut problem with Hilbert space replaced by L_{p} for p ∈ (2, ∞) has a negative answer.

Theorem 1.1. For every p ∈ (2, ∞) there exists a doubling subset of L_{p} that does not admit a bi-Lipschitz embedding into ℝ^{k} for any k ∈ ℕ.

We thank Ofer Neiman for asking us the question that Theorem 1.1 answers. In [BGN13] Bartal, Gottlieb and Neiman concurrently found a construction that also yields Theorem 1.1; their (combinatorial) construction is entirely different from our (analytic) construction. The potential validity of Theorem 1.1 for p ∈ (1, 2] remains an open question, while for p = 1 stronger results are known; see Remark 1.4 below.

Theorem 1.1 is a special case of the following result.

Theorem 1.2. For every p ∈ (2, ∞) there exists a doubling subset D_{p} of L_{p} that does not admit a bi-Lipschitz embedding into L_{q} for any q ∈ (1, p). Furthermore, there exists p_{0} ∈ (2, ∞) such that D_{p} does not admit a bi-Lipschitz embedding into L_{1} for every p ∈ [p_{0}, ∞).

Theorem 1.2 is a formal consequence of the following finitary result.

Theorem 1.3. There exists a universal constant K ∈ [1, ∞) and for every n ∈ ℕ there exists an n-point metric space (X_{n}, d_{X_{n}}) with the following properties. For every n ∈ ℕ and p ∈ [2, ∞) there exists a mapping f_{n,p} : X_{n} → L_{p} such that f_{n,p}(X_{n}) ⊆ L_{p} is K-doubling, and

∀ x, y ∈ X_{n}, d_{X_{n}}(x, y) ⩽ ∥f_{n,p}(x) − f_{n,p}(y)∥_{p} ≲ (log n)^{1/p}d_{X_{n}}(x, y).

Moreover, for every q ∈ (1, ∞), any embedding of X_{n} into L_{q} incurs distortion at least c(q)(log n)^{min{1/2,1/q}}, where c(q) ∈ (0, ∞) may depend only on q. Any embedding of X_{n} into L_{1} incurs distortion at least (log n)^{c} for some universal constant c ∈ (0, 1/2].

Here and in what follows, the notations A ≲ B and B ≳ A mean that A ⩽ CB for some universal constant C ∈ (0, ∞). If we need to allow C to depend on parameters, we indicate this by subscripts, thus e.g. A ≲_{β} B means that A ⩽ C(β)B for some C(β) ∈ (0, ∞) which is allowed to depend only on the parameter β. The notation A ≍ B stands for (A ≲ B) ∧ (B ≲ A).

The fact that Theorem 1.3 implies Theorem 1.2 is simple. Indeed, fix p ∈ (2, ∞). By a standard “disjoint union” argument (see e.g. the beginning of Section 4 in [NN12]), there exists a doubling subset D_{p} of L_{p} that contains an isometric copy of a rescaling of f_{n,p}(X_{n}) for every n ∈ ℕ. If q ∈ (1, p) and f_{n,p}(X_{n}) embeds with bi-Lipschitz distortion M ∈ [1, ∞) into L_{q}, then by Theorem 1.3 we have

M ≳_{q} (log n)^{min\{\frac{1}{2} , \frac{1}{q}\}− \frac{1}{p}} ⟶_{n→∞} ∞.

Consequently, D_{p} does not admit a bi-Lipschitz embedding into L_{q}. For q = 1 the same argument shows that D_{p} does not admit a bi-Lipschitz embedding into L_{1} provided p > 1/c, where c is the (universal) constant from Theorem 1.3.

Remark 1.4. The above reasoning implies that for every p ∈ (2, ∞) and every n ∈ ℕ there exists an n-point O(1)-doubling subset S_{n} of L_{p} such that for every k ∈ ℕ, if S_{n} embeds with distortion M ∈ [1, ∞) into ℓ_{p}^{k} then necessarily,

M ≳ (\frac{log n}{k})^{\frac{1}{2} − \frac{1}{p}} .

INFINITE DIMENSIONAL DOUBLING SUBSET OF L_{p} 3

This is true because ℓ_{p}^{k} embeds into Hilbert space with distortion k^{\frac{1}{2} − \frac{1}{p}}. It is open whether or not a similar statement holds true for p ∈ (1, 2]. For p = 1 an even stronger lower bound was shown to hold true in [LMN05]: for every n ∈ ℕ there exists an n-point O(1)-doubling subset A_{n} of L_{1} such that for every k ∈ ℕ, if A_{n} embeds with distortion M ∈ [1, ∞) into ℓ_{1}^{k} then necessarily

M ≳ \sqrt{\frac{log n}{log k}}.  (1)

The examples leading to (1) are the Laakso graphs [Laa00], which are doubling metric spaces that were shown to embed into L_{1} in [GNRS04]. They yield a doubling subset of L_{1} that does not admit a bi-Lipschitz embedding into Hilbert space [Laa00] (see also [LP01, Thm. 2.3]), any uniformly convex Banach space [MN08], or even any Banach space with the Radon–Nikodým property [Ost11].

1.1. The Heisenberg group. The metric spaces {X_{n}}_{n=1}^{∞} of Theorem 1.3 arise from the discrete Heisenberg group. To explain this, recall that 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 ℍ. 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 denoted d_{W} (·, ·). For r ∈ [1, ∞) let B(r) = {x ∈ ℍ : d_{W} (x, e_{ℍ}) ⩽ r} denote the corresponding closed ball of radius r. Then |B(r)| ≍ r^{4} (see e.g. [Bla03]). It follows that there exists η_{1}, η_{2} ∈ (0, ∞) such that for every large enough n ∈ ℕ there exists X_{n} ⊆ ℍ with |X_{n}| = n and

B (η_{1}\sqrt[4]{n}) ⊆ X_{n} ⊆ B (η_{2}\sqrt[4]{n}) .  (2)

By virtue of the leftmost inclusion in (2), the distortion lower bounds that are asserted in Theorem 1.3 follow from [CKN11] for q = 1, from [ANT10] for q = 2 and from [LN12] for q ∈ (0, ∞) ∖ {2}. The remaining assertions of Theorem 1.3 follow from Theorem 1.5 below.

Theorem 1.5. For every ε ∈ (0, 1/2] and p ∈ [2, ∞) there exists a mapping F_{ε,p} : ℍ → L_{p} such that F_{ε,p}(ℍ) ⊆ L_{p} is 2^{16}-doubling and

∀ x, y ∈ ℍ, d_{W} (x, y)^{1−ε} ⩽ ∥F_{ε,p}(x) − F_{ε,p}(y)∥_{p} ≲ \frac{d_{W} (x, y)^{1−ε}}{ε^{1/p}} .

The case p = 2 of Theorem 1.5 was previously proven in [LN06] relying on Hilbertian arguments, namely on Schoenberg’s characterization [Sch38] of subsets of Hilbert space through positive definite kernels. Here we find a different approach that works also when p ∈ (2, ∞). Note that [LN06] contains a stronger statement that is used crucially in the context of [LN06] and does not follow from our proof.

Theorem 1.5 implies Theorem 1.3 because in light of the rightmost inclusion in (2), all the nonzero distances in X_{n} are between 1 and 2η_{2}\sqrt[4]{n}.

Consequently, for ε_{n} = 1/ log n we have d_{W} (x, y)^{1−ε_{n}} ≍ d_{W} (x, y) for every x, y ∈ X_{n}. We can therefore take f_{n,p} = F_{ε_{n},p} in Theorem 1.3.

Remark 1.6. The dependence on ε in Theorem 1.5 is asymptotically sharp as ε → 0. For p = 2 this was proven in [NN12] using an inequality of [ANT10]. An analogous argument works for p ∈ (2, ∞) using [LN12] instead of [ANT10]. Indeed, write c = [a, b] (recall that a, b are the generators of ℍ). By [LN12] every f : ℍ → L_{p} satisfies

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

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

Suppose that M ∈ [1, ∞) satisfies

∀ x, y ∈ ℍ,  d_{W} (x, y)^{1−ε} ⩽ ∥f(x) − f(y)∥_{p} ⩽ Md_{W} (x, y)^{1−ε}. (4)

Since d_{W} (c^{k}, e_{ℍ}) ≍ \sqrt{k} and |B(m)| ≍ m^{4} for every k, m ∈ ℕ (see e.g. [Bla03]), by substituting (4) into (3) we see that

∑_{k=1}^{n^{2}} n^{4} · \frac{k^{(1−ε)p/2}}{k^{1+p/2}} ≲_{p} M^{p}n^{4}.

Hence M^{p} ≳_{p} ∑_{k=1}^{∞} \frac{1}{k^{1+εp/2}} ≳_{p} \frac{1}{ε}, so M ≳_{p} 1/ε^{1/p}.

2. Proof of Theorem 1.5

For every n ∈ ℕ and x ∈ ℝ^{2n+1} let π(x) ∈ ℝ^{2n} denote the canonical projection of x to ℝ^{2n}, i.e,

π(x_{1}, x_{2}, …, x_{2n}, x_{2n+1}) =^{def} (x_{1}, …, x_{2n}).

For x, y ∈ ℝ^{2n} write

⟨x, y⟩ =^{def} ∑_{j=1}^{2n} x_{j}y_{j} and [x, y] =^{def} ∑_{j=1}^{n}(x_{2j−1}y_{2j} − x_{2j}y_{2j−1}).

We also write as usual ∥x∥_{2} =^{def} \sqrt{⟨x, x⟩}.

The Heisenberg group product on ℝ^{2n+1} is defined as follows. For every x, y ∈ ℝ^{2n+1} let xy ∈ ℝ^{2n+1} ≅ ℝ^{2n} × ℝ be defined as

xy =^{def} (π(x) + π(y), x_{2n+1} + y_{2n+1} − 2[π(x), π(y)]) .

Under this product ℝ^{2n+1} becomes a noncommutative group, called the nth (continuous) Heisenberg group and denoted ℍ_{n}, whose identity element is 0 ∈ ℝ^{2n+1} and the multiplicative inverse of x ∈ ℝ^{2n+1} is given by x^{−1} = −x; see e.g. [Sem03]. The Lebesgue measure on ℝ^{2n+1} is a Haar measure for ℍ_{n}.

The Korányi norm of x ∈ ℝ^{2n+1} is defined by

N(x) =^{def} (∥π(x)∥_{2}^{4} + x_{2n+1}^{2})^{1/4} .

As shown in e.g. [Cyg81], we have N(xy) ⩽ N(x) + N(y) for every x, y ∈ ℝ^{2n+1}. Consequently, if we set

∀ x, y ∈ ℝ^{2n+1}, d_{N}(x, y) =^{def} N(x^{−1}y),

then d_{N} is a left-invariant metric on ℍ_{n}. For every θ ∈ ℝ define δ_{θ} : ℝ^{2n+1} → ℝ^{2n+1} by

∀ x ∈ ℝ^{2n+1},  δ_{θ}(x) =^{def} (θπ(x), θ^{2}x_{2n+1}) .  (5)

Then d_{N}(δ_{θ}(x), δ_{θ}(y)) = |θ|d_{N}(x, y) for every x, y ∈ ℝ^{2n+1}.

Fix p ∈ [1, ∞) and ε ∈ (0, 1). Choose an integer n ∈ ℕ such that

n ⩽ p < n + 1,  (6)

and define

α =^{def} \frac{2n + 2}{p} − 1 + ε.  (7)

Note that by the choice of n we have α ∈ [1 + ε, 3 + ε) ⊆ (1, 4). For every x, z ∈ ℝ^{2n+1} ∖ {0} define T (x)(y) ∈ ℝ by

T (x)(z) =^{def} \frac{1}{N(x^{−1}z)^{α}} − \frac{1}{N(z)^{α}} .  (8)

Lemma 2.1. For every R ∈ (0, ∞) we have

(∫_{B_{N} (0,R)} \frac{dz}{N(z)^{αp}} )^{1/p} ≍ \frac{R^{1−ε}}{p(1 − ε)^{1/p}} .

Proof. This is a straightforward computation. First, since

B_{N}(0, R) ⊆ {z ∈ ℝ^{2n+1} : ∥π(z)∥_{2} ⩽ R ∧ |z_{2n+1}| ⩽ R^{2}} , (9)

by integration in polar coordinates on ℝ^{2n} we have,

(∫_{B_{N} (0,R)} \frac{dz}{N(z)^{αp}} )^{1/p}

⩽ (∫_{0}^{R} 2nv_{2n}r^{2n−1} (∫_{−R^{2}}^{R^{2}} \frac{dt}{(r^{4} + t^{2})^{αp/4}} ) dr)^{1/p}  (10)

≲ \frac{1}{p} (∫_{0}^{R} \frac{dr}{r^{αp−2n−1}} )^{1/p} ≍ \frac{R^{1−ε}}{p(1 − ε)^{1/p}} ,  (11)

where in (10) v_{2n} = π^{n}/n! denotes the volume of the Euclidean unit ball in ℝ^{2n}. The penultimate inequality of (11) uses the fact that v_{2n}^{1/p} ≍ 1/p (recall (6)). In the final step of (11) we used (7). Using the inclusion

B_{N}(0, R) ⊇ \{z ∈ ℝ^{2n+1} : ∥π(z)∥_{2} ⩽ \frac{R}{\sqrt[4]{2}} ∧ |z_{2n+1}| ⩽ \frac{R^{2}}{\sqrt{2}}\} (12)

in place of (9), the reverse inequality is proved analogously. □

Corollary 2.2. For every x ∈ ℝ^{2n+1} and K ∈ [1/3, ∞) we have

\frac{N(x)^{1−ε}}{p(1 − ε)^{1/p}} ≲ (∫_{B_{N} (0,KN(x))} |T (x)(z)|^{p}dz)^{1/p} ≲ \frac{K^{1−ε}N(x)^{1−ε}}{p(1 − ε)^{1/p}} . (13)

Proof. For the upper bound note that by the definition of T in (8),

(∫_{B_{N} (0,KN(x))} |T (x)(z)|^{p}dz)^{1/p}

⩽ (∫_{B_{N} (0,KN(x))} \frac{dz}{N(z)^{αp}} )^{1/p} + (∫_{B_{N} (0,KN(x))} \frac{dz}{N(x^{−1}z)^{αp}} )^{1/p}

= (∫_{B_{N} (0,KN(x))} \frac{dz}{N(z)^{αp}} )^{1/p} + (∫_{B_{N} (x^{−1},KN(x))} \frac{dw}{N(w)^{αp}} )^{1/p} ,

where we used the fact that the Lebesgue measure on ℝ^{2n+1} is a Haar measure of the Heisenberg group, and the left-invariance of the metric d_{N}. By the triangle inequality, B_{N}(x^{−1}, KN(x)) ⊆ B_{N}(0, 4KN(x)), so the rightmost inequality in (13) follows from Lemma 2.1.

If z ∈ B_{N}(0, N(x)/3) then N(x^{−1}z) ⩾ N(x)−N(z) ⩾ 2N(z), whence N(z)^{−α} ⩾ 2N(x^{−1}z)^{−α} (using α ⩾ 1). So |T (x)(z)| ⩾ N(z)^{−α} for every z ∈ B_{N}(0, N(x)/3). Since K ⩾ 1/3, the leftmost inequality in (13) now follows from Lemma 2.1. □

Lemma 2.3. For every x ∈ ℝ^{2n+1} we have T (x) ∈ L_{p}(ℝ^{2n+1}) and

∥T (x)∥_{L_{p}(ℝ^{2n+1})} ≲ \frac{N(x)^{1−ε}}{p} (\frac{1}{ε^{1/p}} + \frac{1}{(1 − ε)^{1/p}} ) .  (14)

Proof. If z ∈ ℝ^{2n+1} ∖ B_{N}(0, 2N(x)) then by the triangle inequality for the Korányi norm we have N(x^{−1}z) ⩽ N(x) + N(z) ⩽ 2N(z) and N(x^{−1}z) ⩾ N(z) − N(x) ⩾ N(z)/2. Consequently N(x^{−1}z) ≍ N(z) for every z ∈ ℝ^{2n+1} ∖ B_{N}(0, 2N(x)), and it therefore follows that

|T (x)(z)| ≲ \frac{|N(x^{−1}z) − N(z)|}{N(z)^{α+1}} ⩽ \frac{N(x)}{N(z)^{α+1}} .

INFINITE DIMENSIONAL DOUBLING SUBSET OF L_{p} 7

We conclude that

(∫_{ℝ^{2n+1}∖B_{N} (0,2N(x))} |T (x)(z)|^{p}dz)^{1/p}

⩽ N(x) (∫_{ℝ^{2n+1}∖B_{N} (0,2N(x))} \frac{dz}{N(z)^{(α+1)p}} )^{1/p}

⩽ N(x) (∫_{U_{x}} \frac{dz}{N(z)^{(α+1)p}} )^{1/p} + N(x) (∫_{V_{x}} \frac{dz}{N(z)^{(α+1)p}} )^{1/p} , (15)

where

U_{x} =^{def} \{z ∈ ℝ^{2n+1} ∖ B_{N} (0, 2N(x)) : ∥π(z)∥_{2} ⩾ \sqrt{|z_{2n+1}|}\}

and

V_{x} =^{def} \{z ∈ ℝ^{2n+1} ∖ B_{N} (0, 2N(x)) : ∥π(z)∥_{2} ⩽ \sqrt{|z_{2n+1}|}\} .

For z ∈ U_{x} we have ∥π(z)∥_{2} ⩽ N(z) ⩽ 2∥π(z)∥_{2}, and therefore

(∫_{U_{x}} \frac{dz}{N(z)^{(α+1)p}} )^{1/p} ⩽ (∫_{\{w∈ℝ^{2n}: ∥w∥_{2}⩾N(x)\}} \frac{2dw}{∥w∥_{2}^{(α+1)p−2}} )^{1/p}

= (∫_{N(x)}^{∞} \frac{4nv_{2n}dr}{r^{(α+1)p−2n−1}} )^{1/p} ≲ \frac{1}{p} (∫_{N(x)}^{∞} \frac{dr}{r^{1+pε}} )^{1/p} ≲ \frac{1}{pε^{1/p}N(x)^{ε}} . (16)

If z ∈ V_{x} then \sqrt{|z_{2n+1}|} ⩽ N(z) ⩽ 2\sqrt{|z_{2n+1}|}, and therefore

(∫_{V_{x}} \frac{dz}{N(z)^{(α+1)p}} )^{1/p}

⩽ (∫_{N(x)^{2}}^{∞} vol_{2n} (\{w ∈ ℝ^{2n} : ∥w∥_{2} ⩽ \sqrt{t}\}) · \frac{2dt}{t^{\frac{(α+1)p}{2}}} )^{1/p}

= (∫_{N(x)^{2}}^{∞} \frac{2v_{2n}dt}{t^{\frac{(α+1)p}{2} −n}} )^{1/p} ≲ \frac{1}{pε^{1/p}N(x)^{ε}} .  (17)

The desired estimate (14) now follows from substituting (16) and (17) into (15), and using Corollary 2.2. □ Corollary 2.4. Define S : ℝ^{2n+1} → L_{p}(ℝ^{2n+1}) by

S =^{def} p(1 − ε)^{1/p}T.  (18)

Then for every x, y ∈ ℝ^{2n+1} we have

d_{N}(x, y)^{1−ε} ≲ ∥S(x) − S(y)∥_{L_{p}(ℝ^{2n+1})} ≲ (1 + \frac{(1 − ε)^{1/p}}{ε^{1/p}} ) d_{N}(x, y)^{1−ε}.

Proof. Observe that since the Lebesgue measure is a Haar measure for the Heisenberg group,

∥S(x) − S(y)∥_{L_{p}(ℝ^{2n+1})} = p(1 − ε)^{1/p}∥T (y^{−1}x)∥_{L_{p}(ℝ^{2n+1})}.

Hence the desired upper bound on ∥S(x) − S(y)∥_{L_{p}(ℝ^{2n+1})} follows from Lemma 2.3 and the desired lower bound on ∥S(x) − S(y)∥_{L_{p}(ℝ^{2n+1})} follows from the leftmost inequality in Corollary 2.2. □

Lemma 2.5. Let S be defined as in (18) and let ϕ : ℝ^{3} → ℝ^{2n+1} be the canonical embedding of the corresponding Heisenberg groups, i.e.,

∀(a, b, c) ∈ ℝ^{3}, ϕ(a, b, c) =^{def} (a, b, \underbrace{0, …, 0}_{2n−2 times}, c) ∈ ℝ^{2n+1}.

Then S ∘ ϕ(ℝ^{3}) ⊆ L_{p}(ℝ^{2n+1}) is 2^{8/(1−ε)}-doubling.

Proof. For θ ∈ (0, ∞), recalling (5) we have

∥S(δ_{θ}(x)) − S(δ_{θ}(y))∥_{L_{p}(ℝ^{2n+1})}

= (∫_{ℝ^{2n+1}} |\frac{1}{N(δ_{θ}(x^{−1})z)^{α}} − \frac{1}{N(δ_{θ}(y^{−1})z)^{α}} |^{p} dz)^{1/p}

= (∫_{ℝ^{2n+1}} |\frac{1}{N(δ_{θ}(x^{−1}w))^{α}} − \frac{1}{N(δ_{θ}(y^{−1}w))^{α}} |^{p} θ^{2n+2}dw)^{1/p} (19)

= θ^{\frac{2n+2−αp}{p}} (∫_{ℝ^{2n+1}} |\frac{1}{N(x^{−1}w)^{α}} − \frac{1}{N(y^{−1}w)^{α}} |^{p} θ^{2n+2}dw)^{1/p} (20)
= θ^{1−ε}∥S(x) − S(y)∥_{L_{p}(ℝ^{2n+1})},  (21)

where (19) uses the change of variable z = δ_{θ}(w) (so dz = θ^{2n+2}dw), and (20) uses the fact that N(δ_{θ}(u)) = θN(u) for every u ∈ ℝ^{2n+1}. For (21), recall the definition of α in (7).

Let μ be the push-forward of the Lebesgue measure on ℝ^{3} under the mapping S ∘ ϕ, i.e.,

μ(A) =^{def} vol_{3}(ϕ^{−1}(S^{−1}(A)))

for every Borel set A ⊆ S ∘ ϕ(ℝ^{3}) ⊆ L_{p}(ℝ^{2n+1}). For f ∈ L_{p}(ℝ^{2n+1}) and r ∈ [0, ∞) let B_{p}(f, r) denote the closed ball of radius r and center f in L_{p}(ℝ^{2n+1}), i.e., B_{p}(f, s) = {g ∈ L_{p}(ℝ^{2n+1}) : ∥f − g∥_{L_{p}(ℝ^{2n+1})} ⩽ r}. By (21) for every 0 < r ⩽ R < ∞ and every f ∈ S ∘ ϕ(ℝ^{3}) we have

ϕ^{−1} ∘ S^{−1} (B_{p}(f, R)) = ϕ^{−1}(S^{−1}(f))δ_{(R/r)^{1/(1−ε)}} (ϕ^{−1} ∘ S^{−1} (B_{p}(0, r))) .

Consequently,

μ (B_{p}(f, R)) = (\frac{R}{r})^{\frac{4}{1−ε}} vol_{3} (ϕ^{−1} ∘ S^{−1} (B_{p}(0, r))) > 0.

In particular,

∀ f ∈ S ∘ ϕ(ℝ^{3}), ∀ r ∈ (0, ∞), \frac{μ (B_{p}(f, 2r))}{μ (B_{p}(f, r))} = 2^{4/(1−ε)}.

By a standard packing argument (see e.g. [CW71, page 67]), this implies that S ∘ ϕ(ℝ^{3}) is a 2^{8/(1−ε)}-doubling subset of L_{p}(ℝ^{2n+1}). □

Proof of Theorem 1.5. The discrete Heisenberg group ℍ embeds into the continuous Heisenebrg group ℍ_{1} as a co-compact discrete subgroup. Hence (see e.g. [BBI01, Thm. 8.3.19]) the metric space (ℍ, d_{W}) is bi-Lipschitz to a subset of (ℝ^{3}, d_{N}). By taking the mapping F_{ε,p} of Theorem 1.5 to be the restriction of S ∘ ϕ to ℍ, the assertions of Theorem 1.5 follow from Lemma 2.5 and Corollary 2.4 (observe that ϕ is an isometric embedding of (ℝ^{3}, d_{N}) into (ℝ^{2n+1}, d_{N})). □

3. A representation theoretic proof of Theorem 1.5

Here we present a different proof of Theorem 1.5 which uses the Schrödinger representation of the Heisenberg group ℍ_{n}. In what follows it will be notationally convenient to consider the Heisenberg group ℍ_{n} as being ℝ^{n} × ℝ^{n} × ℝ, equipped with the group product given by

(u, v, w)(u′, v′, w′) =^{def} (u + u′, v + v′, w + w′ − 2⟨u, v′⟩ + 2⟨v, u′⟩) ,

for every (u, v, w), (u′, v′, w′) ∈ ℍ_{n}. The corresponding Korànyi norm is then given by

∀(u, v, w) ∈ ℍ_{n}, N(u, v, w) = ((∥u∥_{2}^{2} + ∥v∥_{2}^{2})^{2} + w^{2})^{1/4} ,

and for θ ∈ (0, ∞) the Heisenberg dilation δ_{θ} : ℍ_{n} → ℍ_{n} is given by

∀(u, v, w) ∈ ℍ_{n}, δ_{θ}(u, v, w) = (θu, θv, θ^{2}w) .

The Schrödinger representation of ℍ_{n} corresponding to λ ∈ (0, ∞) is defined as follows. For every (u, v, w) ∈ ℍ_{n} and h : ℝ^{n} → ℂ define σ_{λ}(u, v, w)h : ℝ^{n} → ℂ by

∀ x ∈ ℝ^{n}, σ_{λ}(u, v, w)h(x) =^{def} e^{iλ(w−2⟨u,v⟩)+2i\sqrt{λ}⟨v,x⟩}h (x − 2\sqrt{λ}u) .

One checks that this defines a unitary representation of ℍ_{n} on L_{2}(ℝ^{n}), i.e., that for every h ∈ L_{2}(ℝ^{n}) we have ∥σ(x)h∥_{L_{2}(ℝ^{n})} = ∥h∥_{L_{2}(ℝ^{n})} and σ_{λ}(xy)h = σ_{λ}(x)σ_{λ}(y)h for every x, y ∈ ℍ_{n}.

Define g : ℝ^{n} → ℝ to be

g(x) =^{def} e^{− \frac{1}{2} ∥x∥_{2}^{2}},

so that ∥g∥_{L_{2}(ℝ^{n})}^{2} = ∫_{ℝ^{n}} e^{−∥x∥_{2}^{2}}dx = π^{n/2}. Then for every (u, v, w) ∈ ℍ_{n} and x ∈ ℝ^{n} we have

σ_{λ}(u, v, w)g(x) = e^{iλ(w−2⟨u,v⟩)+2i\sqrt{λ}⟨v,x⟩− \frac{1}{2} ∥x∥_{2}^{2}+2\sqrt{λ}⟨u,x⟩−2λ∥u∥_{2}^{2}}.

Consequently,

∥g − σ_{λ}(u, v, w)g∥_{L_{2}(ℝ^{n})}^{2}

= 2∥g∥_{L_{2}(ℝ^{n})}^{2} − 2ℜ (∫_{ℝ^{n}} g(x)σ_{λ}(u, v, w)g(x)dx)

= 2π^{n/2} − 2ℜ (∫_{ℝ^{n}} e^{iλ(w−2⟨u,v⟩)+2i\sqrt{λ}⟨v,x⟩−∥x∥_{2}^{2}+2\sqrt{λ}⟨u,x⟩−2λ∥u∥_{2}^{2}}dx)

= 2π^{n/2} − 2ℜ (e^{iλw−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})} ∫_{ℝ^{n}} e^{−∥x−i\sqrt{λ}v−\sqrt{λ}u∥_{2}^{2}}dx)

= 2π^{n/2} (1 − e^{−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})} cos(λw)) .  (22)

Let L_{p}((0, ∞), L_{2}(ℝ^{n})) denote as usual the space of all measurable mappings F : (0, ∞) → L_{2}(ℝ^{n}) that satisfy

∥F ∥_{L_{p}((0,∞),L_{2}(ℝ^{n}))} =^{def} (∫_{0}^{∞} ∥F (λ)∥_{L_{2}(ℝ^{n})}^{p})^{1/p} < ∞.

Note that since L_{2}(ℝ^{n}) embeds isometrically into L_{p} (see e.g. [Woj91]), also L_{p}((0, ∞), L_{2}(ℝ^{n})) embeds isometrically into L_{p}. For every measurable mapping F : (0, ∞) → L_{2}(ℝ^{n}) and every (u, v, w) ∈ ℍ_{n} define σ(u, v, w)F : (0, ∞) → L_{2}(ℝ^{n}) by

∀ λ ∈ (0, ∞), σ(u, v, w)F (λ) =^{def} σ_{λ}(u, v, w)F.

Thus σ is an action of ℍ_{n} on L_{p}((0, ∞), L_{2}(ℝ^{n})) by isometries. Next, define G : (0, ∞) → L_{2}(ℝ^{n}) by

∀ λ ∈ (0, ∞),  G(λ) =^{def} \frac{g}{\sqrt{2}π^{\frac{n}{4}} · λ^{\frac{1}{p} + \frac{1−ε}{2}}} .  (23)

Lemma 3.1. We have G − σ(u, v, w)G ∈ L_{p}((0, ∞), L_{2}(ℝ^{n})) for every (u, v, w) ∈ ℍ_{n}. Moreover,

∥G − σ(u, v, w)G∥_{L_{p}((0,∞),L_{2}(ℝ^{n}))}
= (∫_{0}^{∞} (1 − e^{−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})} cos(λw))^{p/2} \frac{dλ}{λ^{1+(1−ε)p/2}} )^{1/p}  (24)
≍ (\frac{1}{ε^{1/p}} + \frac{1}{(1 − ε)^{1/p}} ) (∥u∥_{2}^{2} + ∥v∥_{2}^{2})^{(1−ε)/2} + \frac{|w|^{(1−ε)/2}}{(1 − ε)^{1/p}} . (25)

Proof. The identity (24) is a substitution of (23) into (22). Note that

(a, b) ∈ (0, 1) × (−1, 1) ⟹ \frac{1}{3} ⩽ \frac{1 − ab}{(1 − a) + (1 − b)} ⩽ 1.  (26)

Indeed, the leftmost inequality in (26) is equivalent to the inequality (1 + b)(1 − a) + 2a(1 − b) ⩾ 0, and the rightmost inequality in (26) is equivalent to the inequality (1 − a)(1 − b) ⩾ 0. It follows from (26) that for every λ ∈ (0, ∞) we have

1 − e^{−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})} cos(λw) ≍ (1 − e^{−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})}) + (1 − cos(λw)) .

Hence,

(∫_{0}^{∞} (1 − e^{−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})} cos(λw))^{p/2} \frac{dλ}{λ^{1+(1−ε)p/2}} )^{1/p}

≍ (∫_{0}^{∞} (1 − e^{−λ(∥u∥_{2}^{2}+∥v∥_{2}^{2})})^{p/2} \frac{dλ}{λ^{1+(1−ε)p/2}} )^{1/p}

+ (∫_{0}^{∞} (1 − cos(λw))^{p/2} \frac{dλ}{λ^{1+(1−ε)p/2}} )^{1/p}

= (∥u∥_{2}^{2} + ∥v∥_{2}^{2})^{(1−ε)/2} (∫_{0}^{∞} \frac{(1 − e^{−t})^{p/2}}{t^{1+(1−ε)p/2}} dt)^{1/p}

+ |w|^{(1−ε)/2} (∫_{0}^{∞} \frac{(1 − cos t)^{p/2}}{t^{1+(1−ε)p/2}} dt)^{1/p} .  (27)

Note that

(∫_{0}^{∞} \frac{(1 − e^{−t})^{p/2}}{t^{1+(1−ε)p/2}} dt)^{1/p} ≍ (∫_{0}^{1} \frac{dt}{t^{1−εp/2}} + ∫_{1}^{∞} \frac{dt}{t^{1+(1−ε)p/2}} )^{1/p}

≍ \frac{1}{ε^{1/p}} + \frac{1}{(1 − ε)^{1/p}} ,  (28)

and

(∫_{0}^{∞} \frac{(1 − cos t)^{p/2}}{t^{1+(1−ε)p/2}} dt)^{1/p} ≍ (∫_{0}^{1} t^{(1+ε)p/2−1}dt + ∫_{1}^{∞} \frac{dt}{t^{1+(1−ε)p/2}} )^{1/p}

≍ \frac{1}{(1 − ε)^{1/p}}  (29)

By combining (27) with (28) and (29) we obtain (25). □

Second proof of Theorem 1.5. Fix an arbitrary isometric embedding J of L_{p}((0, ∞), L_{2}(ℝ^{n})) into L_{p} and define Q : H_{n} → L_{p} by

∀, x ∈ ℍ_{n}, Q(x) =^{def} (1 − ε)^{1/p}J (G − σ(x)G) .

By Lemma 3.1, for every θ ∈ (0, ∞) and every (u, v, w) ∈ ℍ_{n},

∥Q(δ_{θ}(u, v, w))∥_{p}^{p} = ∫_{0}^{∞} \frac{(1 − e^{−λ(θ^{2}∥u∥_{2}^{2}+θ^{2}∥v∥_{2}^{2})} cos(λθ^{2}w))^{p/2}}{λ^{1+(1−ε)p/2}} dλ

= θ^{(1−ε)p} ∫_{0}^{∞} \frac{(1 − e^{−s(∥u∥_{2}^{2}+∥v∥_{2}^{2})} cos(λs))^{p/2}}{s^{1+(1−ε)p/2}} ds

= θ^{(1−ε)p}∥Q(u, v, w)∥_{p}^{p}.

Since σ is an action of ℍ_{n} on L_{p}((0, ∞), L_{2}(ℝ^{n})) by isometries, for every x, y ∈ ℍ_{n} we have ∥Q(x) − Q(y)∥_{p} = ∥Q(x^{−1}y)∥_{p}, and it therefore follows that ∥Q(δ_{θ}(x)) − Q(δ_{θ}(y))∥_{p} = θ^{1−ε}∥Q(x) − Q(y)∥_{p} for every x, y ∈ ℍ_{n} and θ ∈ (0, ∞). Arguing exactly as in the proof of Lemma 2.5, it follows that Q(ℍ_{1}) ⊆ L_{p} is a 2^{8/(1−ε)}-doubling subset of L_{p}. It remains to note that by Lemma 3.1, for every x, y ∈ ℍ_{n} we have

d_{N}(x, y)^{1−ε} ≲ ∥Q(x) − Q(y)∥_{p} ≲ (1 + \frac{(1 − ε)^{1/p}}{ε^{1/p}} ) d_{N}(x, y)^{1−ε}. □

Acknowledgements. V. L. was supported by ANR grant KInd. A. N. was supported 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 a Visiting Fellow at Princeton University.

References

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

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

[BGN13] Y. Bartal, A. Gottlieb, and O. Neiman. On the impossibility of dimension reduction for doubling subsets of ℓ_{p}, p > 2, 2013. Preprint.

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

[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, [CW71] R. R. Coifman and G. Weiss. Analyse harmonique non-commutative sur

certains espaces homogènes. Lecture Notes in Mathematics, Vol. 242. Springer-Verlag, Berlin, 1971. Étude de certaines intégrales singulières.

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

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

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

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

[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, pages 99–108. 2006. Available at

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

[LN12] V. Lafforgue and A. Naor. Vertical versus horizontal Poincaré inequalities on the Heisenberg group, 2012. To appear in Israel J. Math., preprint

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

[LP01] U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285–307, 2001.

[MN08] M. Mendel and A. Naor. Markov convexity and local rigidity of distorted metrics [extended abstract]. In Computational geometry (SCG’08), pages 49–58. ACM, New York, 2008.

[NN12] A. Naor and O. Neiman. Assouad’s theorem with dimension independent of the snowflaking. Rev. Mat. Iberoam., 28(4):1123–1142, 2012.

[Ost11] M. I. Ostrovskii. On metric characterizations of some classes of Banach spaces. C. R. Acad. Bulgare Sci., 64(6):775–784, 2011.

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

[Sem03] S. Semmes. An introduction to Heisenberg groups in analysis and geometry. Notices Amer. Math. Soc., 50(6):640–646, 2003.

[Woj91] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.

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