ℓ_{p} (p > 2) Does Not Coarsely Embed Into a Hilbert Space

William B. JOHNSON and N. Lovasoa RANDRIANARIVONY ^{1}

A (not necessarily continuous) map f between two metric spaces (X, d) and (Y, δ) is called a coarse embedding (see [G, 7.G]) if there exist two nondecreasing functions φ_{1} : [0, ∞) → [0, ∞) and φ_{2} : [0, ∞) → [0, ∞) such that

1. φ_{1}(d(x, y)) ≤ δ(f(x), f(y)) ≤ φ_{2}(d(x, y))

2. φ_{1}(t) → ∞ as t → ∞.

Nowak [N], improving a theorem due to A. N. Dranishnikov, G. Gong, V. Lafforgue, and G. Yu [DGLY], gave a characterization of coarse embeddability of general metric spaces into a Hilbert space using a result of Schoenberg on negative definite kernels. He used this characterization to show that the spaces L_{p}(μ) coarsely embed into a Hilbert space for p < 2. In this article, we show that ℓ_{p} does not coarsely embed into a Hilbert space when p > 2. It was already proved in [DGLY] that the Lipschitz universal space c_{0} (see [A]) does not coarsely embed into a Hilbert space.

In its full generality, the statement of our result is as follows:

Theorem 1 Suppose that a Banach space X has a normalized symmetric

basis (e_{n})_{n} and that lim inf_{n→∞} n^{− \frac{1}{2}} ∥ ∑_{i=1}^{n} e_{i}∥ = 0. Then X does not coarsely

embed into a Hilbert space.

In [Y] Yu proved that a discrete metric space with bounded geometry must satisfy the coarse geometric Novikov conjecture if it coarsely embeds into a Hilbert space, and in [KY] G. Kasparov and Yu proved that to get the same conclusion it is sufficient that the metric space coarsely embeds into a uniformly convex Banach space. Our theorem suggests that the result of [KY] cannot be deduced from the earlier theorem in [Y], but as yet there is no example of a discrete metric space with bounded geometry which coarsely embeds into ℓ_{p} for some 2 < p < ∞ but not into ℓ_{2}. (The reader should be warned that what we called a “coarse embedding” is called a “uniform embedding” is many places, including [DGLY], [KY], and [Y]. Following [N], we use the term coarse embedding to avoid confusion with the closely related notion of uniform embedding as it is used in non linear Banach space theory [BL]; i.e., a bi-uniformly continuous mapping.)

1Both authors were supported in part by NSF 0200690 and Texas Advanced Research Program 010366-0033-20013.

This paper represents a portion of the second authors’s dissertation being prepared at Texas A&M University under the direction of the first author.

Besides Schoenberg’s classical work [S] on positive definite functions, an important tool for proving the theorem is Theorem 5.2 in [AMM], which asserts that the hypothesis on X in the theorem implies that every symmetric continuous positive definite function on X is constant. We present the proof in five steps.

STEP 0: REDUCING TO THE α-HÖLDER CASE

Let f : X → H be a coarse embedding satisfying

1. φ_{1}(∥x − y∥) ≤ ∥f(x) − f(y)∥ ≤ φ_{2}(∥x − y∥)

2. φ_{1}(t) → ∞ as t → ∞.

Our first claim is that we do not lose generality by assuming that φ_{2}(t) = t^{α} with 0 < α < \frac{1}{2}.

To prove this claim, note first that (x, y) ↦ ∥f(x) − f(y)∥^{2} is a negative definite kernel on X. This can be seen by direct computations (see [N, Proposition 3.1]). We refer the reader to [BL, Chapter 8] or [N, Section 2] for the definitions of negative definite kernels and negative definite functions.

So, ([N, Lemma 4.2]) for any 0 < α < 1, the kernel N(x, y) = ∥f(x) − f(y)∥^{2α} is also negative definite and satisfies N(x, x) = 0 (such a negative definite kernel is called normalized).

As a result, a theorem of Schoenberg ([S] and [BL, Chapter 8]) allows us to find a Hilbert space H_{α} and a function f_{α} : X → H_{α} such that N(x, y) = ∥f_{α}(x) − f_{α}(y)∥^{2}.

On the other hand, since X, being a normed space, is (metrically) convex, the original function f : X → H is Lipschitz for large distances (see e.g. [BL, proof of Proposition 1.11]). Consequently, without loss of generality, we can assume by rescaling that we have the following for ∥x − y∥ ≥ 1:

∥f(x) − f(y)∥_{H} ≤ ∥x − y∥

and

(φ_{1}(∥x − y∥))^{α} ≤ ∥f_{α}(x) − f_{α}(y)∥_{Hα} ≤ ∥x − y∥^{α}

Now, let N be a 1-net in X (i.e. N is a maximal 1-separated subset of X). The restriction of f_{α} to N is α-Hölder, so if 0 < α < \frac{1}{2}, then we can extend f_{α} to an α-Hölder map f̃_{α} defined on the whole of X (see [WW], last statement of Theorem 19.1):

f̃_{α} : X → H_{α}
∀x ∈ N , f̃_{α}(x) = f_{α}(x)

and

∀x, y ∈ X, ∥f_{α}(x) − f_{α}(y)∥_{Hα} ≤ ∥x − y∥^{α}.

Now, write φ̃_{1}(t) = inf{∥f̃_{α}(x) − f̃_{α}(y)∥, ∥x − y∥ ≥ t}, and observe that φ̃_{1}(t) → ∞ as t → ∞.

This finishes the proof of our reduction to the case where f is α-Hölder and thus uniformly continuous. So from now on we will assume that our coarse embedding is a map f : X → H satisfying the following for all x, y ∈ X:

φ_{1}(∥x − y∥) ≤ ∥f(x) − f(y)∥ ≤ ∥x − y∥^{α}

where φ_{1}(t) → ∞ as t → ∞.

STEP 1

Set N(x, y) = ∥f(x) − f(y)∥^{2}. Then N is a normalized (i.e. N(x, x) = 0) negative definite kernel on X, (see [N, Proposition 3.1]). Now if we write ϕ_{1}(t) = (φ_{1}(t))^{2} and ϕ_{2}(t) = t^{2α}, then N satisfies:

\begin{cases}ϕ_{1}(∥x − y∥) ≤ N(x, y) ≤ ϕ_{2}(∥x − y∥), \\ ϕ_{1}(t) → ∞ as t → ∞. \end{cases}

STEP 2

The argument in this paragraph comes from [AMM, Lemma 3.5.]. Let μ be an invariant mean on the bounded functions on X (see e.g. [BL]

for the definition of invariant means). Define:

g(x) = ∫_{X} N(y + x, y) dμ(y)

Then we have the following for g:

• g is well-defined because the map y ↦ N(y + x, y) is bounded for each x ∈ X

• g(0) = ∫_{X} N(y, y) dμ(y) = 0

• For scalars (c_{i})_{1≤i≤n} satisfying ∑_{i=1}^{n} c_{i} = 0, we have:

∑_{i,j=1}^{n} c_{i}c_{j}g(x_{i} − x_{j}) = ∑_{i,j} c_{i}c_{j} ∫_{X} N(y + x_{i} − x_{j}, y) dμ(y)

= ∑_{i,j=1}^{n} c_{i}c_{j} ∫_{X} N(y + x_{i}, y + x_{j}) dμ(y)

= ∫_{X} (∑_{i,j=1}^{n} c_{i}c_{j}N(y + x_{i}, y + x_{j})) dμ(y)

= ∫_{X}(≤ 0) dμ(y)

≤ 0

This is because μ is translation invariant, and N is negative definite. This shows that g is a negative definite function on X.

• Finally, since ∫_{X} dμ(y) = 1, we have:

ϕ_{1}(∥x∥) ≤ g(x) ≤ ϕ_{2}(∥x∥).

In summary, we have found a negative definite function g on X which satisfies g(0) = 0 and ϕ_{1}(∥x∥) ≤ g(x) ≤ ϕ_{2}(∥x∥), where ϕ_{1}(t) → ∞ as t → ∞.

STEP 3

Let (e_{n})_{n} be the normalized symmetric basis for X. This means that for any choice of signs (θ_{n})_{n} ∈ {−1, +1} and any choice of permutation σ : ℕ → ℕ,

∥ ∑_{n} θ_{n}a_{n}e_{σ(n)}∥_{X} = ∥ ∑_{n} a_{n}e_{n}∥_{X}.

The purpose of this paragraph is to show that the negative definite function g we found in the previous paragraph can be chosen to be symmetric, i.e. to satisfy for any choice of signs (θ_{n})_{n} ∈ {−1, +1} and any choice of permutation σ : ℕ → ℕ the equality:

g (∑_{n} θ_{n}a_{n}e_{σ(n)}) = g (∑_{n} a_{n}e_{n}) .

For x = ∑_{n=1}^{∞} x_{n}e_{n} ∈ X, define g_{m}(x) to be the average of g (∑_{n=1}^{∞} θ_{n}x_{n}e_{σ(n)})

over all choices of signs θ and permutations σ with the restrictions that θ_{n} = 1 for n > m and σ(n) = n for n > m.

It follows that for all such θ, σ, and for all x = ∑_{n=1}^{∞} x_{n}e_{n} ∈ X,

g_{m} (∑_{n=1}^{∞} θ_{n}x_{n}e_{σ(n)}) = g_{m} (∑_{n=1}^{∞} x_{n}e_{n}) .

Moreover, we also have

ϕ_{1}(∥x∥) ≤ g_{m}(x) ≤ ϕ_{2}(∥x∥).

Next we show that the sequence (g_{m})_{m} is equicontinuous. To check this, let us first check the continuity of g:

∥g(a) − g(b)∥ ≤ ∫_{X} |N(y + a, y) − N(y + b, y)| dμ(y)

= ∫_{X} |∥f(y + a) − f(y)∥^{2} − ∥f(y + b) − f(y)∥^{2}| dμ(y)

= ∫_{X} (∥f(y + a) − f(y)∥ + ∥f(y + b) − f(y)∥) · |∥f(y + a) − f(y)∥ − ∥f(y + b) − f(y)∥| dμ(y)

≤ ∫_{X} (∥f(y + a) − f(y)∥ + ∥f(y + b) − f(y)∥) · ∥f(y + a) − f(y + b)∥ dμ(y)

≤ ∫_{X} (∥a∥^{α} + ∥b∥^{α}) ∥a − b∥^{α} dμ(y).

So ∥g(a) − g(b)∥ ≤ ∥a − b∥^{α} (∥a∥^{α} + ∥b∥^{α}) and g is continuous. Now for the equicontinuity of (g_{m})_{m}:

∥g_{m}(a) − g_{m}(b)∥ = ∥ave (g (∑ θ_{n}a_{n}e_{σ(n)}) − g (∑ θ_{n}b_{n}e_{σ(n)})) ∥

≤ ave ∥g (∑ θ_{n}a_{n}e_{σ(n)}) − g (∑ θ_{n}b_{n}e_{σ(n)}) ∥

≤ ave (∥ ∑ θ_{n}a_{n}e_{σ(n)} − ∑ θ_{n}b_{n}e_{σ(n)}∥^{α}
· (∥ ∑ θ_{n}a_{n}e_{σ(n)}∥^{α} + ∥ ∑ θ_{n}b_{n}e_{σ(n)}∥^{α}))

= ave (∥a − b∥^{α} (∥a∥^{α} + ∥b∥^{α}))
= ∥a − b∥^{α} (∥a∥^{α} + ∥b∥^{α}) .

So by Ascoli’s theorem, there is a subsequence (g_{m_{k}})_{k} of (g_{m})_{m} which converges pointwise to a continuous function g̃. The property of the g_{m}’s implies that g̃ must necessarily be symmetric. We have that g̃(0) = 0, and that ϕ_{1}(∥x∥) ≤ g̃(x) ≤ ϕ_{2}(∥x∥). Finally, as it is easily checked that the g_{m}’s are negative definite functions, it also follows easily that g̃ is a negative definite function.

STEP 4

There is a relation between negative and positive definite kernels as given by a result of Schoenberg [S]; see also [BL, Chapter 8]. This result states that a kernel N on X is negative definite if and only if e^{−tN} is positive definite for every t > 0.

Since lim inf_{n→∞} \frac{∥e_{1} + e_{2} + ⋯ + e_{n}∥}{\sqrt{n}} = 0, and f̃ = e^{−g̃} is a symmetric contin-

uous positive definite function on X, we conclude by a theorem of Aharoni, Maurey and Mityagin (see [AMM, Theorem 5.2]), that f̃ is constant.

On the other hand, f̃(0) = e^{−g̃(0)} = 1, while 0 ≤ f̃(x) ≤ e^{−ϕ_{1}(∥x∥)} → 0 as ∥x∥ → ∞. This gives a contradiction and finishes the proof.

References

[A] I. Aharoni, Every separable metric space is Lipschitz equivalent to a subset of c_{0}, Israel J. Math. 19 (1974), 284-291.

[AMM] 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) (1985), 251–265.

[BL] Y. Benyamini and J. Lindenstrauss, Geometric Nonlinear Functional Analysis, Coll. Pub. 48, Amer. Math. Soc., Providence, RI (2000).

[DGLY] A. N. Dranishnikov, G. Gong, V. Lafforgue, and G. Yu, Uniform embeddings into Hilbert spaces and a question of Gromov, Canad. Math. Bull. 45(1) (2002), 60–70.

[G] M. Gromov, Asymptotic invariants for infinite groups, Geometric Group Theory, G. A. Nibto and M. A. Roller, ed., Cambridge University Press (1993), 1–295.

[KY] G. Kasparov and G. Yu, The coarse geometric Novikov conjecture and uniform convexity, (preprint).

[N] P. Nowak, Coarse embeddings of metric spaces into Banach spaces, (preprint).

[S] I. J. Schoenberg, Metric spaces and positive definite functions, Trans. Am. Math. Soc. 44 (1938), 522–536.

[WW] J. H. Wells, L. R. Williams, Embeddings and extensions in Analysis, Springer-Verlag (1975).

[Y] G. Yu, The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space, Invent. Math. 139 (2000), no. 1, 201–240.

William B. Johnson Department Mathematics Texas A&M University College Station, TX, USA E-mail: johnson@math.tamu.edu

N. Lovasoa Randrianarivony Department Mathematics Texas A&M University College Station, TX, USA E-mail: nirina@math.tamu.edu