Bourgain's discretization theorem

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 ${1,...,n}^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}$.

Proof of Lemma 5.1 corrected; its statement remains unchanged

References in corpus (1)

• Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$

Cited by in corpus (1)

• Connections between metric characterizations of superreflexivity and the Radon-Nikodým property for dual Banach spaces