塞迈雷迪定理

在算术组合学（英语：arithmetic combinatorics）中，塞迈雷迪定理是个关于自然数集子集中的等差数列的结论。1936年，艾狄胥和图兰·帕尔（英语：Pál Turán）猜想：若整数集 具有正的自然密度，则对任意的正整数 都可以在 中找出一个 项的等差数列。塞迈雷迪·安德烈于 1975 年证明了此结论。

若自然数集的子集 满足

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

定理另有一个等价的有限性叙述（即不牵涉“无穷”的）：对任意的正整数 和实数 ${\displaystyle \mathrm{\delta <!--\; \delta \; -->}\in <!--\; \in \; -->(0,1],}$} 的每个至少 元的子集，都包含长为 的等差数列。

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

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

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

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

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

() 的确切增长速度仍然未知。目前所知的上下界为

其中 ${\displaystyle n=\lceil <!--\; \lceil \; -->\log <!--\; \; -->k\rceil <!--\; \rceil \; -->.}$ 可以找到比起一般情况更紧的上下界。当 = 3 时，布尔甘、希思-布朗 (Roger Heath-Brown)、塞迈雷迪，以及汤·桑德斯（英语：Tom Sanders (mathematician)）依次给出了愈来愈好的下界。目前所知的上下界为

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

当 = 4 时，本·格林（英语：Ben Green (mathematician)）和陶哲轩 证明了存在 > 0 使得

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

亚历山大·莱布门 (Alexander Leibman) 和维塔利·别尔格尔松（英语：Vitaly Bergelson） 给出定理对多项式列的推广：若 ${\displaystyle A\subset <!--\; \subset \; -->\mathbb{N}}$的上密度为正，且 ${\displaystyle p_1(n),p_2(n),\dots <!--\; \dots \; -->,p_k(n)}$为满足 ${\displaystyle p_i(0)=0}$的整值多项式（英语：Integer-valued polynomial），则存在无穷多组 ${\displaystyle u,n\in <!--\; \in \; -->\mathbb{Z}}$使得对${\displaystyle 1\le <!--\; \le \; -->i\le <!--\; \le \; -->k}$都有 ${\displaystyle u+p_i(n)\in <!--\; \in \; -->A.}$ 莱布门和别尔格尔松的结果同样适用于高维的情况。

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

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

埃尔德什等差数列猜想可以推出塞迈雷迪定理和格林-陶定理。