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

2.2　倍增常数Doubling constants

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

本节目标给一个集合 \(A\) 配一个数字，用来度量它内部有多少“加法结构”。这个数字叫倍增常数 \(\sigma[A]\)：先把 \(A\) 自己跟自己相加得到和集 \(A+A\)，再看它比 \(A\) 大了多少倍。倍增常数越接近 \(1\)，集合就越像一个“群”（加起来几乎不变大）；越大，则 \(A\) 内部的加法关系越“杂乱无章”。本节给出定义、它的取值范围、两个端点（群 与 Sidon 集）的含义。

度量一个加性集合 \(A\) 内部加法结构的传统方式，是借助倍增常数（doubling constant）\(\sigma[A]\)，我们现在就来定义它。我们很快还会发展出另外两种度量加法结构的工具，即加性能量（additive energy）\(E(A,A)\)，以及 \(K\)-近似群（\(K\)-approximate group）的概念，它们也很有用，并且与倍增常数密切相关。

定义 2.4（倍增常数）对一个加性集合 \(A\)，其倍增常数 \(\sigma[A]\) 定义为 \[\sigma[A]:=\frac{|2A|}{|A|}=\frac{|A+A|}{|A|}.\] 类似地，定义差常数（difference constant）\(\delta[A]\) 为 \[\delta[A]:=\frac{|A-A|}{|A|}.\]
先把记号讲清楚

\(A+A=\{a+a':a,a'\in A\}\) 是把 \(A\) 中任意两个元素（可以相同）相加得到的全部不同结果组成的集合，记号 \(2A\) 与 \(A+A\) 同义（注意不是把每个元素乘以 \(2\)）。\(A-A=\{a-a':a,a'\in A\}\) 是所有两两之差。\(|X|\) 表示有限集合 \(X\) 的元素个数。

取 \(A=\{1,2,4\}\)。逐对相加：

  1. \(1+1=2,\;1+2=3,\;1+4=5,\;2+2=4,\;2+4=6,\;4+4=8\)。
  2. 收集这些结果（去重）：\(A+A=\{2,3,4,5,6,8\}\)，共 \(6\) 个，故 \(|A+A|=6\)，\(|A|=3\)。
  3. 于是 \(\sigma[A]=\dfrac{|A+A|}{|A|}=\dfrac{6}{3}=2\)。倍增常数 \(2\)，意思是“自加一次后，元素个数变成原来的 \(2\) 倍”。
A = {1, 2, 4} 1 2 4 A + A = {2, 3, 4, 5, 6, 8} 2 3 4 5 6 8 3 个元素 → 自加后 6 个元素 σ[A] = 6 / 3 = 2
倍增常数就是“和集大小”除以“原集大小”。差常数把 \(A+A\) 换成 \(A-A\) 同样地算。

由 (2.2)，我们于是得到如下界： \[1\le \sigma[A]\le \frac{|A|+1}{2}\qquad\text{且}\qquad 1\le \delta[A]\le \frac{|A|-1}{2}+\frac{1}{|A|}.\] 这里的上界相当容易达到；例如若 \(A=2^{\wedge}[0,N)=\{1,2,2^2,\dots,2^{N-1}\}\subset\mathbb{Z}\)，则 \(|A|=N\)，\(|A+A|=\dfrac{N(N+1)}{2}\)，且 \(|A-A|=\dfrac{N(N-1)}{2}+1\)，因此 \(\sigma[A]=\dfrac{N+1}{2}\) 且 \(\delta[A]=\dfrac{N-1}{2}+\dfrac{1}{N}\)。在相反方向，命题 2.2 表明 \(\sigma[A]=1\)（或 \(\delta[A]=1\)）当且仅当 \(A\) 是某个群的陪集；我们将在下面的命题 2.7 中对此详加阐述。

这两个界从哪来（动机）

下界 \(\sigma[A]\ge 1\)：固定 \(A\) 中某个元素 \(a_0\)。把 \(A\) 整体平移 \(a_0+A=\{a_0+a:a\in A\}\) 是 \(A+A\) 的一个子集，而平移不改变个数，所以 \(|A+A|\ge|a_0+A|=|A|\)。两边除以 \(|A|\) 得 \(\sigma[A]\ge1\)。差常数同理（取 \(a_0-A\subseteq A-A\)）。

上界 \(\sigma[A]\le(|A|+1)/2\)：和 \(a+a'\) 只依赖于无序对 \(\{a,a'\}\)（因为 \(a+a'=a'+a\)）。把 \(|A|\) 个元素任取两个（可相同）组成无序对，最多有 \(\binom{|A|}{2}+|A|=\dfrac{|A|(|A|+1)}{2}\) 个，所以 \(|A+A|\le\dfrac{|A|(|A|+1)}{2}\)，除以 \(|A|\) 即得上界。差常数的上界来自类似的对差的计数（在本书所采用的计数下给出 \(\dfrac{|A|-1}{2}+\dfrac{1}{|A|}\)）。

例：把上界达到的“最散”集合 \(A=\{1,2,4,8\}\)（\(N=4\)）
  1. \(|A|=N=4\)。
  2. 所有无序对的和 \(2^i+2^j\)（\(i\le j\)）在二进制下互不相同，故全部 \(\binom{4}{2}+4=10=\dfrac{4\cdot5}{2}\) 个和都不重复，\(|A+A|=\dfrac{N(N+1)}{2}=10\)。
  3. 于是 \(\sigma[A]=\dfrac{10}{4}=\dfrac{N+1}{2}=\dfrac{5}{2}\)，正好顶到上界。
  4. 按书中所给的差的计数，\(|A-A|=\dfrac{N(N-1)}{2}+1=\dfrac{4\cdot3}{2}+1=7\)，\(\delta[A]=\dfrac{N-1}{2}+\dfrac{1}{N}=\dfrac{3}{2}+\dfrac14=\dfrac74\)。

对照前面 \(A=\{1,2,4\}\)（\(N=3\)）：\(\sigma[A]=\dfrac{N+1}{2}=2\)，与我们逐对相加数出的 \(2\) 完全一致——这类“每个和都各不相同”的集合就是把倍增常数顶满的集合。

一个倍增常数取最大值 \(\sigma[A]=(|A|+1)/2\)（等价地，差常数取最大值 \(\delta[A]=\dfrac{|A|-1}{2}+\dfrac{1}{|A|}\)）的加性集合 \(A\)，被称为 Sidon 集（Sidon set）或 \(B_2\) 集（\(B_2\) set）。非正式地说，这意味着 \(A\) 的所有两两之和都互不相同，仅排除来自恒等式 \(a+b=b+a\) 的平凡相等；见习题 2.2.1。我们将在 4.5 节重新讨论 Sidon 集。

两个端点各代表什么（最重要的直觉）
σ = 1 群（陪集） σ = (|A|+1)/2 Sidon 集（最散） 小倍增 ≈ “近似群” （本书核心区域）
倍增常数 \(\sigma[A]\) 落在 \([1,\,(|A|+1)/2]\)。左端是群，右端是 Sidon 集；左端附近的“近似群”是全书研究的重点。

在多种意义下，这种（Sidon 集的）行为是“典型的”（generic）；例如，若 \(A\) 是从单位区间 \(\{x\in\mathbb{R}:0\le x\le1\}\) 中均匀随机选取的 \(N\) 个实数构成的集合，则由习题 2.1.1 可知 \(A\) 以概率 \(1\) 是 Sidon 集，从而 \(|A+A|=\dfrac{N(N+1)}{2}\)；其要点在于：若 \(\{a,b\}\neq\{c,d\}\)，则 \(a+b\) 与 \(c+d\) “一般地”会互不相同。一个更有趣的问题是：去理解在什么条件下倍增常数 \(\sigma[A]\)（或差常数 \(\delta[A]\)）会很小。

为什么随机取点几乎一定是 Sidon 集

“\(a+b=c+d\) 且 \(\{a,b\}\neq\{c,d\}\)” 是一个等式约束。在连续随机取点时，让四个随机实数恰好满足一条精确的线性等式，是一个“测度为零”的事件（概率 \(0\)）。把有限多组这样的四元组的概率加起来仍是 \(0\)，所以“出现任何一次非平凡的相等”概率为 \(0\)，即以概率 \(1\) 全部两两之和互异——这正是 Sidon 集的定义。

如前所述，\(\sigma[A]=1\) 当且仅当 \(A\) 是 \(Z\) 的某个有限子群 \(G\) 的陪集。因此我们预期：若 \(A\) 的倍增常数很小，但又不恰好等于 \(1\)，那么它应当（在平移意义下）“近似地”表现得像一个群；当我们发展出更多分析倍增常数的工具时，将在全书各处看到这一启发式想法的多种体现。事实上，对小倍增常数集合的研究可以被视为一种“近似群论”（approximate group theory），而第 5 章的逆和集定理（inverse sum set theorems）则相当于群的一条分类定理。

对接近最大倍增的集合的研究，目前看来似乎是无望的。Ruzsa [291] 的一个概率构造表明：存在一些大的加性集合 \(A\)，其 \(|A-A|\) 非常接近最大值 \(|A|^2\)，但 \(|A+A|<|A|^{2-c}\)（其中 \(c>0\) 是某个明确的绝对常数）；并且把 \(A-A\) 与 \(A+A\) 的角色互换后也成立。

小结：这一节给了我们什么

习题

习题 2.2.1 设 \(A\) 是加性集合。证明：\(A\) 是 Sidon 集，当且仅当对任意 \(a,b,c,d\in A\)，只要 \(\{a,b\}\neq\{c,d\}\) 就有 \(a+b\neq c+d\)（即除非 \(\{a,b\}=\{c,d\}\)，否则 \(a+b=c+d\) 不成立）。
习题 2.2.2 设 \(Z\) 为加性群，\(a,r\in Z\)，\(N\ge1\) 为整数。设 \(P=\{a,a+r,\dots,a+(N-1)r\}\) 是 \(Z\) 中的一个等差数列。证明 \(\sigma[P]\le 2-\dfrac{1}{N}\)，且等号成立当且仅当 \(\operatorname{ord}(r)\ge 2N-1\)，其中 \(\operatorname{ord}(r)\) 是群元素 \(r\) 在 \(Z\) 中的阶。
习题 2.2.2 的直觉

等差数列是“倍增常数小”的典型例子：把 \(\{a,a+r,\dots,a+(N-1)r\}\) 自加，得到的和集仍落在一个更长的等差数列里，元素个数最多翻不到一倍。当公差 \(r\) 的阶足够大（不发生“绕回来”的重叠）时，\(P+P=\{2a,2a+r,\dots,2a+(2N-2)r\}\) 恰有 \(2N-1\) 个元素，于是 \(\sigma[P]=\dfrac{2N-1}{N}=2-\dfrac1N\)，正好达到上界。这是后面定义“广义算术级数”作为近似群模型的根源。

习题 2.2.3 若 \(\varphi:Z'\to Z\) 是一个满的群同态，其核 \(\ker(\varphi):=\varphi^{-1}(\{0\})\) 有限，且 \(A\) 是 \(Z\) 中的加性集合，证明 \(\sigma[\varphi^{-1}(A)]=\sigma[A]\)。
习题 2.2.4 若 \(A,A'\) 分别是 \(Z,Z'\) 中的加性集合，证明 \(\sigma[A\times A']=\sigma[A]\,\sigma[A']\)。特别地，对所有 \(d\ge1\) 有 \(\sigma[A^{\oplus d}]=\sigma[A]^{d}\)。
习题 2.2.5 设 \(A\) 为任意加性集合。证明：\(A\) 的一个非空子集的倍增常数至多为 \(\sqrt{\sigma[A]\,|A|}\,/\,2\)。举例说明：除了相差一个绝对常数因子之外，此界不能再改进。对差常数，相应的命题是什么？
习题 2.2.6 [100] 设 \(A\) 为任意加性集合。证明：\(A\) 中所含的 Sidon 集的基数至多为 \(\sqrt{2\,\sigma[A]\,|A|}\)。（于是，小倍增的集合只能包含较小的 Sidon 集。）

返回 全书目录