Last time, we were discussing , -metrics and negative type metrics. is negative type if is an -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 . This motivated the Goemans-Linial conjecture, which turned out to be false. Khot and Vishnoi’s examples show that . Whereas Arora-Lee-Naor show that
1. Khot and Vishnoi’s counterexample to Goemans-Linial conjecture
Let . Let be the cyclic group acting on by ciclically permuting coordinates. Consider the quotient metric space , i.e.
Theorem 1 (Khot, Vishnoi)
The heart of the proof is the Kahn-Kalai-Linial theorem.
It is not hard to show that , i.e. . This works for every group action which is transitive on coordinates, provided .
A priori, there need not be a NEG metric which is equivalent to . Fact: If and the square of the Euclidean metric restricted on is a metric, then . 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 to in Khot and Vishnoi’s proof.
Theorem 2 (Lee-Moharrami) There is a metric space such that but does not admit an equivalent metric of negative type.
In fact, the example is an -point space whose distance to is . 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 be the Heisenberg group. For the discrete version , 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 .
Stephen Semmes showed that 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. as a negative type metric
Theorem 3 (Lee, Naor) admits an equivalent left invariant metric of negative type, and the implied constant is independant on .
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 , and .
Bartholdi: Would this work for a step nilpotent group ? The center is even more distorted, and the square root could not absorb it. Answer:
2.3. Intuition about -metrics
Why do we believe this might be hard to embed to ? Recall the cut characterization: If , there is a measure on the set of subsets of such that
This follows from
which implies that embeds isometrically into . The embedding of Euclidean plane into 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 , after rescaling, every half-space looks vertical, i.e. containing orbits of the center. So it seems hard to have in .
2.4. Non embeddability results
Theorem 4 (Cheeger, Kleiner, Naor) Cheeger, Kleiner 2006: does not bilipschitz embed into . With Naor, 2010, a different proof gives: Every embedding of the -ball of in encurs distorsion .
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 is almost everywhere differentiable. Being differentiable at means that the limit
exists and is a group homomorphism.
Corollary 7 (Semmes) No bilipschitz maps .
Proof: The derivative is bilipschitz. Furthermore, it satisfies , thus , contradiction.
3.2. Metric differentiation
The starting point is differentiation along a path.
Definition 8 (Eskin, Fisher, Whyte) Let be a metric space. Let be a length segment. Say is -efficient if triangle inequality is almost an equality, i.e.
Theorem 9 (Eskin, Fisher, Whyte, Lee, Raghavendra) Let be a metric space. For every and there is an such that for every -Lipschitz map , for at least -fraction of -term arithmetic progressions in , is -efficient on .
Proof: If does not work for -progressions of step , then examine -progressions of set , and so on. If it always fails, the length of must me infinite.
Let be -efficient. Say a cut of is monotone if it is not an interval starting at an endpoint. Then at most -fraction of the cuts (in the cut measure associated to ) are non-monotone. Indeed, if is not monotone, then cannot be better than -efficient.
3.3. Link to the planar -embedding problem
Question: Does every planar graph admit a bilipschitz embedding into ?
Known: Let be the bipartite graph. Then tends to as tends to . We improve this lower bound to .
Theorem 10 (Lee, Raghavendra) Let denote the iterated graph. Then
Proof: Apply differentiation (Theorem 9) to each of the paths in the graph, with .
3.4. Boosting distorsion from to
Let be -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 , 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 is constant in the vertical direction, contradiction.