Notes of James Lee’s lecture nr 6

Last time, we were discussing ${L_1}$, ${L_2}$-metrics and negative type metrics. ${d}$ is negative type if ${\sqrt{d}}$ is an ${L_2}$-metric. Such metrics are handy since optimizing linear criteria over the space of negative type metrics is doable.

Negative type Banach spaces embed linearly and isometrically in ${L^1}$. This motivated the Goemans-Linial conjecture, which turned out to be false. Khot and Vishnoi’s examples show that ${D_n (NEG,L_1 )\geq \Omega(\log\log n)}$. Whereas Arora-Lee-Naor show that ${D_n (NEG,L_1 )\leq O(\log\log n)}$

1. Khot and Vishnoi’s counterexample to Goemans-Linial conjecture

Let ${X=\{ 0,1 \}^k}$. Let ${G={\mathbb Z}/k{\mathbb Z}}$ be the cyclic group acting on ${X}$ by ciclically permuting coordinates. Consider the quotient metric space ${Y=X/G}$, i.e.

$\displaystyle \begin{array}{rcl} d_Y (Gx,Gy)=\min_{g\in G}d_X (x,gy). \end{array}$

Theorem 1 (Khot, Vishnoi)

$\displaystyle \begin{array}{rcl} c_1 (X/G)\geq \Omega(\log k)=\Omega(\log\log|X/G|). \end{array}$

The heart of the proof is the Kahn-Kalai-Linial theorem.

It is not hard to show that ${c_2 (X/G,\sqrt{d_{X/G}})\leq O(1)}$, i.e. ${X/G \in \widetilde{NEG}}$. This works for every group action which is transitive on coordinates, provided ${|G|=poly(k)}$.

A priori, there need not be a NEG metric which is equivalent to ${d_{X/G}}$. Fact: If ${X\subset {\mathbb R}^k}$ and the square of the Euclidean metric restricted on ${X}$ is a metric, then ${|X|\leq 2^k}$. So to obtain such a metric, one has to go to high dimension, i.e. do something non trivial. Thus there is an uneasy reduction form ${\widetilde{NEG}}$ to ${NEG}$ in Khot and Vishnoi’s proof.

Theorem 2 (Lee-Moharrami) There is a metric space ${(X,d)}$ such that ${c_2 (X,\sqrt{d})\leq O(1)}$ but ${X}$ does not admit an equivalent metric of negative type.

In fact, the example is an ${n}$-point space whose distance to ${NEG}$ is ${\geq\Omega((\log n)^{1/4})}$. But it seems far from a group, or from any doubling space.

2. Cheeger and Kleiner’s counterexample to Goemans-Linial conjecture

2.1. The example

Let ${X=H^3 ({\mathbb R})=\{\begin{pmatrix} 1&x&z \\ 0 & 1&y 0&0&1 \end{pmatrix}\,;\,x,\,y\,z\in {\mathbb R}\}}$ be the Heisenberg group. For the discrete version ${H^3}$, replace real entries by integer entries. Pick a finite generating set to define a word metric. This is equivalent to the metric induced from the Carnot-Carathéodory metric on ${H^3 ({\mathbb R})}$.

Stephen Semmes showed that ${H^3 ({\mathbb R})}$ does not admit bilipschitz embeddings to Euclidean spaces (more generally, to Banach space having the Radon-Nykodym property, Cheeger-Kleiner, see Pisier’s course).

2.2. ${H^3}$ as a negative type metric

Theorem 3 (Lee, Naor) ${H^n}$ admits an equivalent left invariant metric of negative type, and the implied constant is independant on ${n}$.

We used the Schoenberg characterization of negative type metrics. It leads to several possible metrics, and it turns out that one of them works. It looks like a mixture of ${\ell_2}$, ${\ell_1}$ and ${\ell_4}$.

$\displaystyle \begin{array}{rcl} d((x,y,z),(u,v,t))=\left(((x-u)^2 +(y-v)^2 + (2xv-2yu)^2)^2 +|z-t|\right)^{1/2}. \end{array}$

Bartholdi: Would this work for a step ${3}$ nilpotent group ? The center is even more distorted, and the square root could not absorb it. Answer:

2.3. Intuition about ${L_1}$-metrics

Why do we believe this might be hard to embed to ${L^1}$ ? Recall the cut characterization: If ${f:X\rightarrow L^1}$, there is a measure ${\mu}$ on the set of subsets of ${X}$ such that

$\displaystyle \begin{array}{rcl} |f(x)-f(y)|_1 =\int |1_S (x)-1_S (y)|\,d\mu(S). \end{array}$

This follows from

$\displaystyle \begin{array}{rcl} |x-y|=\int |1_{(-\infty,t]} (x)-1_{(-\infty,t]} (y)|\,dt \end{array}$

which implies that ${t\mapsto 1_{(-\infty,t]}}$ embeds isometrically ${{\mathbb R}}$ into ${L^1}$. The embedding of Euclidean plane into ${L^1}$ comes from the family of linear cuts, i.e. half-planes, with the natural motion-invariant measure. This seems to require existence of half-planes in every direction. In ${H^3 ({\mathbb R})}$, after rescaling, every half-space looks vertical, i.e. containing orbits of the center. So it seems hard to have ${H^3}$ in ${L_1}$.

2.4. Non embeddability results

Theorem 4 (Cheeger, Kleiner, Naor) Cheeger, Kleiner 2006: ${H^3}$ does not bilipschitz embed into ${L_1}$. With Naor, 2010, a different proof gives: Every embedding of the ${n}$-ball of ${H^3}$ in ${L_1}$ encurs distorsion ${\geq /Omega((\log n)^{10^{-100}})}$.

Theorem 5 (Lee, Sidiropoulos) There exists a doubling space ${X}$ and ${n}$-point subsets ${X_n}$ such that

$\displaystyle \begin{array}{rcl} c_1 (X_n)\geq \Omega(\sqrt{\frac{\log n}{\log\log n}}). \end{array}$

3. On Cheeger and Kleiner’s proof

From the global information that the map is Lipschitz, one goes to a local information, using differentiation. This method seems to apply rather widely in geometric group theory, and even in metric geometry. We use it in the proof of Theorem 5.

3.1. Group differentiation

In the context of groups having dilations, the method is very close to ordinary differentiation.

Theorem 6 (Pansu) Every Lipschitz map ${f:H^3 ({\mathbb R})\rightarrow L_2}$ is almost everywhere differentiable. Being differentiable at ${g}$ means that the limit

$\displaystyle \begin{array}{rcl} D_g f (h):=\lim_{t\rightarrow 0}\frac{1}{t}(f(g\delta_t (h))-f(g)) \end{array}$

exists and is a group homomorphism.

Corollary 7 (Semmes) No bilipschitz maps ${H^3 ({\mathbb R})\rightarrow L_2}$.

Proof: The derivative is bilipschitz. Furthermore, it satisfies ${D_g (hk)=D_g (h)+D_g (k)=D_g (kh)}$, thus ${D_g (hkh^{-1}k^{-1})=0}$, contradiction. $\Box$

3.2. Metric differentiation

The starting point is differentiation along a path.

Definition 8 (Eskin, Fisher, Whyte) Let ${X}$ be a metric space. Let ${P_n =[n]}$ be a length ${n}$ segment. Say ${f:P_n \rightarrow X}$ is ${\epsilon}$-efficient if triangle inequality is almost an equality, i.e.

$\displaystyle \begin{array}{rcl} d(f(1),f(n))\leq \sum_{i=1}^{n-1}d(f(i),f(i+1)) \leq (1+\epsilon)d(f(1),f(n)). \end{array}$

Theorem 9 (Eskin, Fisher, Whyte, Lee, Raghavendra) Let ${X}$ be a metric space. For every ${k}$ and ${\delta>0}$ there is an ${n(k,\delta)}$ such that for every ${1}$-Lipschitz map ${f:P_n \rightarrow L_1}$, for at least ${1-\delta}$-fraction of ${k}$-term arithmetic progressions ${S}$ in ${[n]}$, ${f}$ is ${\epsilon}$-efficient on ${S}$.

Proof: If does not work for ${k}$-progressions of step ${1}$, then examine ${k}$-progressions of set ${1/k}$, and so on. If it always fails, the length of ${f}$ must me infinite. $\Box$

Let ${f:P_n \rightarrow L_1}$ be ${\epsilon}$-efficient. Say a cut of ${P_n}$ is monotone if it is not an interval starting at an endpoint. Then at most ${\epsilon}$-fraction of the cuts (in the cut measure associated to ${f}$) are non-monotone. Indeed, if ${S}$ is not monotone, then ${1_S}$ cannot be better than ${2}$-efficient.

3.3. Link to the planar ${L_1}$-embedding problem

Question: Does every planar graph admit a bilipschitz embedding into ${L^1}$ ?

Known: Let ${K_{2,n}}$ be the bipartite graph. Then ${c_1 (K_{2,n}}$ tends to ${\frac{3}{2}}$ as ${n}$ tends to ${\infty}$. We improve this lower bound to ${2}$.

Theorem 10 (Lee, Raghavendra) Let ${K_{2,n}^{\otimes k}}$ denote the iterated graph. Then

$\displaystyle \begin{array}{rcl} c_1 (K_{2,n}^{\otimes k})\rightarrow 2. \end{array}$

Proof: Apply differentiation (Theorem 9) to each of the ${ n^{2^k}}$ paths in the graph, with ${\delta=\frac{1}{n}}$. $\Box$

3.4. Boosting distorsion from ${2}$ to ${\infty}$

Let ${f:{\mathbb R}^2 \rightarrow L_1}$ be ${0}$-efficient. Almost all cuts (in the cut measure) are monotone with respect to almost all lines. Monotone sets are half-planes. So we recover the fact that Euclidean distance is the integral of linear cuts w.r.t. kinematic measure.

In ${H^3 ({\mathbb R})}$, consider the set of horizontal lines, i.e. (group)-translates of the horizontal plane at the identity matrix. This time, monotone sets are vertical half-spaces. Thus ${f}$ is constant in the vertical direction, contradiction.