Pythagorean powers of hypercubes
Annales de l'Institut Fourier, Volume 66 (2016) no. 3, pp. 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:
Revised:
Accepted:
Published online:
DOI: 10.5802/aif.3032
Classification: 46B85, 30L05
Keywords: metric embeddings, Ribe program
Mot clés : Plongements métriques, programme de Ribe

Naor, Assaf 1; Schechtman, Gideon 2

1 Princeton University Mathematics Department Fine Hall, Washington Road Princeton, NJ 08544-1000 (USA)
2 Weizmann Institute of Science Department of Mathematics Rehovot 76100 (Israel)
@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 = {https://aif.centre-mersenne.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  - https://aif.centre-mersenne.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 https://aif.centre-mersenne.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. https://aif.centre-mersenne.org/articles/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., 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 (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 (L q ), 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)

Cited by Sources: