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

2.4　覆盖引理Covering lemmas

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向初学者的详解，逐步推演、举例、画图，不用比喻。

本节目标前几节我们一直在比较一个集合 \(A\) 的“大小”和它各种和差集（如 \(A+A\)、\(A-A\)）的大小。本节要换一个更几何的视角：如果两个集合 \(A,B\) 的加法结构很接近（比如 Ruzsa 距离很小），那么能不能用少数几个 \(B\)（或它的小变形）的平移把 \(A\) 整个盖住？这类“覆盖引理”是把“加法结构小”翻译成“被结构化集合包住”的关键桥梁，最终把研究对象归结为所谓的近似群。

下面我们介绍若干覆盖引理。粗略地说，它们都有这样的味道：如果 \(A\) 与 \(B\) 具有相似的加法结构（例如，它们的 Ruzsa 距离很小），那么就可以用少数几个 \(B\)（或 \(B\) 的某种变形）的平移把 \(A\) 盖住。

2.4.1　Ruzsa 覆盖引理

引理 2.14（Ruzsa 覆盖引理） 设 \(A,B\) 是同处于环境群 \(Z\) 中的加性集合。则存在加性集合 \(X^{+}\subseteq B\)，使得 \[ B\subseteq A-A+X^{+};\qquad |X^{+}|\le\frac{|A+B|}{|A|};\qquad |A+X^{+}|=|A|\,|X^{+}|. \] 类似地，存在加性集合 \(X^{-}\subseteq B\)，使得 \[ B\subseteq A-A+X^{-};\qquad |X^{-}|\le\frac{|A-B|}{|A|};\qquad |A-X^{-}|=|A|\,|X^{-}|. \] 特别地，\(B\) 可以被 \(\min\!\left(\dfrac{|A+B|}{|A|},\dfrac{|A-B|}{|A|}\right)\) 个 \(A-A\) 的平移所覆盖。
先把符号读懂
注记 2.15 这条覆盖引理有一个有用的副产品：至少存在 \(\dfrac{|B|}{|A-A|}\) 个互不相交的平移 \(A+b\)（其中 \(b\in B\)）。把 \(b\) 限制在 \(X^{+}\) 中即可看出这一点。
证明. 只需证明关于 \(A+B\) 的论断；关于 \(A-B\) 的论断，只要把 \(B\) 换成 \(-B\)、把 \(X^{+}\) 换成 \(-X^{-}\) 即可（注意 \(A-A\) 关于原点对称）。 考虑由 \(B\) 中元素对 \(A\) 作平移得到的平移族 \(\{A+b:b\in B\}\)。这些平移每一个的体积都是 \(|A|\)，并且全都含于 \(A+B\) 之中。因此，如果我们取出其中一个极大的两两不相交子族，即对某个 \(X^{+}\subseteq B\) 取出 \(\{A+x:x\in X^{+}\}\)，那么 \(X^{+}\) 的基数至多为 \(\dfrac{|A+B|}{|A|}\)。同时，由构造方式知 \(|A+X^{+}|=|A|\,|X^{+}|\)。 现在对任意元素 \(b\in B\)，平移 \(A+b\) 不可能与 \(\{A+x:x\in X^{+}\}\) 中的每一个都不相交——否则就与 \(X^{+}\) 的极大性矛盾。于是 \(A+b\) 必与 \(A+X^{+}\) 相交，这意味着 \(b\in A-A+X^{+}\)。由于 \(b\in B\) 任取，故 \(B\subseteq A-A+X^{+}\)，论断得证。♦

把这条证明拆成最小的步子，看清它“为什么对”。整个论证只用到一个核心思想——取极大不相交族，即贪心地往里塞互不重叠的平移，直到塞不下为止。

  1. 所有候选平移都装在同一个盒子里。对每个 \(b\in B\)，\(A+b\subseteq A+B\)。所以这些平移全都关在大小为 \(|A+B|\) 的集合 \(A+B\) 内部。
  2. 能塞进多少互不相交的平移是有上限的。若选出的 \(\{A+x:x\in X^{+}\}\) 两两不相交，它们的总体积 \(=|A|\cdot|X^{+}|\)，又必须 \(\le|A+B|\)。于是 \(|X^{+}|\le|A+B|/|A|\)。这就是平移个数的上界。
  3. 极大性逼出覆盖。“极大”意味着再也加不进新的不相交平移。所以对任何 \(b\in B\)，\(A+b\) 一定碰到已选的某个 \(A+x\)。
  4. 相交即可解出 \(b\)。\(A+b\) 与 \(A+x\) 相交，说明存在 \(a_1,a_2\in A\) 与 \(x\in X^{+}\)，使 \(a_1+b=a_2+x\)，即 \(b=a_2-a_1+x\in A-A+X^{+}\)。
大盒子 = A+B（所有平移都在里面） A+x₁A+x₂A+x₃A+x₄ A+b 新来的 A+b 塞不下， 必与已有平移相交
实线圆是已选的极大两两不相交平移族（共 \(|X^{+}|\) 个，总面积不超过盒子面积 \(|A+B|\)）。任何新平移 \(A+b\)（虚线）都无法不碰它们，碰上就给出 \(b\in A-A+X^{+}\)。
例：为什么平移个数那么少 设 \(A\) 加法结构很好，比如 \(|A+B|\le 3|A|\)（\(B\) 相对 \(A\) 只把和集放大了 3 倍）。那么由引理，\(|X^{+}|\le 3\)：只用 3 个 \(A-A\) 的平移就能把整个 \(B\) 盖住——无论 \(B\) 本身多大。这正是覆盖引理威力所在：它把“和集放大倍数小”直接变成“平移片数少”。

像上面这样的覆盖引理之所以方便，有若干原因。首先，它们使迭代和集的计算变得容易。例如，如果已知

\[ A+B\subseteq A+X, \]

那么立即可以推出

\[ A+nB\subseteq A+nX\qquad\text{对一切 }n\ge 0. \]

当 \(X\) 比 \(B\) 小很多时，这一点非常有利。此外，诸如 \(A+B\subseteq A+X\) 的覆盖性质在 Freiman 同态下保持不变；而像 \(|A+A|\le K|A|\) 这样的界则只在 Freiman 同构下保持（见第 5 章，特别是习题 5.3.13）。

为什么覆盖式更"耐用"关键在于：覆盖关系 \(A+B\subseteq A+X\) 是一个纯粹的包含关系，只要把每个元素映成它该去的地方，关系就照样成立——这正是同态能保持的；而“大小之比 \(\le K\)”是一个计数陈述，同态可能把不同元素粘到一起、改变计数，所以只有保持计数的同构才保得住它。
注记 2.16 注意我们是用 \(A-A\)（而非 \(A\) 本身）来覆盖 \(B\) 的。这反映了一个事实：\(A-A\) 是比 \(A\) 更“光滑”的集合，往往含有更少的“窟窿”，因而更适合用来覆盖别的集合。后面我们会看到，更高阶的和差集（如 \(2A-2A\)）甚至更光滑——它们倾向于包含非常长的等差数列；详见 4.7 节与第 12 章的进一步讨论。

2.4.2　Green–Ruzsa 覆盖引理

可以对 Ruzsa 覆盖引理作多种改造。例如，可以保证“用 \(A-A\) 的平移覆盖 \(B\)”这件事具有很高的重数（代价是覆盖个数增大一倍）。

什么叫"重数"普通覆盖只要求 \(B\) 的每个元素 \(y\) 至少有一种写法 \(y=x+a-a'\)。高重数则要求每个 \(y\) 有很多种这样的写法（至少 \(|A|/2\) 种）。写法越多，覆盖越“厚实”，在后面的计数论证里能提供更强的信息（比如用来控制 \(2B-2B\) 这种四重和差集）。
引理 2.17（Green–Ruzsa 覆盖引理） 设 \(A,B\) 是同一环境群中的加性集合。则存在加性集合 \(X\subseteq B\)，满足 \(|X|\le 2\dfrac{|A+B|}{|A|}-1\)，使得对每个 \(y\in B\)，都至少有 \(|A|/2\) 个三元组 \((x,a,a')\in X\times A\times A\) 满足 \(x+a-a'=y\)。更通俗地说，\(A-A+X\) 以至少 \(|A|/2\) 的重数覆盖了 \(B\)。此外，还有 \[ B-B\subseteq A-A+X-X. \] 若把 \(\dfrac{|A+B|}{|A|}\) 换成 \(\dfrac{|A-B|}{|A|}\)，类似结论仍成立。
证明. 同样只需证关于 \(\dfrac{|A+B|}{|A|}\) 的情形。执行如下算法：先把 \(X\) 初始化为空集，于是 \(X+A-A\) 也是空集。然后运行以下循环。如果找不到 \(B\) 中任何一个“与 \(X+A\) 充分不相交”的元素 \(y\)——这里“充分不相交”指 \(|(y+A)\cap(X+A)|\le|A|/2\)——就终止算法。否则，如果存在这样的 \(y\)，就把它加入 \(X\)，然后重复上述步骤。 每当我们往 \(X\) 中加入一个元素，\(|X+A|\) 的大小（由构造）至少增加 \(|A|/2\)，而第一步则增加 \(|A|\)。然而 \(X+A\) 始终必须落在 \(B+A\) 之内。因此该算法至多经过 \(2\dfrac{|A+B|}{|A|}-1\) 步即终止。 现设 \(y\) 为 \(B\) 中任一元素。由构造，终止时有 \(|(y+A)\cap(X+A)|>|A|/2\)，因此 \(y\) 至少有 \(|A|/2\) 种形如 \(x+a-a'\)（其中 \((x,a,a')\in X\times A\times A\)）的表示。 最后，若 \(y,y'\) 是 \(B\) 中两个元素，则 \[ |\{a\in A:y+a\in X+A\}|=|(y+A)\cap(X+A)|>|A|/2, \] 同理 \(|\{a\in A:y'+a\in X+A\}|>|A|/2\)。于是由鸽笼原理，存在 \(a\in A\) 同时满足 \(y+a\in X+A\) 且 \(y'+a\in X+A\)，从而 \[ y-y'=(y+a)-(y'+a)\in (X+A)-(X+A)=A-A+X-X. \] 由于 \(y,y'\in B\) 任取，故 \(B-B\subseteq A-A+X-X\)，论断得证。♦
  1. 贪心循环。每次只挑一个还“不够被覆盖”的 \(y\)（与现有 \(X+A\) 的交不超过 \(|A|/2\)），把它放进 \(X\)。
  2. 每步都让 \(X+A\) 实打实长大。新加的 \(y\) 满足 \(|(y+A)\cap(X+A)|\le|A|/2\)，意味着 \(y+A\) 至少有一半（\(\ge|A|/2\) 个）元素是 \(X+A\) 里没有的“新元素”，故 \(|X+A|\) 至少涨 \(|A|/2\)。
  3. 容量封顶 ⇒ 步数封顶。\(X+A\) 永远关在 \(A+B\) 里，体积 \(\le|A+B|\)。第一步涨 \(|A|\)，以后每步涨 \(\ge|A|/2\)，所以步数 \(\le 2\dfrac{|A+B|}{|A|}-1\)。
  4. 终止条件给出高重数。循环停下来时，每个 \(y\in B\) 都已“够被覆盖”，即 \(|(y+A)\cap(X+A)|>|A|/2\)。每一个交点对应一种表示 \(y=x+a-a'\)，故重数 \(>|A|/2\)。
  5. 鸽笼连接两点。\(y\) 与 \(y'\) 各自都有超过半数的 \(a\) 让 \(y+a,y'+a\) 落进 \(X+A\)。两个“超过半数”的集合必有公共元素，那个公共的 \(a\) 就把 \(y-y'\) 表示成 \(A-A+X-X\) 中的元素。
A 中全部元素 a（共 |A| 个） {a : y+a∈X+A} ＞|A|/2 {a : y′+a∈X+A} ＞|A|/2 公共 a 两块都超过总数一半 ⇒ 必有重叠（鸽笼原理）
两个各自大于 \(|A|/2\) 的子集装在大小为 \(|A|\) 的集合里，必相交——这就保证了存在同时管用的 \(a\)。

在 5.4 节，我们还会发展出又一条覆盖引理（引理 5.31），其中覆盖集 \(X\) 不是任意的，而恰好是一个方体（cube）。

2.4.3　一个应用：控制四重和差集

现在我们给出 Green–Ruzsa 覆盖引理的一个应用，即 (2.6) 的一个变体——它控制的是四重和，而非二重和。

命题 2.18 设 \(A,B\) 是环境群 \(Z\) 中的加性集合。则 \[ |2B-2B|\le 16\,\frac{|A+B|^{4}|A-A|}{|A|^{4}}. \]
先看这要说什么\(2B-2B=(B+B)-(B+B)\) 是 \(B\) 的“四重和差集”，一般来说可能非常大。命题说：只要存在某个 \(A\) 使得 \(|A+B|\) 和 \(|A-A|\) 都不太大，那么 \(2B-2B\) 也被牢牢控制住。证明的核心套路是数表示法的个数：先证明 \(2B-2B\) 里每个元素都有很多种写法，再用“元素个数 × 每个的写法数 ≤ 写法总数”反解出元素个数的上界。
证明. 应用 Green–Ruzsa 覆盖引理，可找到一个集合 \(X\)，其基数 \(|X|\le 2\dfrac{|A+B|}{|A|}\)，使得 \(A-A+X\) 以至少 \(|A|/2\) 的重数覆盖 \(B\)。 现设 \(z\) 为 \(B-B\) 中任一元素。依定义 \(z=b_1-b_2\)，其中 \(b_1,b_2\in B\)。由 \(X\) 的构造，可找到至少 \(|A|/2\) 个三元组 \((x,a_1,a_2)\in X\times A\times A\)，使得 \(b_2=x+a_1-a_2\)，从而 \[ |\{(x,a_1,a_2)\in X\times A\times A:z=b_1-a_1+a_2-x\}|\ge|A|/2. \] 作变量替换 \(c:=b_1+a_2\in A+B\)，得到 \[ |\{(x,c,a_1)\in X\times(A+B)\times A:z=c-a_1-x\}|\ge|A|/2. \] 类似地，若 \(z'\) 是 \(B-B\) 中另一元素，则 \[ |\{(x',c',a_1')\in X\times(A+B)\times A:z'=c'-a_1'-x'\}|\ge|A|/2, \] 于是 \[ \big|\{(x,x',c,c',a_1,a_1')\in X\times X\times(A+B)^2\times A^2: z=c-a_1-x,\ z'=c'-a_1'-x'\}\big|\ge|A|^{2}/4. \] 现记 \(d:=a_1-a_1'\in A-A\)，并注意：若 \(z=c-a_1-x\) 且 \(z'=c'-a_1'-x'\)，则 \[ z-z'=c-c'-d-x+x'. \] 此外，一旦固定 \(z,z',c,c',d,x,x'\)，则 \(a_1,a_1'\) 由方程 \(a_1=c-x-z\)，\(a_1'=c'-x'-z'\) 唯一确定。因此 \[ \big|\{(x,x',c,c',d)\in X\times X\times(A+B)^2\times(A-A): z-z'=c-c'-d-x+x'\}\big|\ge|A|^{2}/4. \] 注意 \(z-z'\) 是 \((B-B)-(B-B)=2B-2B\) 中的任意元素。于是我们证明了：\(2B-2B\) 中任意元素至少有 \(|A|^{2}/4\) 种形如 \(c-c'-d-x+x'\)（其中 \((x,x',c,c',d)\in X\times X\times(A+B)^2\times(A-A)\)）的表示。由于参数总数为 \(|X|^2|A+B|^2|A-A|\) 而 \(|X|\le 2\dfrac{|A+B|}{|A|}\)，论断随之成立。♦
  1. 把目标元素拆成可数的部件。把 \(2B-2B\) 的元素写成 \(z-z'\)，再把每个 \(z,z'\in B-B\) 用覆盖引理展开成 \(X,A+B,A-A\) 里的元素的组合。
  2. 每个目标元素的表示数有下界。合并两套高重数表示，再令 \(d=a_1-a_1'\)，得到：\(2B-2B\) 的每个元素都 \(\ge|A|^2/4\) 种表示。
  3. 表示总数有上界。所有 \((x,x',c,c',d)\) 的组合数不超过 \(|X|^2\cdot|A+B|^2\cdot|A-A|\)。
  4. 反解元素个数。\(|2B-2B|\cdot\dfrac{|A|^2}{4}\le|X|^2|A+B|^2|A-A|\le 4\dfrac{|A+B|^2}{|A|^2}|A+B|^2|A-A|\)，整理即得系数 16。

我们可以利用 Ruzsa 的下述精巧的“张量幂技巧”消去因子 \(16\)：

推论 2.19 设 \(A,B\) 是环境群 \(Z\) 中的加性集合。则 \[ |2B-2B|\le\frac{|A+B|^{4}|A-A|}{|A|^{4}}. \]
证明. 固定 \(A,B\)，令 \(M\) 为一个大整数参数。考虑 \(M\) 重笛卡儿积 \(A^{\oplus M}:=A\times\dots\times A\)，它是加法群 \(Z^{\oplus M}:=Z\oplus\dots\oplus Z\) 的子集；同样考虑 \(B^{\oplus M}\)。则容易验证 \[ 2B^{\oplus M}-2B^{\oplus M}=(2B-2B)^{\oplus M};\quad A^{\oplus M}+B^{\oplus M}=(A+B)^{\oplus M};\quad A^{\oplus M}-A^{\oplus M}=(A-A)^{\oplus M}. \] 于是把命题 2.18 应用到 \(A^{\oplus M},B^{\oplus M}\) 上，得 \[ |2B-2B|^{M}\le 16\,\frac{|A+B|^{4M}|A-A|^{M}}{|A|^{4M}}. \] 两边取 \(M\) 次方根并令 \(M\to\infty\)（此时 \(16^{1/M}\to 1\)），即得结论。♦
张量幂技巧的妙处关键观察：所有相关的量（\(|2B-2B|\)、\(|A+B|\)、\(|A-A|\)、\(|A|\)）在取 \(M\) 重积后都恰好变成 \(M\) 次幂，而那个碍事的常数 \(16\) 不随 \(M\) 增大。于是不等式变成 \(L^M\le 16\,R^M\)，开 \(M\) 次方得 \(L\le 16^{1/M}R\)；让 \(M\to\infty\)，\(16^{1/M}\to 1\)，常数就被“稀释”没了。这是一种把乘性常数变成 \(1\) 的通用手段。
M（重数）→ 16^(1/M) → 1 16
当 \(M=1\) 时系数是 \(16\)，随 \(M\) 增大 \(16^{1/M}\) 迅速逼近 \(1\)，极限恰为 \(1\)。

把推论 2.19 特殊化到 \(B:=-A\) 的情形，得到

推论 2.20 设 \(A\) 是加性集合。则 \[ |2A-2A|\le\frac{|A-A|^{5}}{|A|^{4}}, \] 换言之， \[ d(A-A,\ A-A)\le 4\,d(A,A). \]
从 2.19 到 2.20 的代入 在推论 2.19 中取 \(B=-A\)。则 \(2B-2B=-2A+2A=2A-2A\)（前面的符号不影响集合大小）；\(A+B=A-A\)，故 \(|A+B|^4=|A-A|^4\)。代入便得 \(|2A-2A|\le\dfrac{|A-A|^4|A-A|}{|A|^4}=\dfrac{|A-A|^5}{|A|^4}\)。再回忆 Ruzsa 距离 \(d(X,Y)=\log\dfrac{|X-Y|}{\sqrt{|X|\,|Y|}}\)，把 \(|2A-2A|\le|A-A|^5/|A|^4\) 取对数即得 \(d(A-A,A-A)\le 4d(A,A)\)。
注记 2.21 利用 Plünnecke 不等式的工具，可以把这些估计略加改进；见推论 6.28。

把推论 2.20 与 Ruzsa 覆盖引理（引理 2.14，取 \(B=2A-A\)）结合，得到

推论 2.22 对任意加性集合 \(A\)，\(2A-A\) 可被 \(\delta[A]^{5}\) 个 \(A-A\) 的平移覆盖。

进而可知 \(3A-A\) 可被 \(\delta[A]^{5}\) 个 \(2A-A\) 的平移覆盖，从而被 \(\delta[A]^{10}\) 个 \(A-A\) 的平移覆盖。如此继续下去，一个简单的归纳便给出

\[ m A-n A\text{ 可被 }\delta[A]^{5(m+n-2)}\text{ 个 }A-A\text{ 的平移覆盖}\tag{2.16} \]

对一切 \(m,n\ge 1\) 成立。特别地，

\[ |m A-n A|\le\delta[A]^{5(m+n-1)}|A|\qquad\text{对一切 }m,n\ge 1.\tag{2.17} \]
记号提醒这里 \(\delta[A]=\dfrac{|A-A|}{|A|}\) 是 \(A\) 的差倍数常数（difference constant），衡量差集相对原集合放大了多少倍。若 \(A\) 加法结构好，则 \(\delta[A]\) 接近 \(1\)，于是 \(\delta[A]^{5(m+n-2)}\) 仍然不大——这意味着任意阶的迭代和差集 \(mA-nA\) 都只需多项式级个 \(A-A\) 的平移就能盖住，且本身不会比 \(|A|\) 大太多。
2A−A被 δ⁵ 个 A−A 平移 3A−A被 δ¹⁰ 个 A−A 平移 每升一阶，覆盖片数乘以 δ⁵；归纳得到 (2.16)
归纳链条：\(2A-A\to 3A-A\to\dots\)，每往上一阶覆盖片数乘 \(\delta[A]^5\)，复合后得到 \(\delta[A]^{5(m+n-2)}\)。

由此（再结合平凡估计 \(|kA|\ge|A|\)，对任意 \(k\ge 1\)）可得

推论 2.23（对称和集估计，初步版） 设 \(A\) 是加性集合。则对任意非负整数 \(n_1,n_2,n_3,n_4\)，有估计 \[ d(n_1 A-n_2 A,\ n_3 A-n_4 A)\le 5(n_1+n_2+n_3+n_4)\,d(A,A). \] （常数 \(5\) 并非最优；我们稍后会改进它。）

因此，如果 \(A\) 的差倍数常数较小，那么 \(A\) 的所有迭代和集在 Ruzsa 度量下其实彼此靠得很近。该推论的另一个推论是 \[ \sigma[n_1 A-n_2 A]\le\sigma[A]^{10(n_1+n_2)} \] 对一切非负整数 \(n_1,n_2\) 成立。因子 \(10\) 并非最优；当我们在 6.5 节发展 Plünnecke 不等式的工具时，会得到对该常数的改进。然而，关于 \(n_1\) 与 \(n_2\) 的线性增长是必要的；见习题 2.4.9。

把上述推论与 Ruzsa 三角不等式结合，可以得到关于一对集合的类似估计：

推论 2.24（非对称和集估计，初步版） 设 \(A,B\) 是同处于环境群 \(Z\) 的加性集合。则对任意 \(n_1,\dots,n_8\in\mathbb{N}\)，有估计 \[ d(n_1 A-n_2 A+n_3 B-n_4 B,\ n_5 A-n_6 A+n_7 B-n_8 B)=O\big((n_1+\dots+n_8)\,d(A,B)\big). \] 证明留作习题。

2.4.4　近似群

我们可以利用上述工具，把具有较小差倍数或倍增常数的加性集合，放进一个更具结构的集合中，即所谓的“近似群”。

定义 2.25（近似群） 设 \(K\ge 1\)。称加性集合 \(H\) 为一个 \(K\)-近似群，如果它是对称的（即 \(H=-H\)），含有原点，并且 \(H+H\) 至多可被 \(K\) 个 \(H\) 的平移覆盖。

注意，\(1\)-近似群必然是一个有限群；反过来，每个有限群都是 \(1\)-近似群。

近似群＝"差一点点的群"真正的群 \(H\) 满足 \(H+H=H\)（对加法封闭）。\(K\)-近似群把这个苛刻条件放松成：\(H+H\) 虽然可能比 \(H\) 大，但大不了多少——只需 \(K\) 片 \(H\) 就能盖住。\(K=1\) 时盖住 \(H+H\) 只用 \(1\) 片 \(H\)，等价于 \(H+H=H\)（再加上对称与含 \(0\)），这恰好就是有限群。所以“近似群”是“群”这一刚性概念的定量松弛。
真群：H+H = H（1 片） H = H+H K-近似群：H+H 被 K 片 H 盖住 H+H HHH
左：真群，自加不变。右：近似群，自加后变大，但仍能被 \(K\) 片平移的 \(H\) 盖住（图中 \(K=3\)）。

我们可以把前面许多结果总结成命题 2.7 的如下部分推广。

命题 2.26 设 \(A\) 是加性集合，\(K\ge 1\)。则以下命题在“相差常数”的意义下等价——即：若第 \(j\) 条对某个绝对常数 \(C_j\) 成立，则第 \(k\) 条也将对某个依赖于 \(C_j\) 的绝对常数 \(C_k\) 成立：
  1. \(\sigma[A]\le K^{C_1}\)（即 \(|A+A|\le K^{C_1}|A|\)）；
  2. \(\delta[A]\le K^{C_2}\)（等价地，\(d(A,A)\le C_2\log K\)，或 \(|A-A|\le K^{C_2}|A|\)）；
  3. \(d(A,B)\le C_3\log K\) 对至少一个加性集合 \(B\) 成立；
  4. \(|n A-m A|\le K^{C_4(n+m)}|A|\) 对一切非负整数 \(n,m\) 成立；
  5. 存在一个 \(K^{C_5}\)-近似群 \(H\)，使得 \(A\subseteq x+H\) 对一切 \(x\in A\) 成立，并且进一步 \(|A|\ge K^{-C_5}|H|\)。
证明. 前三条性质的等价性，由 Ruzsa 三角不等式与 (2.11) 推出。第四条与（比如说）第二条的等价性，由推论 2.24 推出。要看出第五条蕴含（比如说）第一条，注意若前者成立，则 \[ |A+A|\le|H+H|\le K^{C_5}|H|\le K^{2C_5}|A|. \] 要从第四条推出第五条，取 \(H=A-A\)，再应用 Ruzsa 覆盖引理即可。♦
这条命题在说什么它把“\(A\) 加法结构好”的五种不同说法证明为彼此等价（在多项式级常数损失的意义下）：和集小（i）、差集小（ii）、与某集合 Ruzsa 距离小（iii）、所有迭代和差集都不大（iv）、被一个近似群的平移密集包住（v）。换言之，无论你从哪个角度定义“结构好”，得到的都是同一类集合。第五条尤其重要——它把抽象的“结构好”落实为具体的几何图像：\(A\) 基本上就是某个近似群的一大块。

于是，在定性意义下，我们已经把具有较小差倍数或倍增常数的加性集合的研究，归结为对近似群的研究——更确切地说，归结为对“近似群的平移的稠密子集”的研究。这是一个相当令人满意的局面，唯一的遗憾是：我们还没有对“哪些集合是近似群”给出好的刻画。著名的有限群结构定理（见下面的推论 3.8）断言：每个有限群都是有限循环群的乘积；我们最终也将能够得到近似群的某种类似刻画，表明它们都被高效地包含在某个广义等差数列之中。关于近似群的其他一些性质，见下面的习题。

命题 2.26 有一个非对称对应版本，其证明留作习题。

命题 2.27 设 \(A,B\) 是环境群 \(Z\) 中的加性集合，\(K\ge 1\)。则以下命题在“相差常数”的意义下等价（含义同前）：
  1. \(d(A,B)\le C_1\log K\)；
  2. \(d(A,-B)\le C_2\log K\)；
  3. \(|A+B|\le K^{C_3}\min(|A|,|B|)\)；
  4. \(|A-B|\le K^{C_4}\min(|A|,|B|)\)；
  5. \(|n_1 A-n_2 A+n_3 B-n_4 B|\le K^{C_5(n_1+n_2+n_3+n_4)}|A|\) 对一切非负整数 \(n_1,n_2,n_3,n_4\) 成立；
  6. \(\sigma[A],\sigma[B]\le K^{C_6}\)，且存在 \(x\in Z\) 使得 \(|A\cap(B+x)|\ge K^{-C_6}|A|^{1/2}|B|^{1/2}\)；
  7. \(\sigma[A],\sigma[B]\le K^{C_7}\)，且 \(E(A,B)\ge K^{-C_7}|A|^{3/2}|B|^{3/2}\)；
  8. 存在一个 \(K^{C_8}\)-近似群 \(H\)，使得 \(A\subseteq H+a\) 且 \(B\subseteq H+b\) 对一切 \(a\in A,b\in B\) 成立，并且进一步 \(|A|,|B|\ge K^{-C_8}|H|\)。

注意，习题 2.3.7 本质上就是本命题 \(K=1\) 的情形。

命题 2.27 用近似群给出了对“具有较小 Ruzsa 距离的成对集合”的满意刻画，前提是人们愿意在指数上损失一些绝对常数。然而要注意，它只适用于那些在数量级上（相差至多 \(K\) 的若干次幂）可比的集合 \(A,B\)（参见习题 2.3.6）。当 \(A\) 与 \(B\) 在数量级上差异很大时，本命题存在一个部分类比，但那里的理论不如这里令人满意；见 2.6 节。

2.4.5　习题

习题 2.4.1 设 \(Z\) 为有限加法群，\(A\) 为 \(Z\) 的一个随机子集，使得各事件 \(\{a\in A\}\) 相互独立、概率均为 \(3/4\)。证明：以 \(1-o_{|Z|\to\infty}(1)\) 的概率有 \(|A|>|Z|/2\)（故由习题 2.1.6 知 \(A+A=A-A=Z\)），但仍不可能用少于 \(\tfrac{1}{10}\log|Z|\) 个 \(A\) 的平移覆盖 \(Z\)。（提示：若 \(X\) 是 \(|X|\le\tfrac{1}{10}\log|Z|\) 的加性集合，用引理 2.14 找出 \(|Y|=\Omega(|Z|/\log^2|Z|)\) 的加性集合 \(Y\)，使平移 \(y-X\) 对一切 \(y\in Y\) 两两不相交；计算 \(A\) 与某个 \(y-X\) 不相交的概率，进而得到 \(A+X=Z\) 概率的上界；再对所有 \(X\) 的选取作并集界。）这表明：在引理 2.14 中，若不允许某种对数损失，则不能把 \(A-A\) 换成 \(A\)。
习题 2.4.2 设 \(A\) 为群 \(Z\) 中的加性集合，\(\varphi:Z\to Z'\) 为群同态。证明不等式 \[ |A|\le|\varphi(A)|\sup_{x\in Z'}|A\cap\varphi^{-1}(x)|\le|2A|. \] （提示：用 Ruzsa 覆盖引理把 \(A\) 用 \(\varphi^{-1}(0)\) 的某子集的平移覆盖。）特别地，当 \(A\) 是某群的陪集时，两个不等式都取等号。
习题 2.4.3 证明推论 2.24。你得到的 \(O()\) 记号中隐含常数取什么值？
习题 2.4.4 设 \(A\) 为加性集合，满足 \(|2A-2A|<2|A|\)。证明 \(A-A\) 是一个群。（提示：用引理 2.14。）由此及推论 2.19 可知：若 \(|A-A|<2^{1/5}|A|\)，则 \(A-A\) 是群。常数 \(2^{1/5}\) 可改进为 \(\tfrac{3}{2}\)；见下面习题 2.6.5。
习题 2.4.5 设 \(G\) 为 \(K\)-近似群（\(K\ge 1\) 为整数）。证明 \(|nG|\le\binom{K+n-1}{n}|G|\) 对一切整数 \(n\ge 1\) 成立。特别地推出界 \[ |nG|\le\min(K^{n},\,n^{K-1})|G|\qquad\text{对一切 }n\ge 1; \] 于是 \(|nG|\) 在 \(n\le K\) 时随 \(n\) 指数增长，但在 \(n>K\) 后稳定为多项式增长。事实上，对任意加性集合，当 \(n\) 足够大时 \(|nA|\) 是 \(n\) 的多项式；该事实的证明及进一步讨论见 [261]。
习题 2.4.6 设 \(A\) 为加性集合，倍增常数 \(\sigma[A]=K\)（\(K\ge 1\)）。证明 \[ |nA|\le\min(K^{Cn},\,n^{CK-1})|A| \] 对一切 \(n\ge 1\) 及某个绝对常数 \(C>0\) 成立。（注意若 \(K\) 非常接近 \(1\)，则可用习题 2.4.4 得到强得多的界。）
习题 2.4.7 设 \(G\) 为环境群 \(Z\) 中的 \(K\)-近似群，\(H\) 为 \(Z\) 中的 \(K'\)-近似群。证明 \(G+H\) 是 \(KK'\)-近似群；证明 \(2G\cap 2H\) 是 \((KK')^3\)-近似群。（提示：先证 \((2G\cap 2H)-(2G\cap 2H)\subset(G+X)\cap(H+Y)\)，其中 \(X,Y\) 的基数分别至多为 \(K^3\) 与 \((K')^3\)；再证每个形如 \((G+x)\cap(H+y)\) 的集合都含于 \(2G\cap 2H\) 的某平移中。）修改习题 2.2.9 以说明：若把集合 \(2G\cap 2H\) 换成 \(G\cap H\)，这类陈述会严重失败。此外，建立基数界 \[ \frac{1}{(KK')^3}\frac{|G||H|}{|G+H|}\le|2G\cap 2H|\le\frac{|G||H|}{|G+H|}. \] （提示：下界用 (2.8)，上界用 Ruzsa 三角不等式。）由此推出估计 \[ d(G,H)\le d(G,G+H)+d(G+H,H)\le d(G,H)+\log KK' \] 以及 \[ d(G,H)\le d(G,2G\cap 2H)+d(2G\cap 2H,H)\le d(G,H)+3\log KK', \] 并与习题 2.3.11 作比较。
习题 2.4.8 对每个 \(j=1,2,3\)，设 \(G_j\) 为环境群 \(Z\) 中的 \(K_j\)-近似群。利用 Ruzsa 三角不等式证明 \[ |G_1+G_2+G_3|\le K_2\frac{|G_1+G_2||G_2+G_3|}{|G_2|}. \] 由此推出 \[ d(G_1+G_2,\ G_1+G_2+G_3)\le d(G_2,\ G_2+G_3)+\log K_1 K_2. \]

返回 全书目录