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

2.5　Balog–Szemerédi–Gowers 定理The Balog–Szemerédi–Gowers theorem

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

在前几节里，我们只考虑了完全和集 \(A+B\) 与完全差集 \(A-B\)。但在许多应用中，人们只能掌控其中一部分和与差。所幸有一件非常有用的工具——Balog–Szemerédi–Gowers 定理（下文简称 BSG 定理）——它允许我们从对部分和集、部分差集的掌控出发，推出对完全和集、完全差集的掌控（代价是把集合稍微缩小一点）。我们先引入一些记号。

本节目标前几节的和集估计（Plünnecke–Ruzsa 等）都要求“所有配对 \(a+b\) 的取值范围很小”，也就是 \(|A+B|\) 小。可是现实中常常只知道：在所有 \(|A||B|\) 个配对里，有相当一部分（比如 \(1/K\) 比例）落在一个小集合中，而剩下的配对可能乱跑。这种“部分信息”能不能救回来？BSG 定理回答：能——只要愿意把 \(A,B\) 各自换成一个仍然很大的子集 \(A',B'\)，就能保证这两个子集的完全和集 \(A'+B'\) 也很小。本节给出定理的现代表述、它与加性能量 \(E(A,B)\) 的等价联系，以及连接二者的关键引理。

部分和集与部分差集

定义 2.28（部分和集） 设 \(A,B\) 是同一个母群 \(Z\) 中的加性集合，\(G\) 是 \(A\times B\) 的一个子集。定义部分和集 \[A\stackrel{G}{+}B:=\{a+b:(a,b)\in G\}\] 以及部分差集 \[A\stackrel{G}{-}B:=\{a-b:(a,b)\in G\}.\]

不妨把 \(G\) 想成连接 \(A\) 与 \(B\) 的一张二部图（bipartite graph）：左边一列顶点是 \(A\) 的元素，右边一列顶点是 \(B\) 的元素，一条边 \((a,b)\in G\) 表示“这一对要参与运算”。部分和集就是只对图中实际连边的配对取 \(a+b\) 所得到的值的集合。注意：当 \(G=A\times B\) 是完全图（每一对都连边）时，部分和集、部分差集就退化为通常的完全和集、完全差集。

A B a₁ a₂ a₃ a₄ b₁ b₂ b₃ b₄ 绿色边 = G 部分和集只收集 这些边上的 a+b
\(G\subseteq A\times B\) 是一张二部图。\(A\stackrel{G}{+}B\) 只把有连边的那些配对相加；没连边的配对（图中没画的线）即使和很大也不算进来。

部分和集、部分差集在代数上不如完全和集那么“好用”。特别地，前面那一整套和集估计的机器，如果你只假设某个部分和集的基数 \(|A\stackrel{G}{+}B|\) 很小，是得不出任何结论的。要注意：即使 \(G\) 非常大，也完全可能出现 \(|A\stackrel{G}{+}B|\) 很小、而完全和集 \(|A+B|\) 却很大的情形（见习题）。所幸我们马上要给出的 BSG 定理确实能从“部分和集的信息”推出“完全和集的信息”——只要我们肯把 \(A\) 与 \(B\) 各缩小一个不大的倍数（即把 \(A,B\) 换成只比它们略小的子集 \(A',B'\)）。

例：为什么部分小、完全可以大 想象 \(A\) 由两团东西拼接而成：一团是 Sidon 集（其中两两之和几乎互不相同，所以这一团内部相加会“炸开”，产生约 \(|A|^2\) 个不同的和），另一团是一段等差数列（其内部相加非常“收紧”，只产生约 \(|A|\) 个和）。如果让图 \(G\) 只连接“等差数列那一团内部”的配对，那么 \(A\stackrel{G}{+}A\) 就很小（约 \(|A|\)）；而完全和集 \(A+A\) 因为含有 Sidon 那一团的贡献，会大到约 \(|A|^2/8\)。可见光看部分和集小，不能保证完全和集小——这正是为什么 BSG 定理必须先“提纯”到子集上。

BSG 定理：从部分到完全

这个方向上的第一个结果由 Balog 与 Szemerédi [16] 给出，使用了正则性引理（regularity lemma）。Gowers [137] 找到了一个不同且更有效的证明（Bourgain [38] 又作了细小的改进），其特点是常数依赖只是多项式量级。这里我们按 [340] 给出该定理的一个现代表述。

定理 2.29（Balog–Szemerédi–Gowers 定理） 设 \(A,B\) 是母群 \(Z\) 中的加性集合，\(G\subseteq A\times B\) 满足 \[|G|\ge \frac{|A||B|}{K}\qquad\text{且}\qquad \Big|A\stackrel{G}{+}B\Big|\le K'\,|A|^{1/2}|B|^{1/2},\] 其中 \(K\ge 1\)、\(K'>0\)。那么存在子集 \(A'\subseteq A\)、\(B'\subseteq B\) 使得 \[|A'|\ge \frac{|A|}{4\sqrt2\,K},\tag{2.18}\] \[|B'|\ge \frac{|B|}{4K},\tag{2.19}\] \[|A'+B'|\le 2^{12}\,K^4\,(K')^3\,|A|^{1/2}|B|^{1/2}.\tag{2.20}\] 特别地有 \[d(A',-B')\le 5\log K+3\log K'+O(1).\]

这条定理的证明是图论式的。它是初等的，但有点冗长，因此我们把它推迟到 6.4 节。当然，可以把本定理与推论 2.24、命题 2.26 结合，从而获得关于 \(A'\) 与 \(B'\) 的迭代和集、差集的更多信息。式 (2.20) 中的因子 \(2^{12}K^4(K')^3\) 很可能还能改进；但是界 (2.18)、(2.19) 已经无法本质改进（见习题）。

怎么读这条定理
  1. 假设给了什么。“\(|G|\ge|A||B|/K\)”说图 \(G\) 占了全部 \(|A||B|\) 个配对的至少 \(1/K\)（\(K\) 越接近 1，信息越多）；“\(|A\stackrel{G}{+}B|\le K'|A|^{1/2}|B|^{1/2}\)”说在这一大批配对上，和只取了很少的值（拿 \(|A|^{1/2}|B|^{1/2}\) 当“小”的标尺——当 \(|A|=|B|=N\) 时即约为 \(N\)）。
  2. 结论给了什么。能挑出子集 \(A',B'\)，它们各自仍占原集的 \(\sim 1/K\)（(2.18)、(2.19) 没丢掉太多元素），并且它们的完全和集 \(|A'+B'|\) 仍然很小（(2.20)）。
  3. 为什么珍贵。一旦有了 \(|A'+B'|\) 小（完全和集！），前面所有的和集估计机器（Plünnecke–Ruzsa、Ruzsa 距离 \(d\) 等）就可以直接套上去了。
A（|A| 个） A′ ≳ |A|/4√2K B（|B| 个） B′ ≳ |B|/4K 提纯后：|A′+B′| ≤ 2¹² K⁴ (K′)³ |A|½|B|½（完全和集变小）
BSG 定理的核心动作：从 \(A,B\) 各自抠出一个仍然很大的子集 \(A',B'\)，代价换来的是 \(A'+B'\)（完全和集）受控。

加性能量与部分和集的桥梁

为了应用 BSG 定理，引入下面这条引理很方便，它把大的加性能量与小的部分和集（或小的部分差集）联系起来。

回顾：加性能量 \(E(A,B)\) 加性能量是满足 \(a+b=a'+b'\) 的加性四元组 \((a,a',b,b')\in A\times A\times B\times B\) 的个数。等价地，若记 \(r(x)=|\{(a,b)\in A\times B:a+b=x\}|=|A\cap(x-B)|\) 为 \(x\) 被表示成 \(a+b\) 的方式数，则 \[E(A,B)=\sum_x r(x)^2=\sum_x|A\cap(x-B)|^2,\qquad \sum_x r(x)=|A||B|.\] 直观上：\(E(A,B)\) 大，意味着“和值高度重复”——很多不同配对给出同一个和，于是和集被挤在很小的范围内。这正是引理 2.9 给出的两个恒等式（求和方式数 \(=|A||B|\)；平方和 \(=E\)）。

a a′ b b′ a + b ‖（相等） a′ + b′
一个加性四元组：两对 \((a,b)\) 与 \((a',b')\) 给出同一个和。这样的四元组越多，\(E(A,B)\) 越大，和值越“拥挤”。
引理 2.30 设 \(A,B\) 是母群 \(Z\) 中的加性集合，\(G\) 是 \(A\times B\) 的一个非空子集。则 \[E(A,B)\ge \frac{|G|^2}{\big|A\stackrel{G}{+}B\big|},\qquad E(A,B)\ge \frac{|G|^2}{\big|A\stackrel{G}{-}B\big|}.\] 反过来，若 \(E(A,B)\ge |A|^{3/2}|B|^{3/2}/K\)（对某个 \(K\ge 1\)），则存在 \(G\subseteq A\times B\) 使得 \[|G|\ge \frac{|A||B|}{2K},\qquad \Big|A\stackrel{G}{+}B\Big|\le 2K\,|A|^{1/2}|B|^{1/2};\] 同理存在 \(H\subseteq A\times B\) 使得 \[|H|\ge \frac{|A||B|}{2K},\qquad \Big|A\stackrel{H}{-}B\Big|\le 2K\,|A|^{1/2}|B|^{1/2}.\]
证明. 先看正向。把 \(G\) 中的配对按它们的和分类：观察到 \[\sum_{x\in A\stackrel{G}{+}B}\big|\{(a,b)\in G:a+b=x\}\big|=|G|,\] 这是因为 \(G\) 中每个配对恰好属于唯一一个和值 \(x\)。于是由 Cauchy–Schwarz 不等式， \[\sum_{x\in A\stackrel{G}{+}B}\big|\{(a,b)\in G:a+b=x\}\big|^2\ge \frac{|G|^2}{\big|A\stackrel{G}{+}B\big|}.\] 但左边正好等于 \[\big|\{(a,a',b,b')\in A\times A\times B\times B:a+b=a'+b';\ (a,b),(a',b')\in G\}\big|,\] 而这个数不超过 \(E(A,B)\)（因为带 \(G\) 限制的四元组只是 \(E(A,B)\) 所计四元组的一部分——\(E(A,B)\) 并不要求两对都落在 \(G\) 里）。这就证明了 \(E(A,B)\ge |G|^2/|A\stackrel{G}{+}B|\)；再利用对称性 \(E(A,B)=E(A,-B)\)，同样得到 \(E(A,B)\ge |G|^2/|A\stackrel{G}{-}B|\)。
现在证反向。假设 \(E(A,B)\ge |A|^{3/2}|B|^{3/2}/K\)。由引理 2.9， \[\sum_{x\in A+B}|A\cap(x-B)|^2\ge \frac{|A|^{3/2}|B|^{3/2}}{K}.\] 令 \[S:=\Big\{x\in A+B:\ |A\cap(x-B)|\ge \tfrac{|A|^{1/2}|B|^{1/2}}{2K}\Big\},\] 即“表示方式较多”的那些和值。再次用引理 2.9（\(\sum_x|A\cap(x-B)|=|A||B|\)）把 \(x\notin S\) 的贡献扣掉：那些 \(x\) 每个的 \(|A\cap(x-B)|<|A|^{1/2}|B|^{1/2}/2K\)，故它们对平方和的贡献小于 \(\tfrac{|A|^{1/2}|B|^{1/2}}{2K}\cdot|A||B|\)。于是 \[\sum_{x\in S}|A\cap(x-B)|^2\ge \frac{|A|^{3/2}|B|^{3/2}}{K}-\frac{|A||B|\,|A|^{1/2}|B|^{1/2}}{2K}=\frac{|A|^{3/2}|B|^{3/2}}{2K}.\] 又由引理 2.9 注意到 \[|S|\cdot\frac{|A|^{1/2}|B|^{1/2}}{2K}\le \sum_{x\in S}|A\cap(x-B)|\le |A||B|,\] （中间用了 \(S\) 中每项都 \(\ge \tfrac{|A|^{1/2}|B|^{1/2}}{2K}\)），从而 \[|S|\le 2K\,|A|^{1/2}|B|^{1/2}.\] 现在令 \(G:=\{(a,b)\in A\times B:a+b\in S\}\)，则显然 \(A\stackrel{G}{+}B\subseteq S\)，因此 \[\Big|A\stackrel{G}{+}B\Big|\le 2K\,|A|^{1/2}|B|^{1/2}.\] 此外， \[ |G|=\sum_{x\in S}\big|\{(a,b)\in A\times B:a+b=x\}\big| =\sum_{x\in S}|A\cap(x-B)| \ge \sum_{x\in S}\frac{|A\cap(x-B)|^2}{|A|^{1/2}|x-B|^{1/2}} \ge \frac{|A|^{3/2}|B|^{3/2}/2K}{|A|^{1/2}|B|^{1/2}}=\frac{|A||B|}{2K}. \] （这里第一个不等号用到 \(|A\cap(x-B)|\le |A|^{1/2}|x-B|^{1/2}\)，因为交集既含于 \(A\) 又含于 \(x-B\)，其大小不超过两者的几何平均；又 \(|x-B|=|B|\)。）这就给出所需的集合 \(G\)。集合 \(H\) 的构造利用对称性 \(E(A,B)=E(A,-B)\) 即可同样得到。♦
这条引理在说什么
  1. 正向（能量 ≥ 比值）：只要存在一张图 \(G\) 使部分和集很小、而 \(G\) 又很大，那么 \(E(A,B)\) 必然大——很多配对挤进很少的和值里，重复自然多。
  2. 反向（能量大 ⟹ 造出好图）：反过来，只要加性能量大，就能显式地造出一张大图 \(G\)（取那些“表示数多”的和值对应的配对），使部分和集小。这正是把“能量假设”翻译成“BSG 定理输入假设”的那一步。
  3. 把这两件事接起来，就能在“加性能量大”和“BSG 结论”之间自由往返。

等价表述

把这条引理与 BSG 定理结合，就能得到“两个集合具有大加性能量”的一个刻画。

定理 2.31（Balog–Szemerédi–Gowers 定理，等价版本） 设 \(A,B\) 是母群 \(Z\) 中的加性集合，\(K\ge 1\)。则下述各命题在相差常数的意义下等价，即：若第 \(j\) 条对某个绝对常数 \(C_j\) 成立，则第 \(k\) 条也对某个依赖于 \(C_j\) 的绝对常数 \(C_k\) 成立：
  1. \(E(A,B)\ge K^{-C_1}|A|^{3/2}|B|^{3/2}\)；
  2. 存在 \(G\subset A\times B\) 使得 \(|G|\ge K^{-C_2}|A||B|\) 且 \(\big|A\stackrel{G}{+}B\big|\le K^{C_2}|A|^{1/2}|B|^{1/2}\)；
  3. 存在 \(G\subset A\times B\) 使得 \(|G|\ge K^{-C_3}|A||B|\) 且 \(\big|A\stackrel{G}{-}B\big|\le K^{C_3}|A|^{1/2}|B|^{1/2}\)；
  4. 存在子集 \(A'\subseteq A\)、\(B'\subseteq B\)，满足 \(|A'|\ge K^{-C_4}|A|\)、\(|B'|\ge K^{-C_4}|B|\)，且 \(d(A',B')\le C_4\log K\)；
  5. 存在一个 \(K^{C_5}\)-近似群 \(H\) 以及 \(x,y\in Z\)，使得 \(|A\cap(H+x)|,\ |B\cap(H+y)|\ge K^{-C_5}|H|\)，并且 \(|A|,|B|\le K^{C_5}|H|\)。

本定理的证明留作习题。定理 2.31 应与习题 2.3.22 比较，后者是本定理 \(K=1\) 的特例。与命题 2.27 一样，本定理限于基数相近的集合 \(A,B\)（见习题）。我们将在下一节处理基数相差悬殊的集合 \(A,B\) 的问题。

五条命题，一个意思
  1. (i) 加性能量大——和值高度重复。
  2. (ii)/(iii) 存在大图使部分和集 / 部分差集小——能在大批配对上把和（或差）压进小范围。
  3. (iv) 能提纯出 Ruzsa 距离小的大子集——\(A',B'\) 在加性结构上彼此“很近”。
  4. (v) 被近似群覆盖——\(A,B\) 都有正比例落在同一个近似群 \(H\) 的平移里。
这五种说法都是同一现象“\(A,B\) 之间有很强的加性结构”在不同语言下的描述；定理保证它们在多项式损失（\(K\) 的幂次、\(\log K\)）内互相推得出来。

习题

习题 2.5.1 设 \(A,B\) 是同一母群 \(Z\) 中的加性集合，满足 \(E(A,B)\ge K^{-1}|A|^{3/2}|B|^{3/2}\)。证明 \(K^{-2}|A|\le |B|\le K^{2}|A|\)，并举例说明这些界无法改进。
习题 2.5.2 举出一个基数为 \(N\) 的加性集合 \(A\subset Z\)，以及一个基数为 \(N^2/4\) 的子集 \(G\subset A\times A\)，使得 \(\big|A\stackrel{G}{+}A\big|\le N\) 而 \(|A+A|\ge N^2/8\)。（提示：把一个 Sidon 集与一段等差数列拼接起来。）
习题 2.5.3 设 \(N\gg K\gg 1\) 为大整数，\(N\) 是 \(K\) 的倍数。举出基数 \(|A|=|B|=N\) 的集合 \(A,B\subset Z\) 以及基数 \(|G|=|A||B|/K\) 的子集 \(G\subset A\times B\)，使得 \(\big|A\stackrel{G}{+}B\big|\le 2N\)，但对任何满足 \(|A'|\ge 2|A|/K\) 的 \(A'\subset A\)、\(B'\subset B\) 都有 \(|A'+B'|\ge N^2/K^2\)。（提示：取 \(B\) 为一段长等差数列，取 \(A\) 为一段短等差数列与一些“一般位置”整数的拼接。）这表明定理 2.29 中的条件 (2.18)、(2.19) 无法本质改进。
习题 2.5.4 设 \(A,B,C\) 是母群 \(Z\) 中的加性集合，\(0<\varepsilon<1/4\)，并设 \(G\subset A\times B\)、\(H\subset B\times C\) 满足 \(|G|\ge (1-\varepsilon)|A||B|\)、\(|H|\ge (1-\varepsilon)|B||C|\)。证明存在子集 \(A'\subseteq A\)、\(C'\subseteq C\)，满足 \(|A'|\ge (1-\varepsilon^{1/2})|A|\)、\(|C'|\ge (1-\varepsilon^{1/2})|C|\)，使得 \[|A'-C'|\le \frac{\big|A\stackrel{G}{-}B\big|\,\big|B\stackrel{H}{-}C\big|}{(1-2\varepsilon^{1/2})|B|}.\] （提示：证明 \(B\) 中至多有 \(\varepsilon^{1/2}|B|\) 个元素的 \(G\)-度小于 \((1-\varepsilon^{1/2})|A|\)，同理至多有 \(\varepsilon^{1/2}|B|\) 个元素的 \(H\)-度小于 \((1-\varepsilon^{1/2})|C|\)。）当图 \(G\) 极其稠密时，这个结果可以充当 BSG 定理的替代品；它的好处是不要求 \(A,B,C\) 在大小上相当，而且证明要简单得多。

返回 全书目录