Differentiating maps into $L^1$, and the geometry of $\rm BV$ functions

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

Authors

Jeff Cheeger

Courant Institute of Mathematical Sciences
251 Mercer Street
New York, NY 10012
United States

Bruce Kleiner

Courant Institute of Mathematical Sciences
251 Mercer Street
New York, NY 10012
United States