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

10.1　总体策略General strategy

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，尽量把每一步的直觉与动机讲清楚，不用比喻。

本节目标我们想证明一类“Roth 型定理”：只要一个集合 \(A\) 在某个有限群里足够稠密，它就一定含有长度为 3 的等差数列（即三个数 \(x,\,x+r,\,x+2r\) 全在 \(A\) 里，且 \(r\neq 0\)）。本节不给完整证明，而是先搭一个统一的框架：用一个“三线性形式” \(\Lambda_3\) 把“\(A\) 里有多少个长度-3 等差数列”变成一个可计算的量，再说明两条通向证明的主干路线——Roth 的密度增量法与 Furstenberg–Szemerédi 的能量增量法。读懂本节，后面几节才有地图可循。

在本节中，我们就长度为 3 的等差数列做一些一般性的观察，并以高层次的语言描述若干可用于证明 Roth 型定理的策略。

设我们工作在一个固定的、奇数阶的有限加性群 \(Z\) 中，并设 \(A\) 是 \(Z\) 的一个子集。我们把 \(A\) 设想为相当稠密的，即其密度 \(0\le \mathbb{P}_Z(A)\le 1\) 适度地大。于是 Roth 定理就是说：若 \(|Z|\) 充分大，则 \(A\) 必含有长度为 3 的等差数列。

先约定几个记号

三线性形式 \(\Lambda_3\)：把“等差数列个数”变成一个平均值

为解释为何 Roth 定理应当成立，引入如下三线性形式是方便的：对任意 \(f,g,h:Z\to\mathbb{C}\)，定义 \[\tag{10.1}\Lambda_3(f,g,h):=\mathbb{E}_{x,r\in Z}\,f(x)\,g(x+r)\,h(x+2r).\] 特别地注意到 \[\tag{10.2}\Lambda_3(1_A,1_A,1_A)=\mathbb{P}_{x,r\in Z}\big(x,\,x+r,\,x+2r\in A\big),\] 因此量 \(\Lambda_3(1_A,1_A,1_A)\) 度量的正是 \(Z\) 中那些完全落在 \(A\) 内的等差数列 \((x,x+r,x+2r)\) 所占的比例。

为什么 (10.1) 一代入示性函数就是“数等差数列” 把 \(f=g=h=1_A\) 代入 (10.1)：乘积 \(1_A(x)\,1_A(x+r)\,1_A(x+2r)\) 只有当三项全为 1（即 \(x,x+r,x+2r\) 都在 \(A\) 里）时才等于 \(1\)，否则为 \(0\)。所以这是一个“是否成立”的指示器。
  1. 对所有 \((x,r)\) 求和，得到的是“三点全在 \(A\) 里的 \((x,r)\) 对”的个数。
  2. 除以总对数 \(|Z|^2\)（因为 \(x,r\) 各有 \(|Z|\) 种取法），就把个数变成了比例，这正是 (10.2) 的右边。
  3. 这里允许 \(r=0\)：那是“退化”的等差数列 \((x,x,x)\)。后面会专门把它扣掉。
奇数阶循环群 Z 上的等差三点 x x+r x+2r +r +r
从 \(x\) 出发，每次走相同的步长 \(r\)，依次得到 \(x+r\)、\(x+2r\)。三点全部落在 \(A\) 中，就算一个“长度-3 等差数列”。\(\Lambda_3(1_A,1_A,1_A)\) 就是这种三点配置在所有 \((x,r)\) 中所占的比例。

启发式：若 \(A\) “像随机的”，则 \(\Lambda_3\approx \mathbb{P}_Z(A)^3\)

直觉上，如果 \(A\) 是“随机”分布的，那么三个事件 \(x\in A\)、\(x+r\in A\)、\(x+2r\in A\) 应当是“独立的”，于是我们期望 \[\tag{10.3}\begin{aligned}\Lambda_3(1_A,1_A,1_A)&\approx \mathbb{P}_{x,r\in Z}(x\in A)\,\mathbb{P}_{x,r\in Z}(x+r\in A)\,\mathbb{P}_{x,r\in Z}(x+2r\in A)\\&=\mathbb{P}_Z(A)^3.\end{aligned}\] 因此若 \(A\) 在 \(Z\) 中相当稠密，我们期望 \(\Lambda_3(1_A,1_A,1_A)\) 是大的。

为什么独立就给出三次方 当 \(x,r\) 在 \(Z\) 上均匀随机时，单个点 \(x\)（或 \(x+r\)、\(x+2r\)）也均匀分布在 \(Z\) 上，所以每个事件“落在 \(A\) 里”的概率都是密度 \(\mathbb{P}_Z(A)\)。
  1. 若三件事真的互不影响，则“三件事同时发生”的概率 = 三个概率相乘 = \(\mathbb{P}_Z(A)\cdot\mathbb{P}_Z(A)\cdot\mathbb{P}_Z(A)\)。
  2. 举例：密度 \(0.3\) 时，期望比例约为 \(0.3^3=0.027\)，乘以总对数 \(|Z|^2\) 就是大量的等差数列——只要 \(|Z|\) 大，这个数远大于 0。
  3. “独立”只是启发式，对某些特殊的 \(A\) 会失效（见下文与习题），所以才需要严格化。

另一方面，若 \(|Z|\) 为奇数且 \(A\) 不含任何真（即 \(r\neq0\) 的）长度-3 等差数列，那么唯一能落在 \(A\) 内的数列 \((x,x+r,x+2r)\) 只能是 \(x\in A\) 且 \(r=0\) 的那些，于是 \[\tag{10.4}\Lambda_3(1_A,1_A,1_A)=\mathbb{P}_Z(A)/|Z|.\] 若 \(|Z|\) 充分大，这似乎与启发式 (10.3) 相冲突。

(10.4) 是怎么算出来的 “没有真等差数列”意味着满足 \(x,x+r,x+2r\in A\) 的 \((x,r)\) 只剩 \(r=0\) 这一种退化情形。
  1. \(r=0\) 时三点重合成 \((x,x,x)\)，要求 \(x\in A\)，共有 \(|A|\) 个 \(x\)。
  2. 这种 \((x,r)\) 对有 \(|A|\) 个，占全部 \(|Z|^2\) 对的比例为 \(|A|/|Z|^2=\mathbb{P}_Z(A)/|Z|\)。
  3. 对比 (10.3) 的 \(\mathbb{P}_Z(A)^3\)：当 \(|Z|\) 很大时 \(\mathbb{P}_Z(A)/|Z|\) 趋于 \(0\)，而 \(\mathbb{P}_Z(A)^3\) 是个固定的正数。两者矛盾——这说明“没有真等差数列”不可能发生，从而 \(A\) 必含真等差数列。
这正是用 \(\Lambda_3\) 证 Roth 定理的核心逻辑：把 (10.3) 严格化即可。

因此，要证明 Roth 定理，只需建立 (10.3) 的某种严格类比。特别地，Roth 定理可由下述结果推出。

定理 10.9（Varnavides 定理）[372]设 \(Z\) 为奇数阶的有限加性群。则对任意非空集合 \(A\subseteq Z\) 有 \[\Lambda_3(1_A,1_A,1_A)=\Omega_{\mathbb{P}_Z(A)}(1).\] 换言之，\(\Lambda_3(1_A,1_A,1_A)\ge c(\mathbb{P}_Z(A))\)，其中 \(c(\mathbb{P}_Z(A))>0\) 只依赖于 \(A\) 的密度 \(\mathbb{P}_Z(A)\)，而不依赖于群 \(Z\)。更一般地，若 \(f:Z\to\mathbb{R}^+\) 是一个非负、不恒为零、且满足 \(0\le f(x)\le 1\)（对一切 \(x\in Z\)）的函数，则 \[\Lambda_3(f,f,f)=\Omega_{\mathbb{E}_Z(f)}(1).\]
记号 \(\Omega_{\delta}(1)\) 是什么意思记号 \(\Lambda_3=\Omega_{\mathbb{P}_Z(A)}(1)\) 读作“\(\Lambda_3\) 有一个只依赖密度的正下界”。关键在于这个下界与 \(Z\) 的大小无关：无论群多大，只要密度固定为 \(\delta\)，等差数列的比例就被某个固定的正数 \(c(\delta)\) 顶住，不会随 \(|Z|\to\infty\) 衰减到 0。这正好封死了 (10.4) 那条退路。

注意，Varnavides 定理实际上比 Roth 定理更强一些：它蕴含密度为 \(\delta\) 的任一子集 \(A\) 含有 \(\Omega_\delta(|Z|^2)\) 个真长度-3 等差数列（当 \(Z\) 依赖 \(\delta\) 充分大时）。这与 Roth 定理形成对照——后者只保证存在一个真长度-3 等差数列。尽管如此，一个简单的平均论证表明这两个定理是等价的：见习题。

没有等差数列 ⇒ 不均匀：线性偏差登场

目前仍不清楚如何把启发式 (10.3) 转化为像定理 10.9 那样的严格陈述。事实上，(10.3) 对某些特殊的 \(A\) 会失效：当 \(A\) 是 \(Z\) 的子群时，\(\Lambda_3(1_A,1_A,1_A)\) 可高达 \(\mathbb{P}_Z(A)^2\)；而当 \(A\) 取自 Behrend 例子时，它可低至 \(\mathbb{P}_Z(A)^{\,O(\log\frac{1}{\mathbb{P}_Z(A)})}\)（见习题）。然而，结果表明：只要 \(A\) 的线性偏差很小，\(\Lambda_3(1_A,1_A,1_A)\) 就会非常接近 (10.3) 所预言的 \(\mathbb{P}_Z(A)^3\)。回忆定义 4.12：加性集 \(A\) 的线性偏差（或 Fourier 偏差）\(\|A\|_u\) 定义为 \[\|A\|_u:=\sup_{\xi\in Z\setminus 0}|\widehat{1_A}(\xi)|=\sup_{\xi\in Z\setminus 0}\Big|\mathbb{E}_{x\in Z}\,1_A(x)\,e(-\xi\cdot x)\Big|.\]

直观：线性偏差测“是否偏向某个频率”这里 \(e(-\xi\cdot x)\) 是单位圆上转动的复数（“频率为 \(\xi\) 的波”），\(\widehat{1_A}(\xi)=\mathbb{E}_{x\in Z}1_A(x)e(-\xi\cdot x)\) 是 \(A\) 与该波的“相关程度”（Fourier 系数）。
命题 10.10（无等差数列蕴含不均匀）[287]设 \(A\) 是奇数阶有限加性群 \(Z\) 中的加性集。则 \[\big|\Lambda_3(1_A,1_A,1_A)-\mathbb{P}_Z(A)^3\big|\le \|A\|_u\,\mathbb{P}_Z(A).\] 特别地，若 \(A\) 不含真长度-3 等差数列，则有线性偏差估计 \[\|A\|_u\ge \mathbb{P}_Z(A)^2-\frac{1}{|Z|}.\]
证明. 由恒等式 \(a-2(a+r)+(a+2r)=0\)，以及当 \(|Z|\) 为奇数时映射 \(x\mapsto 2\cdot x\) 是 \(Z\) 上的双射这一观察，我们看出 \[\Lambda_3(1_A,1_A,1_A)=\frac{1}{|Z|^2}\Big|\big\{(a_1,a_2,a_3)\in A\times(-2\cdot A)\times A:\ 0=a_1+a_2+a_3\big\}\Big|.\] 应用引理 4.13 即得第一个不等式。第二个论断随后由 (10.4) 推出。♦
把命题 10.10 的证明拆开看
  1. 换元的动机：令 \(a_1=x\)、\(a_3=x+2r\)，则 \(x+r=\tfrac{a_1+a_3}{2}\)。等差条件 \(x,x+r,x+2r\in A\) 就变成“\(a_1\in A\)、\(a_3\in A\)，且中点 \(\tfrac{a_1+a_3}{2}\in A\)”。\(|Z|\) 奇数保证“除以 2”有意义（\(x\mapsto 2x\) 可逆）。
  2. 恒等式 \(a-2(a+r)+(a+2r)=0\) 正是说：第一项、第二项的 \(-2\) 倍、第三项三者相加为 0。于是把中点项替换成在 \(-2\cdot A\) 中取值的 \(a_2\)，三点共线条件等价于 \(a_1+a_2+a_3=0\)。
  3. 这样 \(\Lambda_3\) 就被改写成“在 \(A,\,-2\cdot A,\,A\) 三个集合中各取一元、和为 0 的三元组个数”除以 \(|Z|^2\)。这是一种标准的加性能量/相关形式，引理 4.13 给出它与 \(\mathbb{P}_Z(A)^3\) 之差被 \(\|A\|_u\,\mathbb{P}_Z(A)\) 控制。
  4. 得到第二式：若无真等差数列，由 (10.4)，\(\Lambda_3=\mathbb{P}_Z(A)/|Z|\)。代入第一式：\(|\mathbb{P}_Z(A)/|Z|-\mathbb{P}_Z(A)^3|\le\|A\|_u\mathbb{P}_Z(A)\)，两边除以 \(\mathbb{P}_Z(A)\) 并整理即得 \(\|A\|_u\ge \mathbb{P}_Z(A)^2-\tfrac{1}{|Z|}\)。

这说明：启发式 (10.3) 唯一可能失效的方式，就是函数 \(1_A\) 与某个线性特征 \(e(\xi\cdot x)\) 有大的相关。这个非常重要的观察可看作关于 \(\Lambda_3\) 的一条逆定理；下一章我们会回到这个视角。上述命题对一般函数也有类比。定义函数 \(f:Z\to\mathbb{C}\) 的线性偏差 \(\|f\|_{u^2(Z)}\) 为 \[\tag{10.5}\|f\|_{u^2(Z)}:=\sup_{\xi\in Z}|\widehat{f}(\xi)|.\] 记号 \(u^2(Z)\) 的来由将在下一章说得更清楚。例如注意到，对任意 \(A\subseteq Z\) 有 \(\|A\|_u=\|1_A-\mathbb{P}_Z(A)\|_{u^2(Z)}\)。

两个偏差记号的区别\(\|A\|_u\) 的上确界不含 \(\xi=0\)（已经把密度那一项剔掉），而 \(\|f\|_{u^2(Z)}\) 的上确界包含所有 \(\xi\)。等式 \(\|A\|_u=\|1_A-\mathbb{P}_Z(A)\|_{u^2(Z)}\) 把两者对上：从 \(1_A\) 里减去常数 \(\mathbb{P}_Z(A)\)，正好把 \(\xi=0\) 的 Fourier 系数清零，于是“含 0”的上确界等于“不含 0”的上确界。
命题 10.11设 \(Z\) 为奇数阶。对任意函数 \(f,g,h:Z\to\mathbb{C}\)，我们有恒等式 \[\tag{10.6}\Lambda_3(f,g,h)=\sum_{\xi\in Z}\widehat{f}(\xi)\,\widehat{g}(-2\xi)\,\widehat{h}(\xi).\] 由此可得估计 \[|\Lambda_3(f,g,h)|\le \|f\|_{u^2(Z)}\,\|g\|_{L^2(Z)}\,\|h\|_{L^2(Z)},\] 且把 \(f,g,h\) 在右端轮换后同样成立。
证明. 由 Fourier 反演公式 (4.4) 我们有 \[f=\sum_{\xi_1}\widehat{f}(\xi_1)\,e_{\xi_1},\qquad g=\sum_{\xi_2}\widehat{g}(\xi_2)\,e_{\xi_2},\qquad h=\sum_{\xi_3}\widehat{h}(\xi_3)\,e_{\xi_3},\] 于是 \[\Lambda_3(f,g,h)=\sum_{\xi_1,\xi_2,\xi_3\in Z}\widehat{f}(\xi_1)\,\widehat{g}(\xi_2)\,\widehat{h}(\xi_3)\,\Lambda_3(e_{\xi_1},e_{\xi_2},e_{\xi_3}).\] 另一方面，用引理 4.5 直接计算给出 \[\Lambda_3(e_{\xi_1},e_{\xi_2},e_{\xi_3})=\mathbb{I}(\xi_2=-2\xi_1;\ \xi_3=\xi_1),\] 此即给出 (10.6)。再由 Parseval 恒等式 (4.3) 以及 \(Z\) 为奇数阶的假设，我们有 \[\sum_{\xi\in Z}|\widehat{g}(-2\xi)|^2=\|g\|_{L^2(Z)}^2,\qquad \sum_{\xi\in Z}|\widehat{h}(\xi)|^2=\|h\|_{L^2(Z)}^2,\] 于是由 Hölder 不等式即得所要的论断。\(f,g,h\) 角色轮换的情形类似。♦
命题 10.11 在做一件什么事 它把“在物理空间里数等差数列”的 \(\Lambda_3\)，翻译成了“在频率空间里把 Fourier 系数相乘求和”。
  1. 把每个函数按频率展开（反演公式），\(\Lambda_3\) 就成了对所有频率三元组 \((\xi_1,\xi_2,\xi_3)\) 的求和。
  2. 纯频率 \(e_{\xi}\) 的 \(\Lambda_3\) 几乎全为 0，只有当 \(\xi_2=-2\xi_1\) 且 \(\xi_3=\xi_1\) 时才贡献 1（这就是 \(\mathbb{I}(\cdots)\)）。原因仍是等差结构 \(\xi_1-2\xi_2\cdots\) 的“频率守恒”。
  3. 于是三重和塌缩成单重和 (10.6)：只剩参数 \(\xi\)，对应 \(\widehat{f}(\xi)\widehat{g}(-2\xi)\widehat{h}(\xi)\)。
  4. 得到不等式：把 \(\widehat{f}(\xi)\) 用它的最大值 \(\|f\|_{u^2}\) 提到求和外面，剩下 \(\sum_\xi|\widehat{g}(-2\xi)||\widehat{h}(\xi)|\) 用 Cauchy–Schwarz/Hölder 配上 Parseval，就变成 \(\|g\|_{L^2}\|h\|_{L^2}\)。结论：只要 \(f\) 的线性偏差 \(\|f\|_{u^2}\) 小，\(\Lambda_3\) 就小——这是把“均匀⇒可控”严格化的工具。

两条主干路线：密度增量法 vs 能量增量法

为利用诸如命题 10.10 或命题 10.11 这样的逆向结果，有两种论证可供使用：Roth 的密度增量论证，以及 Furstenberg 与 Szemerédi 各自（在非常不同的背景下）发展出的能量增量论证。

密度增量论证非正式地如下进行。为证 Roth 定理，反设可以在一个大群 \(Z\)（或区间 \([1,N]\)）中找到一个稠密集 \(A\)，它不含长度为 3 的等差数列。命题 10.10 于是蕴含 \(A\) 有大的线性偏差，从而 \(1_A\) 与某个线性相位函数 \(e(\xi\cdot x)\) 相关。结果表明，这种线性偏差可以转化为一个密度增量：更确切地说，原空间 \(Z\) 中存在某个结构化子集 \(Z'\)（如一个子群、一个子等差数列，或一个 Bohr 集），\(A\) 在其上的密度更大，即 \(\mathbb{P}_{Z'}(A)>\mathbb{P}_Z(A)\)。（回忆 \(\mathbb{P}_{Z'}(A)=|A\cap Z'|/|Z'|\) 而 \(\mathbb{P}_Z(A)=|A|/|Z|\)。）然后转到这个结构化子集上，重复该论证。若原空间 \(Z\) 足够大，我们就能把这个论证运行如此多步，以致 \(A\) 的相对密度最终超过 1——矛盾。

密度增量为什么能导出矛盾
  1. 起点：稠密的 \(A\)，密度 \(\delta_0=\mathbb{P}_Z(A)\)，假设它没有等差数列。
  2. 由命题 10.10，没有等差数列 ⇒ 线性偏差大 ⇒ 在某结构化子集 \(Z'\) 上密度跳到 \(\delta_1>\delta_0\)（增量有定量下界，例如 \(\delta_1\ge \delta_0+c\delta_0^2\)）。
  3. 在 \(Z'\) 上重复：\(\delta_2>\delta_1>\delta_0\cdots\) 每一步密度严格上升。
  4. 密度永远 \(\le 1\)，但它在不断上升且每步增量不太小，所以不可能无限重复。步数耗尽时只能是“假设错误”——即 \(A\) 其实含有等差数列。这就是反证。

能量增量论证则不同，它瞄准的是证明 Varnavides 定理而非 Roth 定理（即寻求 \(\Lambda_3(f,f,f)\) 的非平凡下界）。我们不再不断更换环绕空间 \(Z\)，而是把 \(Z\) 固定下来，转而构造原函数 \(f\) 的某些低复杂度逼近 \(f_{U^\perp}\)。初始时，我们的逼近就取为密度 \(f_{U^\perp}=\mathbb{P}_Z(A)\)。现在考虑示性函数与逼近之间的误差 \(f_U:=f-f_{U^\perp}\)。若这个误差是非常线性均匀的（即 Fourier 偏差 \(\|f_U\|_{u^2(Z)}\) 很小），则可用命题 10.11 把 \(\Lambda_3(f,f,f)\) 用 \(\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})\) 来逼近，并利用 \(f_{U^\perp}\) 的低复杂度来得到后者的非平凡下界。反之，若误差表现出线性偏差，我们就可以利用它来精化逼近 \(f_{U^\perp}\)，把这个偏差吸收进来；这会使 \(f_{U^\perp}\) 的能量 \(\|f_{U^\perp}\|_{L^2(Z)}^2\) 显著增加。然后重复该论证，直到误差 \(f_U\) 不再含有偏差为止；一个关键点是：\(f\)（从而 \(f_{U^\perp}\)）在整个迭代过程中保持有界，因此 \(f_{U^\perp}\) 的能量不可能无限增长。

密度增量法（Roth） 能量增量法（Furstenberg–Szemerédi） 空间 Z 不断缩小，密度不断上升 δ₀ δ₁>δ₀ δ₂>δ₁ 密度超过 1 ⇒ 矛盾 空间 Z 固定，逼近的能量不断上升 能量有上界 ⇒ 迭代必停
两条路线都靠“某个单调量被一道屏障挡住、却又每步必增、于是迭代必须终止”来收场：左边单调上升且 \(\le 1\) 的是密度，右边单调上升且有上界的是逼近的能量 \(\|f_{U^\perp}\|_{L^2}^2\)。

习题

习题
  1. 10.1.1 设 \(Z\) 为奇数阶有限加性群，\(0<\delta<1\)，并设 \(A\) 是 \(Z\) 的一个随机子集，使得各事件 \(x\in A\) 相互独立且 \(\mathbb{P}(x\in A)=\delta\)。证明：以概率 \(1-o_{|Z|\to\infty;\delta}(1)\)，有 \(\mathbb{P}_Z(A)=\delta+o_{|Z|\to\infty;\delta}(1)\) 且 \(\Lambda_3(1_A,1_A,1_A)=\delta^3+o_{|Z|\to\infty;\delta}(1)\)，从而在随机情形下证实 (10.3)。（提示：用推论 1.9。）
  2. 10.1.2 设 \(Z\) 为奇数阶有限加性群。证明 \(\Lambda_3(1_A,1_A,1_A)\le \mathbb{P}_Z(A)^2\)，且等号成立当且仅当 \(A\) 是 \(Z\) 的某个子群的平移。
  3. 10.1.3 设 \(N,d,r\ge 1\) 为整数，考虑集合 \[A=\big\{(n_1,\dots,n_d)\in[0,N/2)^d:\ n_1^2+\cdots+n_d^2=r\big\},\] 将其视为 \(\mathbb{Z}_N^d\) 的子集。证明该集合不含真长度-3 等差数列，且对适当选取的 \(r\)，其基数可大到 \((N/2)^d/(d^2N^2)\)。特别地推出 \(r_3(\mathbb{Z}_N^d)\ge N^d/(2^d d^2 N^2)\)。
  4. 10.1.4（Behrend 例子）[21] 利用前一习题与一个 Freiman 同构，建立界 \[r_3(\mathbb{Z}_N),\ r_3([1,N])=\Omega\!\big(N\,e^{-O(\sqrt{\log N})}\big)\] 对一切大 \(N\) 成立。特别地，并非对某个固定 \(\varepsilon>0\) 有 \(r_3([1,N]),r_3(\mathbb{Z}_N)=O(N^{1-\varepsilon})\)。这排除了若干证明 Roth 定理或 Szemerédi 定理的初等途径（例如完全基于 Cauchy–Schwarz 与鸽巢原理型的论证），因为它们往往只给出多项式型的界。我们注意到更一般的估计 \[r_k(\mathbb{Z}_N),\ r_k([1,N])=\Omega_k\!\Big(N\exp\!\big(-O_k(\log N)^{1/(1+\log_2(k-1))}\big)\Big)\] 对一切 \(k\ge 3\) 已由类似论证在 [277]、[221] 中建立。
  5. 10.1.5 对任意 \(0<\delta<1\)，给出一个循环群 \(\mathbb{Z}_N\) 中加性集 \(A\) 的例子，使得 \(\mathbb{P}_Z(A)\ge\delta\) 但 \[\Lambda_3(1_A,1_A,1_A)=O\big(\delta^{\,\Omega(\log\frac{1}{\delta})}\big).\] （提示：用 Behrend 例子。）因此，不可能建立任何形如 \(\Lambda_3(1_A,1_A,1_A)=\Omega(\mathbb{P}_Z(A)^C)\) 的下界（对任何绝对常数 \(C>0\)）。
  6. 10.1.6 [253] 设 \(N\) 为大数。证明可将 \(\mathbb{Z}_N\) 染成 \(\exp(O(\sqrt{\log N}))\) 个色类，使得没有任何色类含有真长度-3 等差数列。提示：修改 Behrend 例子。
  7. 10.1.7 证明：对集合 \(A\) 的 Varnavides 定理蕴含对函数 \(f\) 的 Varnavides 定理。（提示：要么用一个示性函数的常数倍从下方界住 \(f\)，要么用 \(f(x)\) 作为 \(x\in A\) 的概率以概率方式构造集合 \(A\)，再用一阶矩方法。）
  8. 10.1.8 证明：Roth 定理的特例 \(r_3([1,N])=o_{N\to\infty}(N)\) 蕴含 \(\mathbb{Z}_N\) 的 Varnavides 定理。（提示：取 \(\mathbb{Z}_N\) 中一个集合 \(A\)，将它与一个随机选取的等差数列 \(a+[1,M]\cdot r\)（\(M\) 适度大）相交，对该等差数列 \(a+[1,M]\cdot r\) 应用 Roth 定理，然后用一阶矩方法。）
  9. 10.1.9 设 \(F\) 为有限域。证明：Roth 定理的特例 \(r_3(F^n)=o_{n\to\infty;F}(N)\) 蕴含 \(F^n\) 的 Varnavides 定理。（提示：取 \(F^n\) 中一个集合 \(A\)，将它与一个随机选取的 \(m\) 维仿射子空间相交（\(m\) 适度大），然后如前一习题那样论证。）
  10. 10.1.10 证明：对任意 \(Z\) 的 Roth 定理蕴含对任意 \(Z\) 的 Varnavides 定理。
  11. 10.1.11 利用命题 10.11 与分解 \(1_A=(1_A-\mathbb{P}_Z(A))+\mathbb{P}_Z(A)\)，给出命题 10.10 的另一种证明。
  12. 10.1.12 假设定理 10.9 成立。设 \((X,\mathcal{B},d\mu)\) 为任一概率空间（故 \(\mu(X)=1\)），\(T:X\to X\) 为 \(X\) 上任一保测双射，即 \(\mu(T^n(E))=\mu(E)\) 对一切 \(E\in\mathcal{B}\) 与 \(n\in\mathbb{Z}\) 成立。证明：若 \(f:X\to\mathbb{R}^+\) 是任一几乎处处满足 \(0\le f(x)\le 1\) 且 \(\int_X f=\delta>0\) 的函数，则 \[\liminf_{N\to\infty}\ \mathbb{E}_{n\in[-N,N]}\int_X f(x)\,T^n f(x)\,T^{2n}f(x)\,d\mu(x)=\Omega_\delta(1).\]

返回 全书目录