Bourgain’s discretization theorem

Ohad Giladi[1]; Assaf Naor[2]; Gideon Schechtman[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

Annales de la faculté des sciences de Toulouse Mathématiques (2012)

  • Volume: 21, Issue: 4, page 817-837
  • ISSN: 0240-2963

Abstract

top
Bourgain’s discretization theorem asserts that there exists a universal constant C ∈ ( 0 , ∞ ) with the following property. Let X , Y be Banach spaces with dim X = n . Fix D ∈ ( 1 , ∞ ) 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 ∈ [ 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 log log N ; the previously best known lower bound for this problem was a constant multiple of log log log N .

How to cite

top

Giladi, Ohad, Naor, Assaf, and Schechtman, Gideon. "Bourgain’s discretization theorem." Annales de la faculté des sciences de Toulouse Mathématiques 21.4 (2012): 817-837. <http://eudml.org/doc/251005>.

@article{Giladi2012,
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 $\delta = e^\{-n^\{Cn\}\}$. Assume that $\mathcal\{N\}$ is a $\delta $-net in the unit ball of $X$ and that $\mathcal\{N\}$ 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 [1,\infty )$: 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 \mathbb\{N\}$ there exists a family $\mathcal\{Y\}$ of $n$-point subsets of $\lbrace 1,\ldots ,n\rbrace ^2\subseteq \mathbb\{R\}^2$ such that if we write $|\mathcal\{Y\}|= N$ then any $L_1$ embedding of $\mathcal\{Y\}$ , 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\}$.},
affiliation = {Institut de Mathématiques de Jussieu, Université Paris VI; Courant Institute, New York University; Department of Mathematics, Weizmann Institute of Science},
author = {Giladi, Ohad, Naor, Assaf, Schechtman, Gideon},
journal = {Annales de la faculté des sciences de Toulouse Mathématiques},
keywords = {nets; local structure of Banach spaces; bi-Lipschitz embeddings; minimum cost matching metric},
language = {eng},
month = {10},
number = {4},
pages = {817-837},
publisher = {Université Paul Sabatier, Toulouse},
title = {Bourgain’s discretization theorem},
url = {http://eudml.org/doc/251005},
volume = {21},
year = {2012},
}

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
DA - 2012/10//
PB - Université Paul Sabatier, Toulouse
VL - 21
IS - 4
SP - 817
EP - 837
AB - 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 $\delta = e^{-n^{Cn}}$. Assume that $\mathcal{N}$ is a $\delta $-net in the unit ball of $X$ and that $\mathcal{N}$ 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 [1,\infty )$: 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 \mathbb{N}$ there exists a family $\mathcal{Y}$ of $n$-point subsets of $\lbrace 1,\ldots ,n\rbrace ^2\subseteq \mathbb{R}^2$ such that if we write $|\mathcal{Y}|= N$ then any $L_1$ embedding of $\mathcal{Y}$ , 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}$.
LA - eng
KW - nets; local structure of Banach spaces; bi-Lipschitz embeddings; minimum cost matching metric
UR - http://eudml.org/doc/251005
ER -

References

top
  1. Albiac (F.) and Kalton (N. J.).— Topics in Banach space theory, volume 233 of Graduate Texts in Mathematics. Springer, New York (2006). Zbl1094.46002MR2192298
  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). Zbl0901.52002MR1491097
  4. Begun (B.).— A remark on almost extensions of Lipschitz functions. Israel J. Math., 109, p. 151-155 (1999). Zbl0944.46038MR1679594
  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). Zbl0946.46002MR1727673
  6. Bourgain (J.).— The metrical interpretation of superre exivity in Banach spaces. Israel J. Math., 56(2), p. 222-230 (1986). Zbl0643.46013MR880292
  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). Zbl0633.46018MR907692
  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). Zbl1194.22009MR2630066
  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). Zbl1247.46020MR2892612
  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). Zbl0207.42901MR161119
  11. Deza (M. M.) and Laurent (M.).— Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin (1997). Zbl0885.52001MR1460488
  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). Zbl0119.31803MR139079
  13. Heinrich (S.).— Ultraproducts in Banach space theory. J. Reine Angew. Math., 313, p. 72-104 (1980). Zbl0412.46017MR552464
  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). Zbl0506.46008MR675426
  15. Hytönen (T.), Li (S.), and Naor (A.).— Quantitative affine approximation for UMD targets. Preprint (2011). MR2807530
  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). Zbl0034.10503MR30135
  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). Zbl1183.46021MR2521361
  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). Zbl0205.12602MR270119
  20. Naor (A.) and Schechtman (G.).— Planar earthmover is not in L 1 . SIAM J. Comput., 37(3), p. 804-826 (electronic) (2007). Zbl1155.46005MR2341917
  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). Zbl0678.53042MR979599
  22. Ribe (M.).— On uniformly homeomorphic normed spaces. Ark. Mat., 14(2), p. 237-244 (197)6. Zbl0336.46018MR440340
  23. Torchinsky (A.).— Real-variable methods in harmonic analysis, volume 123 of Pure and Applied Mathematics. Academic Press Inc., Orlando, FL (1986). Zbl0621.42001MR869816

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.