1936年，保罗·埃尔德什与保罗·图兰一起在发表了一篇论文，引发了对于避免算术（等差）级数（avoiding arithmetic progressions）的整数集合的研究。

避免算术级数是指一组数字中不包含任何长度大于等于3的等差数列。例如，下面这组数字：2，4，6，8，10是一个避免算术级数的数列，因为其中不存在任何长度大于等于3的等差数列。但是，下面这组数字：1, 3, 5, 7, 9不是一个避免算术级数的数列，因为其中包含了一个长度为3的等差数列：1, 3, 5。

保罗·埃尔德什提出了一个关于算术级数的猜想：对于任意给定的正整数 k，存在一个正整数 N，使得任何大于等于 N 的正整数集合中，总存在一个大小为k的等差级数。例如，对于 k=3，存在一个正整数N，使得任何大于等于N的正整数集合中，总存在一个大小为3的等差级数，例如{5, 8, 11}。这个猜想被称为“埃尔德什等差级数猜想”（Erdős arithmetic progression conjecture），是离散数学中的一个重要问题。

通常来说，数字列表越密集，包含等差数列的可能性就越大。因此，埃尔德什提出了一种简单的密度测试方法：只需将数字列表上的数字的倒数相加即可。如果相加的结果为无穷大，那么埃尔德什猜测认为这个数字列表应该包含每一种有限长度的等差数列。

2020年7月，剑桥大学的托马斯·布卢姆和西斯克发表了一篇论文，证明了关于等差三元组的猜想（k=3）。他们证明，每当数字列表的倒数之和是无穷大时，它必须包含无限数量的等差三元组。

今年2月，伊利诺伊大学香槟分校的一名研究生凯利（Zander Kelley）和加州大学洛杉矶分校的麦卡（Raghu Meka）一起写了一篇论文，声称发现了一组整数集合大小的新下限，其中任意3个整数都不能组成等差数列。这打破了之前布鲁姆在2020年创造的记录。西斯克称这是该领域20年来最大的成果。

进展

埃尔德什和图兰想知道在某个上限N内能够放入多少个数字来组成一个不包含任何三项等差数列的集合。N可以是1,000、1百万或者一些无法想象的巨大数字。他们猜想随着N的增大，不含三项等差数列的集合必须变得极度稀疏。创建这样的集合就像收集鞋子，要求避免存在两双鞋颜色相同的情况。也许你可以不断地收集下去，但是随着收集的规模越来越大，你会发现添加鞋子的速度越来越慢。

1946年，菲利克斯·贝伦德发现了一种方法，可以在不产生任何三项级数的情况下构造1到N之间的数集。他的方法得到的集合随着N的增大而增大，但速度很慢。当N为100,000时，贝伦德的集合只包含171个元素。当N是100万时，他的集合有586个数字。

贝伦德的集合为数学家提供了一个基础：不含三项等差数列的最大集合至少要和贝伦德的集合一样大。1953年，克劳斯·罗斯提出了一个上限，他发现了一个阈值，超过了这个阈值，一个集合就不可避免地包含了一个三项等差数列。

罗斯证明了埃尔德什和图兰的猜想，证明了N越大，一个没有“三项等差数列”的集合在1到N之间的数字比例就越小。但是罗斯的上限和贝伦德的下限相距甚远。贝伦德已经证明，在100万到100万之间的元素中，有0.06%可以放入避免等差数列的集合中。虽然罗斯的公式很难精确计算，但它远远高于这个数字，大约在40%左右。

但更重要的是这两个公式的整体行为。画出每个公式所代表的1到N之间元素的比例，你会看到贝伦德的数随着N的增长迅速缩小到零。另一方面，罗斯的比例缓慢而温和地滑向零。这两条曲线的形状非常不同，就数学家所知，在一个避免等差级数的集合中，元素的真实比例可能位于它们之间的任何地方。

克劳斯·罗斯

从20世纪80年代开始，每隔一段时间，就会有人把罗斯的上限降低一些，最终它会大幅降低。相比之下，贝伦德的下限在几十年里都没有改变。

直到麦卡和凯利在 2023 年初发表论文之前，避免算术级数集合的下限由贝伦德的公式给出，上限则由布卢姆和西斯克的公式给出。布卢姆和西斯克在2020年7月的论文已经跨越了关键的“对数”阈值，证明避免算术级数集合必须具有远少于N/(log N)个元素。但是他们的结果仍远高于贝伦德的下限。凯利和麦卡的新上限与贝伦德设定的下限非常接近。

麦卡和凯利在某种程度上超越了所有这些渐进式的进步——陶哲轩

他们的公式和贝伦德的几乎一样，只是稍微调整了几个参数。当N趋于无穷大时，凯利和麦卡公式的曲线将最终形成一条类似贝伦德的曲线。

不同的策略

尽管麦卡和凯利之前从未完全涉足纯数学研究领域，但当他们开始研究等差数列时，这个问题对他们来说并不陌生。过去用于研究避免等差数列集合大小的工具，现在已经广泛应用于复杂性理论的计算机科学子领域。

凯利和麦卡

2021年底，凯利和麦卡在分析一组玩家在某种合作游戏中获胜的几率，这是一种标准的计算机科学问题。他们突然想到，关于避免等差级数集合大小的研究技术可能会有所帮助。

为了了解它们是如何达到新的上限的，取1到N之间的任意一组数字，称之为A。A的密度是它所包含的1到N之间的数字的百分比。因为在1到N之间有很多可能的等差级数，如果不仔细选择A的元素，任何密度高的A都可能包含很多等差级数。

在他们的证明中，麦卡和凯利假设A只有很少或没有等差级数。如果A的密度足够大，他们表明，如果A中没有等差数列，就意味着A内部必须有某种结构，这将不可避免地导致矛盾，也就是说，A必须至少包含一个等差数列。

为了理解这种结构，他们考虑了集合A + A，这个集合由A的两个元素相加得到的所有数字组成。他们注意到，如果A包含相对较少的等差级数，这意味着A + A的元素之间存在冗余：来自A的不同“数字对”加起来是相同的数字。

密度不仅可以与在1到N之间的所有整数相比定义，还可以与某个子集相比进行定义，比如该区间内仅为偶数或3的倍数等。麦卡和凯利利用A+A中的冗余来找到整数的子集，在该子集中A的元素特别常见。

例如，如果A中含有不成比例的3倍数，麦卡和凯利就会专注于包含3倍数的那部分。他们一遍又一遍地重复这个策略。每次他们都能找到越来越小的整数子集，在这些子集上A的密度会继续增长。例如，A可能包含10%的1到N之间的整数，15%的3的倍数，以及25%的3的偶数倍数。

当A很大时，有趣的事情发生了。如果重复这个过程，A在某个子集上的密度超过100%。当然，这是不可能的。A可以包含24的所有倍数，但它不能包含超过24的所有倍数。只有当A足够大时，这个悖论才会出现，但当它足够大时，这意味着A不包含任何等差级数的假设一定是错误的。

麦卡说，当A很大时，要么A包含很多等差级数，要么A + A中有很多冗余，在这种情况下，他们可以使用子集查找程序（称为“密度增量策略”）来显示A中必须出现一个等差级数。虽然密度增量策略是该领域的一个经典方法，但麦卡和凯利创新地将其应用于比以往更小的A。通过这种方式，他们发现了一个新的不含等差级数的集合大学的上限。

麦卡和凯利结合了密度增量蓝图中的不同想法，创造了一种独特的组合方法。他们没有创造全新的框架，而是重新思考了如何寻找密集子集。他们采用了一种叫做“筛选”的技术，通过平移集合并与自身相交，反复进行这个过程多次。在许多次交集后，他们剩下了一个高度结构化的集合，具有可预测的特性。虽然在其他论文中也使用过筛选技术，但这是第一次在解决三项级数问题时使用。

最后

麦卡和凯利通过在传统方法中注入筛选等被忽视的工具，将避免等差级数集合的下限降低了令人震惊的程度。

密度增量策略首次出现在罗斯70年前的论文中，从那时起，它就被用于大多数等差级数的论文中。令格林感到惊讶的是，这个框架可以用来证明一个像麦卡和凯利的那样低的边界。麦卡和凯利发现了曾经被忽视的想法的优点，这表明数学进步的发展常常是断断续续的。