Abstract
This is one of a series of papers examining the interplay between differentiation theory for Lipschitz maps $X\to V$ and bi-Lipschitz nonembeddability, where $X$ is a metric measure space and $V$ is a Banach space. Here, we consider the case $V=L^1$, where differentiability fails. We establish another kind of differentiability for certain $X$, including $\mathbb{R}^n$ and $\mathbb{H}$, the Heisenberg group with its Carnot-Carathéodory metric. It follows that $\mathbb{H}$ does not bi-Lipschitz embed into $L^1$, as conjectured by J. Lee and A. Naor. When combined with their work, this provides a natural counterexample to the Goemans-Linial conjecture in theoretical computer science; the first such counterexample was found by Khot-Vishnoi [KV05].
A key ingredient in the proof of our main theorem is a new connection between Lipschitz maps to $L^1$ and functions of bounded variation, which permits us to exploit results on the structure of BV functions on the Heisenberg group [FSSC01].
Full Article