本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 即时自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标第 12.2 节证明了核心结果——只要集合 \(A\subset[1,n]\) 不太稀疏，那么把它“自己加自己 \(l\) 次”得到的和集 \(lA\) 里就一定会冒出一条很长的等差数列（甚至一整块高维的广义等差数列）。本节回答一个自然的追问：如果把游戏规则稍微改一改，结论还成立吗？ 具体要换掉四样东西——（1）允许各个加项来自不同的集合；（2）把整数换成更一般的群；（3）只允许把互不相同的元素相加（受限和集 \(l^{*}A\)）；（4）把直线上的区间 \([1,n]\) 换成圆圈状的循环群 \(\mathbb{Z}_n\)。每一处改动都对应一条推广定理。本节是“结果陈列馆”：列出这些变体并讲清它们与原版的差别，证明大多留作练习。
先把记号和概念讲清楚
本节会反复用到几个第 12 章一直在用的记号，先用具体例子把它们钉死，免得后面读定理时卡住。
记号回顾
- \(l\) 重和集 \(lA\)：把 \(A\) 中元素（允许重复取用）相加 \(l\) 个所得的全部和，即 \(lA=\{a_1+a_2+\cdots+a_l: a_i\in A\}\)。
- 受限和集 \(l^{*}A\)：只允许取 \(l\) 个互不相同的元素相加，即 \(l^{*}A=\{a_1+\cdots+a_l: a_i\in A,\ a_i\text{ 两两不同}\}\)。
- 秩为 \(d\) 的广义等差数列（GAP）：形如 \(P=\{a+x_1v_1+\cdots+x_dv_d:\ 0\le x_i秩（维数），乘积 \(N_1N_2\cdots N_d\) 称为体积。当 \(d=1\) 时它就是普通的等差数列。
- 真（proper）GAP：上式中不同的坐标 \((x_1,\dots,x_d)\) 给出不同的元素，也就是这 \(N_1\cdots N_d\) 个点互不重合，此时体积恰等于元素个数。
- 渐近记号：\(\Omega_d(X)\) 表示“至少是 \(c_d X\)”，\(O_d(X)\) 表示“至多是 \(C_d X\)”，其中 \(c_d,C_d\) 是只依赖下标 \(d\) 的正常数。
例：\(lA\) 与 \(l^{*}A\) 的区别 取 \(A=\{1,2,4\}\)，\(l=2\)。
- \(2A\)（可重复）：把列表里任两个（含自己加自己）相加——\(1{+}1,1{+}2,1{+}4,2{+}2,2{+}4,4{+}4\)，整理去重得 \(2A=\{2,3,4,5,6,8\}\)。
- \(2^{*}A\)（必须不同）：只能取两个不同元素——\(1{+}2,1{+}4,2{+}4\)，得 \(2^{*}A=\{3,5,6\}\)。
- 对比：\(2^{*}A\subset 2A\)，因为去掉了 \(1{+}1,2{+}2,4{+}4\) 这些“自加”项。受限和集更小、更难控制，所以相应定理更难证。
秩为 \(d\) 的 GAP 就是一块 \(d\) 维“格点砖”。本图 \(d=2\)：从起点 \(a=3\) 出发，沿两个方向 \(v_1=2\)、\(v_2=7\) 各走若干步铺成的 \(4\times3\) 网格。普通等差数列只是 \(d=1\) 的特例（一条直线上的点）。本节定理常说“含一条秩 \(d'\)、体积 \(\ge\Omega_d(\cdots)\) 的（真）GAP”，意思就是和集里能扣出这样一块结构完整的砖。
变体一：允许不同的加项
关于定理 12.4 与定理 12.5 存在多种推广。对上面（指 12.2 节）的论证作一个简单的修改，便可以处理各加项互不相同的集合的情形：
定理 12.10 [350]对任意固定的正整数 \(d\)，存在常数 \(C_d>0\)，使得下述结论成立。设 \(A_1,\dots,A_l\) 是 \([1,n]\) 的子集，每个大小均为 \(m\)，其中 \(l\) 与 \(m\) 满足
\[ l^{d}m\ge C_d\,n. \]
那么 \(A_1+\cdots+A_l\) 含有一条秩为 \(d'\)、体积至少为 \(\Omega_d(l^{d}m)\) 的等差数列（这里 \(d'\) 是某个满足 \(1\le d'\le d\) 的整数）。特别地，\(A_1+\cdots+A_l\) 含有一条长度至少为 \(\Omega_d(l\,m^{1/d})\) 的等差数列。
与原版的差别原来的定理 12.4 处理的是同一个集合 \(A\) 自加 \(l\) 次（即 \(lA\)）。定理 12.10 把它松绑：现在 \(l\) 个加项可以来自 \(l\) 个不同的集合 \(A_1,\dots,A_l\)，只要求它们大小都是 \(m\)。结论的形式完全一样（用 \(m\) 代替 \(|A|\)）。这说明 12.2 节的证明根本没有用到“各加项来自同一集合”这件事——这是一个让人放心的稳健性检验。
例：看清“为什么自然” 取 \(A_1=A_2=\cdots=A_l=A\)，定理 12.10 立刻退化成定理 12.4。所以 12.10 是 12.4 的严格推广，并非另起炉灶。证明的关键技术（“树论证”）只需在树的叶子上放不同的集合即可，见练习 12.3.1。
变体二：换一个群
借助引理 5.25，我们也可以毫无困难地把整数换成任何其它无挠（torsion-free）的加法群。
“无挠”是什么意思一个加法群叫无挠，是指除了 \(0\) 之外，没有任何元素 \(g\) 满足 \(g+g+\cdots+g=0\)（有限次相加就回到 \(0\)）。整数 \(\mathbb{Z}\)、有理数 \(\mathbb{Q}\)、平面整点格 \(\mathbb{Z}^2\) 都是无挠的：你不停地加同一个非零向量，永远走不回原点。反例是循环群 \(\mathbb{Z}_n\)：在 \(\mathbb{Z}_6\) 里 \(2+2+2=6\equiv0\)，所以 \(\mathbb{Z}_n\) 有挠。无挠这个条件保证了等差数列“走出去就不会绕回来撞上自己”，这正是直线情形的论证能照搬过去的原因。一旦群有挠（如 \(\mathbb{Z}_n\)），就得另作处理——这正是下面变体四要解决的问题。
变体三：受限和集 \(l^{*}A\)
一个更困难的加强，是改用受限和集 \(l^{*}A\) 来代替 \(lA\)。我们有可能改造上述方法来处理这种情形：
定理 12.11 [350]对任意固定的正整数 \(d\)，存在常数 \(C_d>0\)，使得下述结论成立。对任意正整数 \(n,l\) 以及任意满足
\[ l\le |A|/2,\qquad l^{d}|A|\ge C_d\,n \]
的集合 \(A\subset[1,n]\)，受限和集 \(l^{*}A\) 含有一条秩为 \(d'\)、体积至少为 \(\Omega_d(l^{d}|A|)\) 的真等差数列（这里 \(1\le d'\le d\) 为某整数）。特别地，\(l^{*}A\) 含有一条长度为 \(\Omega_d(l\,|A|^{1/d})\) 的真等差数列。
如果我们把 \(f^{*}(m,l,n)\) 定义为 \(f(m,l,n)\) 的显然类比——把其中的 \(lA\) 换成 \(l^{*}A\)——那么（对上界使用引理 12.3）我们得出：只要
\[ C_d\,\frac{n}{l^{d}}\ \le\ m\ \le\ c_d\,\frac{n}{l^{d-1}}\qquad\text{且}\qquad m\ge 2l, \]
就有 \(f^{*}(m,l,n)=\Omega_d(l\,m^{1/d})\)。（注意当 \(m
\(f(m,l,n)\) 是什么这是本章一直在追踪的“配方函数”：\(f(m,l,n)\) 表示对所有大小为 \(m\) 的 \(A\subset[1,n]\) 都成立的、\(lA\) 中必含等差数列的最长保证长度。换句话说，无论你怎么挑这个大小为 \(m\) 的集合，\(lA\) 里至少有一条长为 \(f(m,l,n)\) 的等差数列，而且 \(f\) 是能给出这种保证的最大值。\(f^{*}\) 就是把 \(lA\) 换成受限和集 \(l^{*}A\) 的对应物。本节的结论是：在合适的参数范围内，二者的量级一样，都是 \(\Omega_d(l\,m^{1/d})\)——也就是说“禁止重复相加”并没有让保证长度变差。
定理 12.11 比定理 12.4 困难得多，我们在此不予呈现。不过，让我们提一条重要的引理，它可以看作子集和版本的 Freiman 定理。这条引理断言：如果 \(l^{*}A\) 没有像定理所说的那样给出一个真 GAP，那么 \(A\) 本身就必定含有一个结构极其僵硬的大子集。
引理 12.12对任意正常数 \(\nu\) 与 \(d\)，存在正常数 \(\delta,\alpha,d_1\)，使得下述结论成立。设 \(A\) 是 \([n]\) 的子集，\(l\) 为正整数，\(n\ge f(n)\ge 1\) 是 \(n\) 的一个函数，满足
\[ \max\!\Big(\log^{10}n,\ \big(40\,f(n)\log^{2}n\big)^{1/3d}\Big)\ \le\ l\ \le\ |A|/2, \]
且 \(l^{d}|A|f(n)\ge n\)。那么下面两条陈述
必有一条成立：
- \(l^{*}A\) 含有一条秩为 \(d'\)、体积为 \(\Omega(l^{d'}|A|)\) 的真 GAP，其中 \(1\le d'\le d\)；
- 存在 \(A\) 的一个子集 \(\tilde A\)，其元素个数至少为 \(\delta|A|\)，并且被包含在一个秩为 \(d_1\)、体积为 \(O\!\big(|A|\,f(n)^{1+\nu}\log^{\alpha}n\big)\) 的 GAP \(P\) 之中。
函数 \(f(n)\) 可以看成一个僵硬度参数。\(l^{d}|A|\) 越接近 \(n\)，子集 \(\tilde A\) 的结构就越僵硬。
引理 12.12 是一条“二择一”（结构）定理：要么受限和集 \(l^{*}A\) 已经给出我们想要的大块真 GAP（左，皆大欢喜）；要么这件好事没发生，但代价是 \(A\) 自己的一大半被锁死在一个体积很小的 GAP 里（右，结构僵硬）。无论哪种情况，都得到强有力的信息。这种“好结论 or 强结构”的格式正是 Freiman 型定理的典型样貌。
\(d=1\) 的情形尤为重要，它是定理 12.2 的一个推广，我们把它单独列为一条推论。
推论 12.13存在常数 \(C>0\)，使得只要 \(A\subset[1,n]\) 且 \(1\le l\le |A|/2\) 满足 \(l|A|\ge Cn\)，那么受限和集 \(l^{*}A\) 就含有一条长度为 \(cl|A|\) 的等差数列。
这个结果对子集和有如下推论：
推论 12.14 [350]若 \(A\) 是 \([1,n]\) 的子集，其元素个数至少为 \(C\sqrt{n}\)（\(C>0\) 是一个充分大的绝对常数），那么子集和 \(F\!S(A)\) 含有一条长度为 \(n\) 的等差数列。
这个结果的第一部分（把 \(\sqrt{n}\) 换成 \(\sqrt{n\log n}\) 的版本）最初由 Freiman [115] 证明；我们把由推论 12.13 推导出本推论一事留作练习。
\(F\!S(A)\) 是什么，为什么这条推论惊人子集和 \(F\!S(A)\) 是把 \(A\) 的所有子集各自求和得到的全体（每个元素最多用一次，每个子集只数一次）。注意它和 \(l^{*}A\) 的关系：\(F\!S(A)=\bigcup_{l\ge0} l^{*}A\)（对所有规模的“取若干个不同元素相加”取并）。推论 12.14 说的是：只要 \(A\) 的元素个数超过 \(\sqrt n\) 这个门槛，它的子集和就会“铺满”一条长达 \(n\) 的等差数列——换言之，几乎所有不太大的整数都能写成 \(A\) 中某些不同元素之和。\(\sqrt n\) 这个门槛非常省：用大约 \(\sqrt n\) 个数，就能合成一整段长为 \(n\) 的连续算术结构。
例：子集和铺满一段 取 \(A=\{1,2,4\}\)。它的全部子集和为：
\[ \varnothing\to0,\ \{1\}\to1,\ \{2\}\to2,\ \{1,2\}\to3,\ \{4\}\to4,\ \{1,4\}\to5,\ \{2,4\}\to6,\ \{1,2,4\}\to7. \]
于是 \(F\!S(A)=\{0,1,2,3,4,5,6,7\}\)——恰好是一条公差为 \(1\)、长度为 \(8\) 的等差数列！只用 \(3\) 个数就铺满了 \(0\) 到 \(7\)。推论 12.14 正是这个现象在大规模下的定量版本。
变体四：在循环群 \(\mathbb{Z}_n\) 中
另一个变体是在素数阶循环群 \(\mathbb{Z}_n\) 中工作，而不是在区间 \([1,n]\) 中。这里，我们可以修改前面的论证而得到：
定理 12.15 [350]对任意 \(d\ge1\)，存在 \(C_d>0\)，使得下述结论成立。对素数阶循环群 \(\mathbb{Z}_n\) 中的任意加性集合 \(A\)，以及任意满足
\[ l^{d+1}|A|\ge C_d\,n,\qquad |A|\ge2 \]
的 \(l\ge1\)，和集 \(lA\) 含有一条长度为 \(\min\!\big(n,\ \Omega_d(l\,|A|^{1/d})\big)\) 的真等差数列。
这个定理与定理 12.4 之间有两处差别。第一，等差数列的长度变成了 \(\min(n,\Omega_d(l|A|^{1/d}))\)，而不是 \(\Omega_d(l|A|^{1/d})\)；但这是自然的，因为 \(lA\) 的大小不可能超过 \(n\)。第二，对 \(l\) 的条件从 \(l^{d}|A|\ge C_d n\) 放宽成了 \(l^{d+1}|A|\ge C_d n\)。这归根结底是因为：在 \([1,n]\) 情形下用到的平凡上界 \(|lA|\le ln\)，现在可以改进成平凡上界 \(|lA|\le n\)。除此之外，论证本质上相同，留作练习。
左：在直线段 \([1,n]\) 上，把集合自加 \(l\) 次，和可以一直往右长，平凡上界只有 \(|lA|\le ln\)。右：在圆圈状的 \(\mathbb{Z}_n\) 上，加法会“绕回来”，整个群只有 \(n\) 个元素，于是平凡上界直接是 \(|lA|\le n\)。正是这个更强的平凡上界，让定理 12.15 对 \(l\) 的要求可以从 \(l^{d}|A|\ge C_d n\) 放宽到 \(l^{d+1}|A|\ge C_d n\)。素数阶这一假设则避免了等差数列在尺寸接近 \(n\) 之前出现“挠”的麻烦。
本节练习
练习
- 12.3.1 证明定理 12.10。（提示：使用树论证，但在叶子上放置不同的集合。你需要把 Ruzsa–Chang 定理替换成另一个结果，例如定理 4.43，或者使用先前练习中勾勒的初等方法。）
- 12.3.2 由推论 12.13 推导出推论 12.14。
- 12.3.3 设 \(\mathbb{Z}_n\) 是素数阶循环群，并把 \(f(m,l,\mathbb{Z}_n)\) 定义得与 \(f(m,l,n)\) 完全一样，只是现在集合 \(A\) 落在 \(\mathbb{Z}_n\) 中而非 \([1,n]\) 中。证明：\(f(m,l,\mathbb{Z}_n)=n\) 当且仅当 \(l(m-1)\ge n-1\)。（提示：使用练习 12.1.1。）再证明：对每个 \(d\ge1\)，存在常数 \(c_d,C_d>0\)，使得只要 \(C_d\,\dfrac{n}{l^{d+1}}\le m\le c_d\,\dfrac{n}{l^{d}}\)，就有 \(f(m,l,\mathbb{Z}_n)=\Omega_d(l\,m^{1/d})\)。
- 12.3.4 证明定理 12.15。（注意：\(n\) 为素数这一假设会阻止等差数列中出现任何“挠”的问题，直到等差数列的尺寸大到与 \(n\) 可比为止；到那时，可以改用 Cauchy–Davenport 不等式继续推进。）
本节小结把第 12.2 节的核心定理沿四个方向做了推广：（12.10）各加项可来自不同集合；（无挠群）整数可换成任意无挠加法群；（12.11 与引理 12.12、推论 12.13–12.14）可改用受限和集 \(l^{*}A\)，由此得到关于子集和 \(F\!S(A)\) 的漂亮结论——只需 \(\gtrsim\sqrt n\) 个元素即可铺满长为 \(n\) 的等差数列；（12.15）可在素数阶循环群 \(\mathbb{Z}_n\) 中工作，此时更强的平凡上界 \(|lA|\le n\) 让对 \(l\) 的条件得以放宽。这些变体共同说明：和集中出现长等差数列，是一个相当稳健、不挑场地的普遍现象。
返回 全书目录