3. Roth 定理

定理 3.1 (Roth 定理). 每个具有正上密度的整数的子集都包含一个长度为 3 的等差数列.

证明.

取没有长度为 3 的等差数列的 $[N]$ 的子集 $A$. 我们将证明 $A$ 有 $o(N)$ 个元素, 从而证明了定理. 为了简化证明并且避免处理 $A$ 中涉及大元素的边缘情况, 我们将 $A$ 嵌入到一个循环群中. 取 $M=2N+1$ , 我们有 $A\subseteq \mathbb{Z}/M\mathbb{Z}$. 由于我们选取的 $M$ 足够大, 满足 $A$ 中任意两个元素的总和小于 $M$, 因此不会发生回绕, 并且 $A$ 没有长度为 3 的等差数列在 $\mathbb{Z}/M\mathbb{Z}$ 中.

现在, 我们构造一个三部图 $G$, 其中的部分 $X,Y,Z$ 都是 $\mathbb{Z}/M\mathbb{Z}$ 的拷贝. 如果 $y-x\in A$, 则将顶点 $x\in X$ 连接到顶点 $y\in Y$. 类似地, 如果 $z-y\in A$, 则将 $z\in Z$ 与 $y\in Y$ 连接起来. 最后, 如果 $(z-x)/2\in A$, 则连接 $x\in X$ 和 $z\in Z$. 因为我们选择的 $M$ 为奇数, 所以 2 是模 $M$ 可逆的, 最后一步是合理的.

如果 $x,y,z$ 构成一个三角形, 那么元素$$y-x,\frac{z-x}{2},z-y$$都属于 $A$. 这些数字按所列顺序形成等差数列. 然后, 对 $A$ 的假设告诉我们上面列出的元素都是相等的. 这个条件等价于说 $x,y,z$ 是 $\mathbb{Z}/M\mathbb{Z}$ 中的等差数列.

因此, $G$ 的每条边都恰好位于一个三角形中. 这是因为给定一条边 (即 $\mathbb{Z}/M\mathbb{Z}$ 的两个元素) , 存在一种方法可以将该边扩展为唯一的三角形 (以正确的顺序添加该组的另一个元素以形成等差数列) .

那么推论 2.0.7 意味着 $G$ 有 $o\left(M^2\right)$ 条边. 但是通过构造 $G$ 正好有 $3M|A|$ 条边. 由于 $M=2N+1$, 因此 $|A|$ 是 $o(N)$ 的.

$\square$

(...)Roth 定理定理证明的图构造

在本书的后面, 我们讨论了 Roth 定理的傅里叶分析证明, 尽管它使用了不同的方法, 但和上述证明具有相似的思路.

如果我们注意三角形删除引理所隐含的上界, 我们在这里的证明会得到 $|A|$ 的上界 $N/{\left({\log }^{\ast }N\right)}^c$ , 其中 ${\log }^{\ast }N$ 表示必须对 $N$ 取对数多次直到值小于 1 , 而 $c$ 是某个常数. 这是我们之前看到的 2 的迭代次幂的反函数. 目前为止 $A$ 的最佳上界为: 如果 $A$ 没有长度为 3 的等差数列, 则$$|A|\le \frac{N}{(\log N{)}^{1-o(1)}}$$

在下一节中, 我们将证明任何没有长度为 3 的等差数列的 $[N]$ 子集大小的下界. 事实证明, 存在大小为 $N^{1-o(1)}$ 的 $A\subseteq [N]$ 不包含长度为 3 的等差数列. 实际上, 我们将提供一个示例, 其中对于某些常量 $C$ , $|A|\ge N{e}^{-C\sqrt{\log N}}$ .

笔记 3.2. 除了推论 2.0.7 中给出的结果之外, 对问题 3.0.3 的答案我们知之甚少. 在 Roth 定理的证明中, 我们知道, 给定 $[N]$ 的任何没有 3 项等差数列的子集 $A$, 我们可以在 $O(N)$ 顶点上构造一个图, 该图具有 $N|A|$ 数量级的边, 并且它的每条边都包含在一个唯一的三角形中. 这或多或少是构造相对稠密图的唯一已知方法, 其特性是每条边都包含在一个唯一的三角形中.