Bourgain's discretization theorem

Details Bourgain's discretization theorem Bourgain's discretization theorem

2011-10-24

arxiv.org/abs/1110.5368v1

Mathematics

Functional Analysis

Scientific paper

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,...,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}$.

Affiliated with

Also associated with

No associations

Rating

Bourgain's discretization theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bourgain's discretization theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bourgain's discretization theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93769