不到两周就被解决的埃尔德什差异问题

点上方超级数学建模可加关注

用理性的方式去思考问题，是数学带给你的礼物

作者：曾加

来源：知乎

转载请联系本公众号

这是一个值得科普的好问题。

2015 年 9 月 17 日，陶哲轩宣布破解埃尔德什差异问题（the Erdős Discrepancy Problem)（论文地址：http://arxiv.org/abs/1509.05363），实在是可喜可贺。

埃尔德什差异问题当然是一个很难的问题。从提出者和破解者的履历便可见一斑：

Terence Tao有多厉害，相信大家都知道：12 岁获得 IMO 金牌，31 岁获得菲尔兹奖等，都是极其厉害的成就。当然，让我印象深刻的，还有这么一段描述：“陶哲轩的数学生涯 也并非一帆风顺。9岁多时，他未能入选澳大利亚队，去参加国际数学奥林匹克竞赛。”

但我们更应该知道，Paul Erdős也是一个很厉害的人，至少，从成就上来说，他可能比现在的 Tao 更厉害： 他发表论文高达 1475 篇，为现时发表论文数最多的数学家（第二位为 欧拉）；曾和 511 人合写论文。如果你看过《我的大脑敞开了》或《数字情种》，你一定会对这个神奇的数学家留下深刻的印象。

然而，与两人的光辉履历形成鲜明对比的是，“埃尔德什差异问题” 从问题描述来说，却是相当简洁且便于理解的——通过适当的解释，只要是小学毕业了的人，都可以理解这个问题在说什么。

埃尔德什差异问题 的描述是这样的：、

对于任意无穷数列，，

接下来，我尝试用小学生可以理解的方式来解释这个问题：

（1） 首先，有一个无限长的数列 ，数列中的每个数，都是由 1 和 -1 组成的。比如数列 A：1，-1，-1，-1，1，-1……就是一个满足条件的数列。

（2） 接下来，我们要取数列的某些项，这些项在数列中的位置都是某个自然数 N 的倍数，并且是从头开始的连续几个倍数（即第 N 、2N、3N……项）。

比如，我们可以取数列的第 1、2、3、4 项（在 A 中分别为 1，-1，-1，-1），因为它们都是 1 的倍数，且为前 4 项；或者取数列的第 2、4、6 项（在 A 中分别为 -1，-1，-1），因为‘它们都是 2 的倍数，且为前 3 项。但我们不能取数列的第 1、2、4 项 或者 第 4、6、8 项，因为它们不是【从头开始】的【连续几个倍数】。

（3）对于（2）中的每种取法构成的新的数列，我们可以求该数列所有项的和。我们要证明的命题是：无论原来的无穷数列长什么样，我们都可以找到一种取法，使得新数列的和的绝对值大于任意给定的自然数 C。

遇到这样的问题，一个很自然的思路是：试试 C 比较小的时候，我们是否可以给出证明。

当 C=0 时，结论是显然的。

我们只要取数列的第 1 项就可以，它的绝对值肯定大于0。

当 C=1 时，结论就不那么显然了。

我们要证明的是，对任意满足要求的数列，

我思考了这个问题，给出了自己的解法，并认为这可以成为一道中学数学竞赛题。为了便于理解，解答过程不使用超过初中的数学。

证明：

用反证法。假设存在一个数列，满足

于是我们有两个简单的推论：

对任意正整数 d，数列的第 d 项和第 2d 项的和为 0——反之，它们的和必为 2 或-2，矛盾；

对任意正整数 d，数列的第 2d-1 项和第 2d 项的和为 0——反之，设 k 为最小的不满足该条件的数，即第 2k-1 项和 第 2k 项的和为 2 或 -2，则数列的前 2k 项的和为 2 或 -2，矛盾；

不失一般性，设数列第 1 项为 1。

由推论2 => 第 2 项为 -1；

由推论1 => 第 4 项为 1；

由推论2 => 第 3 项为 -1；

由推论1 => 第 6 项为 1；

由推论2 => 第 5 项为 -1；

由推论1 => 第 10 项为 1；

由推论2 => 第 9 项为 -1；

考虑数列的第 12 项：

由于数列的第 6 项为 1，由推论1 => 第 12 项为 -1；

但此时数列的第 3、6、9、12 项分别为 -1，1，-1，-1，其和为 -2，与题设矛盾！

故假设不成立，结论成立。

好了，通过一阵折腾，我们证明了 C=1 的情况是成立的。

那么，C=2 的时候，会是什么情况呢？

2014 年 2 月，英国利物浦大学的 Alexei Lisitsa 和 Boris Konev，利用计算机，几近于暴力验证的办法，验证了 C=2 的特殊情况。但是，计算机验证过程产生数据达到 13G，甚至超过整个Wikipedia 网站的总数据量。

C=3 呢？

相同的计算机算法，没有给出结果……

然后，我们的男神陶哲轩登场了！

他证明了一个更强的命题：

对于任意无穷数列， ，

首先，数列不再局限于由 1 和 -1 组成了，只要满足 即可，其中 H 代表希尔伯特空间。

当然，对于非数学系的同学来说，要理解希尔伯特空间可能有些困难。

为了让高中生也能有一个概念，我们取一个该空间的子集：复数集。

即，对于数列的每一项，只要满足模等于 1 即可。

比如，数列可以长成这样：

在这种情况下，Tao 证明了：

我们总可以找到满足要求的子数列，使得它们的和的模大于任意一个自然数。

现在，你是不是感觉到，这个结论好像真的很强？

然而我们可不能忘记，希尔伯特空间比复数集还要大得多得多。

对了，刚才忘了说，陶哲轩从接触这个问题，到最终发表论文，只用了不到两周：

他并没有专门去攻克埃尔德什差异问题，只是在研究其他问题时，发现恰好和这个问题有关，于是顺手证明了一下而已。

所以，如果陶哲轩的证明最终被认为是正确的，

那么对于我们而言，

除了顶礼膜拜，

还能做什么呢？

如果觉得不错，欢迎赞赏，欢迎分享！

有稿就来投：supermodeling@163.com

你每一次对广告的点击，都是对我们的支持！