微信号:bigdatalab

介绍:宽客俱乐部旗下美国大数据实验室,大数据研究应用.

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

2015-11-06 08:59 大数据实验室

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

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


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

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



证明:

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


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

  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 证明了:


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


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

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

对了,刚才忘了说,陶哲轩从接触这个问题,到最终发表论文,只用了不到两周:
他并没有专门去攻克埃尔德什差异问题,只是在研究其他问题时,发现恰好和这个问题有关,于是顺手证明了一下而已。

所以,如果陶哲轩的证明最终被认为是正确的,
那么对于我们而言,
除了顶礼膜拜,
还能做什么呢?


(作者:曾加 来源:知乎)




人机结合炒单培训班


人机结合,炒单非常容易。

集训两周,不想学会都难!

只要15000元。


咨询报名微信:5424567


详情请点击“阅读原文”


 
大数据实验室 更多文章 用户画像数据建模方法 李光斗:警方是如何利用大数据抓到王全安的 降楼价,新加坡居然靠的是无人驾驶! 小数法则和经验主义 什么性格的人适合 Quant 这个职位?能否描述一下 Quant 一天的生活是怎样的?
猜您喜欢 介绍 LINQ(目录) 独家放送|金融IT行业与容器的巅峰对话:听睿云智合CTO徐年刚畅谈金融行业基于容器技术的DevOps 13 年的 Bug 调试经验总结 PHP100大讲堂直播:【2013-08-15】微信5.0 公众平台开发课程(1) 2015:微软开源年