It is shown here that for every , any embedding into of the -fold Pythagorean power of the -dimensional Hamming cube incurs distortion that is at least a constant multiple of . 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 , implying the above nonembeddability statement. Links to the Ribe program are discussed, as well as related open problems.
On montre que pour tout , tout plongement dans de la puissance pythagoricienne -ième du cube de Hamming de dimension admet une distortion qui est au moins un multiple de 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 que l’on obtient l’énoncé ci-dessus. On explique le rapport avec le programme de Ribe, et on discute des questions ouvertes.
Revised:
Accepted:
Published online:
Keywords: metric embeddings, Ribe program
Mot clés : Plongements métriques, programme de Ribe
@article{AIF_2016__66_3_1093_0, author = {Naor, Assaf and Schechtman, Gideon}, title = {Pythagorean powers of hypercubes}, journal = {Annales de l'Institut Fourier}, pages = {1093--1116}, publisher = {Association des Annales de l{\textquoteright}institut Fourier}, volume = {66}, number = {3}, year = {2016}, doi = {10.5802/aif.3032}, language = {en}, url = {http://archive.numdam.org/articles/10.5802/aif.3032/} }
TY - JOUR AU - Naor, Assaf AU - Schechtman, Gideon TI - Pythagorean powers of hypercubes JO - Annales de l'Institut Fourier PY - 2016 SP - 1093 EP - 1116 VL - 66 IS - 3 PB - Association des Annales de l’institut Fourier UR - http://archive.numdam.org/articles/10.5802/aif.3032/ DO - 10.5802/aif.3032 LA - en ID - AIF_2016__66_3_1093_0 ER -
%0 Journal Article %A Naor, Assaf %A Schechtman, Gideon %T Pythagorean powers of hypercubes %J Annales de l'Institut Fourier %D 2016 %P 1093-1116 %V 66 %N 3 %I Association des Annales de l’institut Fourier %U http://archive.numdam.org/articles/10.5802/aif.3032/ %R 10.5802/aif.3032 %G en %F AIF_2016__66_3_1093_0
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. http://archive.numdam.org/articles/10.5802/aif.3032/
[1] 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] Euclidean distortion and the sparsest cut, J. Amer. Math. Soc., Volume 21 (2008) no. 1, p. 1-21 (electronic) | DOI
[3] 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] Geometric nonlinear functional analysis. Vol. 1, American Mathematical Society Colloquium Publications, 48, American Mathematical Society, Providence, RI, 2000, xii+488 pages
[5] On type of metric spaces, Trans. Amer. Math. Soc., Volume 294 (1986) no. 1, pp. 295-317 | DOI
[6] Lois stables et espaces , Ann. Inst. H. Poincaré Sect. B (N.S.), Volume 2 (1965/1966), pp. 231-259
[7] Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer-Verlag, Berlin, 1997, xii+587 pages | DOI
[8] Uniform homeomorphisms between Banach spaces, Séminaire Maurey-Schwartz (1975–1976), Espaces , applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, Centre Math., École Polytech., Palaiseau, 1976, 7 pages
[9] Filling Riemannian manifolds, J. Differential Geom., Volume 18 (1983) no. 1, pp. 1-147 http://projecteuclid.org/euclid.jdg/1214509283
[10] Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces, Studia Math., Volume 73 (1982) no. 3, pp. 225-251
[11] Ultraproducts in Banach space theory, J. Reine Angew. Math., Volume 313 (1980), pp. 72-104 | DOI
[12] does not coarsely embed into a Hilbert space, Proc. Amer. Math. Soc., Volume 134 (2006) no. 4, p. 1045-1050 (electronic) | DOI
[13] Linear dimension of the spaces and , Uspehi Mat. Nauk, Volume 13 (1958) no. 6 (84), pp. 95-98
[14] Banach spaces embedding into , Israel J. Math., Volume 52 (1985) no. 4, pp. 305-319 | DOI
[15] Some combinatorial and probabilistic inequalities and their application to Banach space theory, Studia Math., Volume 82 (1985) no. 1, pp. 91-106
[16] Some combinatorial and probabilistic inequalities and their application to Banach space theory. II, Studia Math., Volume 95 (1989) no. 2, pp. 141-154
[17] Classical Banach spaces. I, Springer-Verlag, Berlin-New York, 1977, xiii+188 pages (Sequence spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 92)
[18] Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, New York, 2002, xvi+481 pages
[19] Type, cotype and -convexity, Handbook of the geometry of Banach spaces, Vol. 2, North-Holland, Amsterdam, 2003, pp. 1299-1332 | DOI
[20] , Israel J. Math., Volume 5 (1967), pp. 249-271
[21] Euclidean quotients of finite metric spaces, Adv. Math., Volume 189 (2004) no. 2, pp. 451-494 | DOI
[22] Metric cotype, Ann. of Math. (2), Volume 168 (2008) no. 1, pp. 247-298 | DOI
[23] 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] An introduction to the Ribe program, Jpn. J. Math., Volume 7 (2012) no. 2, pp. 167-233 | DOI
[25] Metric embeddings, De Gruyter Studies in Mathematics, 49, De Gruyter, Berlin, 2013, xii+372 pages (Bilipschitz and coarse embeddings into Banach spaces)
[26] 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] Some results on symmetric subspaces of , Studia Math., Volume 89 (1988) no. 1, pp. 27-35
[28] Sur les sous-espaces de , Séminaire d’Analyse Fonctionelle 1984/1985 (Publ. Math. Univ. Paris VII), Volume 26, Univ. Paris VII, Paris, 1986, pp. 49-71
[29] On uniformly homeomorphic normed spaces, Ark. Mat., Volume 14 (1976) no. 2, pp. 237-244
[30] Metric spaces and positive definite functions, Trans. Amer. Math. Soc., Volume 44 (1938) no. 3, pp. 522-536 | DOI
[31] Embeddings and extensions in analysis, Springer-Verlag, New York-Heidelberg, 1975, vii+108 pages (Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84)
Cited by Sources: