This is an announcement for the paper "Bourgain's discretization theorem" by Ohad Giladi, Assaf Naor, and Gideon Schechtman.

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 $\d= e^{-n^{Cn}}$. Assume that $\mathcal N$ is a $\d$-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 \N$ there exists a family $\mathscr Y$ of $n$-point subsets of ${1,\ldots,n}^2\subseteq \R^2$ such that if we write $|\mathscr Y|= N$ then any $L_1$ embedding of $\mathscr 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}$.

Archive classification: math.FA math.MG

Submitted from: naor@cims.nyu.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1110.5368

or

http://arXiv.org/abs/1110.5368