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 .

Theorem 5 (Lee, Sidiropoulos)There exists a doubling space and -point subsets such that

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