L_p metrics on the Heisenberg group and the Goemans-Linial conjecture

We prove that the function d : R³ x R³ → [0, ∞) given by d((x, y, z), (t, u, v)) = ( [((i - x)² + (u - y)²f +(v - z + 2xu - 2yt)²]^1/2 + (t - x) ² + (u - y)²)^1/2. is a metric on ℝ³ such that (ℝ³, √d) is isometric to a subset of Hubert space, yet (R³, d) does not admit a bi-Lipschitz embedding into L₁. This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the semidefinite relaxation of the Sparsest Cut problem. The metric above is doubling, and hence has a padded stochastic decomposition at every scale. We also study the L_p version of this problem, and obtain a counter example to a natural generalization of a classical theorem of Bretagnolle, Dacunha-Castelle and Krivine (of which the Goemans-Linial conjecture is a particular case). Our methods involve Fourier analytic techniques, and a recent breakthrough of Cheeger and Kleiner, together with classical results of Pansu on the differentiability of Lipschitz functions on the Heisenberg group.