8. Freiman 定理的证明

到目前为止, 在本章中, 我们已经在加性组合中展示了许多用来证明 Freiman 定理 (定理 1.0.10) 的方法和定理. 现在, 我们把这些工具放在一起, 形成一个完整的证明.

证明方法如下. 从小倍增集合 $A$ 开始, 我们首先使用 Ruzsa 建模引理 (定理 5.0.2) . 然后, 我们使用 Bogolyubov 的引理 (定理 6.0.3) 和几何数论的结论, 在 $2B-2B$ 内找到一个大 GAP. 这给了我们一个 $2A-2A$ 中的大 GAP. 最后, 我们应用 Ruzsa 覆盖引理 (定理 3.0.1 ) , 从包含在 $2A-2A$ 中的这个 GAP 上创建一个包含 $A$ 的 GAP. 回忆 Freiman 定理 (定理 1.0.10) 的陈述:

如果 $A\subset \mathbb{Z}$ 是有限集并且 $|A+A|\le K|A|$, 则 $A$ 包含在维数最多为 $d(K)$ 且大小最多为 $f(K)|A|$ 的 GAP 中.

证明. 因为 $|A+A|\le K|A|$, 由 Ruzsa 建模引理的推论 (推论 5.0.4) , 存在一个素数 $N\le 2K^{16}|A|$ 和 $A^{\prime }\subset A$ 且 $\left|A^{\prime }\right|\ge |A|/8$, 使得 $A^{\prime }$ 是 Freiman 8 -同构于 $\mathbb{Z}/\mathrm{NZ}$ 的子集 $B$. 在 $B$ 上应用 Bogolyubov 引理 (定理 6.0.3) $$\alpha =\frac{|B|}{N}=\frac{\left|A^{\prime }\right|}{N}\ge \frac{|A|}{8N}\ge \frac{1}{16K^{16}}$$所以 $2B-2B$ 包含玻尔集 $\mathrm{Bohr}(R,1/4)$, 其中 $|R|<$ $256K^{32}$. 因此, 根据定理 7.0.9, $2B-2B$ 包含一个适当 GAP, 其维度 $d<256K^{32}$, 大小至少为 $(4d{)}^{-d}N$.

由于 $B$ 是到 $A^{\prime }$ 的 Freiman $8-$ 同构, 所以 $2B-2B$ 是到 $2A^{\prime }-2A^{\prime }$ 的 Freiman $2-$ 同构. 这是从 Freiman $s-$ 同构的定义得到的. 注意到 $2B-2B$ 中的每个元素都是 $B$ 中四个元素的和和差 ( $2A^{\prime }-2A^{\prime }$ 也是如此) . 因为 $2B-2B$ 中的任何两个元素之间的差被保留, 所以算术级数被 Freiman $2-$ 同构保留. 因此, $2B-2B$ 中的适当 GAP 被映射到具有相同维度和大小的 $2A^{\prime }-2A^{\prime }$ 中的适当 GAP $Q$.

接下来我们将使用 Ruzsa 覆盖引理来覆盖整个集合 $A$ 并将其转换为 $Q$. 因为 $Q\subset 2A-2A$, 我们有 $Q+A\subset$ $3A-2A$ . 根据 Plünnecke-Ruzsa 不等式 (定理 2.0.4) , 我们有$$|Q+A|\le |3A-2A|\le K^5|A|$$

因为 $A^{\prime }\subset \mathbb{Z}/N\mathbb{Z}$, 我们有 $N\ge \left|A^{\prime }\right|\ge |A|/8$. 因为 $|Q|\ge (4d{)}^{-d}N$ , 所以我们有 $K^5|A|\le K^{\prime }|Q|$ , 其中 $K^{\prime }=8(4d{)}^d{K}^5=e^{K^{O(1)}}$. 所以上述不等式变为 $|Q+A|\le K^{\prime }|Q|$. 因此, 根据 Ruzsa 覆盖引理 (定理 5.0.2) , 存在 $A$ 的子集 $X$ 与 $|X|\le K^{\prime }$ 满足 $A\subset X+Q-Q$.

剩下的事情就是证明 $X+Q-Q$ 包含在具有所需的 GAP 中. 注意, $X$ 包含在维度为 $|X|$ 的 GAP 中, 并且 $Q-Q$ 的维数是 $d$. 所以 $X+Q-Q$ 包含在具有如下维度的 GAP $P$ 中$$\dim (P)\le |X|+d\le K^{\prime }+d=8(4d{)}^d{K}^5+d=e^{K^{O(1)}}$$因为 $Q$ 是维度 $d$ 的适当 GAP 并且等差数列的倍增常数是 2 , 所以 $Q-Q$ 的大小至多为 $2^d|Q|$. 包含 $X$ 的 GAP 大小为 $2^{|X|}$. 因此, 应用 Plünnecke-Ruzsa 不等式, $P$ 的大小$$\mathrm{size}(P)\le 2^{|X|}{2}^d|Q|\le 2^{K^{\prime }+d}|2A-2A|\le 2^{K^{\prime }+d}{K}^4|A|=e^{e^{K^{O(1)}}}|A|$$取 $d(K)=e^{K^{O(1)}}$ , $f(K)=e^{e^{K^{O(1)}}}$, 我们完成了 Freiman 定理的证明.

$\square$

考虑 $A=\left\{1,10,10^2,10^3,\dots ,10^{|A|-1}\right\}$ 我们看到 Freiman 定理对于 $d(K)<\Theta (K)$ , $f(K)<2^{\Theta (K)}$ 是错误的. 我们还可以推测 Freiman 的成立的条件为 $d(K)=\Theta (K)$ 和 $f(K)=2^{\Theta (K)}$.

虽然上述 Freiman 定理证明中给出的上界与此相差甚远, 但 Chang 已经证明 Ruzsa 的方法可以给出多项式上界 ($(d(K)=K^{O(1)}$ 和 $f(K)=\exp (K^{O(1)})$, 2002) . 当我们应用 Ruzsa 的覆盖引理时是点浪费的. 我们只对 $A$ 使用了一次覆盖, 一个更好的方法是一点一点地覆盖 $A$. 对其简单叙述如下:

从 $Q$ 开始, 我们用 $Q-Q$ 覆盖部分 $A$. 然后重复下面操作: 对剩余的 $A$ 找到较小维度的 $Q_1$, 用 $Q_1-Q_1$ 覆盖 $A$ 的其余部分. 这种方法显着减少了我们在这一步中损失, 并给出了更好的多项式上界.

如前所述, 最知名的上界 (定理 1.0.13) 为 $d(K)=K(\log K{)}^{O(1)}$ 和 $f(K)=e^{K(\log K{)}^{O(1)}}$, 其证明涉及更多内容.