Tao–Vu · 加性组合学 · 第 12 章 和集中的长等差数列

12.1　引言Introduction

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

本节目标本章研究一个问题：把一个集合 \(A\) 自己加自己很多次得到的和集 \(lA=\{a_1+\dots+a_l\}\)，里面一定藏着多长的等差数列？本节先把这个问题讲清楚、给出它的精确提法（用一个函数 \(f(m,l,n)\) 来度量），并预告本章要证明的两个核心结果（定理 12.2 与定理 12.4）。关键直觉是：把集合反复相加，会让它越来越“规整”，规整到最后必然冒出长的等差数列。

和集比任意集合更有结构

贯穿本书的一个总主题是：和集 \(A+B\) 比任意的集合 \(A,B\) 更有结构；尤其是，迭代和集（iterated sum set）

\[lA=\{a_1+\dots+a_l:a_i\in A_i\}\]

随着 \(l\) 变大应当变得越来越有结构。这种现象的一个例子是引理 4.13，它表明：若 \(A\) 的傅里叶偏差（Fourier bias）很小，则 \(lA\) 会很快铺满整个所在的群。（另见习题 4.3.12，那里给出了和集特殊结构的相关演示。）

例：什么叫“更有结构” 取一个看起来很零散的集合 \(A=\{0,1,3\}\)。它本身没有任何明显规律。
  1. \(2A=A+A=\{0,1,2,3,4,6\}\)——已经几乎填满了 \([0,6]\)，只缺一个 \(5\)。
  2. \(3A=\{0,1,2,3,\dots,9\}\) 去掉个别点后，越来越接近一整段连续区间。
  3. 继续加下去，\(lA\) 会变成一整段从某处到某处的连续整数（即步长为 \(1\) 的等差数列），只在两端有少量缺口。
这就是“越加越规整”的直观：零散的点经过反复相加，缝隙被填满，最终凝结成一条长等差数列。
A 2A 缺 5 lA
反复相加时，原本零散的点（顶行）逐渐填满缝隙，最终在中间凝结成一长段连续整数（绿色区间），只在两端留有少量孤立点。

只看密度时能找到的等差数列很短

再看另一个例子。设 \(A\) 是 \([1,n]\) 的一个子集（\(n\) 很大），并以 \(A\) 中所含最长等差数列的长度作为它“有多少结构”的度量。如果 \(A\) 除了“稠密”之外没有任何结构，譬如 \(|A|\ge 0.99n\)，那么我们能说的就不多了。即便是 Gowers 给出的 Szemerédi 定理的强有力定量版本 \((11.23)\)，也只能保证存在一条长度为 \(\Omega(\log\log\log\log\log n)\) 的等差数列。对于立方体（cube）情形稍好一些（也更简单）：引理 10.49 保证 \(A\) 含有一个维数为 \(\Omega(\log\log n)\) 的真立方体，不过这离 \([1,n]\) 内立方体的最大可能维数 \(\Omega(\log n)\) 仍很远。

怎么读这些长度 注意这里的 \(\log\log\log\log\log n\) 是一个极其缓慢增长的量。
  1. 哪怕 \(n\) 是宇宙级别的天文数字，\(\log n\) 已经不大；再套四五层 \(\log\)，结果几乎是个常数。
  2. 所以“只知道 \(A\) 很稠密”这个条件，几乎保证不了任何像样长度的等差数列——这正是 Szemerédi 定理虽然深刻、定量结论却很弱的写照。
  3. 本章的好消息是：一旦改去考察和集 \(lA\) 而不是 \(A\) 本身，能保证的等差数列长度会戏剧性地变长。

改看和集，情况显著改善

然而，一旦取和集，情况就明显改善了。首先，若 \(A\subset[1,n]\) 的基数至少为 \(0.99n\)，则容易看出 \(A+A\) 或 \(A-A\) 含有一条长度为 \(0.98n\) 的等差数列。这当然是相当极端的情形；更一般地，若 \(A\subset[1,n]\) 满足 \(|A|\ge\delta n\)，则 Bourgain 定理（定理 4.47）表明 \(A+A\) 与 \(A-A\) 含有长度至少为 \(\exp\!\big(c_\delta(\log^{1/3}n)\big)\) 的真等差数列。对于 \(3A\) 与 \(2A-A\)，习题 4.7.1 表明这些集合事实上含有长度为 \(\Omega_\delta\!\big(n^{\Omega_\delta(1)}\big)\) 的真等差数列；而定理 4.43 表明这些集合含有秩为 \(O_\delta(1)\)、体积为 \(\Omega_\delta(n)\) 的真广义等差数列。对于 \(2A-2A\)，Chang 定理（定理 4.42）给出类似结果，但对 \(\delta\) 的依赖更好。

记号速查：\(\Omega,O,\Theta\) 与下标 本节大量用到这些符号来表述“长度至少 / 至多有多大”。

不过这些结果要求 \(A\) 在所在区间 \([1,n]\) 内相当稠密；即便是 Chang 定理，也要求 \(A\) 的密度达到 \(\Omega\!\big(\tfrac{\log\log n}{\log n}\big)\) 才有非平凡内容。若 \(A\) 比这更稀疏，人们仍可追问：当 \(l\) 变大时，像 \(lA\) 这样的和集会发生什么？可以相当容易地证明（见习题）：对固定的 \(A\subset\mathbb{Z}\) 与很大的 \(l\)，\(lA\) 本质上会凝聚成一条长的等差数列，外加边界处一些可忽略的项。对于其他的群，情况略有不同（同样见习题）；注意，与 \(l\) 较小时的情况不同，当 \(l\) 变得很大时，Freiman 同态会少得多，因此对于不同构的所在群，无法刻画 \(l\to\infty\) 时 \(lA\) 的渐近行为。在这个方向上更深入的结果可参见 [260]、[261]。

把问题量化：函数 \(f(m,l,n)\)

现在我们提一个更定量的问题。设给定正整数 \(l,m,n\)，满足 \(2\le m\le n\)（\(m=1\) 的情形太退化，不予考虑）。如果 \(A\) 是 \([1,n]\) 的任意一个基数 \(|A|=m\) 的子集，关于 \(lA\) 的结构我们能说些什么？更确切地说，在 \(lA\) 中能找到的最大等差数列（或广义等差数列）有多长？由前面的讨论，当 \(l\) 较大时我们预期能找到相当长的等差数列。例如，由 Lev 的工作 [226]，有如下结果：

定理 12.1 [226]设 \(A\subset[1,n]\) 满足 \(|A|>2\)，且 \(A\) 不包含于任何步长大于 \(1\) 的等差数列之中。设 \(l\) 满足 \[l\ge \frac{2(n-1)}{|A|-2}.\] 则 \(lA\) 含有某个形如 \([m+1,\,m+n]\) 的区间（其中 \(m\) 为某个整数）。
读懂定理 12.1 的两个条件
  1. “\(A\) 不包含于任何步长大于 \(1\) 的等差数列”：意思是 \(A\) 里的元素的最大公差结构就是 \(1\)。比如 \(A=\{2,4,6\}\) 全在步长 \(2\) 的数列里，就被排除；这种集合相加只会得到偶数，永远填不满一段连续整数。要求“步长为 \(1\)”才能指望和集铺成连续区间。
  2. “\(l\ge 2(n-1)/(|A|-2)\)”：\(A\) 越大（\(|A|\) 越大），需要的相加次数 \(l\) 越少。这与直觉一致——元素越多，缝隙越容易填满。
  3. 结论 \([m+1,m+n]\) 是一段长度为 \(n\) 的完整连续区间，这是最强意义上的“等差数列”（步长 \(1\)）。

事实上还有更精确的陈述；见 [227]。Sárközy 较早的工作 [307] 建立了如下较弱的结果：

定理 12.2 [226]存在绝对常数 \(C>0\) 使得下述成立。设 \(A\subset[1,n]\) 且 \(l\ge1\) 满足 \(|A|\ge2\) 与 \(l|A|\ge Cn\)。则 \(lA\) 含有一条长度为 \(\Omega(l|A|)\) 的真等差数列。

我们将在下文中把该定理作为更一般结果的特例来证明。

为什么 \(\Theta(lm)\) 是对的：取 \(A=[1,m]\) 定理 12.2 说能保证长度 \(\Omega(l|A|)\)。这个量级不能再大了，最简单的例子就能看出上界也是 \(lm\)：
  1. 取 \(A=[1,m]=\{1,2,\dots,m\}\)，则 \(|A|=m\)。
  2. 把 \(l\) 个 \(A\) 中的元素相加，最小是 \(1+1+\dots+1=l\)，最大是 \(m+\dots+m=lm\)，中间每个整数都取得到。所以 \[lA=[l,\,lm]=\{l,l+1,\dots,lm\}.\]
  3. 这是一段连续区间，长度恰为 \(lm-l+1\approx lm\)。它本身就是 \(lA\) 中最长的等差数列。
所以对这个 \(A\)，\(lA\) 里最长等差数列正好是 \(\Theta(lm)\)——定理 12.2 给的下界 \(\Omega(lm)\) 已经达到上限，无法更长。

我们可以把上述定理换一种说法。对任意满足 \(2\le m\le n\) 的 \(l,m,n\)，定义 \(f(m,l,n)\) 为最大的整数，使得对 \([1,n]\) 中每一个基数 \(|A|\ge m\) 的子集 \(A\)，\(lA\) 都含有一条长度为 \(f(m,l,n)\) 的真等差数列。现在的问题就是：对各种 \(m,l,n\) 的取值，确定 \(f(m,l,n)\) 的大小。定理 12.2 断言：只要 \(lm\ge Cn\)，就有 \(f(m,l,n)=\Omega(lm)\)。事实上在此情形下 \(f(m,l,n)=\Theta(lm)\)，这可由考虑集合 \(A=[1,m]\) 看出。

\(f(m,l,n)\) 的关键在于“对每一个 \(A\)”\(f(m,l,n)\) 是一个最坏情形的保证：它必须对所有大小至少为 \(m\) 的 \(A\) 都成立。所以求 \(f\) 的下界要对“任意 \(A\)”证明（这难），求 \(f\) 的上界只需构造一个坏的 \(A\)（让它的 \(lA\) 里没有更长的等差数列即可，这相对容易）。下面的引理 12.3 正是用构造法给上界。

当 \(m\) 较小时上界骤降

当 \(m\) 相对于 \(n/l\) 较大时，这就对问题给出了令人满意的回答。现在自然要问：阈值 \(n/l\) 是否是精确的？当 \(m\) 落到这个阈值以下时，\(f(m,l,n)\) 会怎样？结果表明，此时 \(f(m,l,n)\) 的上界会急剧下降：

引理 12.3（\(f\) 的上界）设 \(d\ge1\) 为整数，\(l,m,n\) 为正整数，满足 \(l\ge2\) 与 \(n\ge 2^{d}l^{\,d-1}m^{d}\)。则 \[f(m^{d},\,l,\,n)\le lm-l+1.\]
证明. 取 \(A\) 为如下的秩 \(d\) 广义等差数列 \[A:=[1,m]^{d}\cdot\big(1,\,2lm,\,\dots,\,(2lm)^{d-1}\big),\] 于是 \[lA=[l,lm]^{d}\cdot\big(1,\,2lm,\,\dots,\,(2lm)^{d-1}\big).\] 通过对几何级数求和可知 \(A\subseteq[1,n]\)。由整数的 \(2lm\) 进制表示可知，映射 \(\varphi:[l,lm]^{d}\to lA\)， \[\varphi(x_0,\dots,x_{d-1})=\sum_{j=0}^{d-1}x_j(2lm)^{j},\] 是一个 \(2\) 阶 Freiman 同态。同样的论证表明 \(A\) 是真的（proper），从而 \(|A|=m^{d}\)。于是由命题 5.24，\(lA\) 中最长等差数列的长度与 \([l,lm]^{d}\) 中最长等差数列的长度相同，而后者显然是 \(lm-l+1\)。断言得证。♦
把引理 12.3 的构造看明白（以 \(d=2\) 为例） 关键想法是用“进制”把一个二维网格无碰撞地塞进一条数轴。
  1. 取基数 \(b=2lm\)。集合 \(A=\{x_0+x_1\cdot b:\ x_0,x_1\in[1,m]\}\)。也就是把数对 \((x_0,x_1)\) 写成“个位 \(x_0\)、‘\(b\) 位’\(x_1\)”的 \(b\) 进制数。
  2. 因为 \(x_0,x_1\le m
  3. 把 \(l\) 个这样的数相加：每个坐标分别相加，落在 \([l,lm]\) 内。由于 \(lm仍然不发生进位，所以 \[lA=\{y_0+y_1\cdot b:\ y_0,y_1\in[l,lm]\},\] 对应一个 \([l,lm]\times[l,lm]\) 的二维网格。
  4. 这个映射保持加法关系（即 \(2\) 阶 Freiman 同态），所以 \(lA\) 中的等差数列与网格里的等差数列一一对应。而二维网格 \([l,lm]^2\) 里最长的等差数列就是一整行（或一整列），长度 \(lm-l+1\)。
结论：这个 \(A\) 有 \(|A|=m^2\) 个元素，却让 \(lA\) 里最长等差数列只有约 \(lm=l|A|^{1/2}\) 这么长——比定理 12.2 的 \(l|A|\) 短得多。这就是 \(m\) 较小时上界骤降的来源。
lA 对应二维网格 \([l,lm]\times[l,lm]\)（d=2） 最长等差数列＝一整行，长 \(lm-l+1\) 横向：\(y_0\)（个位坐标） 纵向：\(y_1\)（\(b\) 位坐标）
把和集 \(lA\) 等价地看成二维网格后，任何等差数列要么沿一行、要么沿一列、要么斜穿，长度都受网格边长 \(lm-l+1\) 限制——这就是上界 \(f(m^2,l,n)\le lm-l+1\) 的几何来源。

由这条引理（以及一个平凡的观察：\(f(m,l,n)\) 关于 \(m\) 单调递增），我们看到存在常数 \(c_d\)（\(d=1,2,3,\dots\)）使得：只要 \(m\le c_d\,\dfrac{n}{l^{\,d-1}}\)，就有 \[f(m,l,n)=O\big(l\,m^{1/d}\big).\] 因此 \(f(m,l,n)\) 的上界在 \(m\) 接近各点 \(n/l,\ n/l^{2},\ n/l^{3},\dots\) 处呈现出阈值跳变的行为。颇为引人注目的是，这些阈值在相差常数的意义下是精确的：

定理 12.4 [350]设 \(d\ge1\)。则存在常数 \(C_d>0\)，使得对任意 \(l\ge1\) 以及满足 \(|A|\ge C_d\,\dfrac{n}{l^{d}}\) 且 \(|A|\ge2\) 的 \(A\subset[1,n]\)，\(lA\) 含有一条长度为 \(\Omega_d\!\big(l\,|A|^{1/d}\big)\) 的真等差数列。

注意定理 12.2 已经给出了本定理 \(d=1\) 的情形。把它与前面的讨论结合起来，我们看到：只要 \[C_d\,\frac{n}{l^{d}}\ \le\ m\ \le\ c_d\,\frac{n}{l^{\,d-1}},\] 就有 \(f(m,l,n)=\Theta_d\!\big(l\,m^{1/d}\big)\)。这就解决了在 \(m\) 远离各阈值 \(n/l,\,n/l^{2},\dots\) 且不太小的前提下，确定 \(f(m,l,n)\) 量级的问题。各阈值附近的精确行为仍不清楚，可能很难解决。

把“阶梯”画出来：\(f\) 随 \(m\) 的分段量级 固定 \(l,n\)，让 \(m\)（即 \(|A|\)）从大到小变化，看 \(f\) 的量级：
  1. \(m\ge n/l\) 时：\(f=\Theta(lm)\)（指数 \(1/d\) 中 \(d=1\)）。
  2. \(n/l^2\le m\le n/l\) 时：\(f=\Theta(l\,m^{1/2})\)（\(d=2\)）。
  3. \(n/l^3\le m\le n/l^2\) 时：\(f=\Theta(l\,m^{1/3})\)（\(d=3\)）。
  4. ……每跨过一个阈值 \(n/l^{d}\)，指数就从 \(1/d\) 退到 \(1/(d{+}1)\)，保证的等差数列变短。
直觉：\(A\) 越稀疏（\(m\) 越小），它越可能像引理 12.3 那样“伪装成”一个高秩 \(d\) 的广义等差数列，从而把 \(lA\) 里的长等差数列藏起来——\(d\) 越大，能藏得越狠。
\(\log m\)（A 越小 → 越靠左） \(\log f\) \(n/l^{2}\) \(n/l\) 斜率 1（d=1） 斜率 1/2（d=2） 斜率 1/3（d=3）
在对数-对数坐标下，\(f(m,l,n)\) 随 \(m\) 呈分段折线：每跨过一个阈值 \(n/l^{d}\)，斜率（即对 \(m\) 的指数 \(1/d\)）就变缓一档。右侧 \(m\) 大时增长最快（\(\propto m\)），向左逐级放慢。

证明思路与后续推广

我们将在接下来的几节中证明定理 12.4（从而也证明定理 12.2）。一个关键观察是：在相差常数的意义下，只需考虑 \(l\) 为 \(2\) 的幂的情形，此时可以把 \(lA\) 视为倍增运算 \(A\to A+A\) 的迭代。这赋予问题一种“动力系统”的味道——我们要分析一个集合在倍增映射作用下的演化过程。随后我们讨论各种推广与变体，特别是限制和集 \[l^{*}A:=\{a_1+\dots+a_l:\ a_1,\dots,a_l\in A\ \text{两两不同}\}\] 以及有限和集 \[FS(A):=\bigcup_{l=0}^{\infty}l^{*}(A)=\Big\{\sum_{x\in B}x:\ B\subset A,\ 0\le|B|<\infty\Big\}.\]

看清 \(l^{*}A\) 与 \(FS(A)\) 的区别 取 \(A=\{1,2,4\}\)。
  1. 普通和集 \(2A=A+A\) 允许重复用同一元素，如 \(1+1=2\)；故 \(2A=\{2,3,4,5,6,8\}\)。
  2. 限制和集 \(2^{*}A\) 要求两个加数不同：\(1+2=3,\ 1+4=5,\ 2+4=6\)，故 \(2^{*}A=\{3,5,6\}\)。
  3. 有限和集 \(FS(A)\) 把 \(A\) 的所有子集之和都收进来：\(\varnothing\to0\)，单元素 \(\to1,2,4\)，双元素 \(\to3,5,6\)，三元素 \(\to7\)。故 \(FS(A)=\{0,1,2,3,4,5,6,7\}\)。
可见三种“相加方式”规则不同：是否允许重复、是否限定个数，都会改变结果集合。本章后续会分别研究它们里面的长等差数列。

返回 全书目录