In "Snowflake universality of Wasserstein spaces"" by Alexandr Andoni, Assaf Naor, and Ofer Neiman, they have the following notation:

  • For a metric space X they write $\mathcal{P}_1(X)$ to denote $1$-Wasserstein space over $X$ aka Earthmover space aka Kantorovich-Rubinstein space etc.
  • $\mathcal{Z} = (\operatorname{Lip}([0,1]^2))^*$ is a dual of real-valued Lipschitz functions on the square $[0,1]^2$. (I assume that we always take the Lipschitz constant as the norm on Lipschitz functions.)

And they mention the following thing that I fail to understand:

As explained in [71], every finite subset of $\mathcal{Z}$ embeds into $\mathcal{P}_1(\mathbb{R}^2)$ with distortion arbitrarily close to 1,...

[71] A. Naor and G. Schechtman. Planar earthmover is not in L1. SIAM J. Comput., 37(3):804–826 (electronic), 2007.

From [71] I learned that by applying Kantorovich duality we can get that if $X$ is finite then every finite subset of $(\operatorname{Lip}_0(X))^*$ embeds into $\mathcal{P}_1(X)$ with distortion arbitrarily close to 1. (Here $\operatorname{Lip}_0(X)$ is the space of Lipschitz functions which are $0$ at some fixed point $x_0$.)

It feels like the argument should be that for a given finite subset of $\mathcal{Z}$ and a fixed D > 1 we are able to embed it with distortion < D into $(\operatorname{Lip}_0(\mathcal{N}))^*$, where $\mathcal{N}$ is a small net in $[0,1]^2$. But I can't figure it out or locate an argument in [71].


1 Answer 1


What the reference is saying is: for every finite metric space $X$, and every $D>0$, there is an embedding $f\colon (\left(\mathrm{Lip}_0(X)\right)^*\to \mathcal{P}_1(X)$ of distortion at most $D$.

Now suppose $X\subset \cal{Z}$ and observe that this induces an isometric embedding $\mathcal{P}_1(X) \to \mathcal{P}_1(\mathcal{Z})$ (every measure on $X$ is a convex combination of delta-measures, which make sense as measures on $\mathcal{Z}$ as well). In particular the low-distortion map $f$ above is also a low-distortion map into $\mathcal{P}_1(\mathcal{Z})$.

  • $\begingroup$ $\mathcal{P}_1(\mathcal{Z})$ is a monster space $\endgroup$ Commented Feb 16, 2021 at 23:15
  • $\begingroup$ The target space is much more modest in the claim. $\endgroup$ Commented Feb 16, 2021 at 23:21
  • $\begingroup$ Hey Lior, thanks for thinking about the thing and replying. $\endgroup$ Commented Feb 16, 2021 at 23:29
  • $\begingroup$ Sorry -- my answer is totally wrong. I'll try fixing it. $\endgroup$ Commented Feb 17, 2021 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.