1. 小倍增集合的结构

加性组合的一个主要任务可以粗略地描述为理解加法下集合的特征. 为了更准确地讨论这一点, 我们将从一些定义开始.

定义 1.1. 令 $A$ 和 $B$ 是阿贝尔群的有限子集. 它们的和集 (sumset) 定义为 $A+B=\{a+b\mid a\in A,b\in B\}$. 我们可以进一步定义 $A-B=\{a-b\mid a\in A,b\in B\}$ 和 $kA=\underset{k\text{ 次 }}{\underbrace{A+A+\cdots +A}}$ , 其中 $k$ 是一个正整数. 注意, 这与将 $A$ 中的每个元素乘以 $k$ 不同, 我们每个元素乘以 $k$ 记作 $k\cdot A=\{kA\mid a\in A\}$.

给定一个有限的整数集 $A$, 我们想了解在这些操作下它的大小会如何变化. 自然的, 我们有如下问题:

问题 1.2. 对于大小 $|A|$ 固定的 $A$ (其中 $A\subset \mathbb{Z}$ ) , $|A+A|$ 可以有多大或多小?

事实上, 这不是一个很难的问题. 在 $\mathbb{Z}$ 中, 给定集合的大小, 我们对和集的大小有精确的界限.

命题 1.3. 如果 $A$ 是 $\mathbb{Z}$ 的有限子集, 则$$2|A|-1\le |A+A|\le (\genfrac{}{}{0ex}{}{|A|+1}{2})$$

证明. 右边的不等号成立是因为 $A$ 中最多构成 $\left(\genfrac{}{}{0ex}{}{|A|+1}{2}\right)$ 个无序元素对.

如果 $A$ 中的元素为 $a_1<a_2<\cdots <a_{|A|}$, 那么$$a_1+a_1<a_1+a_2<\cdots <a_1+a_{|A|}<a_2+a_{|A|}<\cdots <a_{|A|}+a_{|A|}$$是一个项数为 $2|A|-1$ 的递增序列, 且每一项都包含在集合 $A+A$ 中, 所以左边的不等号成立.

$\square$

当 $A+A$ 中没有非平凡的碰撞 (collision) 时, 上界是紧的. 这里的非平凡碰撞是说, $a_1+a_2=a_1^{\prime }+a_2^{\prime }$ , $a_1,a_2,a_1^{\prime },a_2^{\prime }\in A$ 没有非平凡的解.

例 1.4. 如果 $A=\left\{1,a,a^2,\dots ,a^{n-1}\right\}\subset \mathbb{Z}$ , 其中 $a>1$. 则我们有 $|A+A|=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$.

当 $A$ 是等差数列时, 下界很紧. 当我们改为考虑任意 Abel 群时, 问题也同样简单. 在一般的 Abel 群 $G$ 中, 我们只有不等式 $|A+A|\ge |A|$. 如果 $A$ 是某个 $G$ 的有限子群的陪集, 则等号成立. 因为没有 $\mathbb{Z}$ 的非平凡有限子群, 所以在 $\mathbb{Z}$ 中我们有更好的界.

我们可以问的一个更有趣的问题, 对于大小 $|A+A|$ 很小的集合, 会发生什么? 更确切地说:

定义 1.5. 我们定义 Abel 群的有限子集 $A$ 的倍增常数 (doubling constant) 为 $|A+A|/|A|$

问题 1.6. 如果集合的倍增常数是有界的, 那么该集合的结构是怎样的 (例如 $|A+A|\le 100|A|$) ?

我们已经在 $\mathbb{Z}$ 中看到了这样一个集合的例子, 即算术级数 (等差数列) .

例 1.7. 如果 $A\subset \mathbb{Z}$ 是有限等差数列, 则 $|A+A|=2|A|-1\le 2|A|$, 所以它的倍增常数最多为 2 .

此外, 如果我们删除等差数列中的某些元素, 集合的倍增常数应该仍比较小. 事实上, 如果我们删除等差数列的大部分元素, 但保留常数比例的元素, 集合的倍增常数仍比较小.

例 1.8. 如果 $B$ 是有限算术级数且 $A\subseteq B$ 满足 $|A|\ge C|B|$, 则 $|A+A|\le |B+B|\le 2|B|\le 2C^{-1}|A|$, 所以 $A$ 的倍增常数最大为 $2/C$.

一个更实质性的概括是 $d$ 维算术级数.

定义 1.9. 维度为 $d$ 的广义算术级数 (generalized arithmetic progression, 下文简称 GAP) 是如下形式的集合$$\left\{x_0+{\ell }_1{x}_1+\cdots +{\ell }_d{x}_d\mid 0\le {\ell }_1<L_1,\dots ,0\le {\ell }_d<L_d,{\ell }_1,\dots ,{\ell }_d\in \mathbb{Z}\right\}$$其中 $x_0,x_1,\dots ,x_d\in \mathbb{Z}$ 和 $L_1,\dots ,L_d\in \mathbb{N}$.

GAP 的大小定义为 $L_1{L}_2\cdots L_d$, 如果 GAP 的某些元素具有多种表示形式, 则集合的基数可能与大小不同. 如果 GAP 的基数和大小相同, 则称为适当的.

不难看出, 维数为 $d$ 的适当 GAP 倍增常数最大为 $2^d$ (这里用到了等差数列的倍增常数最大为 2) . 此外, 删除常数部分的 GAP 元素后, 集合的倍增常数仍比较小. 我们已经列举了几个倍增常数较小的集合的例子, 一个很自然的问题是, 我们是否可以对这些集合进行准确的分类? 关于问题 1.6 有一个 “逆问题”, 是否所有倍增常数有界的集合都必须是这些示例之一?

这不是一个简单的问题. 幸运的是, 加性组合的一个核心结论给出了这个问题的肯定回答.

定理 1.10 (Freiman 1973). 如果 $A\subset \mathbb{Z}$ 是一个有限集并且 $|A+A|\le K|A|$, 则 $A$ 包含于维度最多为 $d(K)$ 且大小最大为 $f(K)|A|$ 的 GAP 中, 其中 $d(K)$ 和 $f(K)$ 是仅取决于 $K$ 的常数.

定理的结论可以进一步加强, 我们可以保证 GAP 是适当的, 但代价是增大 $d(K)$ 和 $f(K)$, 加强版本的定理如下 (您可以在 Tao 和 Vu 06 年的的著作中的定理 3.40 查阅该结论的证明) .

定理 1.11. 如果 $P$ 是维度为 $d$ 的 GAP, 则 $P$ 包含在维度至多为 $d$ 且大小最大为 $d^{{\mathrm{C}}_0{d}^3}|P|$ 的适当 GAP 中, $C_0>0$ 是某个正实数.

Freiman 定理让我们对小倍增集合 (倍增常数较小的集合, 后面我们都遵循这一简称) 结构有了一定的认识. 我们将在本章的后面看到 Freiman 定理的证明. 它的证明结合了傅立叶分析、几何数论和经典加性组合的思想.

Freiman 的原始证明很难读, 最初也没有得到应有的认可. 后来 Ruzsa 找到了一个更简单的证明 (1994) , 我们将主要按照他的思路介绍. 因此, 该定理有时被称为 Freiman-Ruzsa 定理. Freiman 定理在 Grower 对 Szemerédi 定理的新证明中起到了核心作用, 从而受到大家重视.

如果我们再次考虑示例 1.4, 我们有 $K=\frac{|A|+1}{2}=\Theta (|A|)$, 并且, 我们没有好的办法将其嵌入到一个 GAP 中. 我们记 $A$ 中的元素为 $a_1<a_2<\cdots <a_{|A|}$; 对于 $1\le i\le |A|-1$, 令 $x_0=a_1、x_i=a_{i+1}-a_1$ , $L_i=2$ . 我们可以看到它包含在维度 $|A|-1$ 且大小 $2^{|A|-1}$ 的 GAP 中. 这表明我们可以期望的最好结果是 $d(K)=O(K)$ 和 $f(K)=2^{O(K)}$, 该问题仍是开放的.

问题 1.12. 对于 $d(K)=O(K)$ 和 $f(K)=2^{O(K)}$ , 定理 1.10 是否成立?

最著名的结果要归功于 Sanders.

定理 1.13 (Sanders, 2012). 在 $d(K)=K(\log K{)}^{O(1)}$, $f(K)=e^{K(\log K{)}^{O(1)}}$ 情况下, 定理 1.10 为真.

与之前讨论 Roth 定理的方式类似, 我们将从分析问题的有限域模型开始. 在 ${\mathbb{F}}_2^n$, 如果 $|A+A|\le K|A|$, 那么 $A$ 会是什么样的? 如果 $A$ 是一个子空间, 则它的倍增常数为 1. 考虑其逆问题的一个自然的类比, 是否所有这样的 $A$ 都包含在一个不比 $A$ 大太多的子空间中?

定理 1.14 (Freiman 的定理的 ${\mathbb{F}}_n^2$ 版本). $A\subset {\mathbb{F}}_2^n$, 如果 $|A+A|\le K|A|$, 则 $A$ 包含在一个基数最大为 $f(K)|A|$ 的子空间中, 其中 $f(K)$ 是一个仅取决于 $K$ 的常数.

如果我们令 $A$ 是一个线性独立集 (即一个基) , 那么 $K=\Theta (|A|)$ , 包含 $A$ 的最小子空间的基数为 $2^{|A|}$. 因此 $f(K)$ 至少是 $K$ 的指数. 我们将在第三节中证明定理 1.14.