2. 加性组合的亮点

上面的 Schur 定理是现在被称为加性组合的领域最早的例子之一, 加性组合该术语由 Terry Tao 在 2000 年代初期提出, 用于描述关于加法的简单陈述问题和整数的乘法这一快速发展的数学方向. 加性组合中的问题和方法是深刻而深远的, 连接了许多不同的数学领域, 如图论、调和分析、遍历理论、离散几何和模型论. 本节的其余部分重点介绍了过去一个世纪加性组合学的一些重要发展.

在 1920 年代, van der Waerden 证明了以下关于整数中单色等差数列的结果.

定理 2.1 (van der Waerden 定理). 如果整数用有限多种颜色着色, 则其中一个颜色类别必须包含任意长的等差数列.

笔记 2.2. 具有任意长的等差数列与具有无限长的等差数列非常不同. 作为练习, 请证明可以只使用两种颜色为整数着色可以不会有无限长的单色等差数列.

在 1930 年代, Erdős 和 Turán 猜想一个更强的结论成立, 即密度为正的整数的任何子集都包含任意长的等差数列. 准确地说, 我们说 $A\subseteq \mathbb{Z}$ 具有正的上密度, 如果

$$\underset{N\to \infty }{\mathrm{limsup}}\frac{|A\cap \{-N,\dots ,N\}|}{2N+1}>0.$$(这个定义有几种变体——确切的表述并不重要. )

在 1950 年代, Roth 使用 Fourier 分析方法证明了 3 项算术级数的猜想. 在 1970 年代, Szemerédi 使用组合技术完全解决了这个猜想. 这些是该领域的里程碑式定理. 我们将讨论的大部分内容都是由这些结果及与其相关的发展所推动的.

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

定理 2.4 (Szemerédi 定理). 整数每个具有正上密度的的子集都包含任意长的等差数列.

Szemerédi 的定理是深刻而复杂的. 这项重要的工作导致了加性组合学的许多后续发展. 此后, 人们发现了 Szemerédi 定理的几种不同证明, 其中一些已经发展成为数学研究的丰富领域. 以下是 Szemerédi 定理的一些最具影响力的现代证明 (按历史顺序) :

•	遍历理论方法 (Furstenberg 1977)
•	高阶傅立叶分析 (Gowers 2001)
•	超图正则性引理 (Rödl et al. 2005/Gowers 2007)

Szemerédi 定理的另一个现代证明来自密度 Hales-Jewett 定理, 该定理最初由 Furstenberg 和 Katznelson 使用遍历理论证明 (1991) , 随后在第一个成功的 Polymath 项目中发现了新的组合证明 (2012) . Polymath 项目是由 Gowers 发起的在线协作项目. 这些不同方法之间的关系尚未完全理解, 并且存在许多未解决的问题, 尤其是定量的具体上下界. Szemerédi 定理的所有已知方法背后, 都有一个统一主题, 那就是结构和伪随机性之间的二分法 (译者注: 即 Structure vs Randomness, 也就是为了证明我们的结论, 将某个数学对象分为两种情况. 一种情况下它有特殊的结构, 可以用结构的性质来证明我们的结论; 另一种情况下, 它和随机的情形相似, 可以用伪随机性来证明我们想要的结论. 从而结合起来, 即可证明我们的结论在任意情况下成立. ). 以后会看到在图论和数论的不同背景下, 这种二分法的具体内容.

以下是 Szemerédi 定理的其他一些重要后续发展.

我们不考虑整数的子集, 而是考虑更高维点阵 ${\mathbb{Z}}^d$ 的子集. 我们说 $A\subset {\mathbb{Z}}^d$ 具有正的上密度, 如果$$\underset{N\to \infty }{\mathrm{limsup}}\frac{\left|A\cap [-N,N{]}^d\right|}{(2N+1{)}^d}>0$$(和之前一样, 其他类似的定义也可以, 具体是哪个定义并不重要) . 如果对于每个有限集 $F\subset {\mathbb{Z}}^d$, 存在 $a\in {\mathbb{Z}}^d$ 和 $t\in {\mathbb{Z}}_{>0}$ , 使得 $a+t\cdot F=\{a+tx:x\in F\}$ 包含在 $A$ 中, 则我们称 $A$ 包含任意 “星座”, 换句话说, $A$ 包含每个有限模式 (也就是 “星座”) , 每个模式都由允许扩张和平移的整数网格的某个有限子集组成. Furstenberg 和 Katznelson 最初使用遍历理论证明了 Szemerédi 定理的以下多维推广 (1978) , 尽管后来由前面提到的超图正则性方法可以得到一个组合证明.

定理 2.5 (多维 Szemerédi 定理). ${\mathbb{Z}}^d$ 正上密度的每个子集都包含任意星座.

例如, 该定理意味着 ${\mathbb{Z}}^d$ 的每个正上密度的子集都包含 $10\times 10$ 的一组点, 这些点形成了一个轴对齐的方形网格. Szemerédi 定理还有一个多项式扩展. 让我们首先陈述一个它的特例. 这个特例最初由 Lovász 猜想并由 Furstenberg (1977) 和 Sárkốzy (1978) 独立证明.

定理 2.6. 具有正上密度的整数的任何子集都包含差是完全平方数的两个数.

换句话说, 对于某 $x\in \mathbb{Z}$ 和 $y\in {\mathbb{Z}}_{>0}$, 该集合总是包含 $\left\{x,x+y^2\right\}$. 其他多项式形式呢? Bergelson 和 Leibman 证明了以下多项式推广 (1996) .

定理 2.7 (多项式 Szemerédi 定理). 假设 $A\subset \mathbb{Z}$ 具有正的上密度. 如果 $P_1,\dots ,P_k\in \mathbb{Z}[X]$ 是多项式, 其中 $P_1(0)=\cdots =P_k(0)=0$ , 则存在 $x\in \mathbb{Z}$ 和 $y\in {\mathbb{Z}}_{>0}$ 使得 $x+P_1(y),\dots ,x+P_k(y)\in A$.

我们把表述两个定理的共同扩展留作练习 (即多维多项式 Szemerédi 定理) , 这个定理也被 Bergelson 和 Leibman 证明过了.

我们不会介绍定理 2.5 和 2.7 的证明. 事实上, 目前唯一已知的多项式 Szemerédi 定理的一般证明需要使用遍历论. 尽管如此, 最近在特殊情形下有一些令人兴奋的发展.

基于 Szemerédi 定理以及数论的其他重要发展, Green 和 Tao 证明了他们著名的定理 (2008) , 该定理解决了关于素数口耳相传的古老猜想. 他们的定理被认为是本世纪最著名的数学成果之一.

定理 2.8 (Green-Tao 定理). 全体素数包含任意长度的等差数列.

我们将讨论 Green-Tao 定理证明背后的许多核心思想. 请参阅参考资料 (Conlon, Fox, and Zhao 2014) , 来了解 Green-Tao 定理从图论观点的现代阐述, 以及自原始工作以来发现的一些证明上的简化.