Planar Earthmover is not in L_{1}

Assaf Naor Microsoft Research

        anaor@microsoft.com

Gideon Schechtman^{∗} Weizmann Institute and Microsoft Research

                                       gideon@weizmann.ac.il

Abstract

We show that any L_{1} embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid \{0, 1, …, n\}^{2} ⊆ ^{2} incurs distortion Ω ( \sqrt{logn}). We also use Fourier analytic techniques to construct a simple L_{1} embedding of this space which has distortion O(logn).

1 Introduction

For a finite metric space (X, d_{X}) we denote by 𝒫_{X} the space of all probability measures on X. The transportation cost distance (also known as the Earthmover distance in the computer vision/graphics literature) between two probability measures μ, ν ∈ 𝒫_{X} is defined by

τ(μ, ν) = min { ∑_{x,y∈X}d_{X}(x, y)π(x, y) : ∀x, y ∈ X, π(x, y) ≥ 0, ∑_{z∈X}π(x, z) = μ(x), ∑_{z∈X}π(z, y) = ν(y)}.

Observe that if μ and ν are the uniform probablity distribution over k-point subsets A ⊆ X and B ⊆ X, respectively, then by the fact that all the extreme points of the k×k doubly stochastic matrices are permutation matrices,

τ(μ, ν) = min \{ \frac{1}{k} ∑_{a∈A}d_{X}(a, f (a)) : f : A → B is a bijection\} .  (1)

This quantity is also known as the minimum weight matching between A and B, corresponding to the weight function d_{X}(·, ·) (see [42]). Thus, the Earthmover distance is a natural measure of similarity between images [42, 15, 14]- the distance is the optimal way to match various features, where the cost of such a matching corresponds to the sum of the distances between the features that were matched. Indeed, such metrics occur in various contexts in computer science. Apart from being a popular distance measure in graphics and vision [42, 15, 14, 26], they are used as LP relaxations for classification problems such as 0-extension and metric labelling [9, 8, 2]. Transportation cost metrics are also prevalent in several areas of analysis and PDE (see the book [53] and the references therein).

Following extensive work on nearest neighbor search and data stream computations for L_{1} metrics (see [24, 20, 19, 10, 22]), it became of great interest to obtain low distortion embeddings of useful metrics into L_{1} (here, and in what follows, L_{1} denotes the space of all Lebesgue measurable functions f : [0, 1] → , such that ∥f ∥_{1} ∫_{0}^{1} |f (t)|dt < ∞). Indeed, such embeddings can be used to construct approximate nearest neighbor databases, with an approximation guarantee depending on the distortion of the embedding (we are emphasizing here only one aspect of the algorithmic applications of low distortion embeddings into L_{1}- they are also crucial for the study of various cut problems in graphs, and we refer the reader to [36, 23, 21] for a discussion of these issues).

∗Supported in part by the Israel Science Foundation.

In the context of the Earthmover distance, nearest neighbor search (a.k.a. similarity search in the vision literature) is of particular importance. It was therefore asked (see, e.g. [35]) whether the Earthmover distance embeds into L_{1} with constant distortion (the best known upper bounds on the L_{1} distortion were obtained in [8, 26], and will be discussed further below). In [30] the case of the Hamming cube was settled negatively: It is shown there that any embedding of the Earthmover distance on {0, 1}^{d} (equipped with the L_{1} metric) incurs distortion Ω(d). However, the most interesting case is that of the Earthmover distance on the Euclidean plane, as this corresponds to a natural similarity measure between images [14] (indeed, the case of the L_{1} embeddability of planar Earthmover distance was explicitly asked in [35]). Here we settle this problem negatively by obtaining the first super-constant lower bound on the L_{1} distortion of the planar Earthmover distance. To state it we first recall some definitions.

Given two metric spaces (X, d_{X}) and (Y, d_{Y}), and a mapping f : X → Y, we denote its Lipschitz constant by

∥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} = sup_{\begin{matrix}x,y∈X \\ x y \end{matrix}} \frac{d_{Y}(f (x), f (y))}{d_{X}(x, y)} · sup_{\begin{matrix}x,y∈X \\ x y \end{matrix}} \frac{d_{X}(x, y)}{d_{Y}(f (x), f (y))}.

The smallest distortion with which X can be embedded into Y is denoted c_{Y}(X), i.e.,

c_{Y}(X) inf {dist(f) : f : X ↪ Y is one to one} .

When Y = L_{p} we use the shorter notation c_{Y}(X) = c_{p}(X). Thus, the parameter c_{2}(X) is the Euclidean distortion of X and c_{1}(X) is the L_{1} distortion of X.

Our main result bounds from below the L_{1} distortion of the space of probability measures on the n by n grid, equipped with the transportation cost distance.

Theorem 1.1. c_{1} (𝒫_{\{0,1,...,n\}^{2}}, τ) = Ω ( \sqrt{logn}).

We note that the best known upper bound for c_{1} (𝒫_{{0,1,...,n}^{2}}, τ) is O(logn), as proved in [8, 26]. Later on (see Theorem 1.4) we will show a new embedding which achieves this bound.

After reducing the problem to a functional analytic question, our proof of Theorem 1.1 is a discretization of a theorem of Kislyakov from 1975 [32]. We attempted to make the presentation self contained by presenting here appropriate versions of the various functional anlaytic lemmas that are used in the proof.

For readers who are more interested in the minimum cost matching metric (1), we also prove the following lower bound:

Theorem 1.2 (Discretization). For arbitrarily large integers n there is a family 𝒴 of n-point subsets of \{0, 1 …, O ( \sqrt{n loglogn})\}^{2}, with |𝒴 | ≤ n^{O(loglogn)}, such that any L_{1} embedding of 𝒴 , equipped with the minimum weight matching metric τ, incurs distortion

Ω ( \sqrt{logloglogn}) = Ω ( \sqrt{logloglog|𝒴 |})

A metric spaces (X, d_{X}) is said to embed into squared L_{2}, or to be of negative type, if the metric space (X, \sqrt{d_{X}})is isometric to a subset of L_{2}. Squared L_{2} metrics are important in various algorithmic applications since it is possible to efficiently solve certain optimization problems on them using semidefinite programming (see the discussion in [3, 31]). It turns out that planar Earthmover does not embed into any squared L_{2} metric (see Remark 3.3 for a more general result):

Theorem 1.3 (Nonembeddability into squared L_{2}). lim_{n→∞} c_{2} (𝒫_{\{0,...,n\}^{2}}, \sqrt{τ}) = ∞.

Motivated by the proof of Theorem 1.1, we also construct simple low-distortion embeddings of the space (𝒫_{{0,1,...,n}^{2}}, τ) into L_{1}. It is convenient to work with probability measures on the torus _{n}^{2} instead of the grid {0, 1, …, n}^{2}. One easily checks that {0, …, n}^{2} embeds with constant distortion into _{2n}^{2} (see e.g. Lemma 6.12 in [37]). Every μ ∈ 𝒫_{_{n}^{2}} can be written in the Fourier basis as

μ = ∑_{(u,v)∈ _{n}^{2}} μ̂(u, v)e_{uv},  (2)

where

∀(a, b), (u, v) ∈ _{n}^{2}, e_{uv}(a, b) e^{\frac{2πi(au+bv)}{n}}, and ∀(u, v) ∈ _{n}^{2}, μ̂(u, v) \frac{1}{n^{2}} ∑_{(a,b)∈ _{n}^{2}} μ(a, b)e_{uv}(−a, −b).

Observe that for n = 2^{k} + 1, k ∈ , the decomposition (2) can be computed in time O (n^{2} logn)using the fast Fourier transform [45]. Motivated in part by the results of [40] (see also [5, 41]), we define

Aμ = ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{e^{\frac{2πiu}{n}} − 1}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · μ̂(u, v) · e_{uv},  (3)

and

Bμ = ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{e^{\frac{2πiv}{n}} − 1}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · μ̂(u, v) · e_{uv}.  (4)

Theorem 1.4. The mapping μ ↦ (Aμ, Bμ) from (𝒫_{_{n}^{2}}, τ) to L_{1} ( _{n}^{2}) ⊕ L_{1} ( _{n}^{2}) has distortion O(logn).

The O(logn) distortion in Theorem 1.4 matches the best known distortion guarantee proved in [26, 8]. Our embedding has various nice features. First of all, it is a simple closed-form linear mapping into a low dimensional L_{1} space, which is based on the computation of the Fourier transform. It is thus very fast to compute, and is versatile in the sense that it might behave better on images whose Fourier transform is sparse (we do not study this issue here). Thus there is scope to apply the embedding on certain subsets of the frequencies, and this might improve the performance in practice. This is an interesting “applied” question which should be investigated further (see the “Discussion and open problems” section).

2 Preliminaries and notation

For the necessary background on measure theory we refer to the book [46], however, in the setting of the present paper, our main results will deal with finitely supported measures, in which case no background and measurabilty assumptions are necessary. We also refer to the book [53] for background on the theory of optimal transportation of measures. Let (X, d_{X}) be a metric space. We denote by ℳ_{X} the space of all Borel measures on X with bounded total variation, and by 𝒫_{X} ⊆ ℳ_{X} the set of all Borel probability measures on X. We also let ℳ_{X}^{+} ⊆ ℳ_{X} be the space of non-negative measures on X with finite total mass, and we denote by ℳ_{X}^{0} ⊆ ℳ_{X} the space of all measures μ ∈ ℳ_{X} with μ(X) = 0. Given a measure μ ∈ ℳ_{X}, we can decompose it in a unique way as μ = μ^{+} − μ^{−}, where μ^{+}, μ^{−} ∈ ℳ_{X}^{+} are disjointly supported. If μ, ν ∈ ℳ_{X}^{+} have the same total mass, i.e. μ(X) = ν(X) < ∞, then we let Π(μ, ν) be the space of all couplings of μ and ν, i.e. all non-negative Borel measures π on X × X such that for every measurable bounded f : X → ,

∫_{X×X}f (x)dπ(x, y) = ∫_{X}f (x)dμ(x), and ∫_{X×X}f (y)dπ(x, y) = ∫_{X}f (y)dν(y).

Observe that in the case of finitely supported measures, this condition translates to the standard formulation, in which we require that the marginals of π are μ and ν, i.e.

∀x, y ∈ X, ∑_{z∈X}π(x, z) = μ(x), and ∑_{z∈X}π(z, y) = ν(y).

The transportation cost distance between μ and ν, denoted here by τ(μ, ν) = τ_{(X,d_{X})}(μ, ν) (and also referred to in the literature as the Wasserstein 1 distance, Monge-Kantorovich distance, or the Earthmover distance), is

τ(μ, ν) inf {∫_{X×X}d_{X}(x, y) dπ(x, y) : π ∈ Π(μ, ν)}.  (5)

For μ ∈ ℳ_{X}^{0}, μ^{+}(X) = μ^{−}(X), so we may write ∥μ∥_{τ} τ(μ^{+}, μ^{−}). This is easily seen to be a norm on the vector space ℳ_{X,τ}^{0} {μ ∈ ℳ_{X}^{0} : ∥μ∥_{τ} < ∞} . It is easy to check that for any two non-negative measures μ, ν with the same total mass, and for every non-negative measure σ, we have τ(μ+σ, ν+σ) = τ(μ, ν). It follows that

∥μ − ν∥_{τ} = τ ((μ − ν)^{+}, (μ − ν)^{−}) = τ ((μ − ν)^{+} + min{μ, ν}, (μ − ν)^{−} + min{μ, ν})= τ(μ, ν).  (6)

Fix some x_{0} ∈ X, and let Lip_{0}(X) = Lip_{x_{0}}(X) be the linear space of all Lipschitz mappings f : X → with f (x_{0}) = 0, equipped with the norm ∥ · ∥_{Lip} (i.e. the norm of a function equals its Lipschitz constant). Any μ ∈ ℳ_{X,τ}^{0} can be thought of as a bounded linear functional on Lip_{0}(X), given by f ↦ ∫_{X}f dμ. The famous Kantorovich duality theorem (see Theorem 1.14 in [53]) implies that Lip_{0}(X)^{∗} = ℳ_{X,τ}^{0}, in the sense that every bounded linear functional on Lip_{0}(X) is obtained in this way, and for every μ ∈ ℳ_{X,τ}^{0},

∥μ∥_{τ} = ∥μ∥_{Lip_{0}(X)^{∗}} sup{∫_{X}f dμ : f ∈ Lip_{0}(X), ∥f ∥_{Lip} ≤ 1} .

(We note that this identity amounts to duality of linear programming.)

3 Proof of Theorem 1.1

Fix an integer n ≥ 2 and denote X = {0, 1, …, n − 1}^{2}, equipped with the standard Euclidean metric. In what follows, for concreteness, Lip_{0} Lip_{0}(X) is defined using the base point x_{0} = (0, 0). Also, for ease of notation we denote ℳ = ℳ_{X,τ}^{0}. Observe that Lip_{0} and ℳ are vector spaces of dimension n^{2} − 1, and by Kantorovich duality, Lip_{0}^{∗} = ℳ and ℳ^{∗} = Lip_{0}.

Assume that F : 𝒫_{X} → L_{1} is a bi-Lipschitz embedding, satisfying for any two probability measures μ, ν ∈ 𝒫_{X},

τ(μ, ν) ≤ ∥F(μ) − F(ν)∥_{1} ≤ L · τ(μ, ν).  (7)

Our goal is to bound L from below. We begin by reducing the problem to the case of linear mappings. Recall that given two normed spaces (Z, ∥ · ∥_{Z}) and (W, ∥ · ∥_{W}), the norm of a linear mapping T : Z → W is defined as ∥T∥ = sup_{z∈Z\\{0\}}\frac{∥Tz∥_{W}}{∥z∥_{Z}}(observe that in this case ∥T∥ = ∥T∥_{Lip}).

Lemma 3.1 (Reduction to a linear embedding of ℳ into ℓ_{1}^{N}). Under the assumption of an existence of an embedding F : 𝒫_{X} → L_{1} satisfying (7), there exists an integer N, and an invertible linear operator T : ℳ → ℓ_{1}^{N}, with ∥T∥ ≤ 2L and ∥T(μ)∥_{1} ≥ ∥μ∥_{τ} for all μ ∈ ℳ (the factor 2 can be replaced by 1 + ε for every ε > 0, but this is irrelevant for us here).

Proof. By translation we may assume that F maps the uniform measure on X to 0. For μ ∈ ℳ denote ∥μ∥_{∞} max_{x∈X}|μ(x)|. Observe that it is always the case that ∥μ∥_{∞} ≤ ∥μ∥_{τ}. Indeed, if π ∈ Π(μ^{+}, μ^{−}) then

∫_{X×X}∥x − y∥_{2}dπ(x, y) ≥ ∫_{X×X}dπ(x, y) = μ^{+}(X) = μ^{−}(X) ≥ ∥μ∥_{∞} .

Let B_{ℳ} denote the unit ball of ℳ. Define for μ ∈ B_{ℳ} a probability measure ψ(μ) ∈ 𝒫_{X} by ψ(μ)(x) \frac{μ(x)+1}{n^{2}} . It is clear that for every μ, ν ∈ ℳ, ∥μ−ν∥_{τ} = n^{2}∥ψ(μ)−ψ(ν)∥_{τ}. The mapping h \frac{1}{n^{2}}·F∘ψ : B_{ℳ} → L_{1} satisfies h(0) = 0, ∥h∥_{Lip} ≤ L, and ∥h(μ) − h(ν)∥_{1} ≥ ∥μ − ν∥_{τ}, where we have used (7) and (6). This implies that there exists a map h̃ : ℳ → L_{1} satisfying the same inequalities. We shall present two arguments establishing this fact: The first is a soft non-constructive proof, using the notion of ultraproducts, and the second argument is more elementary, but does not preserve the Lipschitz constant.

Let 𝒰 be a free ultrafilter on , and denote by (L_{1})_{𝒰} the corresponding ultrapower of L_{1} (see [16] for the necessary background on ultrapowers of Banach spaces. In particular, it is shown there that (L_{1})_{𝒰} is isometric to an L_{1}(σ) space, for some measure σ). Define for μ ∈ ℳ, h̃(μ) = (j · h(μ/j))_{j=1}^{∞} /𝒰 , where we set, say, h(ν) = 0 for ν ∈ ℳ \ B_{ℳ} . Then, by standard arguments, ∥h̃∥_{Lip} ≤ L and ∥h̃^{−1}∥_{Lip} ≤ 1. Moreover, h̃(ℳ) spans a separable subspace of (L_{1})_{𝒰} , and thus we may assume without loss of generality that h̃takes values in L_{1}.

An alternative proof (for those of us who don’t mind losing a constant factor), proceeds as follows. For every f ∈ L_{1} let χ(f) : [0, 1] × → {−1, 0, 1} be the function given by

χ(f)(s, t) = sign(f (s)) · 1_{[0,|f (s)|]}(t) = \{ \begin{matrix}1 & f (s) > 0, 0 ≤ t ≤ f (s), \\ −1 & f (s) < 0, 0 ≤ t ≤ −f (s), \\ 0 & otherwise. \end{matrix}

It is straightforward to check that ∥χ(f)−χ(g)∥_{L_{1}([0,1]× )} = ∥f −g∥_{1} for every f, g ∈ L_{1} (We note here that the space L_{1}([0, 1]× ) is isometric to L_{1}.) Define h̃: ℳ → L_{1}([0, 1]× ) by setting h̃(μ) = ∥μ∥_{τ}·χ∘h(μ/∥μ∥_{τ}) for μ ∈ ℳ \ {0}, and h̃(0) = 0. Since for every f ∈ L_{1}, χ(f) takes values in {−1, 0, 1}, we have the following pointwise identity for every μ, ν ∈ ℳ with ∥μ||_{τ} ≥ ∥ν∥_{τ}:

|h̃(μ) − h̃(ν)| = ∥ν∥_{τ} · |χ ∘ h (\frac{μ}{∥μ∥_{τ}}) − χ ∘ h (\frac{ν}{∥ν∥_{τ}})| + (∥μ∥_{τ} − ∥ν∥_{τ})· |χ ∘ h (\frac{μ}{∥μ∥_{τ}})|.

Thus

∥h̃(μ) − h̃(ν)∥_{L_{1}([0,1]× )} = ∥ν∥_{τ} · ∥h (\frac{μ}{∥μ∥_{τ}}) − h (\frac{ν}{∥ν∥_{τ}})∥_{1} + (∥μ∥_{τ} − ∥ν∥_{τ})· ∥h (\frac{μ}{∥μ∥_{τ}})∥_{1}  (8)
≥ ∥ν∥_{τ} · ∥\frac{μ}{∥μ∥_{τ}}− \frac{ν}{∥ν∥_{τ}}∥_{τ} + ∥μ∥_{τ} − ∥ν∥_{τ}
≥ ∥ν − μ∥_{τ} − ∥μ − \frac{∥ν∥_{τ}}{∥μ∥_{τ}}μ∥_{τ} + ∥μ∥_{τ} − ∥ν∥_{τ}
= ∥ν − μ∥_{τ}.

It also follows from the identity (8) that

∥h̃(μ) − h̃(ν)∥_{L_{1}([0,1]× )} ≤ L∥ν∥_{τ} · ∥\frac{μ}{∥μ∥_{τ}}− \frac{ν}{∥ν∥_{τ}}∥_{τ} + L∥μ − ν∥_{τ}
≤ L∥μ − ν∥_{τ} + L∥ν∥_{τ}∥μ∥_{τ} · |\frac{1}{∥μ∥_{τ}}− \frac{1}{∥ν∥_{τ}}| + L∥μ − ν∥_{τ}
≤ 3L∥μ − ν∥_{τ}.

We are now in position to use a Theorem of Ribe [44] (see also [17], and Corollary 7.10 in [4], for softer proofs), which implies that there is an into linear isomorphism S : ℳ → L_{1}^{∗∗} satisfying ∥S∥ ≤ L and ∥S^{−1}∥ ≤ 1. Since ℳ is finite dimensional, by the principle of local reflexivity [33] (alternatively by Kakutani’s representation theorem [27, 34]), and a simple approximation argument, we get that there exists an integer N and an into linear isomorphism T : ℳ → ℓ_{1}^{N} satisfying ∥T∥ ≤ 2L and ∥T^{−1}∥ ≤ 1 (the value of N is irrelevant for us here, and indeed it is possible to conclude the proof without passing to a finite dimensional L_{1} space, but this slightly simplifies some of the ensuing arguments. For completeness we note here that using a theorem of Talagrand [50] we can ensure that N = O(n^{2} logn)).

Remark 3.1. The first argument above is not special for L_{1}, and can be generalized to show that for every finite dimensional Banach space Y, if the unit ball of Y admits a bi-Lipschitz embedding into a Banach space Z, then Y embeds linearly with the same distortion into Z.

From now on let T : ℳ → ℓ_{1}^{N} be the linear operator guaranteed by Lemma 3.1. Since T is an isomorphism, the adjoint operator T^{∗} : ℓ_{∞}^{N} → ℳ^{∗} = Lip_{0} is a quotient mapping, i.e. ∥T^{∗}∥ ≤ 2L and the image of the unit ball of ℓ_{∞}^{N} under T^{∗} contains the unit ball of Lip_{0}.

The rest of the proof follows Kislyakov’s [32] and is a discretization of his argument. The idea is to compose T^{∗} with a map ℱ which is the imaginary part of the discrete two dimensional Fourier transform (see the exact definition below), seen as a map from Lip_{0} to ℓ_{2}(X), and to prove two properties of the composed map: Using the fact that ∥T^{∗}∥ ≤ 2L we shall show that ℱ ∘T^{∗} is order bounded with good bound, that is,

ℱ (T^{∗}(B_{ℓ_{∞}^{N}}))⊆ {y ∈ ℓ_{2}(X) : |y| ≤ x},

for some x ∈ ℓ_{2}(X) such that ∥x∥_{2} ≤ 4Ln. Then, using the quotient property of T^{∗}, we find a family of functions \{ϕ_{i} ∈ B_{ℓ_{∞}^{N}}\}_{i∈I} such that if ℱ (T^{∗}(ϕ_{i}))) ≤ x for all i ∈ I then necessarily ∥x∥_{2} ≥ cn \sqrt{logn}, for some universal c > 0.

We now define two more auxiliary linear operators. The first is the formal identity Id : Lip_{0} → W, where W is the space of all functions f : X → with f (0) = 0, equipped with the (discrete Sobolev) norm

∥f ∥_{W} ∑_{i=0}^{n−1} ∑_{j=0}^{n−2} |f (i, j + 1) − f (i, j)| + ∑_{j=0}^{n−1} ∑_{i=0}^{n−2} |f (i + 1, j) − f (i, j)|

+ n ∑_{i=0}^{n−2} |f (i + 1, 0) − f (i, 0)| + n ∑_{j=0}^{n−2} |f (0, j + 1) − f (0, j)|.

The second operator is also a formal identity (discrete Sobolev embedding) S : W → ℓ_{2}(X), where the Euclidean norm on ℓ_{2}(X) is taken with respect to the counting measure on X. The final operator that we will use is the imaginary part of the Fourier operator, already referred to above, which we denote by ℱ : ℓ_{2}(X) → ℓ_{2}(X). It is defined for f : X → by

ℱ (f)(u, v) ℑ(\frac{1}{n^{2}} ∑_{(k,ℓ)∈X}f (k, ℓ)e^{\frac{2πi(uk+vℓ)}{n}}) = \frac{1}{n^{2}} ∑_{(k,ℓ)∈X}f (k, ℓ) sin(\frac{2π(uk + vℓ)}{n}).

The following lemma summarizes known estimates on the norms of these operators.

Lemma 3.2 (Operator norm bounds). The following operator norm bounds hold true:

• ∥Id∥ ≤ 4n(n − 1). • ∥S∥ ≤ \frac{1}{2}. • ∥ℱ ∥ ≤ \frac{1}{n}.

Proof. The first statement means that for every f : X → with f (0) = 0, ∥f ∥_{W} ≤ 4n(n − 1)∥f ∥_{Lip}, which is obvious from the definitions. The second assertion is that ∥f ∥_{2} ≤ \frac{1}{2}∥f ∥_{W}. This is a discrete version of Sobolev’s inequality [41] (with non-optimal constant), which can be proved as follows. First of all, since f (0) = 0, for every (u, v) ∈ X,

|f (u, v)| = |∑_{k=0}^{u−1} [f (k + 1, v) − f (k, v)] + ∑_{ℓ=0}^{v−1} [f (0, ℓ + 1) − f (0, ℓ)] |

≤ ∑_{k=0}^{n−2} |f (k + 1, v) − f (k, v)| + ∑_{ℓ=0}^{n−2} |f (0, ℓ + 1) − f (0, ℓ)| A(v).  (9)

Analogously,

|f (u, v)| ≤ ∑_{ℓ=0}^{n−2} |f (u, ℓ + 1) − f (u, ℓ)| + ∑_{k=0}^{n−2} |f (k + 1, 0) − f (k, 0)| B(u).  (10)

Multiplying (9) and (10), and summing over X, we see that

∥f ∥_{2}^{2} ≤ ∑_{(u,v)∈X}A(v)B(u) = (∑_{v=0}^{n−1} A(v)) · (∑_{u=0}^{n−1} B(u)) ≤ \frac{1}{4}(∑_{v=0}^{n−1} A(v) + ∑_{u=0}^{n−1} B(u))^{2} = \frac{1}{4}∥f ∥_{W}^{2}.

The final assertion follows from the fact that the system of functions \{(k, ℓ) ↦ e^{\frac{2πi(uk+vℓ)}{n}}\}_{(u,v)∈X} are or-

thogonal in ℓ_{2}^{}(X) (the space of complex valued functions on X), and have norms bounded by n.

We now recall some facts related to absolutely summing operators on Banach spaces (we refer the interested reader to [51, 54] for more information on this topic). Given two Banach spaces Y and Z, the π_{1} norm of an operator A : Y → Z, denoted π_{1}(A), is defined to be the smallest constant K > 0 such that for every m ∈ and every y_{1}, …, y_{m} ∈ Y there exists a norm 1 linear functional y^{∗} ∈ Y^{∗} satisfying

∑_{j=1}^{m} ∥Ay_{j}∥_{Z} ≤ K ∑_{j=1}^{m} |y^{∗}(y_{j})|.  (11)

This defines an ideal norm in the sense that it is a norm, and for every two operators P : W → Y and Q : Z → V we have π_{1}(QAP) ≤ ∥Q∥ · π_{1}(A) · ∥P∥. Observe that it is always the case that π_{1}(A) ≥ ∥A∥.

Lemma 3.3. Using the above notation, π_{1}(Id) ≤ 4n(n − 1). Therefore, Lemma 3.2 implies that

π_{1}(ℱ ∘ S ∘ Id ∘ T^{∗}) ≤ 4nL.

Proof. Fix f_{1}, …, f_{m}: X → with f_{1}(0) = ⋯= f_{m}(0) = 0. Then

∑_{j=1}^{m} ∥f_{j}∥_{W} = ∑_{s=1}^{n−1} ∑_{t=0}^{n−2} ∑_{j=1}^{m} (|f_{j}(s, t + 1) − f_{j}(s, t)| + |f_{j}(t + 1, s) − f_{j}(t, s)|)

+(n + 1) ∑_{t=0}^{n−2} ∑_{j=1}^{m} (|f_{j}(0, t + 1) − f_{j}(0, t)| + |f_{j}(t + 1, 0) − f_{j}(t, 0)|)

≤ 4n(n − 1) max \{ max_{\begin{matrix}0≤s≤n−1 \\ 0≤t≤n−2 \end{matrix}} ∑_{j=1}^{m} |f_{j}(s, t + 1) − f_{j}(s, t)|, max_{\begin{matrix}0≤s≤n−1 \\ 0≤t≤n−2 \end{matrix}} ∑_{j=1}^{m} |f_{j}(t + 1, s) − f_{j}(t, s)|\} .

Assume without loss of generality that the maximum above equals ∑ _{j=1}^{m} |f_{j}(s_{0}, t_{0} + 1) − f_{j}(s_{0}, t_{0})|, for some 0 ≤ s_{0} ≤ n − 1 and 0 ≤ t_{0} ≤ n − 2. Consider the measure μ = δ_{(s_{0},t_{0}+1)} − δ_{(s_{0},t_{0})} ∈ ℳ = Lip_{0}^{∗}. One checks that ∥μ∥_{τ} = 1, and ∑ _{j=1}^{m} |f_{j}(s_{0}, t_{0} + 1) − f_{j}(s_{0}, t_{0})| = ∑ _{j=1}^{m} |μ(f_{j})|, implying the required result.

The fundamental property of the π_{1} norm is the Pietsch Factorization Theorem (see [51]), a special (particularly easy) case of which is the following lemma. We present a proof for the sake of completeness.

Lemma 3.4 (Pietsch factorization). Let Y be a Banach space, and fix a linear operator A : ℓ_{∞}^{N} → Y. Then there exists a probability measure σ on {1, …, N} and a linear operator R : L_{1}(σ) → Y such that A = R ∘ I, where I is the formal identity from ℓ_{∞}^{N} to L_{1}(σ), and ∥R∥ = π_{1}(A).

Proof. Recall that A : ℓ_{∞}^{N} → Y satisfies for all x_{1}, …, x_{m} ∈ ℓ_{∞}^{N},

∑_{j=1}^{m} ∥Ax_{j}∥ ≤ π_{1}(A) · sup_{\begin{matrix}x^{∗}∈(ℓ_{∞}^{N})^{∗} \\ ∥x^{∗}∥=1 \end{matrix}} ∑_{j=1}^{m} |x^{∗}(x_{j})| = π_{1}(A) · max_{1≤k≤N} ∑_{j=1}^{m} |x_{j}(k)|,  (12)

where the last equality follows from the fact that the evaluation functionals x ↦ x(k) are the extreme points of the unit ball of ℓ_{1}^{N} = (ℓ_{∞}^{N})^{∗}.

Denoting by e_{1}, …, e_{N} the standard basis of ^{N} we deduce from (12) that π_{1}(A) ≥ ∑ _{j=1}^{N} ∥Ae_{j}∥. Define a probability measure σ on \{1, …, N\} by σ(k) = \frac{∥Ae_{k}∥}{∑ _{j=1}^{N} ∥Ae_{j}∥}. Then for every x ∈ ℓ_{∞}^{N} we see that

∥Ax∥ = ∥∑_{k=1}^{N} x(k)Ae_{k}∥≤ ∑_{k=1}^{N} |x(k)| · ∥Ae_{k}∥ = (∑_{j=1}^{N} ∥Ae_{j}∥)∫_{{1,...,N}}|x(k)|dσ(k) ≤ π_{1}(A) ∫_{{1,...,N}}|x(k)|dσ(k).

Defining Rx = Ax, this implies the required result.

From now on let R and σ be the operator and probability measure corresponding to A = ℱ ∘S∘Id∘T^{∗} in Lemma 3.4. Thus R ∘ I = ℱ ∘ S ∘ Id∘ T^{∗} and ∥R∥ ≤ 4nL. Schematically, we have the following commuting diagram:

We need only one more simple result from classical Banach space theory. This result can be generalized to the case in which the target space ℓ_{2} is replaced by a more general Banach lattice. For the sake of simplicity we shall prove here only what is needed to conclude the proof of Theorem 1.1.

Lemma 3.5. Let R : L_{1}(σ) → ℓ_{2} be a linear operator. Fix f : {0, …, N} → [0, ∞). Then there is x ∈ ℓ_{2} with non-negative coordinates such that

R ({g : {0, …, N} → : ∀j, |g(j)| ≤ f (j)} ) ⊆ {y ∈ ℓ_{2} : ∀j, |y_{j}| ≤ x_{j}},

and ∥x∥_{2} ≤ ∥R∥ · ∥f ∥_{L_{1}(σ)}.

Proof. R is given by a matrix (R_{ij} : i = 1, …, N, j ∈ ). In other words, for every j, (Rf)_{j} = ∑ _{i=1}^{N} R_{ij}f (i). Observe that using this notation,

∥R∥ = max_{1≤i≤N} (\frac{1}{σ(i)^{2}} ∑_{j=1}^{∞} R_{ij}^{2})^{1/2}.  (13)

Fix g ∈ L_{1}(σ) such that for all i ∈ {1, …, N}, |g(i)| ≤ f (i). Then for all j,

|(Rg)_{j}| ≤ ∑_{i=1}^{N} |R_{ij}|f (i) x_{j}.

Now,

∥x∥_{2} = [∑_{j=1}^{∞} (∑_{i=1}^{N} |R_{ij}|f (i))^{2}]^{1/2} ≤ ∑_{i=1}^{N} (∑_{j=1}^{∞} |R_{ij}|^{2}f (i)^{2})^{1/2} = ∑_{i=1}^{n} σ(i)f (i)(\frac{1}{σ(i)^{2}} ∑_{j=1}^{∞} R_{ij}^{2})^{1/2} ≤ ∥R∥ · ∥f ∥_{L_{1}(σ)},

where we have used (13).

We are now in position to conclude the proof of Theorem 1.1.

Proof of Theorem 1.1. For (u, v) ∈ {1, …, n − 1}^{2} define φ_{u,v}: X → by

φ_{u,v}(k, ℓ) \frac{1}{u + v} · sin(\frac{2π(uk + vℓ)}{n}).

Then φ_{u,v}(0) = 0 and one computes that ∥φ_{u,v}∥_{Lip} < \frac{4π}{n}. By the fact that T^{∗} maps the unit ball of ℓ_{∞}^{N} onto the unit ball of Lip_{0}, it follows that there is ϕ_{u,v} ∈ ℓ_{∞}^{N} with ∥ϕ_{u,v}∥_{∞} ≤ \frac{4π}{n} and T^{∗}ϕ_{u,v} = φ_{u,v}. Now, the functions |I(ϕ_{u,v})| ∈ L_{1}(σ) are point-wise bounded by the constant \frac{4π}{n}, so by Lemma 3.5 there exists x ∈ ℓ_{2}(X) of norm at most \frac{4π}{n}∥R∥ ≤ 16πL such that |R(I(ϕ_{u,v}))| is bounded pointwise by x.

Note that

R ∘ I(ϕ_{u,v})(u, v) = ℱ ∘ S ∘ Id ∘ T^{∗}(ϕ_{u,v})(u, v)
= ℱ (φ_{u,v})(u, v)
= \frac{1}{n^{2}} ∑_{(k,ℓ)∈X} \frac{1}{u + v} · sin^{2} (\frac{2π(uk + vℓ)}{n})

= \frac{1}{n^{2}(u + v)} ∑_{k=0}^{n−1} ∑_{ℓ=0}^{n−1} (\frac{1}{2} − \frac{1}{4} · e^{2πi· \frac{2uk}{n}}· e^{2πi· \frac{2vℓ}{n}}− \frac{1}{4} · e^{−2πi· \frac{2uk}{n}} · e^{−2πi· \frac{2vℓ}{n}})

= \{ \begin{matrix}\frac{1}{2(u+v)} & (u, v) (\frac{n}{2}, \frac{n}{2}), \\ 0 & (u, v) = (\frac{n}{2}, \frac{n}{2}). \end{matrix}

But

(16πL)^{2} ≥ ∥x∥_{2}^{2} ≥ ∑_{u,v=1}^{n−1}x_{u,v}^{2} ≥ ∑_{u,v=1}^{n−1}[R ∘ I(ϕ_{u,v})(u, v)]^{2} ≥ \frac{1}{8} ∑_{u,v=1}^{n−1} \frac{1}{(u + v)^{2}} ≥ \frac{logn}{16},

where the last bound follows from comparison with the appropriate integrals. The proof of Theorem 1.1 is complete.

3.1 Discretization and minimum weight matching

In this section we deduce Theorem 1.2 from Theorem 1.1. The main tool is the following theorem of Bourgain [6], which gives a quantitative version of Ribe’s theorem [44].

Theorem 3.6 (Bourgain’s quantitative version of Ribe’s theorem [6]). There exists a universal constant C with the following property. Let Y and Z be Banach spaces, dim(Y) = d. Assume that 𝒴 is an ε-net in the unit ball of Y, f : 𝒴 → Z satisfies dist(f) ≤ D, and that loglog \frac{1}{ε} ≥ Cd logD. Then there exists an invertible linear operator T : Y → Z satisfying ∥T∥ · ∥T^{−1}∥ ≤ C · D.

Proof of Theorem 1.2. Observe that for every μ ∈ ℳ, the measure \frac{1}{μ^{+}(X)} · (μ^{+} ⊗ μ^{−}) is in Π(μ^{+}, μ^{−}). Thus

∥μ∥_{τ} ≤ \frac{1}{μ^{+}(X)}∫_{X×X}∥x − y∥_{2}dμ^{+}(x)dμ^{−}(y) ≤ \sqrt{2} · (n − 1) · μ^{+}(X) ≤ 2n · |supp(μ^{+})| · ∥μ∥_{∞} ≤ 2n^{3}∥μ∥_{∞} .

On the other hand, as we have seen in the proof of Lemma 3.1, for every μ ∈ ℳ, ∥μ∥_{∞} ≤ ∥μ∥_{τ}. It follows from these consideration, and Theorems 1.1 and 3.6, that for every integer N ≥ e^{e^{C′n^{2} loglogn}}, the set of probability measures 𝒴 ⊆ 𝒫_{X} consisting of measures μ ∈ 𝒫_{X} such that for all x ∈ X, μ(x) = k/N for some k ∈ \{0, …, N\}, satisfies c_{1}(𝒴 , τ) = Ω ( \sqrt{logn}). We pass to a family of subsets as follows. Let M be an integer which will be determined later. For every μ ∈ 𝒴 we assign a subset S_{μ} ⊆ {0, …, nM}^{2} as follows. For every (u, v) ∈ X = {0, …, n − 1}^{2}, if μ(u, v) = k/N, where k ∈ {0, …, N}, then S_{μ} will contain arbitrary k distinct points from the set (uM, vM) + \{0, …, ⌈\sqrt{N}⌉\}^{2}. Provided M ≥ 4 \sqrt{N}, the sets \{S_{μ}\}_{μ∈𝒴} thus obtained are N point subsets of {0, …, nM}^{2}, and it is straightforward to check that the minimum weight matching metric on {S_{μ}}_{μ∈𝒴} is bi-Lipschitz equivalent to (𝒴 , τ) with constant distortion.

3.2 Uniform and coarse nonembeddability into Hilbert space

In this section we prove Theorem 1.3. We shall prove, in fact, that the space ℳ_{[0,1]^{2},τ} does not embed uniformly or coarsely into L_{2}. We first recall the defintions of these important notions (see [4, 37] and the references therein for background on these concepts). Let (X, d_{X}) and (Y, d_{Y}) be metric spaces. For f : X → Y and t > 0 we define

Ω_{f} (t) = sup{d_{Y}(f (x), f (y)); d_{X}(x, y) ≤ t},

and

ω_{f} (t) = inf{d_{Y}(f (x), f (y)); d_{N}(x, y) ≥ t}.

Clearly Ω_{f} and ω_{f} are non-decreasing, and for every x, y ∈ X,

ω_{f} (d_{X}(x, y))≤ d_{Y}(f (x), f (y)) ≤ Ω_{f} (d_{X}(x, y)).

With these definitions, f is uniformly continuous if lim_{t→0} Ω_{f} (t) = 0, and f is said to be a uniform embedding if f is injective and both f and f^{−1} are uniformly continuous. Also, f is said to be a coarse embedding if Ω_{f} (t) < ∞ for all t > 0 and lim_{t→∞} ω_{f} (t) = ∞.

In what follows we will use the following standard notation: Given a sequence of Banach spaces \{(Z_{j}, ∥ · ∥_{Z_{j}})\} _{j=1}^{∞} the Banach space (⨁ _{j=1}^{∞} Z_{j})_{1} is the space of all sequences \overline{z} = (z_{j})_{j=1}^{∞} ∈ ∏ _{j=1}^{∞} Z_{j} such

that ∥\overline{z}∥ ∑ _{j=1}^{∞} ∥z_{j}∥_{Z_{j}} < ∞. If for every j ∈ , Z_{j} = Z_{1}, we write ℓ_{1}(Z_{1}) = (⨁ _{j=1}^{∞} Z_{j})_{1}.

Theorem 3.7. The spaces {ℳ_{{0,...,n}^{2},τ}^{0}} _{n=1}^{∞} do not admit a uniform or coarse embedding into L_{2} with moduli uniformly bounded in n, i.e., there do not exist increasing functions ω, Ω : [0, ∞) → [0, ∞) which either satisfy lim_{t→0} ω(t) = lim_{t→0} Ω(t) = 0, or lim_{t→∞} ω(t) = ∞, and mappings f_{n} : ℳ_{{0,...,n}^{2}}^{0}→ L_{2}, such that ω(∥μ − ν∥_{τ}) ≤ ∥f_{n}(μ) − f_{n}(ν)∥_{2} ≤ Ω(∥μ − ν∥_{τ}) for all μ, ν ∈ ℳ_{{0,...,n}^{2}}^{0}and all n.

Proof. If this is not the case then by passing to a limit along an ultrafilter we easily deduce that ℳ_{[0,1]^{2},τ}^{0} uniformly or coarsely embeds in an ultraproduct of Hilbert spaces and thus in L_{2} (see [16, 17]). By a theorem of Aharoni, Maurey and Mityagin [1] in the case of uniform embeddings, and a result of Randrianarivony [43] in the case of coarse embeddings, this implies that ℳ_{[0,1]^{2}}^{0} is linearly isomorphic to a subspace of L_{0}. By a theorem of Nikišin [39] it follows that ℳ_{[0,1]^{2}}^{0} is isomorphic to a subspace of L_{1−ε} for any ε ∈ (0, 1). We recall that it is an open problem posed by Kwapien (see the discussion in [28, 4]) whether a Banach space which linearly embeds into L_{0} is linearly isomorphic to a subspace of L_{1}. If this were the case, we would have finished by Theorem 1.1. Since the solution of Kwapien’s problem is unknown, we proceed as follows.

Let {S_{j}}_{j=1}^{∞} be a sequence of disjoint squares in [0, 1]^{2} with

d(S_{j}, S_{k}) = min_{a∈S_{j}, b∈S_{k}} ∥a − b∥_{2} > max{diamS_{j} , diamS_{k}}.  (14)

Consider the linear subspace Y of ℳ_{[0,1]^{2}}^{0} consisting of all measures μ satisfying supp(μ) ⊆ ⋃ _{j=1}^{∞} S_{j} and μ(S_{j}) = 0 for all j. It is intuitively clear that in the computation of ∥μ∥_{τ} for μ ∈ Y the best transportation leaves each of the S_{j} invariant; i.e., it is enough to take the infimum in (5) only over measures π ∈ Π(μ, ν) which are supported on ⋃ _{j=1}^{∞} (S_{j} × S_{j}). This is proved formally as follows: Fix μ ∈ Y and write μ = ∑ _{j=1}^{∞} μ_{j}, where supp(μ_{j}) ⊆ S_{j} and μ_{j}(S_{j}) = 0 for all j ∈ . We claim that

∥μ∥_{[0,1]^{2},τ} = ∑_{j=1}^{∞} ∥μ_{j}∥_{S_{j},τ}.  (15)

If π_{j} ∈ Π(μ_{j}^{+}, μ_{j}^{−}) then π ∑ _{j=1}^{∞} π_{j} ∈ Π(μ^{+}, μ^{−}). Thus ∥μ∥_{[0,1]^{2},τ} ≤ ∑ _{j=1}^{∞} ∥μ_{j}∥_{S_{j},τ}. To prove the reverse inequality take π ∈ Π(μ^{+}, μ^{−}). For every j = 1, 2, …define a measure σ_{j} on S_{j} as follows: For A ⊆ S_{j} set σ_{j}(A) π (A × ⋃ _{k j} S_{k}). Thus, in particular, by our assumption (14) for every y ∈ S_{j},

∫_{S_{j}} ∥x − y∥_{2}dσ_{j}(x) = ∫_{S_{j}×⋃ _{k j} S_{k}} ∥x − y∥_{2}dπ(x, z) ≤ ∫_{S_{j}×⋃ _{k j} S_{k}} ∥x − z∥_{2}dπ(x, z).  (16)

Writing

π̃ π · 1_{⋃ _{j=1}^{∞} (S_{j}×S_{j})} + ∑_{j=1}^{∞} \frac{1}{σ_{j}(S_{j})} · σ_{j} ⊗ σ_{j} = π · 1_{⋃ _{j=1}^{∞} (S_{j}×S_{j})} + ∑_{j=1}^{∞} \frac{1}{π (S_{j} × ⋃ _{k j} S_{k})} · σ_{j} ⊗ σ_{j},

it follows from our definitions that π̃ ∈ Π(μ^{+}, μ^{−}) and π̃ is supported on ⋃ _{j=1}^{∞} (S_{j} × S_{j}). Moreover, for each j, π̃_{j} π̃|_{S_{j}} ∈ Π(μ_{j}^{+}, μ_{j}^{−}), so that

∑_{j=1}^{∞} ∥μ_{j}∥_{S_{j},τ} ≤ ∑_{j=1}^{∞} ∫_{S_{j}×S_{j}} ∥x − y∥_{2}dπ̃_{j}(x, y)

= ∫_{⋃ _{j=1}^{∞} (S_{j}×S_{j})} ∥x − y∥_{2}dπ(x, y) + ∑_{j=1}^{∞} \frac{1}{π (S_{j} × ⋃ _{k j} S_{k})} · ∫_{S_{j}×S_{j}} ∥x − y∥_{2}dσ_{j}(x)dσ_{j}(y)

≤^{(16)} ∫_{⋃ _{j=1}^{∞} (S_{j}×S_{j})} ∥x − y∥_{2}dπ(x, y) + ∑_{j=1}^{∞} ∫_{S_{j}×⋃ _{k j} S_{k}} ∥x − z∥_{2}dπ(x, z)

= ∫_{(⋃ _{j=1}^{∞} S_{j})×(⋃ _{j=1}^{∞} S_{j})} ∥x − y∥_{2}dπ(x, y).

This concludes the proof of (15). It follows that Y is isometric to (⨁ _{n=1}^{∞} ℳ_{S_{n},τ}^{0}) _{1}, which in turn is isometric

to ℓ_{1} (ℳ_{[0,1]^{2},τ}^{0}) . Now, Kalton proved in [28] that if for some Banach space X, ℓ_{1}(X) is isomorphic to a subspace of L_{0}, then X is isomorphic to a subspace of L_{1} and we finish by Theorem 1.1.

Proof of Theorem 1.3. Assume for the sake of contradiction that there exists C < ∞ such that for all n ∈ , c_{2} (𝒫_{\{0,...,n\}^{2}}, \sqrt{τ}) < C. By the proof of Lemma 3.1 we know that the unit ball of ℳ_{\{0,...,n\}^{2},τ}is isometric to a subset of (𝒫_{{0,...,n}^{2}}, τ). Thus by our assumption there exist mappings f_{n} : ℳ_{{0,...,n}^{2}}→ L_{2} such that for every μ, ν ∈ ℳ_{{0,...,n}^{2}}with ∥μ∥_{τ}, ∥ν∥_{τ} ≤ 1,

\sqrt{∥μ − ν∥_{τ}} ≤ ∥f_{n}(μ) − f_{n}(ν)∥_{2} ≤ C · \sqrt{∥μ − ν∥_{τ}} .  (17)

Let 𝒰 be a free ultrafilter on . Define f̃_{n} : ℳ_{\{0,...,n\}^{2}} → (L_{2})_{𝒰} by f̃_{n}(μ) = ( \sqrt{j} · f_{n}(μ/j))_{j=1}^{∞} /𝒰 . In-

equalities (17) imply that all μ, ν ∈ ℳ_{\{0,...,n\}^{2}}satisfy \sqrt{∥μ − ν∥_{τ}} ≤ ∥f̃_{n}(μ) − f̃_{n}(ν)∥_{(L_{2})_{𝒰}} ≤ C · \sqrt{∥μ − ν∥_{τ}}. Since the ultrapower (L_{2})_{𝒰} is isometric to a Hilbert space (see [16]), we arrive at a contradiction with Theorem 3.7.

Remark 3.2. We believe that Theorem 1.3 can be made quantitative, i.e. one can give explicit quantitative estimates on the rate with which c_{2} (𝒫_{\{0,...,n\}^{2}}, \sqrt{τ}) tends to infinity. This would involve obtaining quantitative versions of the proofs in [1, 28, 43], which seems easy but somewhat tedious. We did not attempt to obtain such bounds.

Remark 3.3. We do not know whether (𝒫_{[0,1]^{2}}, τ) admits a uniform embedding into Hilbert space. The proof above actually gives that for all α ∈ (0, 1], (𝒫_{[0,1]^{2},τ}, τ^{α}) does not embed bi-Lipschitzly into Hilbert space. But, our proof exploits the homogeneity of the function t ↦ t^{α} in an essential way, so it does not apply to the case of more general moduli.

4 Upper bounds via Fourier analysis

In this section we prove Theorem 1.4, and discuss some related upper bounds. Given a measure μ on _{n}^{2} we decompose it as in (2), and we consider the linear operators A and B, from ℳ_{_{n}^{2}} to L_{1} ( _{n}^{2}), defined in (3) and (4), respectively. One checks that the duals of these operators, A^{∗}, B^{∗} : L_{∞} ( _{n}^{2}) → ℳ_{_{n}^{2}}^{∗} = Lip_{0} ( _{n}^{2}), are given by

A^{∗}f = ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{e^{− \frac{2πiu}{n}} − 1}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · f̂(u, v) · (e_{uv}− 1),  (18)

and

B^{∗}f = ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{e^{− \frac{2πiv}{n}} − 1}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · f̂(u, v) · (e_{uv}− 1).  (19)

To check these identities the reader should verify that for all μ ∈ ℳ_{_{n}^{2}}, ∫_{_{n}^{2}} f d(Aμ) = ∫_{_{n}^{2}}(A^{∗}f)dμ, and

similarly for B (to this end, recall that μ ( _{n}^{2}) = 0, so that μ̂(0, 0) = 0. This explains the subtraction of 1 in the identities (18) and (19)).

We claim that for every μ ∈ ℳ_{Z_{n}^{2}},

∥μ∥_{τ} ≤ ∥Aμ∥_{L_{1}( _{n}^{2})} + ∥Bμ∥_{L_{1}( _{n}^{2})} ≤ C logn · ∥μ∥_{τ},  (20)

where C is a universal constant. This will imply Theorem 1.4 since the mapping μ ↦ μ − U, where U is the uniform probability measure on Z_{n}^{2}, is an isometric embedding of 𝒫_{_{n}^{2}} into ℳ_{_{2}^{n}}.

By duality, (20) is equivalent to the fact that the mapping (f, g) ↦ A^{∗}f + B^{∗}g from L_{∞} ( _{n}^{2}) ⊕ L_{∞} ( _{n}^{2}) to Lip_{0} ( _{n}^{2}) is a C logn quotient map, i.e. for every (f, g) ∈ L_{∞} ( _{n}^{2}) ⊕ L_{∞} ( _{n}^{2})

∥A^{∗}f + B^{∗}g∥_{Lip} ≤ C logn · max{∥f ∥_{∞} , ∥g∥_{∞} },  (21)

and for every h ∈ Lip_{0} ( _{n}^{2}) there is some (f, g) ∈ L_{∞} ( _{n}^{2}) ⊕ L_{∞} ( _{n}^{2}) satisfying A^{∗}f + B^{∗}g = h and max{∥f ∥_{∞} , ∥g∥_{∞} } ≤ ∥h∥_{Lip}. The second assertion is proved as follows: Take f = ∂_{1}h and g = ∂_{2}h, where for j = 1, 2, ∂_{j}h(x) = h(x + e_{j}) − h(x) (here e_{1} = (1, 0) and e_{2} = (0, 1)). Clearly ∥f ∥_{∞} , ∥g∥_{∞} ≤ ∥h∥_{Lip}, and

A^{∗}f + B^{∗}g = ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}(\frac{(e^{− \frac{2πiu}{n}} − 1) · ˆ∂_{1}h(u, v) + (e^{− \frac{2πiv}{n}} − 1) · ˆ∂_{2}h(u, v)}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} )(e_{uv}− 1)

= ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}(\frac{(e^{− \frac{2πiu}{n}} − 1) · (e^{\frac{2πiu}{n}} − 1) + (e^{− \frac{2πiv}{n}} − 1) · (e^{\frac{2πiv}{n}} − 1)}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}})· ĥ(u, v)(e_{uv}− 1)
= ∑_{(u,v)∈ _{n}^{2}\{(0,0)}}ĥ(u, v)e_{uv}− ∑_{(u,v)∈ _{n}^{2}\{(0,0)}}ĥ(u, v)
= ∑_{(u,v)∈ _{n}^{2}} ĥ(u, v)e_{uv} = h,

where we used the fact that h(0) = 0.

It remains to prove (21). To this end, it is enough to show that ∥A^{∗}f ∥_{Lip} ≤ O(logn)·∥f ∥_{∞} and ∥B^{∗}g∥_{Lip} ≤ O(logn) · ∥g∥_{∞} . We will establish this for A^{∗}- the case of B^{∗} is entirely analogous. Observe that

∥A^{∗}f ∥_{Lip} ≤ ∥∂_{1}A^{∗}f ∥_{∞} + ∥∂_{2}A^{∗}f ∥_{∞} ,

so it is enough to establish the following two inequalities:

∥ ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{|e^{\frac{2πiu}{n}} − 1|^{2}}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · f̂(u, v)e_{uv}∥_{∞} ≤ O(logn) · ∥f ∥_{∞} ,  (22)

and

∥ ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{(e^{− \frac{2πiu}{n}} − 1) · (e^{\frac{2πiv}{n}} − 1)}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · f̂(u, v)e_{uv}∥_{∞} ≤ O(logn) · ∥f ∥_{∞} .  (23)

Since for p > 0 the norms on L_{∞} ( _{n}^{2}) and L_{p} ( _{n}^{2}) are equivalent with constant n^{2/p} (by Hölder’s inequality), it is enough to show that for p ≥ 2,

∥ ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{|e^{\frac{2πiu}{n}} − 1|^{2}}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · f̂(u, v)e_{uv}∥_{p} ≤ O(p) · ∥f ∥_{p},  (24)

and

∥ ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}\frac{(e^{− \frac{2πiu}{n}} − 1) · (e^{\frac{2πiv}{n}} − 1)}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} · f̂(u, v)e_{uv}∥_{p} ≤ O(p) · ∥f ∥_{p}.  (25)

To prove inequalities (24) and (25) we will assume that n is odd (all of our results are valid for even n as well, and the proofs in this case require minor modifications). We think of _{n}^{2} as [−(n−1)/2, (n−1)/2]^{2}∩ ^{2}. As before, given m : _{n}^{2} → we denote

∂_{1}m(x, y) = m(x + 1, y) − m(x, y), and ∂_{2}m(x, y) = m(x, y + 1) − m(x, y).

Thus

∂_{1}^{2}m(x, y) = m(x + 2, y) − 2m(x + 1, y) + m(x, y) and ∂_{2}^{2}m(x, y) = m(x, y + 2) − 2m(x, y + 1) + m(x, y),

and

∂_{1}∂_{2}m(x, y) = ∂_{2}∂_{1}m(x, y) = m(x + 1, y + 1) − m(x + 1, y) − m(x, y + 1) + m(x, y).

In what follows we think of m as a Fourier multiplier in the sense that it corresponds to a translation invariant operator T_{m} on L_{2} ( _{n}^{2}) given by

T_{m}(f) ∑_{(u,v)∈ _{n}^{2}} m(u, v) · f̂(u, v) · e_{uv}.  (26)

Recall that an operator T : L_{1} ( _{n}^{2}) → L_{1} ( _{n}^{2}) is said to be weak (1, 1) with constant K if for every f : _{n}^{2} → and every a > 0,

|\{((u, v) ∈ _{n}^{2} : |Tf (u, v)| ≥ a\}| ≤ \frac{K}{a} · ∥f ∥_{1} = \frac{K}{a} · ∑_{(u,v)∈ _{n}^{2}} |f (u, v)|.

We will use the following discrete version of the Hörmander-Mihlin multiplier theorem [38, 18].

Theorem 4.1 (Hörmander-Mihlin multiplier criterion on _{n}^{2}). For j ∈ denote Q_{j} = [−2^{j}, 2^{j}] × [−2^{j}, 2^{j}]. Fix B > 0 and m : _{n}^{2} → with m(0, 0) = 0, and assume that for all j = 0, 1, …, ⌊log_{2}(n − 1)⌋ − 1,

∑_{(u,v)∈(Q_{j}\Q_{j−1} )∩ _{n}^{2}} [2^{−2j} |m(u, v)|^{2} + |∂_{1}m(u, v)|^{2} + |∂_{2}m(u, v)|^{2}+
2^{2j}|∂_{1}^{2}m(u, v)|^{2} + 2^{2j}|∂_{2}^{2}m(u, v)|^{2} + 2^{2j}|∂_{1}∂_{2}m(u, v)|^{2}] ≤ B^{2}.

Then the translation invariant operator T_{m} corresponding to m is weak (1, 1) with constant O(B).

While the continuous version of the Hörmander-Mihlin multiplier theorem is a powerful tool which appears in several texts (e.g. in the books [12, 48, 52]), we could not locate a statement of the above discrete version in the literature. It is, however, possible to prove it using several minor modifications of the existing proofs. The standard proof of the Hörmander-Mihlin criterion is usually split into two parts. The first part, which is based on the Calderón-Zygmund decomposition, transfers virtually verbatim to the discrete settingsee Theorem 3 in Chapter 1 of [48], and Remark 8.1 there which explains how this part of the proof transfers from ^{n} to the setting of finitely generated groups of polynomial growth (in fact, the Calderón-Zygmund decomposition itself, as presented in Theorem 2 in Chapter 1 of [48], is valid in the setting of general metric spaces equipped with a doubling measure). The second part of the proof of the Hörmander-Mihlin theorem, as presented in Theorem 2.5 of [18], requires several straightforward modifications in order to pass to the discrete setting. We leave the simple details to the reader. For the sake of readers that are not familiar with these aspects of Fourier analysis, we will later present a complete reduction to a continuous problem whose proof appears in print, which yields slightly worse bounds on the distortion guarantee.

In order to apply Theorem 4.1 we consider the following two multipliers,

m_{1}(u, v) \frac{|e^{\frac{2πiu}{n}} − 1|^{2}}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}} , and m_{2}(u, v) \frac{(e^{− \frac{2πiu}{n}} − 1) · (e^{\frac{2πiv}{n}} − 1)}{|e^{\frac{2πiu}{n}} − 1|^{2} + |e^{\frac{2πiv}{n}} − 1|^{2}},  (27)

where we set m_{1}(0, 0) = m_{2}(0, 0) = 0. A direct (albeit tedious!) computation shows that m_{1} and m_{2} satisfy the conditions of Theorem 4.1 with B = O(1). Thus, the operators T_{m_{1}} and T_{m_{2}} are weak (1, 1) with constant O(1). Since m_{1} and m_{2} are bounded functions, the operator norms ∥T_{m_{1}}∥_{L_{2}( _{n}^{2})→L_{2}( _{n}^{2})} and ∥T_{m_{2}}∥_{L_{2}( _{n}^{2})→L_{2}( _{n}^{2})} are O(1). Since these operators are self adjoint, by the Marcinkiewicz interpolation theorem (see [56]) it follows that for p ≥ 2, the operator norms ∥T_{m_{1}}∥_{L_{p}( _{n}^{2})→L_{p}( _{n}^{2})} and ∥T_{m_{2}}∥_{L_{p}( _{n}^{2})→L_{p}( _{n}^{2})} are O(p). This is precisely (24) and (25).

The above argument is based on Theorem 4.1, which does not appear exactly as stated in the literature, but its proof is a straightforward adaptation of existing proofs (which is too simple to justify rewriting the lengthy argument here). However, making the necessary changes easily does require some familiarity with Calderón-Zygmund theory. We therefore present now another argument which gives a polylog(n) bound on the distortion, but uses only statements which appear in the literature. This alternative approach appears to be quite versatile, and might be useful elsewhere.

The following lemma reduces the problem of proving inequalities such as (24) and (25) (with perhaps a different dependence on p) to a continuous inequality. The argument is based on the proof of a theorem of Marcinkiewicz from [56] (see Theorem 7.5 in chapter X there). In what follows we denote by the Euclidean unit circle in the plane.

Proposition 4.2 (Transferring multipliers from the torus to _{n}^{2}). Fix an odd integer n. Let {λ(u, v)}_{u,v=0}^{∞} be complex numbers such that λ(u, v) = 0 for max{u, v} ≥ n. Consider the operators M : L_{p} ( ^{2}) → L_{p} ( ^{2}) and M_{n} : L_{p} ( _{n}^{2}) → L_{p} ( _{n}^{2}) given by

M ( ∑_{u,v=−∞}^{∞} f̂(u, v)e^{2πi(ux+vy)})= ∑_{u,v=0}^{∞}λ(u, v)f̂(u, v)e^{2πi(ux+vy)},

and

M_{n} (∑_{u,v=0}^{n−1} f̂(u, v)e^{\frac{2πi}{n}(ua+vb)})= ∑_{u,v=0}^{n−1}λ(u, v)f̂(u, v)e^{\frac{2πi}{n}(ua+vb)}.

Then,

∥M_{n}∥_{L_{p}( _{n}^{2})→L_{p}( _{n}^{2})} ≤ 81 · ∥M∥_{L_{p}( ^{2})→L_{p}( ^{2})} .

Proof. The proof is a variant of the first part of the proof of Theorem 7.5 in chapter X in [56], and a small twist on the second part. Since the terminology in [56] is different from ours, we repeat the proof of the first part as well. Recall that the Dirichlet kernels D_{ℓ} : [0, 1] → are defined as

D_{ℓ}(x) = ∑_{j=−ℓ}^{ℓ} e^{2πijx},

and the Fejér kernels K_{m}: [0, 1] → are

K_{m}(x) = \frac{1}{m + 1} ∑_{ℓ=0}^{m} D_{ℓ}x = ∑_{j=−m}^{m} (1 − \frac{|j|}{m + 1}) e^{2πijx}.

A basic property of D_{ℓ} is that for any trigonometric polynomial S(x) of degree at most ℓ, namely S(x) = ∑ _{j=−ℓ}^{ℓ} a_{j}e^{2πijx}, we have that S(x) = S∗D_{ℓ}(x) = ∫_{0}^{1} S(t)D_{ℓ}(x−t)dt. The same is true with any other function all of whose jth Fourier coefficients for j between −ℓ and ℓ are 1; in particular for the de la Vallée Poussin kernel 2K_{2ℓ−1} − K_{ℓ−1} (see [29]). The well known advantage of the Fejér kernel over the Dirichlet kernel is that it is everywhere (real and) nonnegative. Note also that ∫_{0}^{1} K_{m}(t)dt = 1 for all m. Thus, by convexity of the function t^{p}, for any trigonometric polynomial S of degree at most ℓ, and for all x ∈ [0, 1],

|S(x)|^{p} = |2S ∗ K_{2ℓ−1}(x) − S ∗ K_{ℓ}(x)|^{p}
≤ 3^{p} (\frac{2}{3} ∫ _{0}^{1} |S(t)|^{p}K_{2ℓ−1}(x − t)dt + \frac{1}{3} ∫ _{0}^{1} |S(t)|^{p}K_{ℓ−1}(x − t)dt) .  (28)

Let now ω_{2ℓ+1} be the measure which assign mass \frac{1}{2ℓ+1} to each of 2ℓ + 1 equally spaced points on [0, 1]. Then it is easy to check that

∫ _{0}^{1} K_{m}(x − t)dω_{2ℓ+1}(x) = ∫ _{0}^{1} K_{m}(x − t)dx = 1

for all m ≤ 2ℓ and for all t ∈ [0, 1]. Integrating (28) with respect to ω_{2ℓ+1}, we get that for any trigonometric polynomial S of degree at most ℓ

∫ _{0}^{1} |S(x)|^{p}dω_{2ℓ+1}(x) ≤ 3^{p} ∫ _{0}^{1} |S(x)|^{p}dx.  (29)

It follows that if S(x, y) is a two-variable trigonometric polynomial of degree at most ℓ in each of the variables, i.e. S(x, y) = ∑ _{u,v=−ℓ}^{ℓ} a_{uv}e^{2πi(ux+vy)},

∫_{[0,1]^{2}} |S(x, y)|^{p}dω_{2ℓ+1}(x)dω_{2ℓ+1}(y) ≤ 9^{p} ∫_{[0,1]^{2}} |S(x, y)|^{p}dxdy.

It follows from this that, since n is odd, for every f ∈ L_{p} ( ^{2}),

∥M_{n} (∑_{u,v=0}^{n−1} f̂(u, v)e^{\frac{2πi}{n}(ua+vb)})∥_{L_{p}( _{n}^{2})} ≤ 9 ∥M ( ∑_{u,v=−∞}^{∞} f̂(u, v)e^{2πi(ux+vy)})∥_{L_{p}( ^{2})} .

Note that for each trigonometric polynomial of the form P(x, y) = ∑ _{u,v=−n+1}^{n−1} a_{uv}e^{2πi(ux+vy)},

∫_{[0,1]^{2}} P(x, y)dω_{n}(x)dω_{n}(y) = a_{0} = ∫_{[0,1]^{2}} P(x, y)dxdy.

Fix f ∈ L_{p} ( _{n}^{2}), 1 < p < ∞. By the first part of the proof and duality, there is g ∈ L_{p^{∗}}( ^{2}) (p^{∗} = p/(p − 1)) with ∥g∥_{p^{∗}} = 1 such that

∥M_{n}f ∥_{L_{p}( _{n}^{2})} ≤ 9 ∫_{[0,1]^{2}} (∑_{u,v=0}^{n−1}λ_{j} f̂(u, v)e^{2πi(ux+vy)})\overline{g(x, y)}dxdy

= 9 ∫_{[0,1]^{2}} (∑_{u,v=0}^{n−1}λ(u, v)f̂(u, v)e^{2πi(ux+vy)})(∑_{u,v=0}^{n−1}\overline{ĝ(u, v)}e^{−2πi(ux+vy)})dxdy

= 9 ∫_{[0,1]^{2}} (∑_{u,v=0}^{n−1}λ(u, v)f̂(u, v)e^{2πi(ux+vy)})(∑_{u,v=0}^{n−1}\overline{ĝ(u, v)}e^{−2πi(ux+vy)})dω_{n}(x)dω_{n}(y)

= 9 ∫_{[0,1]^{2}} (∑_{u,v=0}^{n−1} f̂(u, v)e^{2πi(ux+vy)})(∑_{u,v=0}^{n−1}λ(u, v)\overline{ĝ(u, v)}e^{−2πi(ux+vy)})dω_{n}(x)dω_{n}(y)

≤ 9 (∫_{[0,1]^{2}} |∑_{u,v=0}^{n−1} f̂(u, v)e^{2πi(ux+vy)}|^{p} dω_{n}(x)dω_{n}(y))^{1/p} ·

(∫_{[0,1]^{2}} |∑_{u,v=0}^{n−1}λ(u, v)\overline{ĝ(u, v)}e^{−2πi(ux+vy)}|^{p^{∗}} dω_{n}(x)ω_{n}(y))^{1/p^{∗}}

≤ 81 · ∥f ∥_{L_{p}( _{n}^{2})} (∫_{[0,1]^{2}} |∑_{u,v=0}^{n−1} \overline{λ(u, v)}ĝ(u, v)e^{2πi(ux+vy)}|^{p^{∗}} dx)^{1/p^{∗}}
≤ 81 · ∥f ∥_{L_{p}( _{n}^{2})} · ∥M∥_{L_{p}( ^{2})→L_{p}( ^{2})} .

where the inequality before last follows from (29) and the last inequality (that is the fact that the norm of a multiplier in L_{p} ( ^{2}) is the same as the norm of the conjugate multiplier in L_{p^{∗}} ( ^{2})) follows from duality. The case p = 1 (and also a similar inequality for the ∞ norm) follows easily from the L_{p} cases.

Proposition 4.2 implies that it is enough to obtain L_{p} to L_{p} bounds for the operators T_{m_{1}} and T_{m_{2}}, where m_{1}, m_{2} are as in (27), as operators on functions on the torus ^{2}. By a theorem of de Leeuw [11] it is enough to obtain such bounds when we think of T_{m_{1}} and T_{m_{2}} as operators on functions on ^{2} (see [55] for the respective result in the case of weak (1, 1) bounds). The continuous version of the Hörmander-Mihlin multiplier theorem now applies, but unfortunately its conditions are not satisfied. However, a (once again tedious) computation shows it is possible to apply the Marcinkiewicz multiplier theorem (see [47, 52]), in combination with bounds on the Hilbert transform [47, 52], to obtain bounds similar to (24) and (25) with O(p) replaced by O(poly(p)) (it is quite easy to obtain a bound of O(p^{3}), and with more work this can be reduced to O(p^{2}). However we do not see a simple way to obtain O(p) using this approach).

Remark 4.1. Consider the mapping S : 𝒫_{_{n}^{2}} → L_{1} ( _{n}^{2}) given by

Sμ ∑_{(u,v)∈ _{n}^{2}\\{(0,0)\}}(|e^{\frac{2πiu}{n}} − 1| + |e^{\frac{2πiv}{n}} − 1|) · μ̂(u, v)e_{uv}.

Using considerations similar to the above (see Proposition III.A.3 in [54] for a continuous counterpart) it is possible to show that S has distortion O(polylog(n)). However, we were unable to get this bound down to O(logn) as in Theorem 1.4. Nevertheless, this embedding might be of interest since it reduces the dimension of the ambient L_{1} space by a factor of 2.

5 Discussion and open problems

There are several interesting problems that arise from the results presented in this paper- we shall discuss some of them in the list below.

1. The most natural problem is to determine the asymptotic behavior of c_{1} ({0, 1 …, n}^{2}, τ) . It seems hard to use the ideas in Section 4 to obtain an embedding of distortion O ( \sqrt{logn}), as the known bounds on multipliers usually give a weak (1, 1) inequality at best. We do not know what is the actual distortion of the embedding in Theorem 1.4.

2. Remark 4.1 implies that the Banach-Mazur distance between the n^{2} − 1 dimensional normed space ℳ_{_{n}^{2},τ} and ℓ_{1}^{n^{2}−1} is O(polylog(n)). It would be interesting to determine the asymptotic behavior of this distance. In particular, it isn’t clear whether the L_{1} (embedding) distortion of ℳ_{_{n}^{2},τ} behaves differently from its Banach-Mazur distance from ℓ_{1}^{n^{2}−1}.

3. We did not attempt to study the L_{1} distortion of ℳ_{{0,1,...,n}^{d},τ}for d ≥ 3. Observe that this space contains ℳ_{\{0,1,...,n\}^{2},τ}, so the Ω ( \sqrt{logn})lower bound still applies. But the result of [30] shows that the transportation cost metric on the Hamming cube {0, 1}^{d} has distortion Θ(d), so some improvements are still possible. Note that in higher dimensions it becomes interesting to study the transportation cost distance when ^{d} is equipped with other norms. The Banach-Mazur distance between ℓ_{1}^{d} and arbitrary d-dimensional norms has been studied in [7, 49, 13]. In particular, the result of [13] states that any d-dimensional Banach space is at distance O (d^{5/6}) from ℓ_{1}^{d}. Combining this fact with the lower bound on the L_{1} distortion of the transportation cost distance on the Hamming (ℓ_{1}) cube cited above, we see that for any norm ∥ · ∥ on ^{d}, c_{1} (𝒫_{( ^{d},∥·∥),τ}) = Ω (d^{1/6}). It would be interesting to study the dependence on d for general norms on ^{d}.

4. As stated in Remark 3.2, it would be interesting to study the rate with which c_{2} (𝒫_{\{0,...,n\}^{2}}, \sqrt{τ}) tends to infinity.

5. As stated in Remark 3.3, we do not know whether (𝒫_{[0,1]^{2}}, τ) admits a uniform embedding into Hilbert space.

6. The present paper rules out the “low distortion approach” to nearest neighbor search in the Earthmover metric via embeddings into L_{1}. However, it might still be possible to find nearest neighbor preserving embeddings into L_{1} in the sense of [25].

7. On the more “applied side”, as stated in the introduction, there is a possibility that the embedding of Theorem 1.4 behaves better than the theoretical distortion guarantee of O(logn) in “real life” situations, since it is often the case that the bulk of the Fourier spectrum is concentrated on a sparse set of frequencies. Additionally, it might be worthwhile to “thin out” some frequencies of the given set of images before embedding into L_{1} (and then using the known L_{1} nearest neighbor search databases). It would be interesting to carry out such “tweaking” of our algorithm in a more experimental setting.

Acknowledgements. We are grateful to David Jerison and Terence Tao for several helpful suggestions. The first named author wishes to thank Piotr Indyk for his encouragement to work on the planar Earthmover problem. We also thank Guillaume Aubrun for correcting several mistakes in our original manuscript. This work was carried out while the second named author was a long-term visitor at the Theory Group of Microsoft Research.

References

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

[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] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 553–562, New York, NY, USA, 2005. ACM Press.

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

[5] E. Berkson, J. Bourgain, A. Pe�czynski, and M. Wojciechowski. Canonical Sobolev projections of weak type (1, 1). Mem. Amer. Math. Soc., 150(714):viii+75, 2001.

[6] J. Bourgain. Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157–167. Springer, Berlin, 1987.

[7] J. Bourgain and S. J. Szarek. The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization. Israel J. Math., 62(2):169–180, 1988.

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

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

[10] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on pstable distributions. In SoCG ’04: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pages 253–262, New York, NY, USA, 2004. ACM Press.

[11] K. de Leeuw. On L_{p} multipliers. Ann. of Math. (2), 81:364–379, 1965.

[12] J. García-Cuerva and J. L. Rubio de Francia. Weighted norm inequalities and related topics, volume 116 of North-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1985. Notas de Matemática [Mathematical Notes], 104.

[13] A. Giannopoulos. A note on the Banach-Mazur distance to the cube. In Lindenstrauss, J. (ed.) et al., Geometric aspects of functional analysis. Israel seminar (GAFA) 1992-94. Basel: Birkhauser. Oper. Theory, Adv. Appl. 77, 67-73 . 1995.

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

[15] L. J. Guibas, Y. Rubner, and C. Tomassi. A metric for distributions with applications to image databases. In ICCV ’98: Proceedings of the Sixth International Conference on Computer Vision, pages 59–66, 2003.

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

[17] S. Heinrich and P. Mankiewicz. Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces. Studia Math., 73(3):225–251, 1982.

[18] L. Hörmander. Estimates for translation invariant operators in L^{p} spaces. Acta Math., 104:93–140, 1960.

[19] P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In 42nd Annual Symposium on Foundations of Computer Science, pages 10–33. IEEE Computer Society, 2001.

[20] P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In 41st Annual Symposium on Foundations of Computer Science, pages 189–197. IEEE Computer Society, 2001.

[21] P. Indyk. Algorithms for dynamic geometric problems over data streams. In STOC ’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 373–380, New York, NY, USA, 2004. ACM Press.

[22] P. Indyk. Nearest neighbors in high-dimensional spaces. In Handbook of discrete and computational geometry, second edition, pages 877–892. CRC Press, Inc., Boca Raton, FL, USA, 2004.

[23] P. Indyk and J. Matoušek. Low distortion embeddings of finite metric spaces. In Handbook of discrete and computational geometry, second edition, pages 177–196. CRC Press, Inc., Boca Raton, FL, USA, 2004.

[24] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC ’98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 604–613, New York, NY, USA, 1998. ACM Press.

[25] P. Indyk and A. Naor. Nearest neighbor preserving embeddings. Manuscript. Available at

http://research.microsoft.com/research/theory/naor/homepage%20files/lowdim-journal.pdf, 2005.

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

[27] S. Kakutani. Concrete representation of abstract (L)-spaces and the mean ergodic theorem. Ann. Math. (2), 42:523–537, 1941.

[28] N. J. Kalton. Banach spaces embedding into L_{0}. Israel J. Math., 52(4):305–319, 1985.

[29] Y. Katznelson. An introduction to harmonic analysis. Cambridge Mathematical Library. Cambridge University Press, Cambridge, third edition, 2004.

[30] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4):821–852, 2006.

[31] S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into L_{1}. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 53–62.

[32] S. Kislyakov. Sobolev imbedding operators and the nonisomorphism of certain Banach spaces. Funct. Anal. Appl., 9:290–294, 1975.

[33] J. Lindenstrauss and H. P. Rosenthal. The ℒ_{p} spaces. Israel J. Math., 7:325–349, 1969.

[34] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin, 1979. Function spaces.

[35] J. Matoušek. Open problems on embeddings of finite metric spaces. Available at http://kam.mff.

    cuni.cz/^{∼}matousek/metrop.ps.gz.

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

[37] M. Mendel and A. Naor. Metric cotype. To appear in Ann. Math., 2005.

[38] S. G. Mihlin. On the multipliers of Fourier integrals. Dokl. Akad. Nauk SSSR (N.S.), 109:701–703, 1956.

[39] E. M. Nikišin. A resonance theorem and series in eigenfunctions of the Laplace operator. Izv. Akad. Nauk SSSR Ser. Mat., 36:795–813, 1972.

[40] A. Pelczynski. Boundedness of the canonical projection for Sobolev spaces generated by finite families of linear differential operators. In Analysis at Urbana. Vol. 1: Analysis in function spaces, Proc. Spec. Year Mod. Anal./Ill. 1986-87, Lond. Math. Soc. Lect. Note Ser. 137, 395-415 . 1989.

[41] A. Pe�czyński and M. Wojciechowski. Sobolev spaces. In Handbook of the geometry of Banach spaces, Vol. 2, pages 1361–1423. North-Holland, Amsterdam, 2003.

[42] S. Peleg, M. Werman, and H. Rom. A unified approach to the change of resolution: space and graylevel. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(7):739–742, 1989.

[43] N. L. Randrianarivony. Characterization of quasi-Banach spaces which coarsely embed into a Hilbert space. Proc. Amer. Math. Soc., 134(5):1315–1317 (electronic), 2006.

[44] M. Ribe. On uniformly homeomorphic normed spaces. Ark. Mat., 14:237–244, 1976.

[45] D. N. Rockmore. Efficient computation of Fourier inversion for finite groups. J. Assoc. Comput. Mach., 41(1):31–66, 1994.

[46] W. Rudin. Real and complex analysis. 3rd ed. New York, NY: McGraw-Hill., 1987.

[47] E. Stein. Singular integrals and differentiability properties of functions. Princeton University Press. XIV. Princeton, N.J. , 1970.

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

[49] S. J. Szarek and M. Talagrand. An “isomorphic” version of the Sauer-Shelah lemma and the Banach-Mazur distance to the cube. In Geometric aspects of functional analysis (1987–88), volume 1376 of Lecture Notes in Math., pages 105–112. Springer, Berlin, 1989.

[50] M. Talagrand. Embedding subspaces of L_{1} into l_{1}^{N}. Proc. Amer. Math. Soc., 108(2):363–369, 1990.

[51] N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow, 1989.

[52] A. Torchinsky. Real-variable methods in harmonic analysis. Dover Publications Inc., Mineola, NY, 2004. Reprint of the 1986 original [Dover, New York; MR0869816].

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

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

[55] K. Woźniakowski. A new proof of the restriction theorem for weak type (1, 1) multipliers on R^{n}. Illinois J. Math., 40(3):479–483, 1996.

[56] A. Zygmund. Trigonometric series. Volumes I and II combined. With a foreword by Robert Fefferman. 3rd ed. Cambridge Mathematical Library. Cambridge: Cambridge University Press. xiii, 2002.