什么是埃尔德什差异问题? 第1页

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

2015 年 9 月 17 日，陶哲轩 宣布破解 埃尔德什差异问题（the Erdős Discrepancy Problem)（论文地址：

），实在是可喜可贺。

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

• 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 时，结论就不那么显然了。
  

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

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

**********

证明：

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

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

1. 对任意正整数 d，数列的第 d 项和第 2d 项的和为 0——反之，它们的和必为 2 或-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 证明了：

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

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

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

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

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

（注：这其实是一个略带夸张的说法，评论区

指出，Tao自己在这篇paper里就说明了这个结果是基于polymath project的成果，而他本人就参加了这个项目）

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

那么对于我们而言，除了默默围观和赞叹，

还能做什么呢？

【完】

********************

【如需转载，请联系作者】