Tao–Vu · 加性组合学 · 第 10 章 k=3 的 Szemerédi 定理

10.5　一个遍历论的论证An ergodic argument

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 命题 / 引理 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全书较难的一节，讲解会尽量把每一步的直觉与动机讲清楚。

本节目标给出 Roth 定理（即 \(k=3\) 的 Szemerédi 定理）的一个“遍历论风格”的有限版证明。核心思想是：把一个密度不小的函数 \(f\) 拆成两块——一块是“结构化”的、由少数几个波拼成的“反一致”部分 \(f_{U^\perp}\)，另一块是“一致”部分 \(f_U\)（傅里叶系数处处很小，对计数三项等差数列几乎没有贡献）。结构化的那块一定有很多三项等差数列，而一致的那块可以忽略，于是整体也有很多三项等差数列。和前几节最大的不同：把“密度增量”换成了“能量增量”。

1977 年，Furstenberg [121] 给出了 Szemerédi 定理（从而也包括 Roth 定理）一个惊艳的新证明，所用的是遍历论（ergodic theory）的方法，而非傅里叶分析或组合学。该论证依赖的算术结构非常少，几乎完全建立在对移位算子 \(T x := x+1\) 之混合（mixing）性质的分析之上。正因如此，它非常灵活，并已导出 Szemerédi 定理的若干影响深远的推广，其中一些我们将在下一章讨论。

Furstenberg 最初的遍历论论证在本质上是无穷的（infinitary），它处理整数集 \(\mathbb{Z}\)，并实际上把这些整数嵌入到一个抽象的保测系统 \((X,\mathcal{B},T,\mu)\) 之中。在该论证的若干版本里，要用到选择公理（以 Zorn 引理的面目出现）来获得这个保测系统的某种合适的结构分解。然而最近，人们在建立这一论证的有限版本方面取得了进展：此时人们在一个具体而有限的保测系统中工作，例如带标准移位 \(Tx := x+1\) 的循环群 \(\mathbb{Z}_N\)。这些有限版的论证受到了 Szemerédi 正则性引理（将在下一节引入）的启发，虽然比起优雅的无穷版论证要显得繁杂一些，却能给出 \(r_k(\mathbb{Z}_N)\) 的显式（尽管很弱）的定量界。此外，这些有限版的遍历论论证在 Green–Tao 关于素数中等差数列的定理的证明中起到了关键作用。

本节我们给出 Roth 定理的一个有限版遍历论证明，采用 [358] 中的表述。这个证明并不是完全遍历论的，因为我们会借用傅里叶变换；不过在下一章我们会讨论如何去掉对傅里叶变换的这种依赖（从而把论证推广到更高的 \(k\)）。我们将要建立的精确结果是：

定理 10.33 对一切有限群 \(Z\)，以及一切满足 \(0\le f(x)\le 1\) 且 \(\mathbb{E}_Z(f)\ge\delta\) 的函数 \(f:Z\to\mathbb{R}^+\)，我们有 \[\Lambda_3(f,f,f)=\Omega_\delta(1).\]
读懂这条定理

这里 \(Z\) 是一个有限交换群（你可以一直想成 \(\mathbb{Z}_N\)，即 \(\{0,1,\dots,N-1\}\) 上的模 \(N\) 加法）。各记号含义：

所以定理说的就是：只要 \(f\) 平均不小，三项等差数列的计数就有一个不随群变大而消失的正下界——这正是 Roth 定理（密度为正的集合必含三项等差数列）的函数化、定量化版本。

当然，这比纯傅里叶分析方法（例如定理 10.31）所能得到的结论要弱一些，但其证明颇为不同，并且更易于推广到更高的 \(k\)。特别地，它把前几节的密度增量论证替换成了一个能量增量论证。在前面的论证里，人们构造出一系列对象（等差数列或 Bohr 集），使 \(f\) 在其上的密度越来越大；而这里，我们构造的是一系列 \(\sigma\)-代数或分划，使 \(f\) 相对于它们的能量越来越大。这最终导出一个对 \(f\) 的“低复杂度”逼近 \(f_{U^\perp}\)，其中误差 \(f_U:=f-f_{U^\perp}\) 在线性意义下是一致的（linearly uniform），从而对 \(\Lambda_3(f,f,f)\) 的影响微乎其微。这个低复杂度逼近 \(f_{U^\perp}\) 结果是几乎周期的，这将导出 \(\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})\) 的一个下界。

任意 \(f\) 密度 \(\ge\delta\) ＝ 结构化部分 \(f_{U^\perp}\) 少数波拼成 · 几乎周期 → 有很多三项等差数列 一致部分 \(f_U\) 傅里叶系数处处小 → 对计数几乎无贡献 ＋ 结论：\(\Lambda_3(f,f,f)\) \(=\Omega_\delta(1)>0\)
整节的逻辑骨架：把 \(f\) 分解为“结构化”+“一致”两块；结构块贡献很多三项等差数列，一致块可忽略，于是整体的计数有正下界。

几乎周期性

下面进入细节，从几乎周期性的定义开始。为方便起见，我们借助傅里叶变换来定义这一概念，尽管这并非本质（见习题）。

定义 10.34（几乎周期性） 设 \(K\ge 1\) 为整数，\(\sigma>0\)。

称函数 \(f:Z\to\mathbb{C}\) 是 \(K\)-拟周期的（\(K\)-quasiperiodic），若存在频率 \(\xi_1,\dots,\xi_K\in Z\)（可以重复）以及复数 \(c_1,\dots,c_K\)，满足 \(|c_1|,\dots,|c_K|\le 1\)，使得 \(f=\sum_{j=1}^{K}c_j e_{\xi_j}\)，换言之 \[f(x)=\sum_{j=1}^{K}c_j\,e(x\cdot\xi_j).\]

称函数 \(f:Z\to\mathbb{C}\) 是 \((K,\sigma)\)-几乎周期的（\((K,\sigma)\)-almost periodic），若存在一个 \(K\)-拟周期函数 \(g\)，使得 \(\|f-g\|_{L^2(Z)}\le\sigma\)。

例：读懂“几乎周期”

这里 \(e_\xi(x):=e(\xi\cdot x)=e^{2\pi i\,\xi x/N}\) 是一个波（特征标 character）。它绕单位圆均匀地转，是最“规则、可预测”的函数。

关键直觉：波在合适的平移下几乎不变。若 \(h\) 使得每个 \(e(\xi_j h)\approx 1\)，则 \(f(x+h)\approx f(x)\)。这正是“几乎周期”一词的来历，也是后面“递归性/有很多等差数列”的源头。

低频波 \(e_{\xi_1}\) 高频波 \(e_{\xi_2}\) 几个这样的波加权相加 = 拟周期函数（结构化、可预测）
用少数几个频率的波叠加，就得到一个“低复杂度”的规则函数；几乎周期函数就是这种函数再加一个 \(L^2\) 小误差。

一个关键观察是：当 \(K\) 不太大、\(\sigma\) 足够小时，定理 10.33 对几乎周期函数是容易证明的。更精确地，我们有：

命题 10.35（几乎周期函数是递归的） 设 \(f:Z\to\mathbb{R}^+\) 满足 \(0\le f(x)\le 1\) 且 \(\mathbb{E}_Z(f)\ge\delta\)。若 \(f\) 对某个 \(K\ge 1\) 和 \(0<\sigma<\delta^3/8\) 是 \((K,\sigma)\)-几乎周期的，则 \[\Lambda_3(f,f,f)=\Omega\!\big((\delta/K)^K\,\delta^3\big).\]

此命题应与引理 4.44 相比较。这里的一个要点是：对 \(\sigma\) 的“足够小”这一条件不涉及 \(K\)。这对我们很重要，因为 \(K\) 最终会比 \(\sigma\) 大得多。

证明. 根据定义，可找到频率 \(\xi_1,\dots,\xi_K\) 与大小为 \(O(1)\) 的系数 \(c_1,\dots,c_K\)，使得对一切 \(x\in Z\) 有 \[f(x)=\sum_{j=1}^{K}c_j\,e(x\cdot\xi_j)+g(x),\] 其中 \(g\) 的 \(L^2(Z)\) 范数至多为 \(\sigma\)。现令 \(S:=\{\xi_1,\dots,\xi_K\}\)，并设 \(\rho>0\) 为一个稍后选定的半径。若 \(h\) 落在 Bohr 集 \(\mathrm{Bohr}_Z(S,\rho)\) 中，则 \(e(h\cdot\xi_j)=1+O(\rho)\)，因而对 \(j=1,2\) 有 \[T^{jh}f(x)=f(x)+O(K\rho)+T^{jh}g(x),\] 其中 \(T^hf(x)=f(x+h)\) 表示按 \(h\) 平移。特别地有 \[\|T^{jh}f-f\|_{L^2(Z)}\le O(K\rho)+2\sigma,\] 而由 \(f\) 的有界性有 \(\|T^{jh}f\|_{L^\infty(Z)}\le 1\)。经过几次三角不等式与 Hölder 不等式的应用，我们得出 \[\big\|\,f\,(T^hf)\,(T^{2h}f)-f^3\,\big\|_{L^1(Z)}\le O(K\rho)+4\sigma,\] 从而再用一次三角不等式， \[\mathbb{E}_{x\in Z}\,f(x)\,T^hf(x)\,T^{2h}f(x)\ge \mathbb{E}_{x\in Z}\big(f(x)^3\big)-O(K\rho)-4\sigma.\] 另一方面，由 Hölder 不等式有 \[\mathbb{E}_{x\in Z}f(x)^3\ge\big(\mathbb{E}_{x\in Z}f(x)\big)^3=\delta^3,\] 所以由关于 \(\sigma\) 的假设， \[\mathbb{E}_{x\in Z}\,f(x)\,T^hf(x)\,T^{2h}f(x)\ge\frac12\delta^3-O(K\rho).\] 应用 (4.25) 以及 \(f\) 的非负性，我们得出 \[\Lambda_3(f,f,f)=\mathbb{E}_{x,h\in Z}\,f(x)\,T^hf(x)\,T^{2h}f(x)\ge\rho^{K}\max\!\Big(\tfrac12\delta^3-O(K\rho),\,0\Big).\] 于是取 \(\rho\) 为 \(\delta/K\) 的一个足够小的倍数，即得结论。♦
把命题 10.35 的证明拆开看
  1. 选好平移 \(h\)。 Bohr 集 \(\mathrm{Bohr}_Z(S,\rho)=\{h:\ \|\xi_j\cdot h\|_{\mathbb{R}/\mathbb{Z}}\le\rho\ \forall j\}\) 收集了所有“几乎不动每个波”的平移 \(h\)。对这种 \(h\)，每个 \(e(h\cdot\xi_j)\) 与 \(1\) 只差 \(O(\rho)\)。
  2. 波几乎不动 ⇒ 函数几乎不动。 因为 \(f\) 由这 \(K\) 个波（加小误差）拼成，平移 \(h\) 后每个波只动 \(O(\rho)\)，\(K\) 个波合起来动 \(O(K\rho)\)，再加误差项，得 \(\|T^{jh}f-f\|_{L^2}\le O(K\rho)+2\sigma\)。
  3. 三个因子都 \(\approx f\)。 于是 \(f(x)\,f(x+h)\,f(x+2h)\approx f(x)^3\)，对 \(x\) 取平均得到 \(\ge\delta^3-(\text{小误差})\)。误差由 \(K\rho\) 和 \(\sigma\) 控制；因为 \(\sigma<\delta^3/8\)，它至多吃掉一半，剩 \(\tfrac12\delta^3-O(K\rho)\)。
  4. 从“好的 \(h\)”过渡到“所有 \(h\)”。 上面只对 Bohr 集里的 \(h\) 成立。但 Bohr 集在 \(Z\) 中的密度 \(\ge\rho^{K}\)（每个频率独立地切出比例约 \(\rho\) 的 \(h\)），且被积量非负，于是对全体 \(h\) 取平均时至少保留 \(\rho^K\) 倍。
  5. 选半径。 取 \(\rho\sim\delta/K\) 使 \(O(K\rho)\) 不超过 \(\tfrac14\delta^3\)，得 \(\Lambda_3\gtrsim\rho^K\delta^3=(\delta/K)^K\delta^3\)。注意这个下界随 \(K\) 增大会变得很小，但只要 \(K\) 有界，它就是依赖 \(\delta\) 的正常数。
\(e(\xi_1 x)\) 平移 \(h\) 只让相位转一个小角 \(O(\rho)\) \(h\in\mathrm{Bohr}_Z(S,\rho)\)： 所有 \(\xi_j\cdot h\approx 0\) \(\Rightarrow f(x{+}h)\approx f(x)\) \(\Rightarrow f(x)f(x{+}h)f(x{+}2h)\approx f(x)^3\) 这种 \(h\) 占比 \(\ge\rho^{K}\)
对“几乎不动每个波”的平移 \(h\)，三项等差数列的三个值都接近 \(f(x)\)，于是乘积接近 \(f(x)^3\)，计数被界住。

核心分解

为在一般情形下建立定理 10.33，现在需要用一个几乎周期函数去逼近任意函数 \(f\)。事实上我们将建立下面这条基本命题：

命题 10.36（Koopman–von Neumann 分解） 设 \(f:Z\to\mathbb{R}^+\) 满足 \(0\le f(x)\le 1\)，设 \(\sigma>0\)，并设 \(F:\mathbb{R}^+\times\mathbb{R}^+\to\mathbb{R}^+\) 为任意函数。则存在一个量 \(K=O_{\sigma,F}(1)\) 与一个分解 \(f=f_{U^\perp}+f_U\)，具有如下性质：

这条命题一个引人注目的特点是：可以通过让 \(F\) 增长得任意快，从而使对 \(f_U\) 的一致性控制任意强。为此付出的代价是：\(K\) 的上界随之大幅恶化。

读懂这条分解：什么是“一致”与“反一致”

我们将在本节余下的部分证明命题 10.36。现在先看看它如何推出定理 10.33。我们以 \(\sigma:=\delta^3/8\) 应用此命题，\(F\) 稍后选定。由命题 10.35 有 \[\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})=\Omega\!\big((\delta/K)^K\delta^3\big).\] 由于 \(f,f_{U^\perp}\) 都在 \(0\) 与 \(1\) 之间，\(f_U\) 的大小被 \(1\) 界住。应用傅里叶一致性估计与命题 10.11，我们得出 \[\Lambda_3(f,f,f)-\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})=O\!\Big(\frac{1}{F(\sigma,K)}\Big).\] 于是若选 \(F\) 增长得足够快，便可把误差项吸收进主项，得出 \[\Lambda_3(f,f,f)=\Omega\!\big((\delta/K)^K\delta^3\big).\] 由于 \(K=O_{\sigma,F}(1)=O_\delta(1)\)，结论成立。

为什么这就够了：误差吸收的逻辑
  1. 命题 10.35 给结构块 \(f_{U^\perp}\) 一个正下界 \(c(\delta,K)=\Omega((\delta/K)^K\delta^3)\)。
  2. 命题 10.11 + 一致性估计给出：换成完整的 \(f\)，计数只改变 \(O(1/F(\sigma,K))\)。
  3. 注意 \(K\) 一旦确定，下界 \(c(\delta,K)\) 就固定了；而我们事后可以把 \(F\) 选得足够大，使 \(1/F(\sigma,K)\le\tfrac12 c(\delta,K)\)。误差被吃掉一半，主项仍为正。
  4. 这就是为什么命题 10.36 允许“\(F\) 任意快”如此重要：它让我们能在知道 \(K\) 之后再把噪声压到任意小。

余下的就是证明命题 10.36。可以直接应用傅里叶变换来证明它（这本质上是 [34] 的做法）；但我们将采用一种更具遍历论色彩的方法，它更容易推广到更长的等差数列。这里的一个关键工具是条件期望。

定义 10.37（条件期望） 把 \(Z\) 的一个 \(\sigma\)-代数定义为 \(Z\) 的子集所构成的任意一个集族 \(\mathcal{B}\)，它包含 \(\varnothing\) 与 \(Z\)，并且对并、交、补封闭。（\(\sigma\)-代数与 \(Z\) 的分划一一对应，可视为同一回事。）若 \(\mathcal{B},\mathcal{B}'\) 是两个 \(\sigma\)-代数，定义 \(\mathcal{B}\vee\mathcal{B}'\) 为同时包含二者的最小 \(\sigma\)-代数。称函数 \(f:Z\to\mathbb{C}\) 关于 \(\mathcal{B}\) 可测，若它在 \(\mathcal{B}\) 的每个原子上为常值，其中原子是指 \(\mathcal{B}\) 中任一极小非空元素。给定任意 \(f:Z\to\mathbb{C}\)，定义条件期望 \(\mathbb{E}(f|\mathcal{B}):Z\to\mathbb{C}\) 为 \[\mathbb{E}(f|\mathcal{B})(x):=\mathbb{E}_{\mathcal{B}(x)}f=\frac{1}{|\mathcal{B}(x)|}\sum_{y\in\mathcal{B}(x)}f(y),\] 其中 \(\mathcal{B}(x)\) 是包含 \(x\) 的那个唯一原子；等价地，\(\mathbb{E}(f|\mathcal{B})\) 是 \(L^2(Z)\) 中到“\(\mathcal{B}\)-可测函数”空间的正交投影。
分划（\(\sigma\)-代数）把 \(Z\) 切成若干原子： 原子 1 原子 2 原子 3 原子 4 条件期望 \(\mathbb{E}(f|\mathcal{B})\)：在每个原子上把 \(f\) 换成它的平均值（阶梯函数） ＝在每块 上取平均
\(\sigma\)-代数就是把 \(Z\) 切块；条件期望就是把 \(f\) 在每块上抹平成该块的平均值，得到一个“粗粒化”的阶梯函数。分划越细，这个逼近越精。

事实证明，某些 \(\sigma\)-代数 \(\mathcal{B}\) 是“紧致的”，意思是诸如 \(\mathbb{E}(f|\mathcal{B})\) 这样的条件期望自动是几乎周期的。这一点的一个精确表述是：

命题 10.38（特征标生成紧致 \(\sigma\)-代数） 设 \(\xi\in Z\)，\(0<\varepsilon<1\)。则存在一个具有 \(O_\varepsilon(1)\) 个原子的 \(\sigma\)-代数 \(\mathcal{B}_{\varepsilon,\xi}\)，它在以下意义上近似地“包含”特征标 \(e_\xi(x):=e(\xi\cdot x)\)： \[\|e_\xi-\mathbb{E}(e_\xi|\mathcal{B}_{\varepsilon,\xi})\|_{L^\infty(Z)}=O(\varepsilon),\tag{10.20}\] 并且它还具有如下性质：对每个 \(\sigma>0\)，每个满足 \(\|f\|_{L^\infty(Z)}\le 1\) 的 \(\mathcal{B}_{\varepsilon,\xi}\)-可测函数 \(f\) 都是 \((O_{\varepsilon,\sigma}(1),O(\sigma))\)-几乎周期的。
证明. 我们使用一阶矩方法。设 \(\alpha\) 为从单位正方形 \(Q:=\{z\in\mathbb{C}:0\le\mathrm{Re}(z),\mathrm{Im}(z)<1\}\) 中随机选取的元素，并设 \(\mathcal{B}_{\varepsilon,\xi}\) 为由如下诸集合生成的 \(\sigma\)-代数： \[A_{a,b,\varepsilon,\alpha}:=\{x\in Z:\ e_\xi(x)\in\varepsilon(Q+a+bi+\alpha)\};\quad a,b\in\mathbb{Z}.\] 这些集合（它们构成 \(Z\) 的一个分划）本质上是 Bohr 集 \(\mathrm{Bohr}_Z(\{\xi\},\varepsilon)\) 的平移；其中至多 \(O(1/\varepsilon)\) 个是非空的。由于 \(e_\xi\) 在每个这样的集合上的波动至多为 \(O(\varepsilon)\)，我们得到性质 (10.20)。

现在证明后一条性质。注意到 \(f\) 是至多 \(O(1/\varepsilon)\) 个示性函数 \(1_{A_{a,b,\varepsilon,\alpha}}\) 的、系数有界的线性组合，因此只需对这 \(O(1/\varepsilon)\) 个非平凡的示性函数证明该论断。当 \(\sigma\ge 1\) 时论断平凡；并且通过把 \(\sigma\) 用最接近的 \(2\) 的幂来逼近，我们看到只需对 \(\sigma=2^{-n}\)（\(n\ge 0\) 为整数）验证论断。由 Borel–Cantelli 引理，于是只需对每个 \(n\ge 1\) 及 \(a,b\in\mathbb{Z}\) 证明 \[\mathbb{P}\big(1_{A_{a,b,\varepsilon,\alpha}}\text{ 是 }(O_{\varepsilon,n}(1),O(2^{-n}))\text{-几乎周期的}\big)=1-O(\varepsilon 2^{-n}).\]

固定 \(n,a,b\)。改写 \[1_{A_{a,b,\varepsilon,\alpha}}(x)=1_Q\!\Big(\frac{e(x\cdot\xi)}{\varepsilon}-a-bi-\alpha\Big).\] 设 \(B\) 为正方形 \(Q\) 边界的 \(\varepsilon 2^{-3n}\)-邻域。由 Urysohn 引理再接以 Weierstrass 逼近定理，我们可以写 \[1_Q(z)=P_{n,\varepsilon}(z)+O(1_B(z))+O(2^{-n}),\] 其中 \(P_{n,\varepsilon}(z)\) 是一个仅依赖于 \(n\) 的、关于 \(z\) 与 \(\bar z\) 的多项式。我们得出 \[1_{A_{a,b,\varepsilon,\alpha}}(x)=P_{n,\varepsilon}\!\Big(\frac{e(x\cdot\xi)}{\varepsilon}-a-bi-\alpha\Big)+O\!\Big(\mathbb{I}\big(\tfrac{e(x\cdot\xi)}{\varepsilon}-a-bi-\alpha\in B\big)\Big)+O(2^{-n}).\tag{10.21}\] 右端第一项容易验证是 \(O_{n,\varepsilon}(1)\)-拟周期的。一次一阶矩方法的应用很容易表明 \[\mathbb{E}\,\Big\|\mathbb{I}\big(\tfrac{e(x\cdot\xi)}{\varepsilon}-a-bi-\alpha\in B\big)\Big\|_{L^2(Z)}^2=O(\varepsilon 2^{-3n}),\] 因此由 Markov 不等式可见 (10.21) 中第二项以 \(1-O(\varepsilon 2^{-n})\) 的概率具有 \(O(2^{-n})\) 的 \(L^2(Z)\) 范数。于是我们看到 \(1_{A_{a,b,\varepsilon,\alpha}}\) 以 \(1-O(\varepsilon 2^{-n})\) 的概率是 \((O_{n,\varepsilon}(1),O(2^{-n}))\)-拟周期的，正如所欲。♦

命题 10.38 在做什么：把圆盘切成小格子

把波 \(e_\xi(x)\) 看成一个在复平面单位圆上的点。\(\mathcal{B}_{\varepsilon,\xi}\) 就是按 \(e_\xi(x)\) 落进哪个边长约 \(\varepsilon\) 的小方格来给 \(x\) 分类：落进同一格的 \(x\) 归为同一个原子。

  1. 圆周被约 \(O(1/\varepsilon)\) 个小格覆盖，所以只有 \(O(1/\varepsilon)\) 个非空原子。
  2. 同一格内 \(e_\xi\) 的取值差不超过 \(O(\varepsilon)\)，所以“在每格上取平均”得到的阶梯函数与 \(e_\xi\) 相差 \(O(\varepsilon)\)——这就是 (10.20)，即该分划“近似包含”了波 \(e_\xi\)。
  3. 随机平移 \(\alpha\) 是技术手段：让格子边界恰好落在 \(e_\xi\) 取值密集处的“倒霉概率”很小，从而每个示性函数都能被多项式 \(P_{n,\varepsilon}\)（少数波）很好逼近，只有边界附近 \(O(2^{-n})\) 的误差。这就是“紧致 ⇒ 几乎周期”。
\(e_\xi(x)\) 每格边长 \(\sim\varepsilon\)；落进同一格的 \(x\) 是同一个原子
命题 10.38 的构造：按波 \(e_\xi(x)\) 落入哪个边长约 \(\varepsilon\) 的小格，给 \(x\) 分类。格内 \(e_\xi\) 变化 \(\le O(\varepsilon)\)，所以这个分划“看得见”这个波。

可以把它推广到由多个特征标生成的 \(\sigma\)-代数：

推论 10.39 设 \(\xi_1,\dots,\xi_n\in Z\)，\(\varepsilon_1,\dots,\varepsilon_n>0\)。令 \(\mathcal{B}:=\mathcal{B}_{\varepsilon_1,\xi_1}\vee\cdots\vee\mathcal{B}_{\varepsilon_n,\xi_n}\)，其中 \(\mathcal{B}_{\varepsilon,\xi}\) 在上一命题中已定义。则每个满足 \(\|f\|_{L^\infty(Z)}\le 1\) 的 \(\mathcal{B}\)-可测函数 \(f\) 对每个 \(\sigma>0\) 都是 \((O_{\varepsilon_1,\dots,\varepsilon_n,n,\sigma}(1),O_n(\sigma))\)-几乎周期的。
证明. 注意 \(\mathcal{B}\) 至多有 \(O_{n,\varepsilon_1,\dots,\varepsilon_n}(1)\) 个原子，因此只需对示性函数 \(f=1_A\) 验证论断，其中 \(A\) 是 \(\mathcal{B}\) 的一个原子。但此时 \(1_A\) 是 \(n\) 个示性函数 \(1_{A_1}\cdots 1_{A_n}\) 之积，其中 \(A_j\) 是 \(\mathcal{B}_{\varepsilon,\xi_j}\) 的原子，于是论断由上一命题以及如下观察推出：有界几乎周期函数之积仍是有界且几乎周期的（不过常数会稍差一些）。♦

能量增量：核心引理

命题 10.36 之证明的核心，现在归结于下面这条关键引理。我们把 \(\mathcal{B}\) 关于 \(f\) 的能量 \(\mathcal{E}_f(\mathcal{B})\) 定义为 \[\mathcal{E}_f(\mathcal{B}):=\|\mathbb{E}(f|\mathcal{B})\|_{L^2(Z)}^2=\mathbb{E}_{x\in Z}\big|\mathbb{E}(f|\mathcal{B})(x)\big|^2.\]

引理 10.40（不一致性蕴含能量增量） 设 \(\varepsilon,\mu>0\) 满足 \(\varepsilon\le\mu/4\)，设 \(f:Z\to\mathbb{R}^+\) 满足 \(0\le f(x)\le 1\)，并设 \(\mathcal{B}\) 为一个 \(\sigma\)-代数，满足 \[\|f-\mathbb{E}(f|\mathcal{B})\|_{u^2(Z)}\ge\mu.\] 则存在频率 \(\xi\in Z\)，使得有如下能量增量性质： \[\mathcal{E}_f(\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})\ge\mathcal{E}_f(\mathcal{B})+\mu^2/4.\]
能量是什么，为什么会增量
证明. 由 \(u^2(Z)\) 的定义，可找到 \(\xi\in Z\) 使得 \[\big|\langle f-\mathbb{E}(f|\mathcal{B}),\,e_\xi\rangle_{L^2(Z)}\big|\ge\mu.\] 另一方面，由 (10.20) 我们看到 \(e_\xi\) 在 \(\mathcal{B}_{\varepsilon,\xi}\) 的每个原子上波动至多 \(2\varepsilon\)，因而在 \(\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi}\) 的每个原子上亦然。于是 \[\|e_\xi-\mathbb{E}(e_\xi|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})\|_{L^\infty(Z)}\le 2\varepsilon;\] 由于 \(f-\mathbb{E}(f|\mathcal{B})\) 的大小被 \(1\) 界住，我们得出 \[\big|\langle f-\mathbb{E}(f|\mathcal{B}),\,e_\xi-\mathbb{E}(e_\xi|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})\rangle_{L^2(Z)}\big|\le 2\varepsilon.\] 由于 \(\varepsilon<\mu/4\)，我们推得 \[\big|\langle f-\mathbb{E}(f|\mathcal{B}),\,\mathbb{E}(e_\xi|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})\rangle_{L^2(Z)}\big|\ge\mu/2.\] 由易于验证的恒等式 \[\langle f-\mathbb{E}(f|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi}),\,\mathbb{E}(e_\xi|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})\rangle_{L^2(Z)}=0,\] 我们于是有 \[\big|\langle \mathbb{E}(f|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})-\mathbb{E}(f|\mathcal{B}),\,\mathbb{E}(e_\xi|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})\rangle_{L^2(Z)}\big|\ge\mu/2,\] 从而由 Cauchy–Schwarz 不等式 \[\|\mathbb{E}(f|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})-\mathbb{E}(f|\mathcal{B})\|_{L^2(Z)}^2\ge\mu^2/4.\] 结论随即由勾股定理推出。♦
证明里几步的动机
  1. 找到相关的波。 \(\|\cdot\|_{u^2}=\sup_\xi|\widehat{\cdot}(\xi)|\) 大，等价于与某个波 \(e_\xi\) 的内积 \(\ge\mu\)。
  2. 波几乎被新分划抓住。 由 (10.20)，加进 \(\mathcal{B}_{\varepsilon,\xi}\) 后，\(e_\xi\) 与它在新分划上的条件期望只差 \(O(\varepsilon)\)。所以用 \(\mathbb{E}(e_\xi|\cdots)\) 替换 \(e_\xi\)，内积只损失 \(2\varepsilon<\mu/2\)，仍 \(\ge\mu/2\)。
  3. 把残差换成投影差。 恒等式（投影的正交性）让我们把 \(f-\mathbb{E}(f|\mathcal{B})\) 替换成两次投影之差 \(\mathbb{E}(f|\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})-\mathbb{E}(f|\mathcal{B})\)，这正是“新增的能量”那部分。
  4. Cauchy–Schwarz + 勾股。 内积 \(\ge\mu/2\)，而 \(\|\mathbb{E}(e_\xi|\cdots)\|_2\le 1\)，故投影差的范数 \(\ge\mu/2\)，平方 \(\ge\mu^2/4\)。由勾股定理，这个平方恰是能量的增量 \(\mathcal{E}_f(\mathcal{B}\vee\mathcal{B}_{\varepsilon,\xi})-\mathcal{E}_f(\mathcal{B})\)。

命题 10.36 的证明：双重循环算法

现在我们已有足够的工具来证明命题 10.36。

命题 10.36 之证明. 我们通过如下双重循环算法构造一对嵌套的 \(\sigma\)-代数 \(\mathcal{B}\subset\mathcal{B}'\) 以及一个整数 \(K\ge 1\)。

观察：每次从第 3 步返回第 2 步时，能量 \(\mathcal{E}_f(\mathcal{B}')\) 至少增加 \(\dfrac{1}{4F(\sigma,K)^2}\)，而 \(K\) 不变。另一方面，由于 \(f\) 有界，\(\mathcal{E}_f(\mathcal{B}')\) 在 \(0\) 与 \(1\) 之间变化。因此在终止或返回第 1 步之前，最多只能从第 3 步返回第 2 步 \(4F(\sigma,K)^2\) 次。此外，每次从第 3 步返回第 1 步时，能量 \(\mathcal{E}_f(\mathcal{B})\) 至少增加 \(\sigma^2/4\)，所以最多只能从第 3 步返回第 1 步 \(4/\sigma^2\) 次。于是这个算法在有限步后终止。

这时若令 \(f_{U^\perp}:=\mathbb{E}(f|\mathcal{B}')\) 与 \(f_U:=f-\mathbb{E}(f|\mathcal{B}')\)，则有 \(f=f_U+f_{U^\perp}\)，有 \(\|f_U\|_{u^2(Z)}\le\dfrac{1}{F(\sigma,K)}\)，有 \(0\le f_{U^\perp}\le 1\)，以及 \(\mathbb{E}_Z f_{U^\perp}=\mathbb{E}_Z f\)。最后，由构造有 \(\mathcal{E}_f(\mathcal{B}')\le\mathcal{E}_f(\mathcal{B})+\sigma^2/4\)，从而由勾股定理 \(\|f_{U^\perp}-\mathbb{E}(f|\mathcal{B})\|_{L^2(Z)}\le\sigma/2\)。由于由构造 \(\mathbb{E}(f|\mathcal{B})\) 是 \((K,\sigma/2)\)-几乎周期的，我们得出 \(f_{U^\perp}\) 是 \((K,\sigma)\)-几乎周期的。

剩下唯一需要验证的是 \(K=O_{\sigma,F}(1)\)。注意在每个阶段，\(\mathcal{B}\) 与 \(\mathcal{B}'\) 都是有限多个形如 \(\mathcal{B}_{\varepsilon,\xi}\) 的 \(\sigma\)-代数之并（join）。特别地，推论 10.39 对这些 \(\sigma\)-代数适用。一个简单的归纳论证随即表明：在迭代的每个阶段，\(\mathcal{B}\) 与 \(\mathcal{B}'\) 都是至多 \(O_{\sigma,F}(1)\) 个 \(\sigma\)-代数之并，所涉参数 \(\varepsilon\) 从下方被 \(\Omega_{\sigma,F}(1)\) 界住，而参数 \(K\) 始终从上方被 \(O_{\sigma,F}(1)\) 界住。结论成立。♦

算法为什么停、停了为什么是想要的分解
  1. 内层循环（第 2↔3 步）：把当前 \(K\) 固定，疯狂细分分划。 只要残差还不一致（\(u^2\) 范数大），引理 10.40 就让能量每次跳 \(\ge\dfrac{1}{4F^2}\)。能量被 \(1\) 封顶，所以内层最多跑 \(4F^2\) 次。
  2. 外层循环（回第 1 步）：能量一旦累计涨过 \(\sigma^2/4\)，就重置 \(K\)。 因为能量整体只能从 \(0\) 涨到 \(1\)，每次外层涨 \(\ge\sigma^2/4\)，所以外层最多 \(4/\sigma^2\) 次。两层都有限 ⇒ 算法必停。
  3. 停下来的那一刻，恰好两全其美。 终止条件保证 \(f_U=f-f_{U^\perp}\) 的 \(u^2\) 范数 \(\le 1/F\)（足够一致）；而 \(f_{U^\perp}=\mathbb{E}(f|\mathcal{B}')\) 与某个 \((K,\sigma/2)\)-几乎周期的 \(\mathbb{E}(f|\mathcal{B})\) 只差 \(\sigma/2\)，故自身是 \((K,\sigma)\)-几乎周期的（结构化）。
  4. 为什么要分内外两层？ 因为“一致”的标准 \(1/F(\sigma,K)\) 依赖于 \(K\)，而细分会让 \(K\) 变化。两层结构保证：要么 \(K\) 不变而能量稳涨（内层），要么 \(K\) 重置但只发生有限次（外层）。最终 \(K\) 被锁定在 \(O_{\sigma,F}(1)=O_\delta(1)\)。
第1步：定最小 \(K\) 使 \(\mathbb{E}(f|\mathcal{B})\) 几乎周期 第2步：残差一致? \(u^2\le 1/F\)? 引理10.40 细分 能量 +\(\tfrac{1}{4F^2}\) 第3步：累涨\(>\sigma^2/4\)? 否 否：回第2步(内层) 是：回第1步(外层) 是→终止 能量 1 迭代步数 封顶 = 1 小跳=内层 大跳=外层重置K
左：双重循环流程。右：能量单调上升且被 \(1\) 封顶——小台阶来自内层细分（\(K\) 不变），大台阶来自外层（能量累涨过 \(\sigma^2/4\)，重置 \(K\)）。两类台阶都只能发生有限次，故算法必停。

习题

习题
  1. 10.5.1　设 \(f,g:Z\to\mathbb{C}\) 的大小都被 \(1\) 界住，且对某个 \(0<\sigma\le 1\) 都是 \((K,\sigma)\)-几乎周期的。证明 \(f+g\) 是 \((2K,2\sigma)\)-几乎周期的，并且 \(fg\) 是 \((K^2,4\sigma)\)-几乎周期的。
  2. 10.5.2　设 \(f:Z\to\mathbb{C}\) 是 \((K,\sigma)\)-几乎周期的。证明可以用至多 \(O_{K,\sigma}(1)\) 个在 \(L^2(Z)\) 度量下半径为 \(2\sigma\) 的球覆盖集合 \(\{T^hf:h\in Z\}\subset L^2(Z)\)。由此推出 \[\mathbb{P}_{h\in Z}\big(\|T^hf-f\|_{L^2(Z)}\le 4\sigma\big)=\Omega_{K,\sigma}(1),\] 这或许有助于解释“几乎周期”这一术语。关于本结果的一个逆命题，见下面的习题 10.5.5。
  3. 10.5.3　设 \(\xi_1,\dots,\xi_n\) 为 \(Z\) 的一个非结合（dissociated）子集。利用 Rudin 不等式（引理 4.33），证明 \[\mathbb{P}_{h\in Z}\Big(\sum_{j=1}^{n}|e(\xi_j\cdot h)-1|^2
  4. 10.5.4　设 \(f:Z\to\mathbb{C}\) 满足 \(\|f\|_{L^2(Z)}=\|\hat f\|_{\ell^2(Z)}\ge 4\sigma\) 且 \(\|\hat f\|_{\ell^\infty(Z)}\le\delta\sigma\)（对某些 \(\sigma,\delta>0\)）。建立界 \[\mathbb{P}_{h\in Z}\Big(\sum_{\xi\in Z}|e(\xi\cdot h)-1|^2\,|\hat f(\xi)|^2<4\sigma^2\Big)=O(\delta^c)\] （其中 \(c>0\) 为某个绝对常数）。（提示：归一化 \(\|\hat f\|_{\ell^2(Z)}=1\)，从而 \(\sigma\le 1/4\)，然后令 \(\xi_1,\dots,\xi_n\) 为以概率分布 \(|\hat f(\xi)|^2\) 取值的独立同分布随机变量。证明 \(\xi_1,\dots,\xi_n\) 以概率 \(1-O(2^n\delta)\) 是非结合的，并把 (10.22) 与一阶矩方法结合应用。最后对 \(n\) 优化。）

返回 全书目录