Tao–Vu · 加性组合学 · 第 2 章 和集估计

2.1　和集Sum sets

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向初学者的详解，逐步推演、举例、画图，不用比喻。本节较抽象，请耐心跟随每一个具体例子。

本节目标本章研究两个集合相加之后“变大”了多少。最核心的问题只有一句话：把集合 \(A\) 与 \(B\) 逐对相加得到的和集 \(A+B\)，它的元素个数 \(|A+B|\)，什么时候很小、什么时候很大？本节先把和集、差集、重复和集这些基本对象定义清楚，给出它们大小的“平凡上下界”（引理 2.1），再精确刻画两个极端情形：下界何时取到（命题 2.2）、上界何时取到（命题 2.3）。

基本对象：和集、差集、重复和集

我们现在系统地研究两个加性集合（additive set）\(A,B\) 的和集（sum set）\(A+B\) 与差集（difference set）\(A-B\)，它们都处在某个公共的环绕群（ambient group）\(Z\) 之中，正如定义 0.1 所给出的；我们也研究重复和集（iterated sum set）\(nA\)。

回顾（定义 0.1 的记号）设 \(Z\) 是一个交换群（加法记号），\(A,B\subseteq Z\) 是有限非空子集。则 \[A+B:=\{a+b: a\in A,\ b\in B\},\qquad A-B:=\{a-b: a\in A,\ b\in B\}.\] 重复和集 \(nA\) 指 \(n\) 个 \(A\) 相加：\(nA:=\underbrace{A+A+\dots+A}_{n\ \text{个}}\)，约定 \(0A:=\{0\}\)。
例（先把定义算一遍）取整数群 \(Z=\mathbb{Z}\)，\(A=\{0,1,3\}\)，\(B=\{0,2\}\)。
  1. 和集：把 \(A\) 的每个元素与 \(B\) 的每个元素相加， \[A+B=\{0,2,\;1,3,\;3,5\}=\{0,1,2,3,5\},\quad |A+B|=5.\] （注意 \(1+2=3\) 与 \(3+0=3\) 撞到一起，所以个数比 \(3\times2=6\) 少。）
  2. 差集：\(A-B=\{0,-2,\;1,-1,\;3,1\}=\{-2,-1,0,1,3\}\)，\(|A-B|=5\)。

我们要提醒读者：重复和集 \(nA\) 一般不等于伸缩集（dilate）\(n\cdot A:=\{n\cdot a: a\in A\}\)，尽管我们确有包含关系 \(n\cdot A\subseteq nA\)。同样地，差集 \(A-B\) 不应与集合论意义上的差 \(A\backslash B:=\{x\in A: x\notin B\}\) 相混淆。我们还把 \(A+x:=A+\{x\}\) 记作 \(A\) 被元素 \(x\in Z\) 所作的平移（translate）。

例（重复和集 ≠ 伸缩集）仍取 \(A=\{0,1,3\}\)，\(n=2\)。 可见 \(2\cdot A=\{0,2,6\}\subseteq\{0,1,2,3,4,6\}=2A\)，包含关系成立，但远非相等。直觉是：\(n\cdot A\) 只允许“同一个元素重复 \(n\) 次”，而 \(nA\) 允许“任取 \(n\) 个元素相加”，后者得到的组合多得多。
012 345 6 2·A（伸缩）： 2A=A+A（重复和）：
同一个 \(A=\{0,1,3\}\)：上排是伸缩集 \(2\cdot A=\{0,2,6\}\)（3 个点），下排是重复和集 \(2A=\{0,1,2,3,4,6\}\)（6 个点）。前者是后者的子集。

由于群元素的加法满足结合律与交换律，容易验证集合的加法也满足这两条性质。然而我们要提醒：和集运算不可逆。例如 \(A+B-B\) 包含 \(A\)，但一般并不等于 \(A\)。类似地，当 \(n>m\) 时，\(nA-mA\) 包含 \((n-m)A\)，但一般会更大。

例（运算不可逆：“加回去再减”不能复原）取 \(A=\{0,1\}\)，\(B=\{0,3\}\)。
  1. \(A+B=\{0,1,3,4\}\)。
  2. \((A+B)-B=\{0,1,3,4\}-\{0,3\}=\{0,1,3,4,\,-3,-2,0,1\}=\{-3,-2,0,1,3,4\}\)。
  3. 它确实包含 \(A=\{0,1\}\)，但多出了 \(-3,-2,3,4\)。所以 \(A+B-B\supsetneq A\)，“减 \(B\)”并不能把“加 \(B\)”撤销。
原因：减法时 \(b\) 与加法时用的 \(b\) 不必相同，于是产生了额外的组合。

核心问题与平凡估计

本主题中一个非常基本的问题是：在什么条件下 \(A+B\) 是“小”的，又在什么条件下它是“大”的？更确切地说，我们关心和集 \(A+B\) 的基数 \(|A+B|\)。我们有如下的平凡估计。

引理 2.1（平凡和集估计）设 \(A,B\) 是具有公共环绕群 \(Z\) 的加性集合，\(x\in Z\)。则有恒等式 \[|A+x|=|-A|=|A|,\] 不等式 \[\tag{2.1}\max(|A|,|B|)\le |A+B|,\,|A-B|\le |A||B|,\] 以及不等式 \[\tag{2.2}|A|\le |A+A|\le \frac{|A|(|A|+1)}{2}.\] 更一般地，对任意整数 \(n\ge 1\)，有 \(|(n+1)A|\ge |nA|\)，且 \[\tag{2.3}|nA|\le \binom{|A|+n-1}{n}=\frac{|A|(|A|+1)\cdots(|A|+n-1)}{n!}.\]

我们指出：(2.1) 中的下界对特定的群 \(Z\)、或当 \(A,B\) 具有较大“维数”时，可以改进；参见定理 3.16、引理 5.3、定理 5.17、推论 5.13、定理 5.4。

怎么读这些不等式把 (2.1) 拆开看，它其实是三段直觉： 而 (2.2) 是 (2.3) 在 \(n=2\) 时的特例：取两个元素（可相同）相加，无序对共 \(\binom{|A|+1}{2}=\frac{|A|(|A|+1)}{2}\) 种。
例（上界 (2.2) 恰好取到）取 \(A=\{0,1,3\}\)，\(|A|=3\)。理论上界 \(\dfrac{3\cdot4}{2}=6\)。实际 \[A+A=\{0,1,2,3,4,6\},\quad |A+A|=6.\] 恰好顶到上界。直觉：要让 \(A+A\) 尽量大，就要让所有无序对的和两两不同——\(\{0,1,3\}\) 正好做到了这一点（这种集合后面会与 Sidon 集相关）。反之，若 \(A=\{0,1,2\}\)（一段连续整数），则 \(A+A=\{0,1,2,3,4\}\) 只有 \(5\) 个，远未顶到 \(6\)，因为 \(0+2=1+1=2\) 撞了车——这正是“有结构”的征兆。
\(A=\{0,1,3\}\) 的加法表（格内为 \(a_i+a_j\)） +013 013 013 124 346
表中出现的不同数值为 \(\{0,1,2,3,4,6\}\)，共 6 个，即 \(|A+A|=6\)，恰等于上界 \(\binom{4}{2}=6\)。
证明. 我们只证明 (2.3)，因为其余不等式要么由它推出，要么是平凡的。我们对 \(|A|\) 作归纳。
  1. 基础 \(|A|=1\)：此时 \(A=\{x\}\)，\(nA=\{nx\}\)，左边 \(|nA|=1\)；右边 \(\binom{1+n-1}{n}=\binom{n}{n}=1\)。两边都等于 \(1\)。
  2. 归纳步 \(|A|>1\)：把 \(A\) 写成 \(A=B\cup\{x\}\)，其中 \(B\) 是非空集合且 \(|B|=|A|-1\)。于是 \[nA=\bigcup_{j=0}^{n}\bigl(jB+(n-j)\cdot x\bigr).\] （含义：从 \(A\) 取 \(n\) 个元素相加，若其中有 \(j\) 个来自 \(B\)、有 \(n-j\) 个等于那个单独的 \(x\)，所得即 \(jB\) 平移 \((n-j)x\)；让 \(j\) 跑遍 \(0,\dots,n\) 就穷尽所有情形。这里约定 \(0B=\{0\}\)。）
  3. 对这个并集用“并的大小不超过各部分大小之和”，再对每个 \(|jB|\) 用归纳假设（\(|B|=|A|-1\)），最后用帕斯卡三角恒等式（即曲棍球棒求和 \(\sum_{j=0}^n\binom{r+j}{j}=\binom{r+n+1}{n}\)，取 \(r=|A|-2\)）： \[|nA|\le\sum_{j=0}^{n}|jB|\le\sum_{j=0}^{n}\binom{|A|-1+j-1}{j}=\binom{|A|+n-1}{n}.\] 这正是所要证的。♦

平移不变性与“结构”的萌芽

由上述事实可观察到：诸如 \(A+B,\ A-B,\ kA\) 这些和集的大小，在把 \(A\) 或 \(B\) 任意平移后保持不变。这赋予和集理论以一种“平移不变”或“仿射”的风味。我们有时会利用这种平移不变性来对其中一个集合做归一化，例如使它包含原点 \(0\)。

对于“典型的（generic）”加性集合 \(A,B\)，引理 2.1 中考虑的那些和集的基数，更有可能接近上面列出的上界而非下界（例如参见习题 2.1.1）。这表明：只有当 \(A,B\) 具有相当多的结构时，下界才可能被取到、或接近被取到。我们将在本章余下部分发展这一主题，引入诸如倍增常数与差常数、Ruzsa 距离、加性能量以及 \(K\)-近似群等工具，来量化这些“结构”概念。眼下，我们至少先解决：(2.1) 中的下界何时被取到。

下界何时取到：精确逆和集定理

命题 2.2（精确逆和集定理）设 \(A,B\) 是具有公共环绕群 \(Z\) 的加性集合。则下列各条彼此等价：
这条定理在说什么下界 \(|A+B|=|A|\) 意味着：把 \(B\) 加到 \(A\) 上后个数一点没增加。直觉上这要求 \(B\) 的每个元素加上去都只是把 \(A\) “原地搬动”而不扩张——这只有当 \(A\) 是某个子群 \(G\) 的若干整块陪集拼成、且 \(B\) 整个塞在 \(G\) 的一个陪集里时才可能。换句话说：下界取到 \(\iff\) 背后藏着一个子群。这就是“群结构”首次登场。
证明. 我们只证明第一条蕴含第五条；其余各条彼此类似或容易，留作习题。
  1. 若有必要先平移 \(B\)（不改变 \(|A+B|\)），可设 \(B\) 含有 \(0\)。
  2. 于是 \(A+B\supseteq\{0\}+A=A\)。但已知 \(|A+B|=|A|\)，而一个有限集合包含另一个且个数相等，必然相等，故 \(A+B=A\)。
  3. 特别地，对每个 \(b\in B\) 都有 \(A+b\subseteq A+B=A\)，再由 \(|A+b|=|A|\) 得 \(A+b=A\)。
  4. 定义 \(A\) 的对称群 \(\mathrm{Sym}_1(A)\)（也称 \(A\) 的周期）为 \[\mathrm{Sym}_1(A):=\{h\in Z: A+h=A\}.\] 由上一步知 \(B\subseteq\mathrm{Sym}_1(A)\)。
  5. 留给读者验证：\(\mathrm{Sym}_1(A)\) 是一个有限群，且 \(A\) 是 \(\mathrm{Sym}_1(A)\) 的若干陪集之并。于是取 \(G:=\mathrm{Sym}_1(A)\) 即得结论。♦
例（亲手验证下界与子群结构）取环绕群 \(Z=\mathbb{Z}_6=\{0,1,2,3,4,5\}\)（模 \(6\) 加法），子群 \(G=\{0,3\}\)。\(G\) 的三个陪集为 \(\{0,3\},\{1,4\},\{2,5\}\)。
令 \(B=\{1,4\}\)（恰好是一个陪集，更别提“塞进某个陪集”），\(A=\{0,3\}\cup\{1,4\}=\{0,1,3,4\}\)（两个陪集之并）。
  1. 逐项算 \(A+B\)（模 \(6\)）：\(0{+}1{=}1,\ 0{+}4{=}4,\ 1{+}1{=}2,\ 1{+}4{=}5,\ 3{+}1{=}4,\ 3{+}4{=}1,\ 4{+}1{=}5,\ 4{+}4{=}2\)。
  2. 去重得 \(A+B=\{1,2,4,5\}\)，\(|A+B|=4=|A|\)。下界确实取到！
  3. 验证对称群：\(A+3=\{3,4,0,1\}=A\)，而 \(A+1=\{1,2,4,5\}\ne A\)。故 \(\mathrm{Sym}_1(A)=\{0,3\}=G\)，与定理一致：\(B\subseteq\) 陪集 \(\{1,4\}\)，\(A=\{0,3\}\cup\{1,4\}\) 为陪集之并。
\(\mathbb{Z}_6\) 按子群 \(G=\{0,3\}\) 分成 3 个陪集 G={0,3} {1,4} {2,5} 03 14 25 \(A=\{0,3\}\cup\{1,4\}\)（取了左、中两整块），\(B=\{1,4\}\)（落在中间一整块内）
当 \(A\) 由整块陪集拼成、\(B\) 锁在一块陪集内时，加 \(B\) 只是在这些整块之间“轮换”，个数不增，故 \(|A+B|=|A|\)。

我们将在 2.6 节更系统地研究对称群 \(\mathrm{Sym}_1(A)\)，以及更一般的对称集 \(\mathrm{Sym}_\alpha(A)\)。

上界何时取到

至于上界何时被取到，我们没有同样明确的描述，但可以给出该条件的若干等价表述。

命题 2.3设 \(A,B\) 是具有公共环绕群 \(Z\) 的加性集合。则下列各条彼此等价：
这些条件为何彼此等价（直觉）上界 \(|A+B|=|A||B|\) 意味着所有 \(|A||B|\) 个配对 \(a+b\) 的和两两不同，没有任何撞车。 我们把这条命题的简单证明留作习题。它的一个部分推广见下文推论 2.10。
例（上界取到 vs 取不到）

\(A+B\) 与 \(A-B\) 的大小：何时相等，何时不等

在命题 2.2 与命题 2.3 中，集合 \(A+B\) 与 \(A-B\) 具有相同的大小（另见习题 2.1.6）。然而一般情况下这并不成立。一个基本的例子是集合 \(A=\{0,1,3\}\subset\mathbb{Z}\)：此时 \(A+A=\{0,1,2,3,4,6\}\) 有六个元素，而 \(A-A=\{-3,-2,-1,0,1,2,3\}\) 有七个元素。更一般地，若 \(A=\{0,1,3\}^d\subset\mathbb{Z}^d\)，则 \(A+A\) 有 \(6^d\) 个元素，\(A-A\) 有 \(7^d\) 个。于是 \(A-A\) 可以比 \(A+A\) 大出任意大的倍数。

为什么差集会比和集大对一维的 \(A=\{0,1,3\}\)： 减法不对称（\(a-b\ne b-a\)）使差集更“铺得开”，所以常常 \(|A-A|>|A+A|\)。取 \(d\) 次直积后，两边都按 \(d\) 次幂放大（\(6^d\) 对 \(7^d\)），差距可以任意大。
A+A = {0,1,2,3,4,6}，共 6 个 0123456 A−A = {−3,−2,−1,0,1,2,3}，共 7 个 −3−2−10123
同一个 \(A=\{0,1,3\}\)，差集（下，7 个，关于 0 对称）比和集（上，6 个）多一个元素。

在相反的方向上，集合 \[A:=\{(0,0),(1,0),(2,0),(3,1),(4,0),(5,1),(6,1),(7,0),(8,1),(9,1)\}\in\mathbb{Z}_{10}\times\mathbb{Z}_2\] 满足：\(A+A=\mathbb{Z}_{10}\times\mathbb{Z}_2\) 有 \(20\) 个元素，但 \(A-A=(\mathbb{Z}_{10}\times\mathbb{Z}_2)\backslash\{(0,1)\}\) 只有 \(19\) 个元素；可以像之前那样通过取 \(d\) 次幂来放大这个例子。尽管有这些例子，\(|A+A|\) 与 \(|A-A|\) 的大小之间仍存在若干关系；尤其参见下文 (2.11)。

两个方向的结论前一个例子说明 \(A-A\) 可以远大于 \(A+A\)；后一个例子说明反过来 \(A+A\) 也可以严格大于 \(A-A\)（\(20>19\)）。所以一般情况下 \(|A+A|\) 与 \(|A-A|\) 谁大谁小都没有定论——它们只在“有结构”的特殊情形（命题 2.2、2.3）才必然相等。但它们也不是毫无瓜葛：后续 (2.11) 会给出把二者互相约束的不等式。

习题

习题
  1. 2.1.1　设 \(N,M\ge1\) 为整数，\(A,B\) 分别是从实区间 \(\{x\in\mathbb{R}:0\le x\le1\}\) 中均匀随机选取的、基数为 \(N\) 与 \(M\) 的集合。证明：以概率 \(1\) 有 \(|A+B|=|A||B|\)，且对所有 \(n\ge1\) 有 \(|nA|=\binom{|A|+n-1}{n}\)。
  2. 2.1.2　证明命题 2.2 中其余的论断。
  3. 2.1.3　设 \(A\) 为加性集合。证明：\(A\) 是群当且仅当 \(2A=A\)。
  4. 2.1.4　证明命题 2.3。
  5. 2.1.5　[289] 找一个整数加性集合 \(A\)，使得 \(|A-A|<|A+A|\)。（提示：有多种做法。一种是用上面给出的 \(\mathbb{Z}_{10}\times\mathbb{Z}_2\) 例子去铺满格 \(\mathbb{Z}^2\)，再设法截断并投影回 \(\mathbb{Z}\)。）

返回 全书目录