等差数列, 你在吗？

作者 | 沈俊严

原载于 | UniMath

编者荐语

请问:“在数字1-10中, 至少要选取几个数字, 才能保证任意选取的数字中一定存在3个数字构成等差数列?” 这个问题听起来有点拗口, 但你细品, 再一沉思, 是不是能搞定这个问题. 那你知道吗？数学家却在日以继夜地研究这类涉及等差数列存在性的问题. 1936年, 保罗·埃尔德什(Erdős)与保罗·图兰(Turán)一起发表了一篇论文, 引发了关于不存在等差数列(avoiding arithmetic progressions)的整数集合的研究, 并提出了著名的埃尔德什-图兰猜想 (Erdős–Turán conjecture). 那么你想知道数学家是怎么思考的吗, 这个问题是如何发展的其中又有哪些创意呢？

引言

加性组合学(additive combinatorics)是数学的其中一个研究领域, 主要在探讨集合的结构性. 有趣的是, 虽然问题看起来像是单纯的组合数学, 但是证明却经常出现看似不相干的领域所发展出来的方法. 一个经典的例子就是等差数列的存在性.

等差数列的存在性？你说的是中学就接触到的等差数列吗？没错！

我们知道等差数列, 就是一串数字排好站成一列, 使得两两相邻的数字都有一样的差距间隔. 举例来说 1, 3, 5, 7, 9 是一个等差数列；101, 202, 303, 404, 505, 606, 707, 808 也是一个等差数列. 如果再进一步区分等差数列, 我们可以用长度来区分它们, 例如 1, 3, 5, 7, 9 共有五个数字, 故称之为一个长度五的等差数列, 依此类推 101, 202, 303, 404, 505, 606, 707, 808 是长度八的等差数列. 那么我们这边说的等差数列存在性是什么意思？

上述两个数列, 通过检验可以立刻知道它们都是等差数列, 是因为它们被具体的写出来．那如果有一串数字没有被具体描述出来, 我们是否还有办法判断到底会不会在这一串数字中存在部分数字形成等差数列呢？ 接下来我们就来谈谈该问题的发展, 从中也可以看见数学家是如何思考的以及展现的创意.

等差數列的存在性

举例来说, 现在有5个自然数每个数字都不大于10, 请问这样的5个自然数是否保证有一部分形成等差数列呢？如果我们能够找到5个数字使得其中任意3个恰好都不足以形成长度三(等差数列的最小长度)的等差数列, 答案就是NO； 否则的话, 如果任意挑选5个数字都找得到长度三的等差数列, 答案就是YES.

显然, 这组数字 很容易验证不存在等差数列, 因此从1到10之中挑选5个数字并不保证会有等差数列. 另一方面, 这也是能挑出不形成等差数列的数字里面最多的数字了, 也就是说你若从中选6个数字, 就必定会存在长度三的等差数列, 不管这6个数字怎么挑都无法避免.

换句话说, 小于等于10的自然数中, 若挑选大于5个数就保证了等差数列的存在性. 于是我们知道若要避免形成等差数列, 从10以下(含)的数字中最多只能挑选 的数字. 如果从40以下(含)的数字中挑选, 则最多只能拿 的数字才不会形成等差数列. 此处 或 就是数字的密度, 也是数学家用来衡量此问题的重要指标之一.

由于等差数列平移之后仍是等差数列, 上述例子也告诉我们, 若要不形成等差数列, 不管从哪里开始数连续10个正整数, 最多只能挑选其中个数字；连续40个正整数, 则最多只能挑选其中个数字. 你或许已经感觉到, 随着可选范围越来越大, 为了避免等差数列形成, 能够挑选出来的数字密度也越来越小.

如何建构一个数列避免包含等差数列?

如何建构一个数列避免包含等差数列?这是一个具有挑战且有趣的数学问题. 1946 年 F. Behrend 提出了一个建构法, 然而他的方法随着范围变大, 找到的数字密度却下降得相当快, 比方说在连续10万个数字中, Behrend找的不含等差数列的数字集合中只有171个数字； 连续100万个数字中, 他的集合中也只有586个数字, 密度小于.

一个很自然的想法是利用贪婪算法去建构, 比方说先选 1 和 2, 接下来每次都选不会形成等差数列的最小的数字, 所以接下来的数字是 4 (如果选 3 就会形成等差, 4 是最小不形成等差的数), 后面依序就是 1, 2, 4, 5, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40,…, 按照这套逻辑可建构出要多长就有多长的不包含等差数列的数列. 这个方法是 1978 年 A. Odlyzko 和 R. Stanley 在一篇未发表的论文里提出, 后来人们也给这样建构出来的数列冠上 Stanley sequence 的名称. 有没有更好的方法找到更大密度的数列去避免包含等差呢？这是数学家数十年来关心的重要问题.

挑选多少数字就一定会包含等差数列？

另一个方向的有趣问题是挑选多少数字就一定会包含等差数列呢？我们立马就来介绍第一个重量级结果, 英国数学家罗斯 K. Roth (菲尔兹奖得主)于1953年证明：

罗斯(Roth)美妙的结果开创了后续许多衍伸, 也间接让加性组合学在近代蓬勃发展.

例如, 大数学家 Szemeredi (2012 Abel 奖得主) 用组合学的方法证明了更强(事实上可说是强到不可思议)的结果：在相同的假设之下 , 集合 不仅包含长度三的等差数列, Szemeredi 指出包含了"任意长度的等差数列". 也就是你心里面任选一个正整数, 例如 100万, 那么集合里面必定有100万个数字形成等差数列.之后H. Furstenberg(2020 Abel奖得主)用动态系统方法证明了相同的结果, T. Gowers(1998 菲尔兹奖得主)用傅立叶分析也证明了相同的结果.

假设是 的一个子集合, 如果不包含长度三的等差数列, 那么的密度最大可以到多大？我们令(我们用 来代表 集合中的元素个数, 因此就是 的密度). 事实上, 我们可以从罗斯的证明里面得到,

换句话说, 如果一个集合不存在任何长度三的等差数列, 此集合的密度必定趋近于零.

因此在全部自然数中密度大于零(不管多小都可以, 只要大于零)的集合就必定存在等差数列. 当我们用 来思考时, 这些问题变得更加棘手, 也因此估计 的大小也就成了这几年等差数列问题的重要研究方向, 接下来我们就来谈谈一直到最近的重要发展.

• Bourgain的成果

  1999年, 布尔甘(J. Bourgain, 1994 费尔兹奖得主)登场, 他的结果大幅度的改进了罗斯的密度估计, 布尔甘的结果证明了将上界下修到

  也就是说, 一个不存在长度三的等差数列的集合密度是非常小的.

  这里说得非常小是跟罗斯的结果相比, 例如, 当 时, 罗斯说若要不包含等差数列, 那么集合 的密度必定小于 , 也就是不能全选. (咦?!这不是废话吗, 对啦, 在数论的研究中很多结果都是用 来表示, 必须在规模超级大的情况下才显得出威力. ) 布尔甘的结果则说集合 的密度必定小于 (看起来正常多了).

  这里顺便说一下有趣的小故事, 笔者在美国念书时候, 曾经听指导老师说格林 (Green) 和陶(Tao) 有一年做出其它长度的密度定理时, 格林跟陶打赌一百美金说, 他相信短期之内不大可能会有人可以做出比他们更好的密度估计, 不晓得是不是布尔甘知道了, 很快地就做出了更好的结果, 当然我也不清楚格林到底有没有给出这一百美金.

  我们稍微谈谈布尔甘的证明思路, 其实布尔甘证明的叙述是当足够大时, 那么必定存在三个相异的数字 使得 , 当然这就说明存在长度三的等差数列.

• Sanders的成果

  2011年, 一位年轻的英国数学家桑德斯(Sanders) 再次大幅度的改进估计, 得到

  简单来说, 布尔甘和桑德斯皆证明在这些密度估计之下, 我们有这个不等式

  其中 是集合 的特征函数, 也就是 , 当 在 里面； , 当 不在 里. 因此只要上述的和非零, 也就意味着等差数列的存在.

• Bloom 和 Sisask 的成果

  数学家无所畏惧, 总是勇于挑战. 桑德斯的结果在2020年被两位数学家 Bloom 以及 Sisask 再度改进, 而且这次的密度估计突破了大家普遍觉得不大可能可以攻克的境界. 这两位数学家证明了

  其中 是一个大于零的常数. 此密度估计不仅仅突破了分母次方是一的界线, 更重要的是此密度结果对一道非常困难的埃尔德什-图兰猜想 (Erdős-Turán conjecture)给出了重大突破.

  

  Bloom 以及 Sisask 密度估计直接证明了上述猜想在长度为3的等差数列为真. 任何人如果可以证明上述的猜想, 必定会轰动数学界, 因为不仅解决了一个重要的数学问题, 同时也把格林以及陶的结果当作特例, 也就是令 是所有质数的情况.

• R. Meka 和 Z. Kelley 的成果

  时间来到 2023 年, 当大家觉得数学家似乎已经相当相当难在有所突破时候, 两位信息科学家, R. Meka 和 Z. Kelley 震撼了数学界. 他们给出了远比 Bloom 以及 Sisask 还要更小的估计,

  其中 是两个大于零的固定常数. 这意味着一个集合如果没有任何等差数列, 此集合的密度是以指数函数的速度趋近到零. R. Meka 和 Z. Kelley 的证明几乎用了前述所有数学家的方法, 加上许多全新的细腻操作才得到如此重要的突破, 有些人甚至形容 Meka 和 Kelley 的结果是"在干毛巾上再拧出水来".

更多思考

指数递减这样的密度估计并不是第一次出现. 一款很火的桌游隐含的数学问题就与这里讨论的问题相关. 这款游戏称为SET桌游, 由81张卡牌组成, 这些卡牌有不同的图案及花色, 如下图. 具体来讲就是每张卡牌上的图案都有4个维度（颜色, 形状, 数量, 填充）组成, 其中每个维度都有3种不同属性可选. 我们将属性都相同或都不同的三张牌称为一个“组合”(比如图中红色框出来的三张卡牌: 颜色维度都不相同, 形状都不相同, 数量都相同, 填充都不相同.).

其中一种游戏规则是先把若干张卡牌在桌上排好, 背面朝上, 每人轮流翻一张之后盖回去, 接下来如果有人记得哪三张牌恰好是一个“组合”, 就可以拿走这三张牌, 最后拿最多牌的人赢.

于是我们可以问如果这副卡牌有N张, 最多可以有多少张, 使得找不到任何三张牌刚好构成一个“组合”. 依此类推, 在高维度空间, 我们也可以问相同的问题使得集合里没有任何长度为三的等差数列. 事实上, 这些问题的密度估计在几年前已经被几位数学家用非常巧妙的线性代数方法, 得到了指数函数型的递减密度估计.

总结来说, 比起等差数列的存在, 要让它不存在是一件更难办到的事情, 难到说不存在等差数列的集合中, 数字的个数相对来说非常非常的稀少.

关于作者

国立台湾大学数学系教授