按：Jean Bourgain(1954-2018)绝对属于当代最富创造力的一批数学家，在诸多领域留下不胜数的成果和洞见. 也许每个分析学工作者都会在生命的某个阶段接触Bourgain的工作或思想. 这是一个(不定期)连载系列，记录Bourgain的数学魔法.
这个系列写过很多调和分析和PDE的内容，这次调转视角讲讲Bourgain早年在度量几何的工作. 最近太忙so几个长篇系列都在赶工咕咕咕...先水一篇备好的旧文吧（笑）
有一个来自泛函分析和计算机科学的经典问题：一般的度量空间和Hilbert空间 $\ell^2$ (或者 $k$ 维Euclidean空间 $\mathbf{E}^k$) 相差多远？1985年，文章
[1] J. Bourgain, On Lipschitz embedding of finite metric spaces into Hilbert space
在有限度量空间的情形解决了这个问题. 证明利用了随机化和尺度分解-平均等精细的分析技术（超有Bourgain的风格耶），我们来详细展示其中的魔法.
定义. 设 $(X, d_X)$ , $(Y, d_Y)$ 是（有限）度量空间，$f: X\to Y$ 为单射，则定义 $X, Y$之间的 $f$-distorsion $\mathrm{d}_f(X,Y) := \Vert f\Vert_{Lip} \ \Vert f^{-1}|_{f(X)}\Vert_{Lip}$ , 其中 $$\Vert f\Vert_{Lip} := \sup_{x,x'\in X} \frac{d_Y(f(x), f(x'))}{d_X(x, x')} \ .$$ 进一步可以定义 $X, Y$ 之间的distorsion $\mathrm{d}(X,Y) := \inf_{f} \ d_f(X, Y)$ .
注. 不难得知 $\mathrm{d}_f(X,Y)\geq 1$, 等号成立 iff $f$ 是等距同构，所以distorsion $\mathrm{d}_f$ 和 $\mathrm{d}$ 就是刻画两个度量空间相差程度的理想指标.
定理 (Bourgain's Embedding, 1985). 存在常数 $C>0$ , 对任意一个 $n$-point 度量空间 $(X,d)$ 都存在一个嵌入映射 $f: X\to E=(\mathbf{E}^{2^n}, \Vert \cdot \Vert)$ s.t. $$ \Vert f(x)-f(y)\Vert \leq d(x,y) \leq C \log{n} \Vert f(x)-f(y)\Vert \ .$$ i.e. $\mathrm{d}(X, E)=O(\log{n})$ .
可以看到定理将 distorsion 控制在相较于 $|X|$ 非常小的尺度；进一步Linial-London-Rabinovich将 dimension 从 $2^n$ 显著地改进为 $O(\log^2{n})$ 并说明了构造过程是多项式复杂度, 这使得定理在理论和应用都非常重要. 如果有机会再写一篇博客讲讲这个改进吧.
注. [1]给出了一个例子：给定一个有限连通无向图 $G$ , 顶点数 $|V(G)|=n$ . 可以赋予 $V(G)$ 一个度量 $d$ 为连接两点最短路径的长度，这里设每条边的长度为 $1$ . 读者可以自己证明当 $G$ 是一个square-graph（即 $4$ 个顶点首尾相连）时，$V(G)$ 不可能等距嵌入 $\ell^2$ 中（自然不可能嵌入 $\mathbf{E}^k$）. 这种非Euclidean例子在理论计算机科学和数据分析中经常出现，将这些离散数据小误差地嵌入低维度的Euclidean空间将方便我们采用高效、直观的几何算法进行处理.
注. [1]还证明了
命题 (Bourgain, 1985). 存在常数 $c>0$ s.t. $$\mathrm{d}(V(G), \ell^2) \geq c \frac{\log{n}}{\log \log n} \ .$$
说明Bourgain的结果是几乎sharp的，从理论上否定了更小distorsion的方案. 值得一提的是Bourgain的证明同样引入了随机图这类随机化对象，有时间的话也许还会再谈谈（咕~）事实上Linial-London-Rabinovich和Khot-Naor还进一步把命题的结果加强到sharp.
下面我们分三步构造Bourgain's Embedding. 证明来自[Noar](p. 13-14) 对Bourgain原始证明的简化.
只需考虑 $n>2$ 的情形. 用每个子集 $A\in \mathscr{P}(X)$ ($X$ 的幂集) 标记它的基底. 现在将 $X$ 看作一个（离散）概率空间: 选定一个整数 $1\leq j \leq \log{n} $ , 我们在 $X$ 随机选取点组成一个随机集 $A_p$ ，每个点独立地有 $2^{-j}$ 的概率被选中, 这自然地诱导了 $$p_j : p_j(A)=\mathbb{P}(A_p=A)= \frac{1}{2^{j|A|}}\left(1-\frac{1}{2^j} \right)^{n-|A|} \ .$$ 这里采用二进概率是为了和后续讨论 $A$ 的尺度相对应. 构造单射 $f_j$ : $f_j(x)$ 在 $A$-基底的（加权）坐标为 $\sqrt{p_j(A)} \ d(x,A)$ , 那么 $$\begin{align*} \Vert f_j(x)-f_j(y)\Vert^2 = &\sum_{A} p_j(A) \left(d(x,A)-d(y,A)\right)^2 \\ \leq & \sum_{A} p_j(A) d(x,y)^2 \\ \leq & d(x,y)^2 \ , \end{align*}$$ 定理的第一个不等号得证. 注意这一步与 $j$ 的选取无关. 可以看到 $\Vert f_j(x)-f_j(y)\Vert^2$ 等于 期望 $\mathbb{E}_j |d(x,A)-d(y,A)|^2$ .
定理的第二个不等号需要更多讨论. 直观上我们希望 $A$ 能良好地分离 $x, y$ 同时 $p_j(A)$ 足够大，从而控制 $\mathbb{E}_j |d(x,A)-d(y,A)|^2$ 的下界，为此我们加入一些几何上的考虑. 对于Step 1中的 $j$ 和给定的 $x,y\in X$ , 定义 $$r_j := \inf \ \{r>0: |B(x,r)|, |B(y,r)| \geq 2^{j}\}\ ,$$ 其中 $B(x,r) := \{x'\in X : d(x,x')\leq r\}$ . 这里我们通过集合的大小来构造 尺度 $r_j$ ，因为Step 1定义的 $p_j$ 只与 $A$ 的大小有关（这样才能得到与 $x,y$ 无关的估计）. 由 $r_j$ 的定义可知（不妨设）开球 $B^o(x,r_j)$ 只包含 $\lt 2^j$ 个点. 一个观察是如果 $|A_0|=2^j$ , $|A_1|=2^{j-1}$ , 则分离的概率和相交的概率 $$S_j:=\mathbb{P}(A\cap A_0=\emptyset) = (1-\frac{1}{2^j})^{2^j}\geq S_1 = \frac{1}{4} \ , $$ $$I_j:=\mathbb{P}(A\cap A_1\neq \emptyset) = 1-(1-\frac{1}{2^j})^{2^{j-1}} \geq 1-e^{-1/2}\ .$$ 如果 $A_0\cap A_1 = \emptyset$ , 上述两个事件相互独立. 所以对 $r_j$ 做一个修正 $$\tilde{r}_j := \min{(r_j, d(x,y)/3)}\ ,$$ 于是 $B^o(x,\tilde{r}_j) \cap B(y,\tilde{r}_{j-1})=\emptyset$ . 所以如果发生事件 $$\mathcal{E}_j^{x,y} : A\cap B^o(x,\tilde{r}_j)=\emptyset\ , \ A\cap B(y,\tilde{r}_{j-1}) \neq \emptyset$$ 则有 $$|d(x,A)-d(y,A)|\geq \tilde{r}_j-\tilde{r}_{j-1} \ ,$$ $$\mathbb{P}\left( \mathcal{E}_j^{x,y}\right) \geq S_j\ I_j \geq \frac{1}{C} \ .$$ 第一个估计意味着可以用 $A$ 在尺度 $r_j$ 的层次分离 $x, y$ . 对于第二个估计，考虑事件 $$\Omega_{j}^{x,y} := \{A\subset X : \vert d(x,A)-d(y,A)|\geq \tilde{r}_j-\tilde{r}_{j-1}\} \ ,$$ 那么有 $$\mathbb{E}_j |d(x,A)-d(y,A)|^2 \geq \mathbb{P}(\Omega_j^{x,y}) (\tilde{r}_j-\tilde{r}_{j-1})^2 \geq (\tilde{r}_j-\tilde{r}_{j-1})^2/C \ .$$ 这里的关键在于 $C>0$ 与 $j$ 无关，这来自于一开始的观察中 $A_1$ 与 $A_0$ 大小相近 $\approx 2^j$ ！
现在还有一个问题：$\tilde{r}_j-\tilde{r}_{j-1}$ 无法控制 $d(x,y)$（控制distortion）. 观察到在大尺度下 $\tilde{r}_{\log{n}} = d(x,y)/3$ ; 而可以令 $\tilde{r}_0=0$ . 所以一个巧妙的想法是将各个尺度的概率取平均：定义新的概率测度 $$p: p(A)=\frac{1}{\log{n}}\sum_{j=1}^{\log{n}} p_j(A) \ ,$$ 并构造真正的单射 $f$ s.t. $f(x)$ 在 $A$-基底的坐标为 $\sqrt{p(A)} \ d(x,A)$ . 平均化不会改变Step 1的结果；而 $$\begin{align*} \Vert f(x)-f(y)\Vert^2 = &\frac{1}{\log{n}} \sum_{j=1}^{\log{n}} \mathbb{E}_j \left(d(x,A)-d(y,A)\right)^2 \\ \gtrsim & \frac{1}{\log{n}} \sum_{j=1}^{\log{n}} (\tilde{r}_j-\tilde{r}_{j-1})^2 \\ \gtrsim & \frac{1}{(\log{n})^2} \left(\sum_{j=1}^{\log{n}} \tilde{r}_j-\tilde{r}_{j-1} \right)^2 \\ \gtrsim & \frac{1}{(\log{n})^2} d(x,y)^2\ , \end{align*}$$ 定理1的第二个不等号得证，我们得到了 $X\to \mathbf{E}^{2^n}$ 的 $O(\log{n})$-distorsion嵌入. $\Box$