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

Bourgain’s discretization theorem asserts that there exists a universal constant $C\in \left(0,\infty \right)$ with the following property. Let $X,Y$ be Banach spaces with $dimX=n$. Fix $D\in \left(1,\infty \right)$ and set $\delta ={e}^{-{n}^{Cn}}$. Assume that $𝒩$ is a $\delta$-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\in \left[1,\infty \right)$: in this case it suffices to take $\delta ={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 ${\left\{1,...,n\right\}}^{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{loglogN}$; the previously best known lower bound for this problem was a constant multiple of $\sqrt{logloglogN}$.

Le théorème de discrétisation de Bourgain affirme qu’il existe une constante universelle $C\in \left(0,\infty \right)$ avec la propriété suivante. Soient $X,Y$ des espaces de Banach avec $dimX=n$. Considérons $D\in \left(1,\infty \right)$ fixé et posons $\delta ={e}^{-{n}^{Cn}}$. Supposons que $𝒩$ est un $\delta$-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\in \left[1,\infty \right)$ : dans ce cas il suffit de prendre $\delta ={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 ${\left\{1,...,n\right\}}^{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{loglogN}$. Jusqu’à présent, la meilleure minoration connue pour ce problème était par un multiple de $\sqrt{logloglogN}$.

DOI: 10.5802/afst.1352

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,
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},
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  - 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 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/

[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: