Bourgain’s discretization theorem
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 21 (2012) no. 4, pp. 817-837.

Le théorème de discrétisation de Bourgain affirme qu’il existe une constante universelle C(0,) avec la propriété suivante. Soient X,Y des espaces de Banach avec dimX=n. Considérons D(1,) fixé et posons δ=e -n Cn . Supposons que 𝒩 est un δ-réseau dans la boule unité X et que 𝒩 admet un plongement bi-Lipschitz dans Y de distorsion au plus D. Alors l’espace tout entier X admet un plongement bi-Lipschitz dans Y de distorsion au plus CD. Cet article, d’exposition pour l’essentiel, est consacré à une présentation détaillée d’une preuve du théorème de Bourgain.

Nous obtenons aussi une amélioration du théorème de Bourgain dans le cas important où Y=L p pour un p[1,) : dans ce cas il suffit de prendre δ=C -1 n -5/2 pour que la même conclusion soit valable. Le cas p=1 de ce résultat de discrétisation amélioré a la conséquence suivante. Pour n arbitrairement grand, il existe une famille 𝒴 de sous-ensembles à n points de {1,...,n} 2 2 telle que si nous écrivons |𝒴|=N alors tout plongement dans L 1 de 𝒴 , muni de la métrique du coût du transport (ou métrique de l’appariement de poids minimal), a nécessairement une distorsion au moins égale à une constante fois loglogN. Jusqu’à présent, la meilleure minoration connue pour ce problème était par un multiple de logloglogN.

Bourgain’s discretization theorem asserts that there exists a universal constant C(0,) with the following property. Let X,Y be Banach spaces with dimX=n. Fix D(1,) and set δ=e -n Cn . Assume that 𝒩 is a δ-net in the unit ball of X and that 𝒩 admits a bi-Lipschitz embedding into Y with distortion at most D. Then the entire space X admits a bi-Lipschitz embedding into Y with distortion at most CD. This mostly expository article is devoted to a detailed presentation of a proof of Bourgain’s theorem.

We also obtain an improvement of Bourgain’s theorem in the important case when Y=L p for some p[1,): in this case it suffices to take δ=C -1 n -5/2 for the same conclusion to hold true. The case p=1 of this improved discretization result has the following consequence. For arbitrarily large n there exists a family 𝒴 of n-point subsets of {1,...,n} 2 2 such that if we write |𝒴|=N then any L 1 embedding of 𝒴 , equipped with the Earthmover metric (a.k.a. transportation cost metric or minimumum weight matching metric) incurs distortion at least a constant multiple of loglogN; the previously best known lower bound for this problem was a constant multiple of logloglogN.

DOI : 10.5802/afst.1352
Giladi, Ohad 1 ; Naor, Assaf 2 ; Schechtman, Gideon 3

1 Institut de Mathématiques de Jussieu, Université Paris VI
2 Courant Institute, New York University
3 Department of Mathematics, Weizmann Institute of Science
@article{AFST_2012_6_21_4_817_0,
     author = {Giladi, Ohad and Naor, Assaf and Schechtman, Gideon},
     title = {Bourgain{\textquoteright}s discretization theorem},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {817--837},
     publisher = {Universit\'e Paul Sabatier, Institut de math\'ematiques},
     address = {Toulouse},
     volume = {Ser. 6, 21},
     number = {4},
     year = {2012},
     doi = {10.5802/afst.1352},
     zbl = {1283.46015},
     mrnumber = {3052032},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/afst.1352/}
}
TY  - JOUR
AU  - Giladi, Ohad
AU  - Naor, Assaf
AU  - Schechtman, Gideon
TI  - Bourgain’s discretization theorem
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2012
SP  - 817
EP  - 837
VL  - 21
IS  - 4
PB  - Université Paul Sabatier, Institut de mathématiques
PP  - Toulouse
UR  - http://archive.numdam.org/articles/10.5802/afst.1352/
DO  - 10.5802/afst.1352
LA  - en
ID  - AFST_2012_6_21_4_817_0
ER  - 
%0 Journal Article
%A Giladi, Ohad
%A Naor, Assaf
%A Schechtman, Gideon
%T Bourgain’s discretization theorem
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2012
%P 817-837
%V 21
%N 4
%I Université Paul Sabatier, Institut de mathématiques
%C Toulouse
%U http://archive.numdam.org/articles/10.5802/afst.1352/
%R 10.5802/afst.1352
%G en
%F AFST_2012_6_21_4_817_0
Giladi, Ohad; Naor, Assaf; Schechtman, Gideon. Bourgain’s discretization theorem. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 21 (2012) no. 4, pp. 817-837. doi : 10.5802/afst.1352. http://archive.numdam.org/articles/10.5802/afst.1352/

[1] Albiac (F.) and Kalton (N. J.).— Topics in Banach space theory, volume 233 of Graduate Texts in Mathematics. Springer, New York (2006). | MR | Zbl

[2] Austin (T.), Naor (A.), and Tessera (R.).— Sharp quantitative nonembeddability of the Heisenberg group into superre exive Banach spaces. Preprint available at http://arxiv.org/abs/1007.4238. To appear in Groups Geom. Dyn. (2010).

[3] Ball (K.).— An elementary introduction to modern convex geometry. In Flavors of geometry, volume 31 of Math. Sci. Res. Inst. Publ., pages 158. Cambridge Univ. Press, Cambridge (1997). | MR | Zbl

[4] Begun (B.).— A remark on almost extensions of Lipschitz functions. Israel J. Math., 109, p. 151-155 (1999). | MR | Zbl

[5] Benyamini (Y.) and Lindenstrauss (J.).— Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI (2000). | MR | Zbl

[6] Bourgain (J.).— The metrical interpretation of superre exivity in Banach spaces. Israel J. Math., 56(2), p. 222-230 (1986). | MR | Zbl

[7] Bourgain (J.).— Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., p. 157-167. Springer, Berlin (1987). | MR | Zbl

[8] Cheeger (J.) and Kleiner (B.).— Differentiating maps into L 1 , and the geometry of BV functions. Ann. of Math. (2), 171(2), p. 1347-1385 (2010). | MR | Zbl

[9] Cheeger (J.), Kleiner (B.), and Naor (A.).— Compression bounds for Lipschitz maps from the Heisenberg group to L 1 . Acta Math., 207(2), p. 291-373 (2011). | MR

[10] Corson (H.) and Klee (V.).— Topological classification of convex sets. In Proc. Sympos. Pure Math., Vol. VII, p. 37-51. Amer. Math. Soc., Providence, R.I. (1963). | MR | Zbl

[11] Deza (M. M.) and Laurent (M.).— Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin (1997). | MR | Zbl

[12] Dvoretzky (A.).— Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), p. 123-160. Jerusalem Academic Press, Jerusalem (1961). | MR | Zbl

[13] Heinrich (S.).— Ultraproducts in Banach space theory. J. Reine Angew. Math., 313, p. 72-104 (1980). | MR | Zbl

[14] Heinrich (S.) and Mankiewicz (P.).— Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces. Studia Math., 73(3), p. 225-251 (1982). | MR | Zbl

[15] Hytönen (T.), Li (S.), and Naor (A.).— Quantitative affine approximation for UMD targets. Preprint (2011). | MR

[16] John (F.).— Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, p. 187-204. Interscience Publishers Inc. (1948). | MR | Zbl

[17] Johnson (W. B.), Maurey (B.), and Schechtman (G.).— Non-linear factorization of linear operators. Bull. Lond. Math. Soc., 41(4), p. 663-668 (2009). | MR | Zbl

[18] Li (S.) and Naor (A.).— Discretization and affine approximation in high dimensions. Preprint available at http://arxiv.org/abs/1202.2567, to appear in Israel J. Math. (2011).

[19] Lindenstrauss (J.) and Rosenthal (H. P.).— The L p spaces. Israel J. Math., 7, p. 325-349 (1969). | MR | Zbl

[20] Naor (A.) and Schechtman (G.).— Planar earthmover is not in L 1 . SIAM J. Comput., 37(3), p. 804-826 (electronic) (2007). | MR | Zbl

[21] Pansu (P.).— Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. of Math. (2), 129(1), p. 1-60 (1989). | MR | Zbl

[22] Ribe (M.).— On uniformly homeomorphic normed spaces. Ark. Mat., 14(2), p. 237-244 (197)6. | MR | Zbl

[23] Torchinsky (A.).— Real-variable methods in harmonic analysis, volume 123 of Pure and Applied Mathematics. Academic Press Inc., Orlando, FL (1986). | MR | Zbl

Cité par Sources :