塞迈雷迪定理

定理叙述

若自然数集的子集 A 满足 （公式略）

则称 A 具有正的上密度。塞迈雷迪定理断言，若自然数集的一个子集具有正的上密度，则对任意的正整数 k, 该子集都包含无穷多个长为 k 的（公差不为 0) 的等差数列。

定理另有一个等价的有限性叙述（即不牵涉“无穷”的）：对任意的正整数 k 和实数 δ ∈ (0,1], 都存在正整数 N=N(k,δ)

使得 {1, 2,..., N} 的每个至少 δN 元的子集，都包含长为 k 的等差数列。

定义 rk(N) 为 {1, 2,..., N} 的子集当中，不包含长为 k 的等差数列的最大子集的大小。塞迈雷迪定理给出渐近上界 rₖ(N)=o(N).

换言之，rk(N) 随 N 的增长慢于线性。

历史

范德瓦尔登定理是塞迈雷迪定理的先驱，其于 1927 年获证。

塞迈雷迪定理中， k = 1 和 k = 2 的情况显然成立。 k = 3 的结论关乎萨莱姆-斯宾塞集（不包含 3 项等差数列的整数子集）的大小。1953 年，克劳斯·罗特 利用类似哈代-李特尔伍德圆法的方法，证明了 k = 3 的结论。1969 年，塞迈雷迪·安德烈利用组合学方法证明了 k = 4 的情况。在 1972 年，罗特利用类似自己证明 k = 3 的情况的方法，给出了 k = 4 的情况的另证。

塞迈雷迪于 1975 年给出了适用于所有 k 的证明。 他巧妙地扩展了自己先前对 k = 4 的情况的组合论证，埃尔德什称该证明为“组合学推理的杰作”("a masterpiece of combinatorial reasoning"). 定理亦有若干其他证明，较重要的有：1977 年希勒尔·菲尔斯滕贝格利用遍历理论给出的证明，以及 2001 年高尔斯结合傅里叶分析和组合数学给出的证明。陶哲轩称塞迈雷迪定理的众多证明为“罗塞塔石碑”，因为它们连结了几个乍看之下迥异的数学分支。

rk(N) 的具体大小

rk(N) 的确切增长速度仍然未知。目前所知的上下界为 （公式略）

其中 （公式略） 欧布莱恩（Kevin O'Bryant) 证出了上述的下界，其证明建基于贝哈连德（Felix Behrend)、罗伯特·蓝钦，以及埃尔金（Michael Elkin) 先前的成果。上界由高尔斯证出。

对于较小的 k, 可以找到比起一般情况更紧的上下界。当 k = 3 时，布尔甘、希斯-布朗、塞迈雷迪，以及汤姆·桑德斯依次给出了愈来愈好的下界。目前所知的上下界为 （公式略）

两边的界限分别由欧布莱恩 和布鲁姆（Thomas Bloom) 给出。

当 k = 4 时，本·格林和陶哲轩 证明了存在 c > 0 使得 （公式略）

推广

希勒尔·菲尔斯滕贝格和伊扎克·卡茨内勒松利用遍历理论整明了塞迈雷迪定理的高维推广。 高尔斯、沃伊杰赫·勒德尔和约泽夫·斯科肯 (Jozef Skokan)，以及布兰登·纳格 (Brendan Nagle)、 勒德尔和马蒂亚斯·沙赫特，和陶哲轩给出了各自的组合学证明。

亚历山大·莱布门 (Alexander Leibman) 和维塔利·别尔格尔松 给出定理对多项式列的推广：若 A⊂ N 的上密度为正，且 （公式略） 为满足 pᵢ(0)=0 的整值多项式，则存在无穷多组 u,n∈ Z 使得对 1≤ i≤ k 都有 u+pᵢ(n)∈ A. 莱布门和别尔格尔松的结果同样适用于高维的情况。

塞迈雷迪定理的有限性版本可推广至有限的加法群上，例如有限域上的向量空间。 定理在有限域上的类比，是有助理解原定理（在正整数集上）的模型。 所谓封顶集问题，就是要找出向量空间 F ₃ⁿ 所包含的无 3 项等差数列的最大子集的大小，即塞迈雷迪定理当 k = 3 时的界限。

格林-陶定理断言，存在任意长的素数等差数列。此结论不能由塞迈雷迪定理推出，因为素数集的密度为 0. 本·格林和陶哲轩在其证明中引入了“相对性”（英语：relative） 的塞迈雷迪定理，该定理适用于任意具特定伪随机性的整数子集（允许密度为 0)。大卫·康伦，雅各布·福克斯和赵宇飞 (Yufei Zhao)其后亦给出了适用于更一般情况的相对性塞迈雷迪定理。

埃尔德什等差数列猜想（断言倒数和发散的集合，必有任意长的等差数列）可以推出塞迈雷迪定理和格林-陶定理。

延申阅读

Tao, Terence. Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József, 编. Additive Combinatorics. CRM Proceedings & Lecture Notes 43. Providence, RI: American Mathematical Society: 145–193. 2007. Bibcode:2006math......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005. arXiv:math/0604456 .