Bourgain's discretization theorem (Q692778): Difference between revisions

First of all, recall that a \(\delta\)-net in a metric space is a maximal \(\delta\)-separated subset. The positive number \(\delta\) will be referred to as the separation parameter. Let \((X,d_X)\) and \((Y,d_Y)\) be two metric spaces. The (bi-Lipschitz) distortion of \(X\) in \(Y\), denoted \(c_Y(X)\), is defined as the infimum over those \(D\in[1,\infty]\) such that there exists \(f: X\to Y\) and a scaling factor \(s\in(0,\infty)\) satisfying \[ s\cdot d_X(x,y)\leqslant d_Y(f(x),f(y))\leqslant D\cdot s\cdot d_X(x,y) \mathrm{ for all } x,y\in X. \] It follows from the work of \textit{M. Ribe} [Ark. Mat. 14, No. 2, 237--244 (1976; Zbl 0336.46018)] and \textit{S. Heinrich} and \textit{P. Mankiewicz} [Stud. Math. 73, 225--251 (1982; Zbl 0506.46008)] that, for every \(\epsilon\in(0,1)\), there exists \(\delta\in(0,1)\) such that, for every \(\delta\)-net \(\mathcal{N}_\delta\) in \(B_X\) (the unit ball of a finite-dimensional Banach space \(X\)), we have \[ (1-\epsilon)c_Y(X)\leqslant c_Y(\mathcal{N}_\delta)\leqslant c_Y(X),\tag{*} \] where \(Y\) is an arbitrary infinite-dimensional Banach space. Note that the right-most inequality of \((\ast)\) is obviously true for any subset of \(X\). Roughly speaking, one can find a nonlinear and discrete object, namely, a \(\delta\)-net, which is a ``good approximation'' vis-à-vis bi-Lipschitz embeddings, of a linear and highly non-discrete object, a finite-dimensional Banach space. Intuitively, in order to get a good approximation, the separation parameter of the net is expected to be rather small. The general topic of this article is a fine quantitative analysis of the order of magnitude of the separation parameter \(\delta\) in terms of the dimension \(n\) of the domain space \(X\), the error \(\epsilon\) and the geometric properties of the target space \(Y\). The authors introduce the discretization modulus, denoted \(\delta_{X\hookrightarrow Y}(\epsilon)\), as the supremum over those \(\delta\in(0,1)\) such that every \(\delta\)-net \(\mathcal{N}_\delta\) in \(B_X\) satisfies the left-hand side inequality of \((\ast)\), namely, \(c_Y(\mathcal{N}_\delta)\geqslant (1-\epsilon)c_Y(X)\). The authors are mainly concerned with \(X\) being an arbitrary finite-dimensional Banach and \(Y\) being some infinite-dimensional Banach space, and in the sequel \(X\) and \(Y\) will always have such dimensionality properties. We know that, for every \(\epsilon\in(0,1)\), \(\delta_{X\hookrightarrow Y}(\epsilon)>0\). In this review, we denote for all \(n\geqslant 1\), \[ \delta_n^Y(\epsilon):=\inf\{\delta_{X\hookrightarrow Y}(\epsilon)\mid X \mathrm{ is a Banach space of dimension }n\}. \] We then follow the notation of the authors and simply denote \[ \delta_n(Y):=\delta_n^Y(1/2) \] and set \[ \delta_n:=\inf\{\delta_n(Y)\mid Y \mathrm{ is an infinite-dimensional Banach space}\}. \] As already mentioned, the article under review deals with the asymptotic behavior of the parameter \(\delta_n(Y)\) where \(Y\) is infinite dimensional, in particular an \(L_p\)-space, and its application to a computer science related problem. The article is described by its authors as ``mostly expository'' and ``devoted to a detailed description of a proof of Bourgain's theorem''. However, besides giving a clear and thorough exposition of Bourgain's theorem, the article also contains some important and very interesting new estimates on the parameter \(\delta_n(L_p)\) for \(p\in[1,\infty)\). Bourgain's theorem we are referring to is the following lower estimate: { Theorem} (Bourgain's discretization theorem [\textit{J. Bourgain}, in: Geometrical aspects of functional analysis, Israel Semin. 1985--86, Lect. Notes Math. 1267, 157--167 (1987; Zbl 0633.46018)]): For some universal constant \(A\in(0,\infty)\), we have \(\delta_n\geqslant e^{-n^{An}}\). Note that the lower bound on the parameter \(\delta_n\) converges extremely fast to \(0\) when the dimension is growing. We invite the reader to take a look at Theorem \(1.2\) from the article itself for a more precise estimate where the dependence in \(\epsilon\) is visible, and the discussion that follows for possible refinements. If \(Y\) is an \(L_p\)-space, the authors obtain the following, much better estimate. {Theorem:} For some universal constant \(B\in(0,\infty)\), for every \(p\in[1,\infty)\), and for all \(n\geqslant 1\), we have \[ \delta_n(L_p)\geqslant \frac{B}{n^{5/2}}. \] As before, we direct the reader to Corollary \(1.4\) in the article for the dependence in \(\epsilon\) and to the more general and technical Theorem \(1.3\). The question of the sharpness of the estimates is still open. As the authors remark, we have, for instance, \[ \frac{B}{n^{5/2}}\leqslant\delta_n(L_2)\leqslant \delta_{\ell_1^n\hookrightarrow L_2}(1/2)\leqslant\frac{8}{n}. \] They also present a very nice application in theoretical computer science. We recall the definition of the minimum cost matching metric on \(\mathbb{R}^2\). Given \(n\in\mathbb{N}\), consider the metric \(\tau\) on the set of all \(n\)-point subsets of \(\mathbb{R}^2\) defined by \[ \tau(A,B)=\min\left\{\left.\sum_{a\in A}\|a-f(a)\|_2\right\arrowvert f: A\to B \mathrm{ is a bijection}\right\}. \] They obtain, as a corollary of the previous theorem in the case \(p=1\), an improved lower bound on the \(L_1\)-distortion of the minimum cost matching metric (a particular case of the earthmover metric) on \(\mathbb{R}^2\) in the following sense. { Corollary:} There exists a universal constant \(c\in(0,\infty)\) with the following property. For arbitrarily large \(n\in\mathbb{N}\), there exists a family \(\mathcal{Y}\) of \(n\)-point subsets of \(\{1,\dots,n\}^2\subseteq\mathbb{R}^2\) such that, if we write \(|\mathcal{Y}|=N\), then \[ c_{L_1}(\mathcal{Y},\tau)\geqslant c\sqrt{\log\log N}. \] The previous best known lower bound, due to the last two authors, was \[ c_{L_1}(\mathcal{Y},\tau)\geq c\sqrt{\log\log\log N}. \] Important ingredients of the proofs presented in this article range from classical probabilistic and differentiability arguments to a construction of a Lipschitz almost-extension of a Lipschitz map and properties of evolutes of Lipschitz maps under the Poisson semigroup. The authors also use a method introduced by \textit{W. B. Johnson}, \textit{B. Maurey} and \textit{G. Schechtman} in their study of nonlinear factorization of linear operators [Bull. Lond. Math. Soc. 41, No.~4, 663--668 (2009; Zbl 1183.46021)].