Bourgain’s discretization theorem

Giladi, Ohad¹ ; Naor, Assaf² ; Schechtman, Gideon³ 

¹ 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, Série 6, Tome 21 (2012) no. 4, pp. 817-837

Abstract (VO)

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 $dimX=n$. Fix $D\in (1,\infty )$ 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 [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 $𝒴$ of $n$-point subsets of ${\{1,...,n\}}^2\subseteq {ℝ}^2$ such that if we write $\left|𝒴\right|=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}$.

Résumé

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 $dimX=n$. Considérons $D\in (1,\infty )$ 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 [1,\infty )$ : 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 \mathbb{N}$ arbitrairement grand, il existe une famille $𝒴$ de sous-ensembles à $n$ points de ${\{1,...,n\}}^2\subseteq {ℝ}^2$ telle que si nous écrivons $\left|𝒴\right|=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}$.

Détail

DOI : 10.5802/afst.1352