Mathematics Colloquium
Quantitative Behavior of Lipschitz Maps from the Heisenberg Group to \(L^1\)
Speaker: Jeff Cheeger, New York University, Courant Institute of Mathematical Sciences
Location: Warren Weaver Hall 1302
Date: Monday, February 9, 2009, 3:45 p.m.
Synopsis:
Let \(\left ( X, d \right )\) denote a metric space and let \(\mathcal{C}\) denote a collection of metrics on \(X\) such that \({d}' \in \mathcal{C}\) implies \(c \cdot {d}' \in \mathcal{C}\), for any real number \(c > 0\). Put
$$\rho \left ( d, \mathcal{C} \right ) = \inf_{{d}' \in \mathcal{C}} \inf \left \{ c \mid {d}' \leq d \leq c \cdot {d}' \right \}.$$
Let \(\mathcal{L}\) denote the collection of metrics on \(X\) of the form, \({d}' \left ( x_1, x_2 \right ) = \left \| f \left ( x_1 \right ) - f \left ( x_2 \right ) \right \|_{L_1}\), for some map \(f : X \rightarrow L^1\) and let \(\mathcal{N}\) denote the collection of metrics \(\underline{d}\) on \(X\) such that \(\left ( X, \underline{d}^{\frac{1}{2}} \right )\) embeds isometrically in \(L^2\). It is easy to verify that \(\mathcal{C} \subset \mathcal{N}\), and so, \(\rho \left ( d , \mathcal{N} \right ) \leq \rho \left ( \mathcal{L} \right )\). If \(X\) is finite with cardinality \(n\), it was shown by Bourgain that \(\rho \left ( d , \mathcal{L} \right ) = O \left ( \log n \right )\), for any metric \(d\).
Although the problem of computing \(\rho \left ( d , \mathcal{L} \right )\) exactly is equivalent to various other fundamental problems for which there is believed to be no polynomial time algorithm, there is a polynomial time algorithm for computing \(\rho \left ( d , \mathcal{N} \right )\). Goemans and Linial conjectured that for some universal constant \(C > 0\), independent of \(n\),
$$\rho \left ( d , \mathcal{N} \right ) \leq C \cdot \rho \left ( d , \mathcal{L} \right ).$$
Their conjecture was refuted by Khot-Vishnoi (2005) who gave a sequence of examples for which the best \(C\) grows at least like a constant times \(\log \log n\). We will discuss a very different sequence based on the Heisenberg group, for which \(C\) grows at least like \(\left ( \log n \right )^{a}\), for some explicit \(a > 0\). This is joint work with Kleiner and Naor. It is an outgrowth of earlier work of Lee-Naor and Cheeger-Kleiner.