Pythagorean powers of hypercubes
Annales de l'Institut Fourier, Volume 66 (2016) no. 3, p. 1093-1116

It is shown here that for every 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 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.

On montre que pour tout 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 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.

Received : 2015-01-27
Revised : 2015-09-11
Accepted : 2015-11-25
Published online : 2016-12-14
Classification:  46B85,  30L05
Keywords: metric embeddings, Ribe program
     author = {Naor, Assaf and Schechtman, Gideon},
     title = {Pythagorean powers of hypercubes},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {66},
     number = {3},
     year = {2016},
     pages = {1093-1116},
     doi = {10.5802/aif.3032},
     language = {en},
     url = {}
Naor, Assaf; Schechtman, Gideon. Pythagorean powers of hypercubes. Annales de l'Institut Fourier, Volume 66 (2016) no. 3, pp. 1093-1116. doi : 10.5802/aif.3032.

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

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

[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, Providence, RI, American Mathematical Society Colloquium Publications, Tome 48 (2000), xii+488 pages

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

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

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

[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., Tome 18 (1983) no. 1, pp. 1-147

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

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

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

[13] Kadecʼ, M. Ĭ. Linear dimension of the spaces L p and l q , Uspehi Mat. Nauk, Tome 13 (1958) no. 6 (84), pp. 95-98

[14] Kalton, N. J. Banach spaces embedding into L 0 , Israel J. Math., Tome 52 (1985) no. 4, pp. 305-319 | Article

[15] Kwapień, Stanisław; Schütt, Carsten Some combinatorial and probabilistic inequalities and their application to Banach space theory, Studia Math., Tome 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., Tome 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, Springer-Verlag, New York, Graduate Texts in Mathematics, Tome 212 (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 | Article

[20] Mccarthy, Charles A. c p , Israel J. Math., Tome 5 (1967), pp. 249-271

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

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

[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., Tome 7 (2012) no. 2, pp. 167-233 | Article

[25] Ostrovskii, Mikhail I. Metric embeddings, De Gruyter, Berlin, De Gruyter Studies in Mathematics, Tome 49 (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., Tome 134 (2006) no. 5, p. 1315-1317 (electronic) | Article

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

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

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

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

[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)