Pythagorean powers of hypercubes

Naor, Assaf; Schechtman, Gideon

Annales de l'Institut Fourier, Tome 66 (2016) no. 3, pp. 1093-1116.

On montre que pour tout $n\in \mathbb{N}$, tout plongement dans $L_1$ de la puissance pythagoricienne $n$-ième du cube de Hamming de dimension $n$ admet une distortion qui est au moins un multiple de $\sqrt{n}$ par une constante. Pour cela on introduit un nouvel invariant bi-Lipschitz des espaces métriques, inspiré par une inégalité linéaire de Kwapień et Schütt (1989). C’est en évaluant ce nouvel invariant sur $L_1$ que l’on obtient l’énoncé ci-dessus. On explique le rapport avec le programme de Ribe, et on discute des questions ouvertes.

It is shown here that for every $n\in \mathbb{N}$, any embedding into $L_1$ of the $n$-fold Pythagorean power of the $n$-dimensional Hamming cube incurs distortion that is at least a constant multiple of $\sqrt{n}$. This is achieved through the introduction of a new bi-Lipschitz invariant of metric spaces that is inspired by a linear inequality of Kwapień and Schütt (1989). The new metric invariant is evaluated here for $L_1$, implying the above nonembeddability statement. Links to the Ribe program are discussed, as well as related open problems.

Classification : 46B85, 30L05
Keywords: metric embeddings, Ribe program
Mot clés : Plongements métriques, programme de Ribe

[1] Aharoni, I.; Maurey, B.; Mityagin, B. S. Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces, Israel J. Math., Volume 52 (1985) no. 3, pp. 251-265 | DOI

[2] Arora, Sanjeev; Lee, James R.; Naor, Assaf Euclidean distortion and the sparsest cut, J. Amer. Math. Soc., Volume 21 (2008) no. 1, p. 1-21 (electronic) | DOI

[3] Ball, Keith The Ribe programme, Astérisque (2013) no. 352, pp. Exp. No. 1047, viii, 147-159 (Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058)

[4] Benyamini, Yoav; Lindenstrauss, Joram Geometric nonlinear functional analysis. Vol. 1, American Mathematical Society Colloquium Publications, 48, American Mathematical Society, Providence, RI, 2000, xii+488 pages

[5] Bourgain, J.; Milman, V.; Wolfson, H. On type of metric spaces, Trans. Amer. Math. Soc., Volume 294 (1986) no. 1, pp. 295-317 | DOI

[6] Bretagnolle, Jean; Dacunha-Castelle, Didier; Krivine, Jean-Louis Lois stables et espaces $L^p$, Ann. Inst. H. Poincaré Sect. B (N.S.), Volume 2 (1965/1966), pp. 231-259

[7] Deza, Michel Marie; Laurent, Monique Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer-Verlag, Berlin, 1997, xii+587 pages | DOI

[8] Enflo, P. Uniform homeomorphisms between Banach spaces, Séminaire Maurey-Schwartz (1975–1976), Espaces $L^p$, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, Centre Math., École Polytech., Palaiseau, 1976, 7 pages

[9] Gromov, Mikhael Filling Riemannian manifolds, J. Differential Geom., Volume 18 (1983) no. 1, pp. 1-147 http://projecteuclid.org/euclid.jdg/1214509283

[10] Heinrich, S.; Mankiewicz, P. Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces, Studia Math., Volume 73 (1982) no. 3, pp. 225-251

[11] Heinrich, Stefan Ultraproducts in Banach space theory, J. Reine Angew. Math., Volume 313 (1980), pp. 72-104 | DOI

[12] Johnson, William B.; Randrianarivony, N. Lovasoa $l_p(p>2)$ does not coarsely embed into a Hilbert space, Proc. Amer. Math. Soc., Volume 134 (2006) no. 4, p. 1045-1050 (electronic) | DOI

[13] Kadecʼ, M. Ĭ. Linear dimension of the spaces $L_p$ and $l_q$, Uspehi Mat. Nauk, Volume 13 (1958) no. 6 (84), pp. 95-98

[14] Kalton, N. J. Banach spaces embedding into $L_0$, Israel J. Math., Volume 52 (1985) no. 4, pp. 305-319 | DOI

[15] Kwapień, Stanisław; Schütt, Carsten Some combinatorial and probabilistic inequalities and their application to Banach space theory, Studia Math., Volume 82 (1985) no. 1, pp. 91-106

[16] Kwapień, Stanisław; Schütt, Carsten Some combinatorial and probabilistic inequalities and their application to Banach space theory. II, Studia Math., Volume 95 (1989) no. 2, pp. 141-154

[17] Lindenstrauss, Joram; Tzafriri, Lior Classical Banach spaces. I, Springer-Verlag, Berlin-New York, 1977, xiii+188 pages (Sequence spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 92)

[18] Matoušek, Jiří Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, New York, 2002, xvi+481 pages

[19] Maurey, Bernard Type, cotype and $K$-convexity, Handbook of the geometry of Banach spaces, Vol. 2, North-Holland, Amsterdam, 2003, pp. 1299-1332 | DOI

[20] McCarthy, Charles A. $c_p$, Israel J. Math., Volume 5 (1967), pp. 249-271

[21] Mendel, Manor; Naor, Assaf Euclidean quotients of finite metric spaces, Adv. Math., Volume 189 (2004) no. 2, pp. 451-494 | DOI

[22] Mendel, Manor; Naor, Assaf Metric cotype, Ann. of Math. (2), Volume 168 (2008) no. 1, pp. 247-298 | DOI

[23] Naor, Assaf $L_1$ embeddings of the Heisenberg group and fast estimation of graph isoperimetry, Proceedings of the International Congress of Mathematicians. Volume III, Hindustan Book Agency, New Delhi (2010), pp. 1549-1575

[24] Naor, Assaf An introduction to the Ribe program, Jpn. J. Math., Volume 7 (2012) no. 2, pp. 167-233 | DOI

[25] Ostrovskii, Mikhail I. Metric embeddings, De Gruyter Studies in Mathematics, 49, De Gruyter, Berlin, 2013, xii+372 pages (Bilipschitz and coarse embeddings into Banach spaces)

[26] Randrianarivony, N. Lovasoa Characterization of quasi-Banach spaces which coarsely embed into a Hilbert space, Proc. Amer. Math. Soc., Volume 134 (2006) no. 5, p. 1315-1317 (electronic) | DOI

[27] Raynaud, Y.; Schütt, C. Some results on symmetric subspaces of $L_1$, Studia Math., Volume 89 (1988) no. 1, pp. 27-35

[28] Raynaud, Yves Sur les sous-espaces de $L^p\left(L^q\right)$, Séminaire d’Analyse Fonctionelle 1984/1985 (Publ. Math. Univ. Paris VII), Volume 26, Univ. Paris VII, Paris, 1986, pp. 49-71

[29] Ribe, M. On uniformly homeomorphic normed spaces, Ark. Mat., Volume 14 (1976) no. 2, pp. 237-244

[30] Schoenberg, I. J. Metric spaces and positive definite functions, Trans. Amer. Math. Soc., Volume 44 (1938) no. 3, pp. 522-536 | DOI

[31] Wells, J. H.; Williams, L. R. Embeddings and extensions in analysis, Springer-Verlag, New York-Heidelberg, 1975, vii+108 pages (Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84)