{"id":"arxiv/2602.19434","url":"https://arxiv.org/abs/2602.19434","tags":["math.FA","cs.CG","math.MG"],"score":0,"title":"$L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids","domain":"math.FA","source":"arxiv","authors":["Chris Gartland","Mikhail Ostrovskii","Yuval Rabani","Robert Young"],"reviews":0,"subject":"math.FA","summary":"We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\\{1,\\dots m\\}^d$ is $Ω(\\log N)$, where $N$ is the number of vertices and the implicit constant is universal (in particular, independent of dimension). This lower bound matches the universal upper bound $O(\\log N)$ holding for any $N$-point metric space. Our proof relies on a new Sobolev inequality for real-valued functions on the grid, based on random measures supported on dyadic cubes.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-23","reactions":{}}