Nonembeddability theorems via Fourier analysis

Subhash Khot Georgia Institute of Technology

                khot@cc.gatech.edu

Assaf Naor Microsoft Research

                                            anaor@microsoft.com

Abstract Various new nonembeddability results (mainly into L_{1}) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on \{0, 1\}^{d} has L_{1} distortion Ω(\sqrt{log d/ log log d}). We also give new lower bounds on the L_{1} distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

1 Introduction

The bi-Lipschitz theory of metric spaces has witnessed a surge of activity in the past four decades. While the original motivation for this type of investigation came from metric geometry and Banach space theory, since the mid-1990s it has become increasingly clear that understanding metric spaces in the bi-Lipschitz category is intimately related to fundamental algorithmic questions arising in theoretical computer science. Despite the remarkable list of achievements of this field, which includes the best known approximation algorithms for a a wide range of NP hard problems, the bi-Lipschitz theory is still in its infancy. In particular, there are very few known methods for proving nonembeddability results. The purpose of this paper is to the develop a Fourier-analytic approach to proving nonembeddability theorems. In doing so, we resolve several problems, and shed new light on existing results. Additionally, our work points toward several interesting directions for future research, with emphasis on the study of the bi-Lipschitz structure of quotients of metric spaces.

Let (X, d_{X}) and (Y, d_{Y}) be metric spaces. The Lipschitz constant of a function f : X → Y is

∥f∥_{Lip} := sup_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} \frac{d_{Y} (f(x), f(y))}{d_{X}(x, y)}.

If f is one-to-one then its distortion is defined as

dist(f) := ∥f∥_{Lip} · ∥f^{−1}∥_{Lip}.

If f is not one-to-one then we set dist(f) = ∞. The least distortion with which X can be embedded into Y is denoted c_{Y} (X), namely

c_{Y} (X) := inf{dist(f) : f : X ↪ Y }.

We are particularly interested in embeddings into L_{p} spaces. In this case we write c_{p}(X) = c_{L_{p}}(X). The most studied type of embeddings are into Hilbert space, in which case the parameter c_{2}(X) is known as the Euclidean distortion of X. The parameter c_{1}(X), i.e. the least distortion required to embed X into L_{1}, is of great algorithmic significance, especially in the study of cut problems in graphs. The Euclidean distortion of a metric space X is relatively well understood: it is enough to understand the distortion of finite subsets of X, and for finite metrics there is a simple semidefinite program which computes their Euclidean distortion [37]. Embeddings into L_{1} are much more mysterious (see [36]), and there are very few known methods to bound c_{1}(X) from below.

The present paper contains several new nonembeddability results, which we now describe. The common theme is that our proofs are based on analytic methods, most notably Fourier analysis on {0, 1}^{d} and ℝ^{n}. We stress that this is not the first time that nonembeddability results have drawn on techniques from harmonic analysis. Indeed, the proofs of results in [14, 54, 50, 32, 43] all have a Fourier analytic component.

Our results.

1) Quotients of the discrete hypercube and transportation cost. A classical theorem of Banach states that every separable Banach space is a quotient of ℓ_{1}. More precisely, for every separable Banach space X, there is a linear subspace Y ⊆ ℓ_{1} such that ℓ_{1}/Y is linearly isometric to X. This suggests that interesting “bad examples” of metric spaces can be obtained as metric quotients of the Hamming cube. Roughly speaking, this says that we can obtain interesting metrics (i.e. metrics that do not embed into nice spaces, say L_{1}) by identifying points of the hypercube. Quotients of metric spaces are a well studied concept (see [25, 15] for an introduction, and [42] for a discussion of quotients of finite metric spaces)- we refer the reader to Section 3 for a precise definition of this notion.

Motivated by this analogy, in Section 3 we exhibit classes of quotients of the Hamming cube which do not embed into L_{1}. A fundamental theorem of Bourgain [10] states that for every finite metric space X, c_{1}(X) ≤ c_{2}(X) = O(log |X|). In [10] Bourgain used a counting argument to show that there exist arbitrarily large metric spaces X with c_{2}(X) = Ω(log |X|/ log log |X|). In [37, 3] it was shown that there exit arbitrarily large metric spaces X with c_{1}(X) = Ω(log |X|) (namely X can be taken to be a constant degree expander). In Section 3 we show that there exist simple n-point quotients of the Hamming cube {0, 1}^{d} which incur distortion Ω(log n) in any L_{1} embedding. This can be viewed a non-linear quantitative analog of Banach’s theorem stated above. We also show that certain quotients of the Hamming cube obtained from the action of a transitive permutation group of the coordinates do not well-embed into L_{1}. These results are proved via a flexible Fourier analytic approach.

As an application of the results stated above we settle the problem of the L_{1} embeddability of the transportation cost metric (also known as the Earthmover metric in the computer vision/graphics literature) on the set of all probability measures on {0, 1}^{d}. Denoting by P({0, 1}^{d}) the space of all probability measures on the Hamming cube {0, 1}^{d}, let T_{ρ}(σ, τ) denote the transportation cost distance between σ, τ ∈ P({0, 1}^{d}), with respect to the cost function induced by the Hamming metric ρ (see Section 3.2 for the definition). Such metrics occur in various contexts in computer science: they are a popular distance measure in graphics and vision [27, 30], and they are used as LP relaxations for classification problems such as 0-extension and metric labelling [20, 18, 2]. Transportation cost metrics are also prevalent in several areas of analysis and PDEs (see the book [58] and the references therein).

Motivated by applications to nearest neighbor search (a.k.a. similarity search in the vision literature), the problem of embedding transportation cost metrics into L_{1} attracted a lot of attention in recent years (see [18, 30, 41]). In [18, 30] it is shown that c_{1}(P({0, 1}^{d}), T_{ρ}) = O(d). In Section 3.2 we show that this bound is optimal, i.e. c_{1}(P({0, 1}^{d}), T_{ρ}) = Ω(d). From an analytic perspective, Kantorovich duality (see [58]) implies that (P({0, 1}^{d}), T_{ρ}) embeds isometrically into Lip({0, 1}^{d})^{∗}- the dual of the Banach space of all real valued Lipschitz functions on the hypercube. A result of Bourgain [11] implies that sup_{d∈ℕ} c_{1}(Lip({0, 1}^{d})^{∗}) = ∞. Our result shows that in fact c_{1}(Lip({0, 1}^{d})^{∗}) = Ω(d), improving upon the lower bound obtained in [11].

2) Edit Distance does not embed into L_{1}. Edit Distance (also known as Levenstein distance [35]) is a metric defined on the set of all finite-length binary strings, which we denote {0, 1}^{∗}. This metric is best viewed as the shortest path metric on the following infinite graph : Let G be a graph with set of vertices {0, 1}^{∗}, and {x, y} is an edge of the graph if the string y can be obtained from string x by either deleting one character from x or by inserting one character into x. For strings x, y, denote the shortest path distance in G (i.e. the Edit Distance) between x, y as ED(x, y). In words, ED(x, y) is the minimum number of edit operations needed to transform x into y. Here we assume that only insertion/deletion operations are allowed. Character substitution can be simulated by a deletion followed by an insertion. Similarly, one can shift a string by deleting its first character and inserting it at the end.

Edit Distance is a very useful metric arising in several applications, most notably in string and text comparison problems, which are prevalent in computer science (e.g. compression and pattern matching), computational biology, and web searching (see the papers [47, 21, 1, 29, 5, 52, 17] and the references therein, and the book [28] for a discussion of applications to computational biology).

Let ({0, 1}^{d}, ED) denote the space {0, 1}^{d} with the Edit Distance metric (inherited from the metric ED on {0, 1}^{∗}). A well known problem, stated e.g. in [41], is whether the space ({0, 1}^{d}, ED) embeds into L_{1} with uniformly bounded distortion. Had this been true, it would have had significant applications in computer science (see [41]). Most notably it would lead to approximate nearest neighbor search algorithms under Edit Distance, and to efficient algorithms for computing the Edit Distance between two strings (both of these problems are being solved, by computational biologists, every day, hundreds of times. Getting a substantially faster algorithm for any of them would be of great practical importance). In Section 4 we show that the L_{1} embedding approach fails, by proving via Fourier analytic methods that

c_{1}(\{0, 1\}^{d}, ED) = Ω (\sqrt{\frac{log d}{log log d}}) .  (1)

The previous best known lower bound is due to [1], where it is shown that c_{1}({0, 1}^{d}, ED) ≥ 3/2.

The best known upper bound on c_{1}({0, 1}^{d}, ED) is due to [52], where it is proved that

c_{1}(\{0, 1\}^{d}, ED) ≤ 2^{O(\sqrt{log d log log d})}.

3) Flat tori can be highly non-Euclidean. The Nash embedding theorem [51] states that any n-dimensional Riemannian manifold is isometric to a Riemannian sub-manifold of ℝ^{2n}. In the bi-Lipschitz category this is no longer the case- it is easy to construct Riemannian manifolds (indeed, even Riemannian surfaces) which do not embed bi-Lipschitzly even into infinite dimensional Hilbert space. However, all the known constructions were highly curved, and the possibility remained that any manifold with zero curvature embeds bi-Lipschitzly into L_{2}, with a uniform bound on the distortion. In Section 5 we show that this isn’t the case: there is an n-dimensional flat torus, i.e. ℝ^{n}/Λ for some lattice Λ ⊆ ℝ^{n}, equipped with the natural Riemannian metric (whose sectional curvature is identically 0), such that c_{1}(ℝ^{n}/Λ) = Ω(\sqrt{n}). This result answers the question, posed by W. B. Johnson, whether a Lipschitz quotient (in the sense of [7]) of Hilbert space embeds bi-Lipschitzly into Hilbert space. In [7] it is shown that a Banach space which is a Lipschitz quotient of a Hilbert space is isomorphic to a Hilbert space. Johnson’s question is whether the condition that the quotient is a Banach space is necessary. Since the natural quotient map π : ℝ^{n} → ℝ^{n}/Λ is a Lipschitz quotient (see Section 3), the above example shows that Lipschitz quotients of Hilbert space need not embed into Hilbert space (indeed, they may not embed even into L_{1}). Our approach is a variant of our study of quotient metrics in Section 3, and the proof is based on Fourier analysis over ℝ^{n}, instead of discrete Fourier analysis over {0, 1}^{n}.

This paper is organized as follows. In Section 2 we present some background and preliminary results on Fourier analysis on the Hamming cube. In section 3 we investigate quotients of the hypercube under group actions. In Section 4 we prove our lower bound on the L_{1} distortion of Edit Distance, and in Section 5 we discuss the L_{1} and L_{2} embeddability of flat tori. We end with Section 6, which contains a brief discussion which relates the notion of length of metric spaces (first introduced by Schechtman [56] in the context of the concentration of measure phenomenon) to nonembeddability results. This gives, in particular, new lower bounds on the Euclidean distortion of various groups equipped with a group invariant metric.

2 Preliminaries on Fourier analysis on the hypercube

We start by introducing some notation concerning Fourier analysis on the group 𝔽_{2}^{d} = {0, 1}^{d}. For ε ∈ (0, 1) we denote by μ_{ε} the product ε-biased measure on 𝔽_{2}^{d}, i.e. the measure given by

∀ x ∈ 𝔽_{2}^{d}, μ_{ε}({x}) = ε^{∑_{j=1}^{d} x_{j}}(1 − ε)^{d−∑_{j=1}^{d} x_{j}}.

For the sake of simplicity we write μ = μ_{1/2}. Given A ⊆ {1, …, d} we define the Walsh function W_{A} : 𝔽_{2}^{d} → ℝ by

W_{A}(x) = (−1)^{∑_{j∈A} x_{j}}.

Then {W_{A} : A ⊆ {1, …, d}} is an orthonormal basis of L_{2}(𝔽_{2}^{d}, μ). In particular any f : 𝔽_{2}^{d} → L_{2} has a unique Fourier expansion

f = ∑_{A⊆{1,...,d}} f̂(A)W_{A},

where

f̂(A) = ∫_{𝔽_{2}^{d}} f(x)W_{A}(x)dμ(x) ∈ L_{2},

and Parseval’s identity reads as

∫_{𝔽_{2}^{d}} ∥f(x)∥_{2}^{2}dμ(x) = ∑_{A⊆{1,...,d}} ∥f̂(A)∥_{2}^{2}.

Let e_{j} ∈ 𝔽_{2}^{d} be the vector whose only non-zero coordinate is the jth coordinate. We also write e := e_{1} + … + e_{d} for the all 1s vector. The partial differentiation operator on L_{2}(𝔽_{2}^{d}) is defined by

∂_{j}f(x) := \frac{f(x + e_{j}) − f(x)}{2}.

Since for every A ⊆ {1, …, d} we have that

∂_{j}W_{A} = \{ \begin{matrix}−W_{A} & j ∈ A \\ 0 & j ∉ A, \end{matrix}

we see that for every f : 𝔽_{2}^{d} → ℝ

∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∂_{j}f(x)^{2}dμ(x) = ∑_{A⊆{1,...,d}} |A|f̂(A)^{2}.  (2)

In what follows we denote by ρ the Hamming metric on 𝔽_{2}^{d}, namely for x, y ∈ 𝔽_{2}^{d},

ρ(x, y) := |{j ∈ {1, …, d} : x_{j} ≠ y_{j}}|.

Observe that for every f : 𝔽_{2}^{d} → ℝ,

∫_{𝔽_{2}^{d}} |f(x) − f(x + e)|^{2}dμ(x) = ∑_{\begin{matrix}A⊆\{1,...,d\} \\ |A|≡1 mod 2 \end{matrix}} 4f̂(A)^{2} ≤ 4 ∑_{A⊆\{1,...,d\}} |A|f̂(A)^{2} = 4 ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}}[∂_{j}f(x)]^{2}dμ(x).

This famous inequality, first proved by Enflo in [23] via a geometric argument, implies that c_{2}(𝔽_{2}^{d}) ≥ \sqrt{d}. Indeed, by integration we see that for every f : 𝔽_{2}^{d} → L_{2},

∫_{𝔽_{2}^{d}} ∥f(x) − f(x + e)∥_{2}^{2}dμ(x) ≤ 4 ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∥∂_{j}f(x)∥_{2}^{2}dμ(x).

Thus, assuming that f is invertible we see that

\frac{d^{2}}{∥f^{−1}∥_{Lip}^{2}} ≤ 4d · (\frac{∥f∥_{Lip}}{2} )^{2} ,

i.e.

∥f∥_{Lip} · ∥f^{−1}∥_{Lip} ≥ \sqrt{d}.

This Fourier-analytic approach to Enflo’s theorem motivates the ensuing arguments in this paper, since it turns out to be remarkably flexible. For future reference we record here the basic Poincaré inequality implied by the above reasoning:

Lemma 2.1. For every f : 𝔽_{2}^{d} → L_{2},

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f(x) − f(y)∥_{2}^{2}dμ(x)dμ(y) ≤ \frac{2}{min\{|A| : A ≠ ∅, f̂(A) ≠ 0\}} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∥∂_{j}f(x)∥_{2}^{2}dμ(x).

Proof. We simply observe that

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f(x) − f(y)∥_{2}^{2}dμ(x)dμ(y) = 2 ∫_{𝔽_{2}^{d}} ∥f(x) − f̂(∅)∥^{2}dμ(x) = 2 ∑_{∅≠A⊆{1,...,d}} ∥f̂(A)∥_{2}^{2},

and the required inequality follows from (2).

3 Quotients of the hypercube

Let (X, d_{X}) be a metric space. For A, B ⊆ X the Hausdorff distance between A, B is defined as

H_{X}(A, B) = sup {max{d_{X}(a, B), d_{X}(b, A)} : a ∈ A, b ∈ B} .  (3)

Following [25, 15, 42], given a partition U = {U_{1}, …, U_{k}} of X, we define the quotient metric induced by X on U, denoted X/U, as follows: assign to each i, j ∈ {1, …, k} the weight w_{ij} = d_{X}(U_{i}, U_{j}) = min_{x∈U_{i}, y∈U_{j}} d_{X}(x, y), and let d_{X/U}(U_{i}, U_{j}) be the shortest path distance between i and j in the weighted complete graph on {1, …, k} in which the edge {i, j} has weight w_{ij}.

In the following lemma the right-hand inequality is an immediate consequence of (3), and the left-hand inequality follows from the fact that the Hausdorff distance is a metric on subsets of X.

Lemma 3.1. Assume that U = {U_{1}, …, U_{k}} is a partition of a metric space X such that for every i, j ∈ {1, …, k}, for every x ∈ U_{i} there exists y ∈ U_{j} such that d_{X}(x, y) = d_{X}(U_{i}, U_{j}). Then for every i, j ∈ {1, …, k},

d_{X/U}(U_{i}, U_{j}) = H_{X}(U_{i}, U_{j}) = d_{X}(U_{i}, U_{j}).

A particular case of interest is when a group G acts on X by isometries. In this case the orbit partition induced by G on X clearly satisfies the conditions of Lemma 3.1, implying that for all x, y ∈ X,

d_{X/G}(Gx, Gy) = d_{X}(Gx, Gy),

where we slightly abuse notation by letting X/G be the quotient of X induced by the orbits of G. This is the only type of quotients that we study in this paper. In particular, Lemma 3.1 implies that the quotients we study here are also Lipschitz quotients in the sense of [7] (see Section 6 in [42] for an explanation).

We will require the following lower bound on the average distance in quotients of the hypercube.

Lemma 3.2. Let G be a group of isometries acting on 𝔽_{2}^{d} with 2 < |G| < 2^{d}. Then

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ρ_{𝔽_{2}^{d}/G}(Gx, Gy)dμ(x)dμ(y) = Ω (\frac{log_{2} |G|}{log_{2} (\frac{d}{d−log_{2} |G|})}) .

Proof. For every t > 0,

μ × μ\{x, y ∈ 𝔽_{2}^{d} : ρ(Gx, Gy) ≥ t\} ≥ 1 − ∑_{g∈G} μ × μ\{x, y ∈ 𝔽_{2}^{d} : ρ(x, gy) ≤ t\} = 1 − \frac{|G|}{2^{d}} · ∑_{k≤t} \binom{d}{k}.

We shall use the following (rough) bounds, which are a simple consequence of Stirling’s formula: For every 1/n ≤ δ ≤ 1/2,

\frac{[δ^{δ}(1 − δ)^{1−δ}]^{−d}}{6\sqrt{δd}} ≤ ∑_{k≤δd} \binom{d}{k} ≤ 2\sqrt{δd} · [δ^{δ}(1 − δ)^{1−δ}]^{−d}.  (4)

Thus, using Lemma 3.1 we get that

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} [ρ_{𝔽_{2}^{d}/G}(Gx, Gy)]^{2}dμ(x)dμ(y) ≥ δd (1 − \frac{|G|}{2^{d}}2\sqrt{δd} · [δ^{δ}(1 − δ)^{1−δ}]^{−d})

Choosing δ = Θ (_{\frac{log_{2} |G|}{d log_{2}( \frac{d}{d−log_{2} |G|} )}}) yields the required result.

3.1 A simple construction of n-point spaces with c_{1} = Ω(log n)

In what follows we refer to [38, 9] for the necessary background on coding theory. Let C ⊆ {0, 1}^{d} be a code, i.e. a linear subspace of 𝔽_{2}^{d}. Denote by w(C) the minimum Hamming weight of nonzero elements of C, i.e.

w(C) = min_{x∈C\{0}} ∥x∥_{1}.

We also use the standard notation

C^{⊥} := {x ∈ 𝔽_{2}^{d} : ∀ y ∈ C, ⟨x, y⟩ ≡ 0 mod 2} ,

where ⟨x, y⟩ := ∑_{j=1}^{n} x_{j}y_{j}.

Lemma 3.3. Assume that f : 𝔽_{2}^{d} → L_{2} satisfies for every x ∈ 𝔽_{2}^{d} and y ∈ C^{⊥}, f(x + y) = f(x). Then for every nonempty A ⊆ {1, …, d} with |A| < w(C), f̂(A) = 0.

Proof. Since (C^{⊥})^{⊥} = C (see [9]), 1_{A} ∉ (C^{⊥})^{⊥}, implying that there exists v ∈ C^{⊥} such that ⟨1_{A}, v⟩ ≡ 1 mod 2. Now,

f̂(A) = ∫_{𝔽_{2}^{n}} f(x)W_{A}(x)dμ(x)
= ∫_{𝔽_{2}^{n}} f(x + v)W_{A}(x)dμ(x)
= ∫_{𝔽_{2}^{n}} f(x)W_{A}(x − v)dμ(x)
= (−1)^{⟨1_{A},v⟩} ∫_{𝔽_{2}^{n}} f(x)W_{A}(x)dμ(x)
= −f̂(A).

So f̂(A) = 0. Theorem 3.4. Let C ⊆ 𝔽_{2}^{d} be a code. Then

c_{1}(𝔽_{2}^{d}/C^{⊥}) = Ω (w(C) · \frac{1 − \frac{dim(C)}{d}}{log (\frac{d}{dim(C)})}) .

Proof. Let f : 𝔽_{2}^{d}/C^{⊥} → L_{1} be a bijection. Define f̃: 𝔽_{2}^{d} → L_{1} by f̃(x) = f(x + C^{⊥}). It is well known [22] that there exists a mapping T : L_{1} → L_{2} such that for all x, y ∈ L_{1},

∥T (x) − T (y)∥_{2} = \sqrt{∥x − y∥_{1}}.

Define h : 𝔽_{2}^{d} → L_{2} by h = T ∘ f̃. By Lemma 3.3 and Lemma 2.1 we get that

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f̃(x) − f̃(y)∥_{1}dμ(x)dμ(y) = ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥h(x) − h(y)∥_{2}^{2}dμ(x)dμ(y)
≤ \frac{2}{w(C)} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∥∂_{j}h(x)∥_{2}^{2}dμ(x)
= \frac{2}{w(C)} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∥∂_{j}f̃(x)∥_{1}dμ(x)
≤ \frac{d}{w(C)}∥f∥_{Lip}.  (5)

On the other hand, by Lemma 3.2 we see that

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f̃(x) − f̃(y)∥_{1}dμ(x)dμ(y) = ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f(x + C^{⊥}) − f(y + C^{⊥})∥_{1}dμ(x)dμ(y)
≥ \frac{1}{∥f^{−1}∥_{Lip}} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ρ_{𝔽_{2}^{d}/C^{⊥}}(x + C^{⊥}, y + C^{⊥})dμ(x)dμ(y)

= Ω (\frac{log_{2} |C^{⊥}|}{log_{2} (\frac{d}{d−log_{2} |C^{⊥}|})}) · \frac{1}{∥f^{−1}∥_{Lip}}

= Ω (\frac{d − dim(C)}{log (\frac{d}{dim(C)})}) · \frac{1}{∥f^{−1}∥_{Lip}} ,  (6)

where we used the fact that |C^{⊥}| = 2^{d−dim(C)}.

Combining (5) and (6) yields the required result.

Corollary 3.5. There exists arbitrarily large finite metric spaces X for which c_{1}(X) = Ω(log |X|).

Proof. Let C ⊆ \{0, 1\}^{d} be a code with dim(C) ≥ \frac{d}{4} and w(C) = Ω(d). Such codes are well known to exist (see [38]), and are easy to obtain via the following greedy construction: fix k ≤ d/4 and let V be a k dimensional subspace of 𝔽_{2}^{d} with w(V) > δd. Then V contains 2^{k} points. The number vectors x ∈ 𝔽_{2}^{d} with ∥x + v∥_{1} ≤ δd for some v ∈ V is at most 2^{k} ∑_{ℓ≤δd} \binom{d}{ℓ} ≤ 2^{k+1}\sqrt{δd} · [δ^{δ}(1 − δ)^{1−δ}]^{−d}. It follows that there exists δ = Ω(1) such that for every k ≤ d/4 there exists x ∈ 𝔽_{2}^{d} such that w(span(V ∪ {x})) > δd, as required. Now, for C as above, Theorem 3.4 implies that

c_{1}(𝔽_{2}^{d}/C^{⊥}) = Ω(d) = Ω(log |𝔽_{2}^{d}/C^{⊥}|).

Remark 3.1. Using the Matoušek’s extrapolation lemma for Poincaré inequalities [40] (see also Lemma 5.5 in [6]), it is possible to prove that for a code C as in Corollary 3.5, for every p ≥ 1, c_{p}(𝔽_{2}^{d}/C^{⊥}) ≥ c(p)d.

3.2 The relation to transportation cost

Given a finite metric space (X, d) we denote by P(X) the set of all probability measures on X. For σ, τ ∈ P(X) we define

Π(σ, τ) = {π ∈ P(X × X) : ∀ x ∈ X, ∫_{X} dπ(x, y) = σ(x), and ∫_{X} dπ(y, x) = τ(x)}

The optimal transportation cost (with respect to the metric d) between σ and τ is defined as

T_{d}(σ, τ) = inf_{π∈Π(σ,τ)} ∫_{X×X} d(x, y)dπ(x, y).

Given A ⊆ X we denote by μ_{A} ∈ P(X) the uniform probability measure on A. If A, B ⊆ X have the same cardinality then a straightforward extreme point argument (see [58]) shows that

T_{d}(μ_{A}, μ_{B}) = inf {∫_{A} d(a, f(a))dμ_{A} : f : A → B is 1 − 1 and onto} .

Lemma 3.6. Let G be a finite group, equipped with a group invariant metric d (i.e. d(xg, yg) = d(x, y) for all g, x, y ∈ G). Then for every subgroup H ⊆ G and x, y ∈ G,

d_{G/H}(xH, yH) = T_{d}(μ_{xH}, μ_{yH}).

Proof. For every bijection f : xH → yH,

∫_{xH} d(g, f(g))dμ_{xH}(g) ≥ d(xH, yH) = d_{G/H}(xH, yH).

On the other hand, fix h_{1}, h_{2} ∈ H such that d(xh_{1}, yh_{2}) = d(xH, yH). Then the mapping f : xH → yH given by f(g) = yh_{2}h_{1}^{−1}x^{−1}g satisfies for all g ∈ xH, d(g, f(g)) = d(xh_{1}, yh_{2}) = d(xH, yH), implying the required result.

Corollary 3.7. It follows from Corollary 3.5 and Lemma 3.6 that c_{1}(P(𝔽_{2}^{d}), T_{ρ}) = Ω(d). This matches the upper bound proved in [18, 30]. In fact, from Remark 3.1 we see that for all p ≥ 1, c_{p}(P(𝔽_{2}^{d}), T_{ρ}) ≥ c(p)d.

Remark 3.2. Let Lip(𝔽_{2}^{d}) be the Banach space of all functions f : 𝔽_{2}^{d} → ℝ satisfying f(0) = 0, equipped with the Lipschitz norm ∥·∥_{Lip}. By Kantorovich duality (see [58]), (P(𝔽_{2}^{d}), T_{ρ}) is isometric to a subset of the dual space Lip(𝔽_{2}^{d})^{∗}. It follows that c_{1}(Lip(𝔽_{2}^{d})^{∗}) = Ω(d). As remarked in the introduction, the fact that sup_{d∈ℕ} c_{1}(Lip(𝔽_{2}^{d})^{∗}) = ∞ was first proved by Bourgain [11] using a different argument (which yields a worse lower bound on the distortion).

3.3 Actions of transitive permutation groups

Let G ≤ S_{d} be a subgroup of the symmetric group. Clearly G acts by isometries on 𝔽_{2}^{d} via permutations of the coordinates.

Theorem 3.8. Let f : 𝔽_{2}^{d} → L_{1} be a G-invariant function, where G is transitive. Then

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f(x) − f(y)∥_{1}dμ(x)dμ(y) ≤ \frac{20}{log d} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∥∂_{j}f(x)∥_{1}dμ(x).

Proof. Let A ⊆ 𝔽_{2}^{d} be a G invariant subset of the hypercube and write μ(A) = p. For f = 1_{A} the required inequality becomes:

2p(1 − p) ≤ \frac{10}{log d} ∑_{j=1}^{d} I_{j}(A),  (7)

where I_{j}(A) = μ{x ∈ 𝔽_{2}^{d} : |{x, x + e_{j}} ∩ A| = 1}| is the influence of the jth variable on A. By [31], max_{1≤j≤d} I_{j}(A) ≥ \frac{log d}{5d} · p(1 − p). But, since A is invariant under the action of a transitive permutation group, I_{j}(A) is independent of j, so (7) does indeed hold true.

In the general case let f : 𝔽_{2}^{d} → L_{1} be a G invariant function. Denote by π : 𝔽_{2}^{d} → 𝔽_{2}^{d}/G the natural quotient map, i.e. π(x) = Gx. Since f is G-invariant, there is a function h : 𝔽_{2}^{d}/G → L_{1} such that f = h ∘ π. By the cut-cone representation of L_{1} metrics (see [22]), there are nonnegative weights {λ_{A}}_{A⊆𝔽_{2}^{d}/G} such that for every x, y ∈ 𝔽_{2}^{d},

∥f(x) − f(y)∥_{1} = ∥h(π(x)) − h(π(y))∥_{1}
= ∑_{A⊆𝔽_{2}^{d}/G}λ_{A}|1_{A}(π(x)) − 1_{A}(π(y))|
= ∑_{A⊆𝔽_{2}^{d}/G}λ_{A}|1_{π^{−1}(A)}(x) − 1_{π^{−1}(A)}(y)|.

Observe that for every A ⊆ 𝔽_{2}^{d}/G, π^{−1}(A) ⊆ 𝔽_{2}^{d} is G-invariant. Thus by the above reasoning

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ∥f(x) − f(y)∥_{1}dμ(x)dμ(y) = ∑_{A⊆𝔽_{2}^{d}/G}λ_{A} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |1_{π^{−1}(A)}(x) − 1_{π^{−1}(A)}(y)|dμ(x)dμ(y)

≤ ∑_{A⊆𝔽_{2}^{d}/G}λ_{A} · \frac{20}{log d} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} |∂_{j}1_{π^{−1}(A)}(x)|dμ(x)

= \frac{20}{log d} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∑_{A⊆𝔽_{2}^{d}/G}λ_{A} |\frac{1_{π^{−1}(A)}(x) − 1_{π^{−1}(A)}(x + e_{j})}{2}| dμ(x)

= \frac{20}{log d} ∑_{j=1}^{d} ∫_{𝔽_{2}^{d}} ∥∂_{j}f(x)∥_{1}dμ(x).

We thus get many examples of spaces which do not well-embed into L_{1}:

Corollary 3.9. Let G be a transitive permutation group with |G| < 2^{εd}, for some ε ∈ (0, 1). Then

c_{1}(𝔽_{2}^{d}/G) ≥ Ω (\frac{(1 − ε)}{log(1/ε)} · log d) .

Proof. This is a direct consequence of Theorem 3.8 and lemma 3.2.

Remark 3.3. It is possible to obtain slightly stronger results analogous to Corollary 3.9 when we have additional information on the structure of the group G. Indeed, in this case, in the proof of Theorem 3.8, one can use the results of Bourgain and Kalai [13] on the influence of variables on group invariant Boolean functions, instead of using [31].

Remark 3.4. We do not know if (𝔽_{2}^{d}, ∥·∥_{2})/G embeds bi-Lipschitzly in Hilbert space with uniformly bounded distortion. This seems to be unknown even in the case when G is generated by the cyclic shift of the coordinates. This problem is interesting since if this space does embed into Hilbert space, then the results of this section will yield an alternative approach to the recent solution of the Goemans-Linial conjecture in [32].

4 Edit Distance does not embed into L_{1}

In this section we settle the L_{1} embeddability problem of Edit Distance negatively, by proving the following theorem:

Theorem 4.1. The following lower bound holds true:

c_{1}(𝔽_{2}^{d}, ED) = Ω (\sqrt{\frac{log d}{log log d}}) .

The following lemma is a useful way to prove L_{1} nonembeddability results. The case δ = 0 of this lemma is due to [37]. Variants of the case δ > 0, which is the case used in our proof of Theorem 4.1, seem to be folklore. We include here the formulation we need for the sake of completeness (the main part of the proof below is a variant of the proof of Lemma 3.6 in [49]).

Lemma 4.2. Fix α > 0 and 0 < δ < \frac{1}{3}. Let (X, d) be a finite metric space, σ a probability measure on X, and τ a probability measure on X × X. Assume that for every A ⊆ X with δ ≤ σ(A) ≤ \frac{2}{3} we have that τ({(x, y) ∈ X × X : |{x, y} ∩ A| = 1}) ≥ ασ(A). Then,

c_{1}(X) ≥ \frac{α}{2} · \frac{∫_{X×X} d(x, y) dσ(x)dσ(y) − 2δ diam(X)}{∫_{X×X} d(x, y) dτ(x, y)}.

Proof. We claim that there exists a subset Y ⊆ X with σ(Y) ≥ 1−δ such that for every f : Y → L_{1},

∫_{Y ×Y} ∥f(x) − f(y)∥_{1}dσ(x)dσ(y) ≤ \frac{2}{α} ∫_{Y ×Y} ∥f(x) − f(y)∥_{1}dτ(x, y).  (8)

This will imply the required lower bound on c_{1}(X) since if f : X → L_{1} is a bijection then

∫_{Y ×Y} ∥f(x) − f(y)∥_{1}dτ(x, y) ≤ ∥f∥_{Lip} ∫_{X×X} d(x, y) dτ(x, y),

while

∫_{Y ×Y} ∥f(x) − f(y)∥_{1}dσ(x)dσ(y) ≥ \frac{1}{∥f^{−1}∥_{Lip}} (∫_{X×X} d(x, y) dσ(x)dσ(y)−
2 ∫_{X×(X\Y)} d(x, y) dσ(x)dσ(y))
≥ \frac{1}{∥f^{−1}∥_{Lip}} (∫_{X×X} d(x, y) dσ(x)dσ(y) − 2δ diam(X)) .

It remains to prove the existence of the required subset Y. For simplicity we denote for every A, B ⊆ X,

{A, B} = {(x, y) ∈ X × X : {x, y} ∩ A ≠ ∅ ∧ {x, y} ∩ B ≠ ∅}.

Define inductively disjoint subsets ∅ = W_{0}, W_{1}, …, W_{k} ⊆ X as follows. Having defined W_{1}, …, W_{i}, write Y_{i} = ∪_{ℓ=1}^{i}W_{ℓ} and let W_{i+1} ⊆ X \ Y_{i} be an arbitrary nonempty subset for which

τ(\{W_{i+1}, X \ (Y_{i} ∪ W_{i+1})\}) < ασ(W_{i+1}) ≤ \frac{α}{2}σ(X \ Y_{i}).

If no such W_{j} exists then this process terminates. We claim that σ(Y_{k}) < δ. Indeed, otherwise let j be the first time at which σ(Y_{j}) ≥ δ. Observe that

σ(Y_{j}) = σ(Y_{j−1}) + σ(W_{j}) < σ(Y_{j−1}) + \frac{1}{2}σ(X \ Y_{j−1}) ≤ \frac{1 + δ}{2} ≤ \frac{2}{3}.

By our assumptions it follows that τ({Y_{j}, X\Y_{j}}) ≥ ασ(Y_{j}). But from the following simple inclusion

{Y_{j}, X \ Y_{j}} = {⋃_{i=1}^{j} W_{i}, X \ ⋃_{i=1}^{j} W_{i}} ⊆ ⋃_{i=1}^{j}{W_{i}, X \ (Y_{i−1} ∪ W_{i})}

we deduce that

0 < ασ(Y_{j}) ≤ τ({Y_{j}, X \ Y_{j}}) ≤ ∑_{i=1}^{j} τ({W_{i}, X \ (Y_{i−1} ∪ W_{i})}) < ∑_{i=1}^{j} ασ(W_{i}) = ασ(Y_{j}),

a contradiction. Thus, taking Y = Y_{k} we see that for every A ⊆ Y with σ(A) ≤ \frac{1}{2} we have τ({A, Y \ A}) ≥ ασ(A). In other words,

∫_{Y ×Y} ∥1_{A}(x) − 1_{A}(y)∥_{1}dτ(x, y) = τ({A, Y \ A})
≥ ασ(A)
≥ ασ(A)[σ(Y) − σ(A)]
= \frac{α}{2} ∫_{Y ×Y} ∥f(x) − f(y)∥_{1}dσ(x)dσ(y),

which implies (8) by the cut cone representation of L_{1} metrics (as in the proof of Theorem 3.8).

In what follows we let S denote the cyclic shift operator on 𝔽_{2}^{d}, namely

S(x_{1}, …, x_{d}) = (x_{d}, x_{1}, x_{2}, …, x_{d−1}).

Lemma 4.3. There exists a universal constant C > 0 such that for every ε ∈ (0, 1/2), every integer k ≥ (1/ε)^{C/ε}, and every f : 𝔽_{2}^{d} → {−1, 1},

\frac{1}{2} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(y)|dμ(x)dμ(y) − 3ε ≤ \frac{8}{k\sqrt{ε}} ∑_{j=1}^{k} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(S^{j}(x) + y)|dμ(x)dμ_{ε}(y). (9)

Proof. Observe that for every x, y ∈ 𝔽_{2}^{d}, |f(x) − f(y)| = 1 − f(x)f(y). Thus for every j ∈ {1, …, d}

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(S^{j}(x) + y)|dμ(x)dμ_{ε}(y) = 1 − ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} f(x)f(S^{j}(x) + y)dμ(x)dμ_{ε}(y)

= 1 − ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ( ∑_{A,B⊆{1,...,d}} f̂(A)f̂(B)W_{A}(x)W_{B}(S^{j}(x) + y)) dμ(x)dμ_{ε}(y)

= 1 − ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ( ∑_{A,B⊆{1,...,d}} f̂(A)f̂(B)W_{A}(x)W_{S^{−j}(B)}(x)W_{B}(y)) dμ(x)dμ_{ε}(y)
= 1 − ∑_{A⊆{1,...,d}}(1 − 2ε)^{|A|}f̂(A)f̂(S^{j}(A))
≥ 1 − ∑_{A⊆{1,...,d}}(1 − 2ε)^{|A|}f̂(A)^{2},  (10)

where we used the Cauchy-Schwartz inequality and the facts that for all B ⊆ {1, …, d} we have ∫_{𝔽_{2}^{d}} W_{B}(y)dμ_{ε}(y) = (1 − 2ε)^{|B|} and ∫_{𝔽_{2}^{d}} W_{A}W_{S^{−j}(B)}dμ = 0 when B ≠ S^{j}(A). Averaging (10) over j = 1, …, k we see that

\frac{1}{k} ∑_{j=1}^{k} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(S^{j}(x) + y)|dμ(x)dμ_{ε}(y) ≥ 1 − ∑_{A⊆\{1,...,d\}}(1 − 2ε)^{|A|}f̂(A)^{2}.

Thus, in order to prove (9) we may assume that

∑_{A⊆\{1,...,d\}}(1 − 2ε)^{|A|}f̂(A)^{2} ≥ 1 − \frac{\sqrt{ε}}{4}.  (11)

By a recent theorem of Mossel, O’Donnell and Oleszkiewicz [46], together with a theorem of Friedgut [24] (weaker estimates can be obtained using Bourgain’s noise sensitivity theorem [12]), inequality (11) implies that there exists a constant c > 0, an integer t ≤ (1/ε)^{c/ε}, a function g : 𝔽_{2}^{t} → {−1, 1}, and indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{t} ≤ d such that if we extend g to a function g̃: 𝔽_{2}^{d} → {−1, 1} by setting

g̃(x_{1}, …, x_{d}) = g(x_{i_{1}}, x_{i_{2}}, …, x_{i_{d}}),

then

∫_{𝔽_{2}^{d}} |f(x) − g̃(x)|dμ(x) ≤ ε.

Write I = {i_{1}, …, i_{t}} and for j ∈ {1, …, d} define I + j = {i_{1} + j mod d, …, i_{d} + j mod d}. If I ∩ (I + j) = ∅ then we have the identity

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |g̃(x) − g̃(S^{j}(x) + y)|dμ(x)dμ_{ε}(y) = ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |g̃(x) − g̃(y)|dμ(x)dμ(y).

Assume that k ≥ 2t^{2}. In this case

|\{j ∈ \{1, …, k\} : I ∩ (I + j) = ∅\}| ≥ k − t^{2} ≥ \frac{k}{2} .

Thus

\frac{1}{k} ∑_{j=1}^{k} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |g̃(x) − g̃(S^{j}(x) + y)|dμ(x)dμ_{ε}(y) ≥ \frac{1}{2} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |g̃(x) − g̃(y)|dμ(x)dμ(y).

It follows that

\frac{1}{k} ∑_{j=1}^{k} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(S^{j}(x) + y)|dμ(x)dμ_{ε}(y) ≥ \frac{1}{2} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(y)|dμ(x)dμ(y) −
3 ∫_{𝔽_{2}^{d}} |f(x) − g̃(x)|dμ(x)
≥ \frac{1}{2} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} |f(x) − f(y)|dμ(x)dμ(y) − 3ε.

This completes the proof of (9).

We require the following rough bound on the average edit distance on 𝔽_{2}^{d}.

Lemma 4.4. We have the following lower bound on the average Edit Distance on 𝔽_{2}^{d}:

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ED(x, y)dμ(x)dμ(y) ≥ \frac{d}{160}.

Proof. For every x ∈ 𝔽_{2}^{d} and every integer r < d/2,

|\{y ∈ 𝔽_{2}^{d} : ED(x, y) = r\}| ≤ 2^{r}\binom{2d}{r}.

This is best seen by observing that any sequence of r insertions or deletions can be executed in a sorted order, that is, the indices of positions on which the operation is performed increases. There are at most \binom{2d}{r} ways to choose the r locations of these edit operations, and 2^{r} possible insertion/deletion operations on these r locations.

Now,

μ × μ(\{(x, y) ∈ 𝔽_{2}^{d} × 𝔽_{2}^{d} : ED(x, y) > d/16\}) ≥ 1 − \frac{1}{2^{d}} ∑_{r≤d/16} 2^{r}\binom{2d}{r}
≥ 1 − \frac{1}{2^{d}} · 2^{d/8} · 2\sqrt{d/8}[(1/16)^{1/16}(15/16)^{15/16}]^{−2d}
≥ \frac{1}{10}.

Proof of Theorem 4.1. Let C be the constant in Lemma 4.3. Fix ε ∈ (0, 1/2) such that εd > (1/ε)^{C/ε} − 1, and an integer εd ≥ k ≥ (1/ε)^{C/ε}. Define a distribution τ on 𝔽_{2}^{d} × 𝔽_{2}^{d} as follows: pick a pair (x, y) ∈ 𝔽_{2}^{d} × 𝔽_{2}^{d} according to the measure μ × μ_{ε}, pick j ∈ {1, …, k} uniformly at random, and consider the random pair (x, S^{j}(x) + y). This induces a probability distribution τ on 𝔽_{2}^{d} × 𝔽_{2}^{d}. Observe that

ED(x, S^{j}(x) + y) ≤ 2ρ(0, y) + 2j ≤ 2ρ(0, y) + 2εd.

Thus

∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ED(x, y)dτ(x, y) = \frac{1}{k} ∑_{j=1}^{k} ∫_{𝔽_{2}^{d}×𝔽_{2}^{d}} ED(x, S^{j}(x) + y)dτ(x, y)

≤ 2εd + 2 ∑_{r=0}^{d} \binom{d}{r}rε^{r}(1 − ε)^{d−r} = 4εd.  (12)

Lemma 4.3 implies that for every A ⊆ 𝔽_{2}^{d},

\frac{16}{\sqrt{ε}} · τ(\{(x, y) ∈ 𝔽_{2}^{d} × 𝔽_{2}^{d} : |\{x, y\} ∩ A| = 1\}) ≥ 2μ(A)[1 − μ(A)] − 3ε.

Thus, the conditions of Lemma 4.2 hold true with δ = 6ε and α = \frac{\sqrt{ε}}{32}. Hence by (12) and Lemma 4.4

c_{1}(𝔽_{2}^{d}, ED) ≥ \frac{\sqrt{ε}}{64} · \frac{\frac{d}{80} − 6ε · 2d}{4εd}.

This implies the required result when we choose 10^{−3} > ε ≈ \frac{log log d}{log d}.

5 Flat tori which do not embed into L_{1}

Let Λ ⊆ ℝ^{n} be a lattice in ℝ^{n} of rank n. The quotient space ℝ^{n}/Λ is a Riemannian manifold (n-dimensional torus) whose curvature is identically zero. Nevertheless, we show here that it is possible to construct lattices Λ such that c_{1}(ℝ^{n}/Λ) = Ω(\sqrt{n}). For a lattice Λ ⊆ ℝ^{n} we denote its fundamental parallelepiped by P_{Λ}. The dual lattice of Λ, denoted Λ^{∗}, is defined by

Λ^{∗} = {x ∈ ℝ^{n} : ∀ y ∈ Λ, ⟨x, y⟩ ∈ ℤ}.

We shall use the following notation

N(Λ) = min_{x∈Λ\{0}} ∥x∥_{2} and r(Λ) = max_{x∈ℝ^{n}} min_{y∈Λ} ∥x − y∥_{2}.

In words, N(Λ) is the length of the shortest vector in Λ, and r(Λ) is the smallest r such that balls of radius r centered at lattice points cover ℝ^{n}.

Theorem 5.1. Let Λ ⊆ ℝ^{n} be a lattice. Then

c_{1}(ℝ^{n}/Λ) = Ω (\frac{N(Λ^{∗})}{r(Λ^{∗})} · \sqrt{n}) .

Corollary 5.2. Let Λ be a lattice such that Λ^{∗} is almost perfect, i.e. N(Λ^{∗}) = 1 and r(Λ^{∗}) ≤ 4, say. Such lattices are well known to exists (see [59, 39]). Then Theorem 5.1 implies that c_{1}(ℝ^{n}/Λ) = Ω(\sqrt{n}). This is, in particular, an example of a Riemannian manifold whose curvature is identically zero which does not well-embed bi-Lipschitzly into ℓ_{2}. This fact should be contrasted with the Nash embedding theorem [51], which says that any n-dimensional Riemannian manifold is isometric to a Riemannian submanifold of ℝ^{2n}.

Remark 5.1. Some restrictions on the Lattice Λ should be imposed in order to obtain a torus ℝ^{n}/Λ which does not embed into ℓ_{2}. Indeed, the mapping f : ℝ^{n}/ℤ^{n} → ℂ^{n} defined by f(x_{1}, …, x_{n}) = (e^{2πix_{1}}, …, e^{2πix_{n}}) has distortion O(1). We leave open the interesting problem of determining the value of c_{1}(ℝ^{n}/Λ) and c_{2}(ℝ^{n}/Λ) as a function of intrinsic geometric parameters of the lattice Λ. In Theorem 5.8 below we show that for every n

L_{n} := sup{c_{2}(ℝ^{n}/Λ) : Λ ⊆ ℝ^{n} is a lattice} < ∞.

Corollary 5.2 shows that L_{n} = Ω(\sqrt{n}), while the upper bound obtained in Theorem 5.8 is L_{n} = O(n^{3n/2}). It would be of great interest to close the large gap between these bounds.

The proof of Theorem 5.1 will be broken down into a few lemmas. In what follows we fix a lattice Λ ⊆ ℝ^{n} and denote by m the normalized Riemannian volume measure on the torus ℝ^{n}/Λ. Given a function f : ℝ^{n}/Λ → L_{1} we also think of f as an Λ-invariant function defined on ℝ^{n}. We refer to [57] for the necessary background on Fourier analysis on tori used in the ensuing arguments.

Lemma 5.3. Let γ denote the standard Gaussian measure on ℝ^{n}, i.e. dγ(x) = \frac{1}{(2π)^{n/2}} e^{−∥x∥_{2}^{2}/2}. Then for every continuous f : ℝ^{n}/Λ → L_{1},

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} ∥f(x) − f(y)∥_{1}dm(x)dm(y)
≤ \frac{1}{1 − e^{−2π^{2}[N(Λ^{∗})]^{2}}} ∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} ∥f(x) − f(x + y)∥_{1}dm(x)dγ(y).

Proof. By integration it is clearly enough to deal with the case of real-valued functions, i.e. f : ℝ^{n}/Λ → ℝ. Moreover, we claim that it suffices to prove the required inequality when f takes values in {0, 1}. Indeed, assuming the case of f : ℝ^{n}/Λ → {0, 1}, we pass to the general case as follows:

∫_{(ℝ^{/}Λ)×(ℝ^{n}/Λ)} |f(x) − f(y)|dm(x)dm(y)
= ∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} (∫_{−∞}^{∞} |1_{(−∞,t]}(f(x)) − 1_{(−∞,t]}(f(y))|dt) dm(x)dm(y)
≤ \frac{1}{1 − e^{−2π^{2}[N(Λ^{∗})]^{2}}} ∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} (∫_{−∞}^{∞} |1_{(−∞,t]}(f(x)) − 1_{(−∞,t]}(f(x + y))|dt) dm(x)dγ(y)
= \frac{1}{1 − e^{−2π^{2}[N(Λ^{∗})]^{2}}} ∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} |f(x) − f(x + y)|dm(x)dγ(y).

So, it remains to prove the required inequality for a measurable function f : ℝ^{n}/Λ → {0, 1}. The function f can be decomposed into a Fourier series indexed by the dual lattice Λ^{∗}:

f(y) = ∑_{x∈Λ^{∗}} f̂(x)e^{2πi⟨x,y⟩},

where

f̂(x) = ∫_{ℝ^{n}/Λ} f(y)e^{−2πi⟨x,y⟩}dm(y).

Using the fact that |f(x) − f(x + y)| = f(x) + f(x + y) − 2f(x)f(x + y) we get from Parseval’s identity that for every y ∈ ℝ^{n}

∫_{ℝ^{n}/Λ} |f(x) − f(x + y)|dm(x) = 2f̂(0) − 2 ∫_{ℝ^{n}/Λ} ( ∑_{u,v∈Λ^{∗}} f̂(u)f̂(v)e^{2πi(⟨u,x⟩+⟨v,x+y⟩)}) dm(x)
= 2f̂(0) − 2 ∑_{w∈Λ^{∗}} e^{2πi⟨w,y⟩}|f̂(w)|^{2}.

Integrating with respect to the Gaussian measure, and using the identity ∫_{ℝ^{n}} e^{2πi⟨w,y⟩}dγ(y) = e^{−2π^{2}∥w∥_{2}^{2}}, we get that

∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} |f(x) − f(x + y)|dm(x)dγ(x) = 2f̂(0)[1 − f̂(0)] − 2 ∑_{w∈Λ^{∗}\{0}} e^{−2π^{2}∥w∥_{2}^{2}}|f̂(w)|^{2}. (13)

On the other hand, since f is Boolean function we have the identities:

∫_{(ℝ^{/}Λ)×(ℝ^{n}/Λ)} |f(x) − f(y)|dm(x)dm(y) = 2f̂(0)[1 − f̂(0)] = 2 ∑_{w∈Λ^{∗}\{0}} |f̂(w)|^{2}.  (14)

Combining (13) and (14) we get

∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} |f(x) − f(x + y)|dm(x)dγ(x) = 2 ∑_{w∈Λ^{∗}\{0}} (1 − e^{−2π^{2}∥w∥_{2}^{2}}) |f̂(w)|^{2}

≥ 2 (1 − e^{−2π^{2}[N(Λ^{∗})]^{2}}) ∑_{w∈Λ^{∗}\{0}} |f̂(w)|^{2}
= (1 − e^{−2π^{2}[N(Λ^{∗})]^{2}}) ∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} |f(x) − f(y)|dm(x)dm(y).

Lemma 5.4. For every lattice Λ ⊆ ℝ^{n},

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} d_{ℝ^{n}/Λ}(x, y)dm(x)dm(y) ≥ \frac{n}{16r(Λ^{∗})}.

Proof. Let V_{Λ} be the Voronoi cell of Λ centered at 0, i.e.

V_{Λ} = {x ∈ ℝ^{n} : ∥x∥_{2} = d(x, Λ)}.

Denote by B_{2}^{n} the unit Euclidean ball of ℝ^{n} centered at 0. Then by the definition of r(Λ^{∗}) we have that V_{Λ^{∗}} ⊆ r(Λ^{∗})B_{2}^{n}. Hence vol(V_{Λ^{∗}}) ≤ [r(Λ^{∗})]^{n}vol(B_{2}^{n}). It is well known (see [26, 44, 39]) that

vol(V_{Λ}) · vol(V_{Λ^{∗}}) = vol(P_{Λ}) · vol(P_{Λ^{∗}}) = 1.

Thus

vol(V_{Λ}) ≥ \frac{1}{[r(Λ^{∗})]^{n}vol(B_{2}^{n})}.

It follows that

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} d_{ℝ^{n}/Λ}(x, y)dm(x)dm(y) = \frac{1}{vol(V_{Λ})} ∫_{V_{Λ}} ∥x∥_{2}dx

≥ \frac{n}{8r(Λ^{∗})} · \frac{vol (\{x ∈ V_{Λ} : ∥x∥_{2} ≥ \frac{n}{8r(Λ^{∗})}\})}{vol(V_{Λ})}
≥ \frac{n}{8r(Λ^{∗})} · (1 − (\frac{n}{8r(Λ^{∗})})^{n} vol(B_{2}^{n}) · [r(Λ^{∗})]^{n}vol(B_{2}^{n}))
≥ \frac{n}{16r(Λ^{∗})}.

Proof of Theorem 5.1. If f : ℝ^{n}/Λ → L_{1} is bi-Lipschitz then

∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} ∥f(x) − f(x + y)∥_{1}dm(x)dγ(y) ≤ ∥f∥_{Lip} · ∫_{ℝ^{n}} ∫_{ℝ^{n}/Λ} d_{ℝ^{n}/Λ}(x, x + y)dm(x)dγ(y)
≤ ∥f∥_{Lip} · ∫_{ℝ^{n}} ∥y∥_{2}dγ(y)
≤ ∥f∥_{Lip} · \sqrt{n}.

On the other hand, using Lemma 5.4 we see that

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} ∥f(x) − f(y)∥_{1}dm(x)dm(y) ≥ \frac{1}{∥f^{−1}∥_{Lip}} ∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} d_{ℝ^{n}/Λ}(x, y)dm(x)dm(y)
≥ \frac{1}{∥f^{−1}∥_{Lip}} · \frac{n}{16r(Λ^{∗})},

so by Lemma 5.3 we deduce that

∥f∥_{Lip} · ∥f^{−1}∥_{Lip} = Ω (\frac{1 − e^{−2π^{2}[N(Λ^{∗})]^{2}}}{r(Λ^{∗})} · \sqrt{n}) .

It follows that for every t > 0,

c_{1}(ℝ^{n}/Λ) = c_{1}(ℝ^{n}/(tΛ)) = Ω (\frac{1 − e^{−2π^{2}[N((tΛ)^{∗})]^{2}}}{r((tΛ)^{∗})} · \sqrt{n}) = Ω (\frac{1 − e^{−2π^{2}[N(Λ^{∗})]^{2}/t^{2}}}{r(Λ^{∗})/t} · \sqrt{n}) .

Optimizing over t yields the required result.

If one is interested only in bounding the Euclidean distortion of ℝ^{n}/Λ, then the following lemma gives an alternative proof of Theorem 5.1 (in the case of embeddings into L_{2}).

Lemma 5.5. For every continuous f : ℝ^{n}/Λ → L_{2},

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} ∥f(x) − f(y)∥_{2}^{2}dm(x)dm(y) ≤ \frac{2}{[N(Λ^{∗})]^{2}} ∫_{ℝ^{n}/Λ} ∥∇f(x)∥_{2}^{2}dm(x).

Proof. By Parseval’s identity

∫_{ℝ^{n}/Λ} ∥∇f(x)∥_{2}^{2}dm(x) = ∑_{j=1}^{n} ∫_{ℝ^{n}/Λ} (\frac{∂f}{∂x_{j}} (x))^{2} dm(x)
= ∑_{x∈Λ^{∗}} ∥f̂(x)∥_{2}^{2} · ∥x∥_{2}^{2}
≥ [N(Λ^{∗})]^{2} ∑_{x∈Λ^{∗}\{0}} ∥f̂(x)∥_{2}^{2}
= [N(Λ^{∗})]^{2} ∫_{ℝ^{n}/Λ} ∥f(x) − f̂(0)∥_{2}^{2}dm(x)
= \frac{[N(Λ^{∗})]^{2}}{2} ∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} ∥f(x) − f(y)∥_{2}^{2}dm(x)dm(y).

Lemma 5.5 yields the lower bound c_{2}(ℝ^{n}/Λ) = Ω (\frac{N(Λ^{∗})}{r(Λ^{∗})} · \sqrt{n}) as follows. Let f : ℝ^{n}/Λ → L_{2} be a bi-Lipschitz function. Since L_{2} has the Radon-Nikodym property, f is differentiable almost everywhere (see [8]). Now, by Lemma 5.5,

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} ∥f(x) − f(y)∥_{2}^{2}dm(x)dm(y) ≤ \frac{2}{[N(Λ^{∗})]^{2}} ∑_{j=1}^{n} ∫_{ℝ^{n}/Λ} ∥\frac{∂f}{∂x_{j}} ∥_{2}^{2} dm(x)
≤ \frac{2}{[N(Λ^{∗})]^{2}} · n∥f∥_{Lip}^{2}.

On the other hand, arguing as in the proof of Theorem 5.1, we get

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} ∥f(x) − f(y)∥_{2}^{2}dm(x)dm(y) ≥ \frac{1}{∥f^{−1}∥_{Lip}^{2}} ∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} d_{ℝ^{n}/Λ}(x, y)^{2}dm(x)dm(y)
= \frac{1}{∥f^{−1}∥_{Lip}^{2}} · Ω (\frac{n^{2}}{[r(Λ^{∗})]^{2}} ) .

It follows that

c_{2}(ℝ^{n}/Λ) = Ω (\frac{N(Λ^{∗})}{r(Λ^{∗})} · \sqrt{n}) .

The following corollary of Lemma 5.5 will not be used in the sequel, but we record it here for future reference.

Corollary 5.6. For every continuous f : ℝ^{n}/Λ → ℝ,

∫_{(ℝ^{n}/Λ)×(ℝ^{n}/Λ)} |f(x) − f(y)|dm(x)dm(y) ≤ \frac{2\sqrt{10}}{N(Λ^{∗})} ∫_{ℝ^{n}/Λ} ∥∇f(x)∥_{2}dm(x).

Proof. Lemma 5.5 implies that λ_{1}(ℝ^{n}/Λ) ≥ [N(Λ^{∗})]^{2}, where λ_{1}(ℝ^{n}/Λ) is the smallest nonzero eigenvalue of the Laplace-Beltrami operator on ℝ^{n}/Λ. Since ℝ^{n}/Λ has curvature 0, an inequality of Buser [16] implies that λ_{1}(ℝ^{n}/Λ) ≤ 10[h(ℝ^{n}/Λ)]^{2}, where h(ℝ^{n}/Λ) is the Cheeger constant of ℝ^{n}/Λ (Buser’s inequality can be viewed as a reverse Cheeger inequality [19] when the Ricci curvature is bounded from below). Thus h(ℝ^{n}/Λ) ≥ N(Λ^{∗})/\sqrt{10}, which is precisely the required inequality.

We end this section by showing that there exists a constant D_{n} < ∞ such that for any rank n lattice Λ ⊆ ℝ^{n}, c_{2}(ℝ^{n}/Λ) ≤ D_{n}.

Lemma 5.7. Every rank n lattice Λ ⊆ ℝ^{n} has a basis (over ℤ^{n}) x_{1}, …, x_{n} such that for every u_{1}, u_{2}, …, u_{n} ∈ ℝ,

\frac{1}{n^{(3n−1)/2}} · (∑_{j=1}^{n} u_{j}^{2}∥x_{j}∥_{2}^{2})^{1/2} ≤ ∥∑_{j=1}^{n} u_{j}x_{j}∥_{2} ≤ \sqrt{n} · (∑_{j=1}^{n} u_{j}^{2}∥x_{j}∥_{2}^{2})^{1/2} .  (15)

Proof. Let {x_{1}, …, x_{n}} be a basis of Λ, and denote by A the matrix whose columns are the vectors \frac{x_{1}}{∥x_{1}∥_{2}} , …, \frac{x_{n}}{∥x_{n}∥_{2}} . If we let \{x_{1}, …, x_{n}\} be the Korkin-Zolotarev basis of Λ, we can ensure that (see [33]):

| det(A)| ≥ \frac{1}{n^{n}} .

Denote by s_{1}(A) ≥ s_{2}(A) ≥ ⋯ s_{n}(A) > 0 the singular values of A. Given a vector u = (u_{1}, …, u_{n}) ∈ ℝ^{n} we have by the Cauchy-Schwartz inequality that

∥Au∥_{2} = ∥∑_{j=1}^{n} \frac{u_{j}}{∥x_{j}∥_{2}} · x_{j}∥_{2} ≤ ∑_{j=1}^{n} |u_{j}| ≤ \sqrt{n} · ∥u∥_{2}.

This proves the right-hand side of (15), and also shows that s_{1}(A) ≤ \sqrt{n}. Now

\frac{1}{n^{n}} ≤ | det(A)| = ∏_{j=1}^{n} s_{j}(A) ≤ s_{1}(A) · [s_{n}(A)]^{n−1} ≤ s_{1}(A) · n^{(n−1)/2},

i.e. s_{1}(A) ≥ n^{−(3n−1)/2}. It follows that for every u ∈ R^{n}, ∥Au∥_{2} ≥ s_{1}(A)∥u∥_{2} ≥ n^{−(3n−1)/2}∥u∥_{2}, which is precisely the left-hand side of (15).

Theorem 5.8. Let Λ ⊆ ℝ^{n} be a lattice of rank n. Then ℝ^{n}/Λ embeds into ℝ^{2n} with distortion O(n^{3n/2}).

Proof. Let {x_{1}, …, x_{n}} be a basis as in Lemma 5.7. Define f : ℝ^{n} → ℂ^{n} by

f (∑_{j=1}^{n} a_{j}x_{j}) = (∥x_{1}∥_{2}e^{2πia_{1}}, …, ∥x_{n}∥_{2}e^{2πia_{n}}) .

Since f is Λ-invariant, we may think of it a a function defined on the torus ℝ^{n}/Λ. For every t ∈ ℝ let m(t) be the unique integer such that t − m(t) ∈ [−1/2, 1/2). Given u, v ∈ ℝ^{n},

∥f (∑_{j=1}^{n} u_{j}x_{j}) − f (∑_{j=1}^{n} v_{j}x_{j})∥_{2}^{2} = ∑_{j=1}^{n} |e^{2πi(u_{j}−v_{j})} − 1|^{2} · ∥x_{j}∥_{2}^{2}

= 2 ∑_{j=1}^{n} [1 − cos(2π(u_{j} − v_{j}))] · ∥x_{j}∥_{2}^{2}.

Since for every t ∈ ℝ,

\frac{[t − m(t)]^{2}}{12} ≤ 1 − cos(2πt) ≤ \frac{[t − m(t)]^{2}}{2} ,

we get that

∥f (∑_{j=1}^{n} u_{j}x_{j}) − f (∑_{j=1}^{n} v_{j}x_{j})∥_{2}^{2} = Θ (∑_{j=1}^{n}[u_{j} − v_{j} − m(u_{j} − v_{j})]^{2}∥x_{j}∥_{2}^{2}) .

On the other hand, by (15),

d_{ℝ^{n}/Λ} (∑_{j=1}^{n} u_{j}x_{j}, ∑_{j=1}^{n} v_{j}x_{j}) = d_{ℝ^{n}}(∑_{j=1}^{n}(u_{j} − v_{j})x_{j}, Λ)

≤ ∥∑_{j=1}^{n}(u_{j} − v_{j})x_{j} − ∑_{j=1}^{n} m(u_{j} − v_{j})x_{j}∥_{2}

≤ \sqrt{n} (∑_{j=1}^{n}[u_{j} − v_{j} − m(u_{j} − v_{j})]^{2}∥x_{j}∥_{2}^{2})^{1/2} .

In the reverse direction, let m_{1}, …, m_{n} ∈ ℤ be such that ∑_{j=1}^{n} m_{j}x_{j} ∈ Λ is a closest lattice point to u − v. Then

d_{ℝ^{n}/Λ} (∑_{j=1}^{n} u_{j}x_{j}, ∑_{j=1}^{n} v_{j}x_{j}) = ∥∑_{j=1}^{n}[u_{j} − v_{j} − m_{j}]x_{j}∥_{2}

≥ \frac{1}{n^{(3n−1)/2}} (∑_{j=1}^{n}[u_{j} − v_{j} − m_{j}]^{2} · ∥x_{j}|∥_{2}^{2})^{1/2}

≥ \frac{1}{n^{(3n−1)/2}} (∑_{j=1}^{n}[u_{j} − v_{j} − m(u_{j} − v_{j})]^{2} · ∥x_{j}∥_{2}^{2})^{1/2} .

It follows that f has distortion O(n^{3n/2}).

6 Length of metric spaces

The following definition, due to G. Schechtman [56], plays an important role in the study of the concentration of measure phenomenon and Levy families [45, 34].

Definition 6.1. Let (X, d) be a finite metric space. The length of (X, d), denoted ℓ(X, d) is the least constant ℓ such that there exists a sequence of partitions of X, P^{0}, P^{1}, …, P^{N} with the following properties:

1. For every i ≥ 1, P^{i} is a refinement of P^{i−1}.

2. P^{0} = {X} and P^{N} = {{x} : x ∈ X}.

3. For every i ≥ 1 there exists a_{i} > 0 such that if A ∈ P^{i−1} and B, C ∈ P^{i} are such that B, C ⊆ A, then there exists a one-to-one onto function ϕ = ϕ_{B,C} : B → C such that for every x ∈ B, d(x, ϕ(x)) ≤ a_{i}.

4. ℓ = \sqrt{∑_{i=1}^{N} a_{i}^{2}}.

For p ≥ 1 we can can define an analogous concept if we demand that ℓ = (∑_{i=1}^{N} a_{i}^{p})^{1/p}. In this case we call the parameter obtained the ℓ_{p} length of (X, d), and denote it by ℓ_{p}(X, d). Observe that it is always the case that ℓ_{p}(X, d) ≤ diam(X).

Recall that for p ∈ [1, 2], a Banach space Y is called p-smooth with constant S if for every x, y ∈ Y,

∥x + y∥_{Y}^{p} + ∥x − y∥_{Y}^{p} ≤ 2∥x∥_{Y}^{p} + 2S^{p}∥y∥_{Y}^{p} .

The least constant S for which this inequality holds is called the p-smoothness constant of Y, and is denoted S_{p}(Y). It is known [4] that for q ≥ 2, S_{2}(L_{q}) ≤ \sqrt{q − 1}, and for q ∈ [1, 2], S_{q}(L_{q}) ≤ 1.

The following theorem relates the notion of length to nonembeddability results.

Theorem 6.2. Let (X, d) be a metric space and Y a p-smooth Banach space. Then

c_{Y} (X, d) ≥ \frac{1}{2^{1−1/p} · S_{p}(Y)ℓ_{p}(X, d)} (\frac{1}{|X|^{2}} ∑_{x,y∈X} d(x, y)^{p})^{1/p} .

In particular for 2 ≤ p < ∞,

c_{p}(X, d) ≥ \frac{1}{ℓ(X, d)\sqrt{2p − 2}} (\frac{1}{|X|^{2}} ∑_{x,y∈X} d(x, y)^{2})^{1/2} .

Proof. Let {P^{i}}_{i=0}^{N}, {a_{i}}_{i=1}^{N} be as above, and denote by F_{i} the σ-algebra generated by the partition P^{i}. In what follows all expectations are taken with respect to the uniform probability measure on X. Given a bijection f : X → Y we let f_{i} = 𝔼(f|F_{i}). In other words, if A ∈ P^{i} and x ∈ A then

f_{i}(x) = \frac{1}{|A|} ∑_{y∈A} f(y).

Now {f_{i}}_{i=0}^{N} is a martingale, so by Pisier’s inequality [53] (see Theorem 4.2 in [48] for the constant we use below), we see that

𝔼∥f_{N} − f_{0}∥_{Y}^{p} ≤ \frac{S_{p}(Y)^{p}}{2^{p−1} − 1} ∑_{j=0}^{N−1} 𝔼∥f_{j+1} − f_{j}∥_{Y}^{p} .

Now f_{0} = 𝔼f and f_{N} = f. Thus

𝔼∥f_{N} − f_{0}∥_{Y}^{p} = \frac{1}{|X|} ∑_{x∈X} ∥f(x) − \frac{1}{|X|} ∑_{y∈X} f(y)∥_{Y}^{p}
≥ \frac{1}{2^{p−1}|X|^{2}} ∑_{x,y∈X} ∥f(x) − f(y)∥_{Y}^{p}
≥ \frac{1}{2^{p−1}∥f^{−1}∥_{Lip}^{p}} · \frac{1}{|X|^{2}} ∑_{x,y∈X} d(x, y)^{p}.

On the other hand fix j ∈ {0, …, N − 1}, and A ∈ P^{j}, B ∈ P^{j+1} such that x ∈ B ⊆ A. Then

f_{j}(x) − f_{j+1}(x) = \frac{1}{|A|} ∑_{y∈A} f(y) − \frac{1}{|B|} ∑_{y∈B} f(y) = \frac{1}{|A|} ∑_{A⊇C∈P^{j+1}} (∑_{y∈C}[f(ϕ_{C,B}(y)) − f(y)]) .

So by convexity

∥f_{j}(x) − f_{j+1}(x)∥_{Y} ≤ ∥f||_{Lip} · a_{j+1}.

It follows that

c_{Y} (X, d) ≥ \frac{1}{2^{1−1/p} · S_{p}(Y)} · ( \frac{\frac{1}{|X|^{2}} ∑_{x,y∈X} d(x, y)^{p}}{∑_{j=1}^{N} a_{j}^{p}} )^{1/p}

= \frac{1}{2^{1−1/p} · S_{p}(Y)ℓ_{p}(X, d)} (\frac{1}{|X|^{2}} ∑_{x,y∈X} d(x, y)^{p})^{1/p} .

As shown in [45, 34], if we consider the group of permutations of {1, …, n}, S_{n}, equipped with the metric d(σ, π) = |\{i : σ(i) ≠ τ(i)\}|, then ℓ(S_{n}, d) ≤ 2\sqrt{n}, while diam(S_{n}) = Θ(n). It follows from Theorem 6.2 that c_{2}(S_{n}) = Ω(\sqrt{n}). On the other hand, by mapping each permutation π ∈ S_{n} to the matrix (1_{π(i)=j}) we see that c_{2}(S_{n}) = O(\sqrt{n}). Thus

c_{2}(S_{n}) = Θ (\sqrt{\frac{log |S_{n}|}{log log |S_{n}|}}) .

Similar optimal bounds can be deduced for c_{p}(S_{n}), p ≥ 1.

The metric d on S_{n} is the shortest path metric induced by the Cayley graph on S_{n} obtained by taking the set of all transpositions as generators. It is of interest to study the Euclidean distortion of metrics on S_{n} induced by Cayley graphs coming from other generating sets. In particular, it is a long standing conjecture (see [55]) that there exists a bounded set of generators of S_{n} with respect to which the Cayley graph is an expander. It is thus natural to ask whether there exists a set of generators of S_{n} with respect to which the metric induced by the Cayley graph has Euclidean distortion Ω(log |S_{n}|) = Ω(log n log log n).

Another example discussed in [45, 34] is the case of the Hamming cube. In this case ℓ(𝔽_{2}^{d}, ρ) = O(\sqrt{d}), and so Theorem 6.2 implies that for p ≥ 2, c_{p}(𝔽_{2}^{d}, ρ) ≥ c(p)\sqrt{d}. This result was first proved in [50].

More generally, let G be a finite group equipped with a translation invariant metric d. Let G = G_{0} ⊇ G_{1} ⊇ · ⊇ G_{n} = {e} be a decreasing sequence of subgroups. Then it is shown in [45, 34] that

ℓ(G, d) ≤ \sqrt{∑_{j=1}^{n} [ diam(G_{i−1}/G_{i})]^{2}}.

This estimate implies a wide range of additional nonembeddability results.

7 Acknowledgments

We are grateful to Keith Ball, Henry Cohn, Piotr Indyk, László Lovász and Gideon Schechtman for helpful suggestions.

References

[1] A. Andoni, M. Deza, A. Gupta, P. Indyk, and S. Raskhodnikova. Lower bounds for embedding edit distance into normed spaces. In SODA ’03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 523–526. Society for Industrial and Applied Mathematics, 2003.

[2] A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and E. Tardos. Approximate classification via earthmover metrics. In SODA ’04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1079–1087. Society for Industrial and Applied Mathematics, 2004.

[3] 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 (electronic), 1998.

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

[5] Z. Bar-Yossef, T. S. Jayram, R. Krauthgamer, and R. Kumar. Approximating edit distance efficiently. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 550–559. IEEE, Oct. 2004.

[6] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. Math., 2005. To appear.

[7] J. Bates, W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9(6):1092–1127, 1999.

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

[9] A. Beutelspacher and U. Rosenbaum. Projective geometry: from foundations to applications. Cambridge University Press, Cambridge, 1998.

[10] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[11] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222–230, 1986.

[12] J. Bourgain. On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math., 131:269–276, 2002.

[13] J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal., 7(3):438–461, 1997.

[14] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986.

[15] M. R. Bridson and A. Haefliger. Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999.

[16] P. Buser. A note on the isoperimetric constant. Ann. Sci. École Norm. Sup. (4), 15(2):213–230, 1982.

[17] M. Charikar and R. Krauthgamer. Embedding edit distance submetrics into ℓ_{1}. Manuscript, 2005.

[18] M. S. Charikar. Similarity estimation techniques from rounding algorithms. In STOC ’02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380– 388. ACM Press, 2002.

[19] J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pages 195–199. Princeton Univ. Press, Princeton, N. J., 1970.

[20] C. Chekuri, S. Khanna, J. Naor, and L. Zosin. Approximation algorithms for the metric labeling problem via a new linear programming formulation. In SODA ’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 109–118. Society for Industrial and Applied Mathematics, 2001.

[21] G. Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. In SODA ’02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 667–676. Society for Industrial and Applied Mathematics, 2002.

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

[23] P. Enflo. On the nonexistence of uniform homeomorphisms between L_{p}-spaces. Ark. Mat., 8:103–105 (1969), 1969.

[24] E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998.

[25] M. Gromov. Metric structures for Riemannian and non-Riemannian spaces, volume 152 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1999. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates.

[26] P. M. Gruber and C. G. Lekkerkerker. Geometry of numbers, volume 37 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, second edition, 1987.

[27] L. J. Guibas, Y. Rubner, and C. Tomassi. The earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision, 40(2):99–121, 2000.

[28] D. Gusfield. Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge, 1997. Computer science and computational biology.

[29] P. Indyk. Approximate nearest neighbor under edit distance via product metrics. In SODA ’04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 646–650. Society for Industrial and Applied Mathematics, 2004.

[30] P. Indyk and N. Thaper. Fast image retrieval via embeddings. In ICCV ’03: Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision, 2003.

[31] J. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions. In 29th Symposium on Foundations of Computer Science, pages 68–80, 1988.

[32] S. Khot and N. Vishnoi. On embeddability of negative type metrics into ℓ_{1}. Manuscript, 2005.

[33] J. C. Lagarias, H. W. Lenstra JR., and C. P. Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 10(4):333–348, 1990.

[34] M. Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.

[35] V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Dokl., 10:707–710, 1965.

[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, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[38] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. I. North-Holland Publishing Co., Amsterdam, 1977. North-Holland Mathematical Library, Vol. 16.

[39] J. Martinet. Perfect lattices in Euclidean spaces, volume 327 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 2003.

[40] J. Matoušek. On embedding expanders into l_{p} spaces. Israel J. Math., 102:189–197, 1997.

[41] J. Matoušek. Open problems on embeddings of finite metric spaces. Available at http://kam.mff.cuni.cz/∼matousek/metrop.ps.gz, 2002.

[42] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451– 494, 2004.

[43] M. Mendel and A. Naor. Metric cotype. Manuscript, 2005.

[44] D. Micciancio and S. Goldwasser. Complexity of lattice problems. The Kluwer International Series in Engineering and Computer Science, 671. Kluwer Academic Publishers, Boston, MA, 2002. A cryptographic perspective.

[45] V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[46] E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Manuscript, 2005.

[47] S. Muthukrishnan and S. C. Sahinalp. Approximate nearest neighbors and sequence comparison with block operations. In STOC 2000: Proceedings of the 32th Annual ACM Symposium on Theory of Computing, pages 416–424, 2000.

[48] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Preprint, 2004.

[49] A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal. To appear.

[50] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552:213–236, 2002.

[51] J. Nash. C^{1} isometric imbeddings. Ann. of Math. (2), 60:383–396, 1954.

[52] R. Ostrovsky and Y. Rabani. Low distortion embeddings for edit distance. In STOC 2005: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005. To appear.

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

[54] G. Pisier. Probabilistic methods in the geometry of Banach spaces. In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167–241. Springer, Berlin, 1986.

[55] E. Rozenman, A. Shalev, and A. Wigderson. A new family of Cayley expanders? In STOC 2004: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 445– 454, 2004.

[56] G. Schechtman. Lévy type inequality for a class of finite metric spaces. In Martingale theory in harmonic analysis and Banach spaces (Cleveland, Ohio, 1981), volume 939 of Lecture Notes in Math., pages 211–215. Springer, Berlin, 1982.

[57] E. M. Stein and G. Weiss. Introduction to Fourier analysis on Euclidean spaces. Princeton University Press, Princeton, N.J., 1971. Princeton Mathematical Series, No. 32.

[58] C. Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003.

[59] C. Zong. From deep holes to free planes. Bull. Amer. Math. Soc. (N.S.), 39(4):533–555 (electronic), 2002.