Bourgain’s discretization theorem

Ohad Giladi; Assaf Naor; Gideon Schechtman

doi:10.5802/afst.1352

Ohad Giladi ¹; Assaf Naor ²; Gideon Schechtman ³

¹ Institut de Mathématiques de Jussieu, Université Paris VI
² Courant Institute, New York University
³ Department of Mathematics, Weizmann Institute of Science

Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 21 (2012) no. 4, pp. 817-837.

Abstract
Abstract

Bourgain’s discretization theorem asserts that there exists a universal constant $C \in (0, \infty)$ with the following property. Let $X, Y$ be Banach spaces with $dim X = n$ . Fix $D \in (1, \infty)$ and set $δ = e^{- n^{C n}}$ . 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 $C D$ . 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 \in [1, \infty)$ : 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 \in ℕ$ there exists a family $𝒴$ of $n$ -point subsets of ${1, ..., n}^{2} \subseteq ℝ^{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 $\sqrt{log log N}$ ; the previously best known lower bound for this problem was a constant multiple of $\sqrt{log log log N}$ .

Le théorème de discrétisation de Bourgain affirme qu’il existe une constante universelle $C \in (0, \infty)$ avec la propriété suivante. Soient $X, Y$ des espaces de Banach avec $dim X = n$ . Considérons $D \in (1, \infty)$ fixé et posons $δ = e^{- n^{C n}}$ . 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 $C D$ . 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 \in [1, \infty)$ : 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 \in ℕ$ arbitrairement grand, il existe une famille $𝒴$ de sous-ensembles à $n$ points de ${1, ..., n}^{2} \subseteq ℝ^{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 $\sqrt{log log N}$ . Jusqu’à présent, la meilleure minoration connue pour ce problème était par un multiple de $\sqrt{log log log N}$ .

EuDML MR Zbl

DOI: 10.5802/afst.1352

Author's affiliations:

Ohad Giladi ¹; Assaf Naor ²; Gideon Schechtman ³

¹ Institut de Mathématiques de Jussieu, Université Paris VI
² Courant Institute, New York University
³ Department of Mathematics, Weizmann Institute of Science

@article{AFST_2012_6_21_4_817_0,
     author = {Ohad Giladi and Assaf Naor and Gideon Schechtman},
     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},
     mrnumber = {3052032},
     zbl = {1283.46015},
     language = {en},
     url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1352/}
}

TY  - JOUR
AU  - Ohad Giladi
AU  - Assaf Naor
AU  - Gideon Schechtman
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  - https://afst.centre-mersenne.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 Ohad Giladi
%A Assaf Naor
%A Gideon Schechtman
%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 https://afst.centre-mersenne.org/articles/10.5802/afst.1352/
%R 10.5802/afst.1352
%G en
%F AFST_2012_6_21_4_817_0

Ohad Giladi; Assaf Naor; Gideon Schechtman. Bourgain’s discretization theorem. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 21 (2012) no. 4, pp. 817-837. doi : 10.5802/afst.1352. https://afst.centre-mersenne.org/articles/10.5802/afst.1352/

References
Cited by

[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

Cited by Sources: