热点 前沿 数学

陶哲轩宣布破解埃尔德什差异问题

erdos Terence Tao 数论 离散数学 埃尔德什猜想

Chris Cesare 发表于  2015-09-26 22:43

(Stellasun/编译)2015年9月17日,2006年菲尔茨奖得主、华裔数学家陶哲轩宣布破解了80年未决的埃尔德什差异问题(the Erdos Discrepancy Problem),论文预印本已经发表在arXiv.org上。

埃尔德什差异问题由数学家保罗·埃尔德什(Paul Erdős)在1932年提出,指的是在任意只由1和-1组成的无限数列中,能找到项与项间等距的有限子列,使子列各项之和的绝对值大于一个任意大的常数C。和许多数论问题一样,埃尔德什差异问题描述起来很简单,但证明难度却很大。埃尔德什于1996年去世,没能看到这一问题的证明。

直觉上看,对有些数列而言,这个问题的答案非常简单——在只有1的数列中,把各项加起来一定能得到任意大的数;对无限数列(-1,1,-1,1,-1,1,...)来说,要找到一个各项之和大于2、而且间隔固定的子数列,取第二位和第四位就行;要找到各项之和大于4的子数列,可以取第二位、第四位、第六位、第八位;无论多大的数,都能在(-1,1,-1,1,-1,1)中找到加起来等于这个数的子数列。但埃尔德什的猜想是,无论这些正负1怎么排,这个结论都成立:给出一个任意大的常数,就能找到这样的数列。

这到底是什么意思呢?假设你和你的朋友玩一个抛硬币游戏。掷出正面,你往左走一步。掷出反面,你往右走一步。你知道他在硬币上做了手脚,出来正面还是反面,随心所欲他说了算。

但你也有杀手锏:你可以忽略某些硬币的结果——只不过不能瞎忽略,而是有规矩:每过固定数量的硬币就有一个算数,剩下的全不算。具体隔几个,你在结束的时候说了算。埃尔德什猜想的意义在于,虽然你最后往左还是往右你说了不算,但是你想离出发点多远,就能有多远。

陶哲轩的证明说明了埃尔德什的猜想是对的,但他并没有给出计算这个数值的方法(也就是说,具体怎么挑还不知道,但这个杀手锏是存在的)。虽然他的证明还没有经过严格的同行评议,但数学家们对他的结果很有信心。“我绝对相信他的结果,”以色列希伯来大学的数学家吉尔·卡莱(Gil Kalai)这样说道,但他随后补充道评议可能需要花上一些时间。

数学家们最近一次向这个问题发起挑战的行动始于2009年12月,并在2010年组建起了团队。来自剑桥大学的数学家蒂莫西·高尔(Timothy Gowers)建议用“博学项目”(Polymath Project)解决问题——一个数学家合作的在线平台(译注:Polymath Project还参与过对张益唐孪生素数结果的改进,详情请见《孪生素数猜想之后的故事》)。陶哲轩是几十位参与者之一。

这次合作在2012年告一段落,但数学家们证明了只要能证明埃尔德什猜想对一类数列成立,就能推广到普遍情况。这种数列是这样的:在质数项,数值是随机的,但其他项的数值是它的质数因子项上的数值的积。比如说,第十五项的数值是第三项和第五项的积。

2014年2月,研究人员们用计算机证明了埃尔德什问题的一个特殊情况——子列的和一定能大于2,但没能证明一定能大于3. 陶哲轩的证明说明了这个和一定能大于任意大的有限数。

这个证明发表后,数学家们很长一段时间来都没能取得新的进展。就在这个月初,陶哲轩在博客收到了一条评论,提醒他他正在研究的另一个问题可能与埃尔德什猜想有关。“一开始,我觉得这两个问题之间的联系只是表面的,”陶哲轩在一封电子邮件中这样写道;但他很快意识到,将新思路和之前的结果结合在一起,很可能得到问题的证明。不到两周后,他就发表了论文,并在致谢中感谢了这位评论者——图宾根大学的数学博士尤威·斯特罗斯基(Uwe Stroinski)。

陶哲轩把论文发表在了高尔管理的开源期刊《离散分析》上。《离散期刊》是9月初创刊的,它提供传统的同行评议,但由于只接受已经发表在arXiv上的论文,避免了大量的发行成本。“蒂姆(译注:指前文中的数学家蒂莫西·高尔)的期刊是对论文完全开源出版的一次前景大好的实验。”陶哲轩说。

埃尔德什和十岁的陶哲轩一起研究数学问题。图片来源:nature.com

埃尔德什在陶哲轩申请普林斯顿大学的博士项目时曾为他写过推荐信;他经常对自己提出的猜想提供现金奖励。他为解决埃尔德什差异问题设下的奖金是500美元。在他去世后,别人接管了这些奖金的颁发。

陶哲轩也被问到如果别人决定把奖金授予他,会不会真的去领奖,他的回答是:“在埃尔德什还在世的时候,传统做法是不兑现奖金支票;人们一般会把它裱起来。”(编辑:Ent)

*注:文中的比喻不一定正确,欢迎在评论中提出更严密(以及更人话)的类比……

 

拓展阅读

埃尔德什差异问题特殊情况的证明
全部评论(162)
  • 31楼
    2015-09-27 21:30 阖馫
    引用@FreeYourMind 的话:数学这些及其抽象的理论,很多都是当下看不到甚至很长时间段内看不到实际用处的。但是有谁知道,几年,几十年,几百年……后,很多“然并卵”的理论将会绽放出耀眼的光芒。你说原子裂变聚变有个卵用?没事干去研究这...

    然而,我们中国每年的好多好多科技创新就是卵用没有的……要这么说,别说中国就落后于此……

    [0] 评论
  • 32楼
    2015-09-27 21:38 abada张宏兵

    花别人(比如纳税人)的钱,别人当然要问可能有什么用。当回答说不清时,别人当然要问有用的概率,这涉及投资风险收益率问题。有多少闲钱冒多大风险。不可能拿太多的钱去研究离现实太远的事,比如总是登月研究月球。不能因为地下可能有油,你就总支持掘地万米的事。

    [5] 评论
  • 33楼
    2015-09-27 21:42 loli什么的最喜欢了

    每当这种非常看不懂的研究成果出现时,总有人要问研究这些有什么用

    不考虑经费上的问题的话,研究就非得要有用吗,探索真理一定需要“有用”吗?这个问题的解答也许是完全没有实际用处,甚至在几千年后也是如此。但那又怎么样?

    朝闻道,夕死可矣。

    [4] 评论
  • 34楼
    2015-09-27 23:09 蠢人大晒
    引用@方弦 的话:说句不好听的,人类值得造福吗?无论多好的技术,最终只有极少数人知道它的来源和细节,而绝大多数人沉浸在用自己的钱买了个好玩意儿,如果由于他们自身的原因,将技术用到了适用范围以外,他们不会去尝试理解,而是...

    嗯。。。。

    我的看法是,科学始终是以让人过上更美好的生活为出发点的。

    我觉得吧

    许多的普通大众的确可能是愚昧而无知的,他们(包括我)对科学的理解可能还停留在几百年前。但正因为如此,向这些人普及科学的知识与思考方式,把这些人从阻碍科学进步的因素转变为推进科学进步的因素,才显得如此重要,这不正是果壳网创立的初衷吗。。。。这也是果壳微博坚持不懈地“强行科普″的原因吧哈哈

    [3] 评论
  • 35楼
    2015-09-27 23:33 昂拉克

    看到评论只想说一句话:

    只要足够酷,总会有用的。——胡立德

    [2] 评论
  • 36楼
    2015-09-28 00:10 方弦 科学松鼠会成员,信息学硕士生
    引用@蠢人大晒 的话:嗯。。。。我的看法是,科学始终是以让人过上更美好的生活为出发点的。我觉得吧许多的普通大众的确可能是愚昧而无知的,他们(包括我)对科学的理解可能还停留在几百年前。但正因为如此,向这些人普及科学的知识与思...

    你说错了一点:技术是让人过上更美好的生活,科学不是。科学的目的是让人更好地理解这个世界。数学就更高一些,它的目的是让人更好地理解所有可能的世界。其余的话,将科学换成技术也还可以说得通。

    在以前,技术跟科学是分开的。做一张桌子是技术,我国古代有一流的榫接技术,那个就不需要多复杂的科学。而现在为什么技术总是依赖科学,那是因为对这个世界更深刻的认知才能更好地利用事物创造现象。而为什么科学依赖越来越多的数学,这是因为数学此前探索了非常多人类可以认知的模型(可能的世界),积累了很多对这些模型的理解,科学可以直接用上。

    你说的,是乐观的看法。我说的,是悲观的看法。也许真实的现象在这两种看法中间,但科学普及这种事情,不需要看法也能做下去,或者说,持两种看法都能做下去。

    [11] 评论
  • 37楼
    2015-09-28 00:24 方弦 科学松鼠会成员,信息学硕士生
    引用@马甲与小号 的话:然而这些东西现在就有用……比如说密码学中要用到大量的数论。而日常上个网,就有很多地方会用到密码学。而抽代和数论联系密切,数论的研究会用到大量抽代的内容。因此,密码学也会离不开抽代。至于拓扑和流形,物理...

    其实密码学用到的数论不是特别多。RSA用的其实只是一个假定:因数分解是单向陷门,然后剩下的很大一部分就是工程式的构造。椭圆曲线和后量子加密法可能用得稍微多一些,但主要也是单向陷门的假定,剩下的跟RSA差不多。

    拓扑和流形的确在物理上常用,但即使只说点集拓扑,物理上应该很少用到比较奇怪的拓扑,比如类似Zariski空间的那种是T_0但不是T_1的。如果用到了,那基本上是那种跟数学差不多的物理。

    不过的确现在因为现象越来越多样,有用的数学分支也越来越多,非常可惜。但老分支到现在还没有用的还是有,比如说很多数理逻辑的东西,只要涉及不可计算的,那么基本上就没多少用。还有组合,有很多还是没什么用的,比如我现在做的,数出来有多少个,生成函数算出来了,但是也还是没什么用,除非是某个物理模型的离散化。

    [3] 评论
  • 38楼
    2015-09-28 00:28 方弦 科学松鼠会成员,信息学硕士生
    引用@马甲与小号 的话:然而这些东西现在就有用……比如说密码学中要用到大量的数论。而日常上个网,就有很多地方会用到密码学。而抽代和数论联系密切,数论的研究会用到大量抽代的内容。因此,密码学也会离不开抽代。至于拓扑和流形,物理...

    其实你如果想举数学在生活中应用的例子的话,可能举编码理论更加好。它虽然看起来很工程,但也正因为如此,它用到了很多别的分支的知识,离散几何、代数几何之类的,数学含量比密码学要更高一些。密码学的数学含量主要在破解一方,而不是应用一方。

    [3] 评论
  • 39楼
    2015-09-28 00:55 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话: 然而并没有满不满意这个说法,我只想知道他有什么用。您激动什么?

    那好,它并没有什么实际上的用途,并且数学家们在赞赏的同时对此表示意见不大。

    请问您对这个答案是否满意?

    [1] 评论
  • 40楼
    2015-09-28 01:20 长弓落日

    @方弦

    关于这个命题的研究,我有一些自己的理解,你用专业眼光看一下是不是正确:

    还记得前一阵有人讨论英雄与恶魔抢公主那个话题吗?这个话题如果使用这个差异的结论是不是可以做如下推论:只要英雄知道了恶魔的下注原则(哪怕是恶魔作弊),那就必胜;同理,对于恶魔也是如此。所以只要知道对方的下注原则,并顺着对方的思路走下去,并控制好输赢的节奏,那就有方法使自己获胜。因为那个话题的本质就是1,-1的数列,然后在有限步数内使得累加和大于某一固定数值。。

    因为我在之前自己推理和模拟的过程中已经发现这个苗头(知道原则似乎就必胜无疑),只是一直没有彻底把推理过程完善,模拟程序也没做完。如果套用埃尔德什差异的结论,是不是就可以像我上面那样理解?毕竟恶魔问题只是个有限子集,要求的步数也只有5而已。

    如果我想的没错的话,这个理论的实际用途还是很明显的嘛~

    盼复,谢谢。

    [0] 评论
  • 41楼
    2015-09-28 01:34 方弦 科学松鼠会成员,信息学硕士生
    引用@长弓落日 的话:@方弦 关于这个命题的研究,我有一些自己的理解,你用专业眼光看一下是不是正确:还记得前一阵有人讨论英雄与恶魔抢公主那个话题吗?这个话题如果使用这个差异的结论是不是可以做如下推论:只要英雄知道了恶魔的下...

    我不清楚这个话题,但陶哲轩的结果是存在性的,并没有给出具体的界,所以并不能说实际上有什么用,因为无助于对于任意数列实际找到这样的子数列。

    [1] 评论
  • 42楼
    2015-09-28 01:59 陈邪邪邪
    引用@阴月 的话:然这个定理的实际用处在哪?

    没啥用,不过钱用到这上面总比给人贪了,起码这东西说不定啥时候就有用了

    [0] 评论
  • 43楼
    2015-09-28 02:20 长弓落日
    引用@方弦 的话:我不清楚这个话题,但陶哲轩的结果是存在性的,并没有给出具体的界,所以并不能说实际上有什么用,因为无助于对于任意数列实际找到这样的子数列。

    找了半天找不到原帖了,是不是删掉了,不知道~

    我也不是说要具体的子数列,我理解的意思就是:这类问题肯定有确切的解,而没确定具体的结果是什么。即只肯定了必然性。——这点结论我认为就足够了。

    [0] 评论
  • 44楼
    2015-09-28 02:29 方弦 科学松鼠会成员,信息学硕士生
    引用@长弓落日 的话:找了半天找不到原帖了,是不是删掉了,不知道~我也不是说要具体的子数列,我理解的意思就是:这类问题肯定有确切的解,而没确定具体的结果是什么。即只肯定了必然性。——这点结论我认为就足够了。

    如果不清楚问题是否完全相同的话,难以判断这个定理是否解决了你的问题,因为数学上的东西,只要定义上有一点微妙的差异,最后得到的结果可能大相径庭。

    [1] 评论
  • 45楼
    2015-09-28 02:36 长弓落日
    引用@方弦 的话:如果不清楚问题是否完全相同的话,难以判断这个定理是否解决了你的问题,因为数学上的东西,只要定义上有一点微妙的差异,最后得到的结果可能大相径庭。

    先谢谢,等我整理完发个新帖再和你详细讨论吧。谢谢

    [0] 评论
  • 46楼
    2015-09-28 06:58 蓝冰之心

    似乎可以解决宇宙诞生问题,如果是反物质存在,那么一个固定的干扰,就是导致反物质希少的原因。

    [0] 评论
  • 47楼
    2015-09-28 08:32 选修myth
    引用@方弦 的话:说句不好听的,人类值得造福吗?无论多好的技术,最终只有极少数人知道它的来源和细节,而绝大多数人沉浸在用自己的钱买了个好玩意儿,如果由于他们自身的原因,将技术用到了适用范围以外,他们不会去尝试理解,而是...
    引用文章内容:证明难度却很大。埃尔德什于1996年去世,没能看到这一问题

    你就是降临派咯···

    [0] 评论
  • 48楼
    2015-09-28 10:17 Heat0n
    引用@阴月 的话:我问个实际用处在哪您激动个卵

    艺术本身对于某些人来说也没有实际的用处,在很多人看来,数论其实也是艺术的一种,当然,不排除在以后会有某位天才将数论利用到能改变世界的工程项目中

    [1] 评论
  • 49楼
    2015-09-28 11:46 q68257962
    引用@继续存在 的话:这个跟酒鬼回家那个问题是不是很像


    只是描述比较像吧。酒鬼回家是一个特定的数列,而这个是要证明所有这样的数列,并且这里面还有可数种等差项选取。

    [0] 评论
  • 50楼
    2015-09-28 11:47 Karlson

    Mark

    下届诺数学奖的的Flag

    [0] 评论
  • 51楼
    2015-09-28 11:49 LLH123

    我等凡人无法理解啊

    [0] 评论
  • 52楼
    2015-09-28 11:59 yefllower

    一开始没反应过来埃尔德什是Erdos... 看到照片双重震惊... 原来他们一起做研究...感觉每个细胞都受了刺激

    [1] 评论
  • 53楼
    2015-09-28 12:01 yefllower
    引用@选修myth 的话:你就是降临派咯···

    对对对我也一下想起这个... 第一次看那段的时候还觉得不真实不合理...后来认识了实验室的phd们, 这一段成为了三体里感觉最现实最犀利的部分之一!

    [0] 评论
  • 54楼
    2015-09-28 12:33 gundamfire
    引用@Heat0n 的话:艺术本身对于某些人来说也没有实际的用处,在很多人看来,数论其实也是艺术的一种,当然,不排除在以后会有某位天才将数论利用到能改变世界的工程项目中

    其实推而广之,文学、音乐之类的也没太多用处。但是,人类花了上百万年才成为第一个拥有智慧的种族,是不应该把自己局限于问“这究竟有什么用”这个层次的。

    不过其中一位壳友的回复挺赞的(虽然除了我这种点赞狂魔之外没人理他),毕竟这是用了纳税人 and / or 捐助人的钱的事情,即使人家都听不懂,好歹也简单宣传一下,告诉一下大家为什么要在这上面花钱。@方弦 这差不多也就是我的想法吧。

    [2] 评论
  • 55楼
    2015-09-28 12:56 果壳啥时能加个踩

    我本来已经是个反对“然并卵”、反对“认真你就输了”党了,结果看到上面那个“这样的人类值得造福吗”……我简直……一言难尽。只是感觉很久没见过活着的中二病了。

    [7] 评论
  • 56楼
    2015-09-28 13:15 一叶22
    引用@阴月 的话:我问个实际用处在哪您激动个卵

    因为对于研究纯数学(或者是研究任何科学)的人来说,问理论的实际用处在哪本身就是一个非常充满敌意的问题。

    在现在很多人认为无用的知识就是没有价值的情况下,这种问题大多出于挑衅而非真正疑惑,很多人只是想通过宣扬‘你们的研究根本没有用只是在浪费资源’来满足自己‘哪怕我没你们聪明依然比你们对社会有用’的虚荣心。

    [8] 评论
  • 57楼
    2015-09-28 13:24 霜焰
    引用@蠢人大晒 的话:但把科学的进步真正造福于人类的,正是那些提出“这个有什么用?”这种问题的...


    才不是呢,科学的进步真正造福于人类的那帮人是自己想做某个实际的事情,然后去找数学工具,不是为了一个数学理论找用处,才去做某个实际的事情。他们提出的问题不是“这个有什么用?”,而是“哪个能用于我想的东西”。

    [1] 评论
  • 58楼
    2015-09-28 13:43 果壳乙烷
    引用@一叶22 的话:因为对于研究纯数学(或者是研究任何科学)的人来说,问理论的实...

    说说我的看法吧,我知道研究纯粹数学不是为了实际应用 ,不过真的问它有没有实际用途我个人觉得倒是没有什么敌意,那个提问者@阴月 也就是单纯的想知道会不会有什么用途,而不是说他觉得你研究这是在浪费时间、浪费精力,做无用功,可是那个回答确实过激了。

    [1] 评论
  • 59楼
    2015-09-28 13:51 benOZ
    引用@FreeYourMind 的话:数学这些及其抽象的理论,很多都是当下看不到甚至很长时间段内看不到实际用处的。但是有谁知道,几年,几十年,几百年……后,很多“然并卵”的理论将会绽放出耀眼的光芒。你说原子裂变聚变有个卵用?没事干去研究这...

    同意你的论点,但不同意你的论据。原子裂变是核电站的理论基础。要知道法国25%的电力来源于核电,没有原子物理学的话,他们只能点蜡烛了~~另外尖端科学和实际生活紧密程度远超平常人想象,比如很多人认为“没卵用”的相对论和量子力学,其实每个人每天都能用到~~

    1 GPS每个人都用过吧?原理是卫星用电磁波定位并通过来去时间差测定速度距离。但如果不用相对论效应修正时间,误差会大到无法实用~~

    2 电脑手机里的芯片,电磁作用已不是传统弱电,而是量子效应~~

    [1] 评论
  • 60楼
    2015-09-28 13:55 方弦 科学松鼠会成员,信息学硕士生
    引用@Ensign_Katja 的话:我本来已经是个反对“然并卵”、反对“认真你就输了”党了,结果看到上面那个“这样的人类值得造福吗”……我简直……一言难尽。只是感觉很久没见过活着的中二病了。

    嘛,嘛,当然我的说法可能是过于严重了,但你看一下社会事件,看一下转基因方面的争议,看一下基站方面的争议,还有IVF、食品添加剂等等,你就会觉得人类脑里默认的思考回路还真的不适合科技发展的时代。

    当然,这也是我们需要教育的原因,但是教育大纲又是谁负责修订呢?

    [1] 评论

显示所有评论

你的评论

登录 发表评论

Chris Cesare
Chris Cesare Chris Cesare是《自然》杂志的实习记者。

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区