Catalogue et commandes en ligne (paiement sécurisé, VISA ou MASTERCARD uniquement)

Revues disponibles par abonnement

Annales scientifiques de l'ENS

Astérisque

Bulletin de la SMF

Mémoires de la SMF

Revue d'Histoire des Mathématiques

Gazette des Mathématiciens

Séries de livres

Astérisque

Cours Spécialisés

Documents Mathématiques

Mémoires de la SMF

Panoramas et Synthèses

Séminaires et Congrès

Série Chaire Jean Morlet

SMF/AMS Texts and Monographs

La Série T

Fascicules « Journée Annuelle »

Autres livres

Donald E. Knuth - traductions françaises

Rééditions du Séminaire Nicolas Bourbaki

Rééditions des Œuvres de Jean Leray

Revue de l'Institut Elie Cartan

Editions électroniques

Annales scientifiques de l'ENS

Bulletin de la SMF

Revue d'Histoire des Mathématiques

Séminaires et Congrès

Plus d'information / Abonnement

Publications grand public

L'explosion des mathématiques (smf.emath.fr)

Mathématiques L'explosion continue (smf.emath.fr)

Zoom sur les métiers des maths (smf.emath.fr)

Zoom sur les métiers des mathématiques et de l'informatique (smf.emath.fr)

Où en sont les mathématiques ?

La Série T

Pour les auteurs

Soumission des manuscrits

Formats et documentation

Plus d'info

Liste de diffusion électronique (smf.emath.fr)

Information pour les libraires et diffuseurs (smf.emath.fr)

Publications de la SMF
fr en
Votre numéro IP : 3.238.173.209
Accès aux édit. élec. : SémCong

Annales scientifiques de l'ENS

Présentation de la publication

Parutions

Dernières parutions

Comité de rédaction / Secrétariat

Série 4 :
Série 3 :
Série 2 :
Série 1 :

Faire une recherche


Catalogue & commande

Annales scientifiques de l'ENS - Parutions - série 4, 51 (2018)

Parutions < série 4, 51

ANNALES SCIENTIFIQUES DE L’ÉCOLE NORMALE SUPÉRIEURE, série 4 51, fascicule 3 (2018)

Alexandr Andoni, Assaf Naor, Ofer Neiman
Snowflake universality of Wasserstein spaces
Annales scientifiques de l'ENS 51, fascicule 3 (2018), 657-700

Télécharger cet article : Fichier PDF

Résumé :
Universalité des espaces de Wasserstein à floconnage près
Pour p(1,) notons P (R ^3) l'espace métrique des mesures de probabilité p-intégrables sur R ^3, muni de la p-métrique de Wasserstein W _p. Nous montrons que pour tout >0, tout (0,1/p] et tout espace métrique fini (X,d_X), l'espace métrique (X,d_X^) se plonge dans P (R ^3) avec distortion au plus 1+. Nous montrons que cela est optimal quand p(1,2] au sens où l'exposant 1/p ne peut pas être augmenté. En fait pour nN assez grand il existe un espace métrique à n points (X_n,d_n) tel que pour tout (1/p,1] tout plongement de l'espace métrique (X_n,d_n^) dans P (R ^3) a une distortion au moins égale à un multiple par une constante de (n)^-1/p. Ces résultats impliquent qu'il existe un espace d'Alexandrov de courbure positive, à savoir P_2(R ^3), vis- à-vis duquel il n'existe pas de suite de graphes expanseurs de degré borné. Il en résulte aussi que P_2(R ^3) n'admet pas de plongement uniforme, grossier ou quasisymétrique dans un espace de Banach de type non trivial. Nous discutons le lien avec plusieurs questions ouvertes depuis longtemps en géométrie des espaces métriques, dont la caractérisation des sous-ensembles des espaces d'Alexandrov, l'existence d'expandeurs, le problème d'universalité pour P_ 2(R ^k), et le problème de dichotomie pour le cotype métrique.

Mots-clefs : Plongements d'espaces métriques, espaces de Wasserstein, espaces d'Alexandrov, floconnage d'espaces métriques, trou spectral non linéaire, cotype métrique, type de Markov.

Abstract:
For p(1,) let P (R ^3) denote the metric space of all p-integrable Borel probability measures on R ^3, equipped with the Wasserstein p metric W _p. We prove that for every >0, every (0,1/p] and every finite metric space (X,d_X), the metric space (X,d_X^) embeds into P (R ^3) with distortion at most 1+. We show that this is sharp when p(1,2] in the sense that the exponent 1/p cannot be replaced by any larger number. In fact, for arbitrarily large nN there exists an n-point metric space (X_n,d_n) such that for every (1/p,1] any embedding of the metric space (X_n,d_n^) into P (R ^3) incurs distortion that is at least a constant multiple of (n)^-1/p. These statements establish that there exists an Alexandrov space of nonnegative curvature, namely P_2(R ^3), with respect to which there does not exist a sequence of bounded degree expander graphs. It also follows that P_2(R ^3) does not admit a uniform, coarse, or quasisymmetric embedding into any Banach space of nontrivial type. Links to several longstanding open questions in metric geometry are discussed, including the characterization of subsets of Alexandrov spaces, existence of expanders, the universality problem for P_2(R ^k), and the metric cotype dichotomy problem.

Keywords: Metric embeddings, Wasserstein spaces, Alexandrov spaces, Snowflakes of metric spaces, nonlinear spectral gaps, metric cotype, Markov type.

Class. math. : 46B85, 53C23, 46E27.


ISSN : 0012-9593
Publié avec le concours de : Centre National de la Recherche Scientifique

Bibliographie:

1
Schoenberg, I.J.
Metric spaces and positive definite functions
Trans. Amer. Math. Soc. 44 (1938) 522–536
2
Ding, J. and Lee, James R. and Peres, Yuval
Markov type and threshold embeddings
Geom. Funct. Anal. 23 (2013) 1207–1229
3
Bourgain, Jean
On Lipschitz embedding of finite metric spaces in Hilbert space
Israel J. Math. 52 (1985) 46–52
Math Reviews MR815600
4
Maurey, Bernard
Type, cotype and K-convexity
in Handbook of the geometry of Banach spaces
2 (2003) 1299–1332
5
Naor, Assaf
An application of metric cotype to quasisymmetric embeddings
in Metric and differential geometry
Progr. Math. 297 (2012) 175–178
Math Reviews MR3220443
6
Wells, J. H. and Williams, L. R.
Embeddings and extensions in analysis
Ergebn. Math. Grenzg., vol. 84, Springer, 1975
Math Reviews MR0461107
7
Kleiner, Bruce and Leeb, Bernhard
Rigidity of quasi-isometries for symmetric spaces and Euclidean buildings
Publ. Math. IHÉS 86 (1997) 115–197
Math Reviews MR1608566
8
Alexander, Stephanie and Kapovitch, Vitali and Petrunin, Anton
Alexandrov meets Kirszbraun
in Proceedings of the Gökova Geometry-Topology Conference 2010
(2011) 88–109
Math Reviews MR2931882
9
Andoni, A. and Naor, Assaf and Neiman, O.
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost
in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Leibniz International Proceedings in Informatics (LIPIcs) 55 (2016) 83:1–83:14
10
Austin, Tim and Naor, Assaf
On the bi-Lipschitz structure of Wasserstein spaces
(2015)
11
Austin, Tim and Naor, Assaf and Peres, Yuval
The wreath product of Z with Z has Hilbert compression exponent 23
Proc. Amer. Math. Soc. 137 (2009) 85–90
Math Reviews MR2439428
12
Ball, K.
Markov chains, Riesz transforms and Lipschitz maps
Geom. Funct. Anal. 2 (1992) 137–172
Math Reviews MR1159828
13
Bartal, Yair
Probabilistic approximation of metric spaces and its algorithmic applications
in 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996)
(1996) 184–193
Math Reviews MR1450616
14
Bartal, Yair and Linial, Nathan and Mendel, Manor and Naor, Assaf
On metric Ramsey-type phenomena
Ann. of Math. 162 (2005) 643–709
Math Reviews MR2183280
15
Berg, I. D. and Nikolaev, I. G.
On a distance characterization of A. D. Aleksandrov spaces of nonpositive curvature
Dokl. Akad. Nauk 414 (2007) 10–12
Math Reviews MR2447040
16
Berg, I. D. and Nikolaev, I. G.
Quasilinearization and curvature of Aleksandrov spaces
Geom. Dedicata 133 (2008) 195–218
Math Reviews MR2390077
17
Beurling, A. and Ahlfors, L.
The boundary correspondence under quasiconformal mappings
Acta Math. 96 (1956) 125–142
Math Reviews MR0086869
18
Bourgain, Jean
New Banach space properties of the disc algebra and H
Acta Math. 152 (1984) 1–48
Math Reviews MR736210
19
Bourgain, Jean
The metrical interpretation of superreflexivity in Banach spaces
Israel J. Math. 56 (1986) 222–230
Math Reviews MR880292
20
Bourgain, Jean and Milman, Vitali
Dichotomie du cotype pour les espaces invariants
C. R. Acad. Sci. Paris Sér. I Math. 300 (1985) 263–266
Math Reviews MR785065
21
Bridson, Martin R. and Haefliger, André
Metric spaces of non-positive curvature
Grundl. math. Wiss., vol. 319, Springer, Berlin, 1999
Math Reviews MR1744486
22
Briët, Jop and Naor, Assaf and Regev, Oded
Locally decodable codes and the failure of cotype for projective tensor products
Electron. Res. Announc. Math. Sci. 19 (2012) 120–130
Math Reviews MR2999057
23
Buckley, S. M. and Falk, K. and Wraith, D. J.
Ptolemaic spaces and CAT(0)
Glasg. Math. J. 51 (2009) 301–314
Math Reviews MR2500753
24
Burago, Yu. and Gromov, Mikhael and Perel'man, G.
A. D. Aleksandrov spaces with curvatures bounded below
Uspekhi Mat. Nauk 47 (1992) 3–51, 222
Math Reviews MR1185284
25
Busemann, Herbert
The geometry of geodesics
Academic Press Inc., New York, N. Y., 1955
Math Reviews MR0075623
26
Critchley, Frank and Fichet, Bernard
The partial order by inclusion of the principal classes of dissimilarity on a finite set, and some of their basic properties
in Classification and dissimilarity analysis
Lect. Notes Stat. 93 (1994) 5–65
Math Reviews MR1334332
27
David, Guy and Semmes, Stephen
Fractured fractals and broken dreams
Oxford Lecture Series in Mathematics and its Applications, vol. 7, The Clarendon Press, Oxford Univ. Press, New York, 1997
Math Reviews MR1616732
28
Enflo, Per
On the nonexistence of uniform homeomorphisms between Lp-spaces
Ark. Mat. 8 (1969) 103–105
Math Reviews MR0271719
29
Enflo, Per
Uniform homeomorphisms between Banach spaces
in Séminaire Maurey-Schwartz (1975–1976), Espaces, Lp, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18
(1976)
Math Reviews MR0477709
30
Foertsch, Thomas and Lytchak, Alexander and Schroeder, Viktor
Nonpositive curvature and the Ptolemy inequality
Int. Math. Res. Not. 2007 (2007) Art. ID rnm100, 15
Math Reviews MR2376212
31
Foertsch, Thomas and Schroeder, Viktor
Hyperbolicity, CAT(-1)-spaces and the Ptolemy inequality
Math. Ann. 350 (2011) 339–356
Math Reviews MR2794913
32
Garling, D. J. H.
Inequalities: a journey into linear analysis
Cambridge Univ. Press, Cambridge, 2007
Math Reviews MR2343341
33
Godefroy, G. and Kalton, N. J.
Lipschitz-free Banach spaces
Studia Math. 159 (2003) 121–141
Math Reviews MR2030906
34
Gromov, Mikhael
Filling Riemannian manifolds
J. Differential Geom. 18 (1983) 1–147
Math Reviews MR697984
35
Gromov, Mikhael
Asymptotic invariants of infinite groups
in Geometric group theory, vol. 2 (Sussex, 1991)
London Math. Soc. Lecture Note Ser. 182 (1993) 1–295
Math Reviews MR1253544
36
Gromov, Mikhael
Metric structures for Riemannian and non-Riemannian spaces
Progress in Math., vol. 152, Birkhäuser, 1999
Math Reviews MR1699320
37
Gromov, Mikhael
CAT()-spaces: construction and concentration
Zap. Nauchn. Sem. S. Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 280 (2001) 100–140, 299–300
Math Reviews MR1879258
38
Gromov, Mikhael
Random walk in random groups
Geom. Funct. Anal. 13 (2003) 73–146
Math Reviews MR1978492
39
Har-Peled, Sariel and Mendel, Manor
Fast construction of nets in low-dimensional metrics and their applications
SIAM J. Comput. 35 (2006) 1148–1184
Math Reviews MR2217141
40
Hoory, Shlomo and Linial, Nathan and Wigderson, Avi
Expander graphs and their applications
Bull. Amer. Math. Soc. 43 (2006) 439–561
Math Reviews MR2247919
41
Jost, Jürgen
Nonpositive curvature: geometric and analytic aspects
Lectures in Mathematics ETH Zürich, Birkhäuser, 1997
Math Reviews MR1451625
42
Kay, David C.
The ptolemaic inequality in Hilbert geometries
Pacific J. Math. 21 (1967) 293–301
Math Reviews MR0213968
43
Khot, Subhash and Naor, Assaf
Nonembeddability theorems via Fourier analysis
Math. Ann. 334 (2006) 821–852
Math Reviews MR2209259
44
Kwapień, S. and Pełczyński, A.
Absolutely summing operators and translation-invariant spaces of functions on compact abelian groups
Math. Nachr. 94 (1980) 303–340
Math Reviews MR582532
45
Laakso, Tomi J.
Plane with A_-weighted metric not bi-Lipschitz embeddable to R^N
Bull. London Math. Soc. 34 (2002) 667–676
Math Reviews MR1924353
46
Lafforgue, Vincent
Un renforcement de la propriété (T)
Duke Math. J. 143 (2008) 559–602
Math Reviews MR2423763
47
Lafforgue, Vincent
Propriété (T) renforcée banachique et transformation de Fourier rapide
J. Topol. Anal. 1 (2009) 191–206
Math Reviews MR2574023
48
Lang, Urs and Pavlović, B. and Schroeder, Viktor
Extensions of Lipschitz maps into Hadamard spaces
Geom. Funct. Anal. 10 (2000) 1527–1553
Math Reviews MR1810752
49
Lang, Urs and Plaut, Conrad
Bilipschitz embeddings of metric spaces into space forms
Geom. Dedicata 87 (2001) 285–307
Math Reviews MR1866853
50
Lang, Urs and Schroeder, Viktor
Kirszbraun's theorem and metric spaces of bounded curvature
Geom. Funct. Anal. 7 (1997) 535–560
Math Reviews MR1466337
51
Lebedeva, Nina and Petrunin, Anton
Curvature bounded below: a definition a la Berg-Nikolaev
Electron. Res. Announc. Math. Sci. 17 (2010) 122–124
Math Reviews MR2735031
52
Lee, James R. and Mendel, Manor and Naor, Assaf
Metric structures in L_1: dimension, snowflakes, and average distortion
European J. Combin. 26 (2005) 1180–1190
Math Reviews MR2163751
53
Lee, James R. and Naor, Assaf
Embedding the diamond graph in L_p and dimension reduction in L_1
Geom. Funct. Anal. 14 (2004) 745–747
Math Reviews MR2084978
54
Liao, Benben
Strong Banach property (T) for simple algebraic groups of higher rank
J. Topol. Anal. 6 (2014) 75–105
Math Reviews MR3190138
55
Linial, Nathan and Magen, A. and Naor, Assaf
Girth and Euclidean distortion
Geom. Funct. Anal. 12 (2002) 380–394
Math Reviews MR1911665
56
Lott, John and Villani, Cédric
Ricci curvature for metric-measure spaces via optimal transport
Ann. of Math. 169 (2009) 903–991
Math Reviews MR2480619
57
Matoušek, Jiř
On embedding expanders into l_p spaces
Israel J. Math. 102 (1997) 189–197
Math Reviews MR1489105
58
Matoušek, Jiř
Lectures on discrete geometry
Graduate Texts in Math., vol. 212, Springer, 2002
59
Mendel, Manor
Metric dichotomies
in Limits of graphs in group theory and computer science
(2009) 59–76
Math Reviews MR2562140
60
Mendel, Manor and Naor, Assaf
Metric cotype
Ann. of Math. 168 (2008) 247–298
Math Reviews MR2415403
61
Mendel, Manor and Naor, Assaf
Maximum gradient embeddings and monotone clustering
Combinatorica 30 (2010) 581–615
Math Reviews MR2776721
62
63
Mendel, Manor and Naor, Assaf
Markov convexity and local rigidity of distorted metrics
J. Eur. Math. Soc. (JEMS) 15 (2013) 287–337
Math Reviews MR2998836
64
Mendel, Manor and Naor, Assaf
Nonlinear spectral calculus and super-expanders
Publ. Math. IHÉS 119 (2014) 1–95
Math Reviews MR3210176
65
Mendel, Manor and Naor, Assaf
Expanders with respect to Hadamard spaces and random graphs
Duke Math. J. 164 (2015) 1471–1548
Math Reviews MR3352040
66
Mimura, Masato
Sphere equivalence, Banach expanders, and extrapolation
Int. Math. Res. Not. 2015 (2015) 4372–4391
Math Reviews MR3356758
67
Naor, Assaf
A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L_p spaces
Mathematika 48 (2001) 253–271
Math Reviews MR1996375
68
Naor, Assaf
An introduction to the Ribe program
Jpn. J. Math. 7 (2012) 167–233
Math Reviews MR2995229
69
Naor, Assaf
Comparison of metric spectral gaps
Anal. Geom. Metr. Spaces 2 (2014) 1–52
Math Reviews MR3208067
70
Naor, Assaf and Peres, Yuval
Embeddings of discrete groups and the speed of random walks
Int. Math. Res. Not. 2008 (2008) Art. ID rnn 076, 34
Math Reviews MR2439557
71
Naor, Assaf and Peres, Yuval
L_p compression, traveling salesmen, and stable walks
Duke Math. J. 157 (2011) 53–108
Math Reviews MR2783928
72
Naor, Assaf and Peres, Yuval and Schramm, Oded and Sheffield, Scott
Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
Duke Math. J. 134 (2006) 165–197
Math Reviews MR2239346
73
Naor, Assaf and Schechtman, Gideon
Remarks on non linear type and Pisier's inequality
J. reine angew. Math. 552 (2002) 213–236
Math Reviews MR1940437
74
Naor, Assaf and Schechtman, Gideon
Planar earthmover is not in L_1
SIAM J. Comput. 37 (2007) 804–826
Math Reviews MR2341917
75
Naor, Assaf and Silberman, Lior
Poincaré inequalities, embeddings, and wild groups
Compos. Math. 147 (2011) 1546–1572
Math Reviews MR2834732
76
Newman, Ilan and Rabinovich, Yuri
A lower bound on the distortion of embedding planar metrics into Euclidean space
Discrete Comput. Geom. 29 (2003) 77–81
Math Reviews MR1946795
77
Nowak, Piotr W.
Poincaré inequalities and rigidity for actions on Banach spaces
J. Eur. Math. Soc. (JEMS) 17 (2015) 689–709
Math Reviews MR3323202
78
Ohta, Shin-ichi
Markov type of Alexandrov spaces of non-negative curvature
Mathematika 55 (2009) 177–189
Math Reviews MR2573607
79
Ohta, Shin-ichi and Pichot, Mikaël
A note on Markov type constants
Arch. Math. (Basel) 92 (2009) 80–88
Math Reviews MR2471990
80
Otto, Felix
The geometry of dissipative evolution equations: the porous medium equation
Comm. Partial Differential Equations 26 (2001) 101–174
Math Reviews MR1842429
81
Ozawa, Narutaka
A note on non-amenability of B(l_p) for p=1,2
Internat. J. Math. 15 (2004) 557–565
Math Reviews MR2078880
82
Pełczyński, A.
Banach spaces of analytic functions and absolutely summing operators
Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, vol. 30, Amer. Math. Soc., 1977
83
Pisier, Gilles
Ensembles de Sidon et espaces de cotype 2
in Séminaire sur la Géométrie des Espaces de Banach (1977–1978), exp. no 14
(1978)
Math Reviews MR520214
84
Pisier, Gilles
Factorization of operator valued analytic functions
Adv. Math. 93 (1992) 61–125
Math Reviews MR1160843
85
Rachev, Svetlozar T. and Rüschendorf, Ludger
Mass transportation problems. Vol. II
Probability and its Applications (New York), Springer, New York, 1998
Math Reviews MR1619171
86
Rešetnjak, Ju. G.
Non-expansive maps in a space of curvature no greater than K
Sibirsk. Mat. Ž. 9 (1968) 918–927
Math Reviews MR0244922
87
Sato, Takashi
An alternative proof of Berg and Nikolaev's characterization of CAT(0)-spaces via quadrilateral inequality
Arch. Math. (Basel) 93 (2009) 487–490
Math Reviews MR2563595
88
Sturm, Karl-Theodor
Metric spaces of lower bounded curvature
Exposition. Math. 17 (1999) 35–47
Math Reviews MR1687468
89
Sturm, Karl-Theodor
Probability measures on metric spaces of nonpositive curvature
in Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002)
Contemp. Math. 338 (2003) 357–390
Math Reviews MR2039961
90
Sturm, Karl-Theodor
On the geometry of metric measure spaces. I
Acta Math. 196 (2006) 65–131
Math Reviews MR2237206
91
92
Tomczak-Jaegermann, Nicole
The moduli of smoothness and convexity and the Rademacher averages of trace classes Sp(1p<)
Studia Math. 50 (1974) 163–182
Math Reviews MR0355667
93
Tukia, P. and Väisälä, J.
Quasisymmetric embeddings of metric spaces
Ann. Acad. Sci. Fenn. Ser. A I Math. 5 (1980) 97–114
Math Reviews MR595180
94
Varopoulos, Nicolas
Une remarque sur les ensembles de Helson
Duke Math. J. 43 (1976) 387–390
Math Reviews MR0405002
95
Villani, Cédric
Topics in optimal transportation
Graduate Studies in Math., vol. 58, Amer. Math. Soc., Providence, RI, 2003
Math Reviews MR1964483
96
Wojtaszczyk, P.
Banach spaces for analysts
Cambridge Studies in Advanced Math., vol. 25, Cambridge Univ. Press, Cambridge, 1991
Math Reviews MR1144277
97
Yokota, Takumi
A rigidity theorem in Alexandrov spaces with lower curvature bound
Math. Ann. 353 (2012) 305–331
Math Reviews MR2915538
98
Ribe, M.
On uniformly homeomorphic normed spaces
Ark. Mat. 14 (1976) 237–244
Math Reviews MR0440340
99
Maurey, Bernard and Pisier, Gilles
Caractérisation d'une classe d'espaces de Banach par des propriétés de séries aléatoires vectorielles
C. R. Acad. Sci. Paris 277 (1973) A687–A690
Math Reviews MR0331017