热点 前沿 数学

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

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)
  • 61楼
    2015-09-28 13:55 字符与标点

    绝大部分基础研究最大的用处就是,给那些“有用”的东西打基础。“我们发现了一种能把鸟苷酸环化的酶”--民众:没卵用,你们在浪费纳税人的钱!“我们发现它的活性受一氧化氮的调节”--民众:没卵用,你们在浪费纳税人的钱!“我们发现环鸟苷酸能调节细胞的信号通路”--民众:没卵用,你们在浪费纳税人的钱!我们根据以上结果生产出了速效救心”民众:我爸/妈的心脏病有治了!“我们要继续研究环鸟苷酸的效应”--民众:没卵用,你们在浪费纳税人的钱!

    [5] 评论
  • 62楼
    2015-09-28 13:58 生命激流
    引用@一叶22 的话:因为对于研究纯数学(或者是研究任何科学)的人来说,问理论的实...

    是不是敏感过度了。

    在现在很多人认为无用的知识就是没有价值的情况下——毕竟这里是果壳,你可以轻松点。我个程序员算是干工程的了,还不是经常被人说整那看不见摸不着的玩意有啥用。我年轻时还会争论几句,现在都习惯了。

    我没你们聪明依然比你们对社会有用’的虚荣心。——我感觉对社会有用是件真正值得拿来炫的事情,不是什么虚荣。

    Ps. 私以为有用的意思不是马上就能拿出去换钱。价格跟价值是两回事儿。

    搞纯理论的,虽然现在可能静下心挺难,但是你们的成果用处在于解释世界的本质,这是有用的,最多是时候未到。其实不止你们经常被买菜大妈质疑有用没用,自己心里有数就好。世上还是明白人多。

    [2] 评论
  • 63楼
    2015-09-28 14:15 C.P.

    那谁我也不好意思@您了

    我觉得大家是对您的提问有点反应过度了。

    不过我也特真诚地想知道,您提的问题有什么“实际作用”? 是可以提升GDP?还是国民幸福感?

    千万不要回答说,没别的,您就是想知道而已。

    因为人家研究这么高深复杂的问题,说不定就是想知道是怎么回事而已,行不行?

    [1] 评论
  • 64楼
    2015-09-28 14:56 C.P.
    引用@阴月 的话:知道了有什么用>想办法去用>创造价值

    哪方面价值?具体一点?

    让人觉得爽了算不算有价值?

    [0] 评论
  • 65楼
    2015-09-28 14:57 果壳啥时能加个踩
    引用@方弦 的话:嘛,嘛,当然我的说法可能是过于严重了,但你看一下社会事件,看一下转基因方面的争议,看一下基站方面的争议,还有IVF、食品添加剂等等,你就会觉得人类脑里默认的思考回路还真的不适合科技发展的时代。当然,这...

    除了那句话之外,你说的其他我本质上都赞同。

    不过赞同之后就没下文了,因为个人学识与见识所限我觉得这简直无解(°ー°〃)

    多数时候下我只能这样想:几千年前的人全把星星当成众神与魔鬼,现在虽然还是满大街满嘴十二星座跑火车,但至少他们知道那是“星星”了。

    [1] 评论
  • 66楼
    2015-09-28 14:59 ldcarrot

    这都能撕起来是反映了果壳用户的平均水平也在下降吗。。。

    [2] 评论
  • 67楼
    2015-09-28 15:07 方弦 科学松鼠会成员,信息学硕士生
    引用@Ensign_Katja 的话:除了那句话之外,你说的其他我本质上都赞同。不过赞同之后就没下文了,因为个人学识与见识所限我觉得这简直无解(°ー°〃)多数时候下我只能这样想:几千年前的人全把星星当成众神与魔鬼,现在虽然还是满大街满嘴十...

    那也花了几千年(好吧,如果从认识的角度来说,从科学家大概搞清楚恒星是啥大概100年吧),而且还不完全,于是世界上这么多的科学,要等到啥时候才能被理解?

    也不要说人类值不值得吧,就比如你做出来一个东西,面对着毫不理解而且自己弄坏了基本上会不分青红皂白直接过来弄你的一个人,这个东西你是交给他好还是不给他好?目前看来最好的方法是只告诉他你能干什么,根本不要告诉他这个东西的存在,免得他乱想。但明显这与科学的价值观不太符合。

    [1] 评论
  • 68楼
    2015-09-28 15:07 生命激流
    引用@ldcarrot 的话:这都能撕起来是反映了果壳用户的平均水平也在下降吗。。。

    只是个别处撕了n久的问题又被扯起来而已……

    [2] 评论
  • 69楼
    2015-09-28 15:08 C.P.
    引用@阴月 的话:创造价值是使用这个理论的人的事,而不是研究者的事。让人觉得爽也是实在的产品的效果。您确定要在这装这个逼?

    我不是装这个逼,

    我不是针对您个人,只是个人反对用二元价值观看问题,不是世上所有东西都能划分为有用/无用的。

    很多时候,单纯地知道真相,就是让人爽

    [1] 评论
  • 70楼
    2015-09-28 15:10 C.P.
    引用@ldcarrot 的话:这都能撕起来是反映了果壳用户的平均水平也在下降吗。。。

    只是大家讨论一下哲学话题而已,不是撕吧。

    [0] 评论
  • 71楼
    2015-09-28 15:53 ldcarrot
    引用@czp0412 的话:只是大家讨论一下哲学话题而已,不是撕吧。

    怪我,没仔细看。。。。看前几楼讨论的激动地要命,没注意往下就开始探讨哲学了。。

    [0] 评论
  • 72楼
    2015-09-28 16:09 方弦 科学松鼠会成员,信息学硕士生
    引用@gundamfire 的话:其实推而广之,文学、音乐之类的也没太多用处。但是,人类花了上百万年才成为第一个拥有智慧的种族,是不应该把自己局限于问“这究竟有什么用”这个层次的。不过其中一位壳友的回复挺赞的(虽然除了我这种点赞狂魔之...

    这个当然可以有,要不为啥我写那么多数学方面的科普……

    然而与此同时,我也宣传了很久“不要问数学家这东西有什么用”,因为很多现在做的数学目前都没什么用,而在可预见的将来会有用的也不多。这个钱花的就是在于探索所有可能的世界,探索人类能认知的极限。但似乎这种宣传并没有什么效果,可能还加深了人们对数学的忽视……

    要我说“你看一两百年前发展出来的复变多有用啊”,也不是不可以(拇姬老师跟我提过这一点,希望我写个系列介绍各种数学定理有什么用,其实有些定理甚至是一个行业的基石),因为其实一般人主要关心的就是这个……但是这显然不是做数学的人心里真正想的事情……

    [3] 评论
  • 73楼
    2015-09-28 16:19 我该换个昵称了捂脸啊
    引用@阴月 的话:然这个定理的实际用处在哪?

    基础科学总是超前工程学很多年。主要的原因其他回复都说了,我讲点关系不大的。

    举个不恰当的例子,以陶哲轩的智商,他看我们就跟我们看狗一个感觉,他如果去研究比如计算机啊通讯啊之类的东西估计能碾压这些领域的大牛。我们能给他这样的人提供足够多的资源,让他能在没有经济压力且受到足够尊重的环境中去研究一些近几十年甚至近几百年都没有“钱途”的东西,这应该是我们的社会体系里少数能让人类作为一个物种感到骄傲的事情了。

    [1] 评论
  • 74楼
    2015-09-28 16:34 雷龙小姐

    我只是来围观高颜值的数学家!!!

    我只是看够数学书上奇奇怪怪的高斯、笛卡尔等数学名人画像了!!!!

    [1] 评论
  • 75楼
    2015-09-28 17:19 xyfd
    引用@阴月 的话:心有病才会伤,所谓被害妄想。

    您那个“然而”就已经能说明你的态度了

    [0] 评论
  • 76楼
    2015-09-28 17:55 xyfd
    引用@AI油泳的鹰 的话:所以留下那极少数人,其他的全都杀光算了

    那些人怎么说也都交税了,没有那么多人哪儿来的钱

    [1] 评论
  • 77楼
    2015-09-28 18:20 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:数学问题证明的最大价值就是确定一个等式或不等式的用法不是么?

    不是,数学证明的最大价值是对某种数学结构更深入的理解。用法的话,做数学的人不关心。

    说回这个问题的证明的话,我可以肯定陶哲轩的这个结果不会有用。先不说这个模型会不会在现实中对应什么,因为证明没有给上界,而且也是存在性证明,不能给出具体算法,所以只能说这个东西存在,没有办法找出来。而如果应用的话,不实际把子数列找出来恐怕做不成。在这个意义上,我之前写过的C=2的可能更“有用”,那个至少有个上界,但也没有给出具体找子数列的方法,而且从数学上来说要平凡得多。这个问题的研究下一步应该是对于不同的C,上界的渐近估计是多少(精确估计应该太难),但因为是渐近估计,所以大概也很难用上。

    但没有实际用处这一点,不影响它的数学价值。这篇论文拓展了离散傅立叶分析这个数学工具,揭示了自然数中又一项拉姆赛结构,就这两点就足够令人兴奋了,根本不会想到有没有用。

    [0] 评论
  • 78楼
    2015-09-28 18:38 ChrisR

    陶哲轩大神又一次让我们仰望。。

    [0] 评论
  • 79楼
    2015-09-28 19:15 uauefeoauf

    虽然不懂,但特佩服那种能有耐心解决别人解决不了的问题的人

    顺便一提,良心来说奖金和荣誉也不关那些网民什么事,那还1313什么?

    [0] 评论
  • 80楼
    2015-09-28 19:31 戴草帽的旅人

    其实这个问题我不知道是作者没描述清楚还是怎么呢,1和-1组成的序列没有强制的限制诸如所占比例或者1和-1的数量关系。文中作者描述的应该是任意的序列的前提下猜想存在,而不是特定的序列如1,-1,1,-1的序列正负1无限交替出现序列中。那在任意数列中,如果我用一个序列如1,-1,-1,-1,-1,-1……。序列后跟无穷个-1,他的猜想成立吗?

    [0] 评论
  • 81楼
    2015-09-28 19:35 戴草帽的旅人

    如果没有对1和-1没有在数量上的关系两者的限制条件。很难成立

    [0] 评论
  • 82楼
    2015-09-28 19:50 戴草帽的旅人

    1或-1有限时结论不成立

    [0] 评论
  • 83楼
    2015-09-28 20:00 方弦 科学松鼠会成员,信息学硕士生
    引用@戴草帽的旅人 的话:其实这个问题我不知道是作者没描述清楚还是怎么呢,1和-1组成的序列没有强制的限制诸如所占比例或者1和-1的数量关系。文中作者描述的应该是任意的序列的前提下猜想存在,而不是特定的序列如1,-1,1,-1...

    原题是要取和的绝对值的,文章里可能没说清楚。

    [0] 评论
  • 84楼
    2015-09-28 20:01 戴草帽的旅人

    序列存在的1的数量有限不成立,上面那条是错的

    [0] 评论
  • 85楼
    2015-09-28 20:53 高黛冥

    说没有什么意义的人可能是被智商碾压后心生嫉妒用一句“然并卵”来平衡一下内心(话说的大多数人确被碾压的很彻底 但不说然并卵至少显得科学素养高啊 但坚持说出自己真实想法 性格还是率真 一大优点)

    [0] 评论
  • 86楼
    2015-09-28 21:27 戴草帽的旅人

    还有个1,-1,-1……。1后共跟9个-1,接下来1,-1,-1,-1,-1……,1后跟99个-1,接下来1,-1,-1……后跟999个-1。这样由前到后,10倍扩大,把序列分组,后一组是前一组的十倍,每组的第一个是1,其余的都是-1,也是否决猜想的。条件不变,每组是前一组的不为1的自然数的整数倍也得到一样的结果,还可以继续已有的数列排列公式带入去扩展。我开始就想的这个,但后面在复查我式子的时候发现序列中1的存在没有数量上的限制条件。就想到一开始的那个序列。

    [0] 评论
  • 87楼
    2015-09-28 21:30 戴草帽的旅人
    引用@方弦 的话:原题是要取和的绝对值的,文章里可能没说清楚。

    取绝对值有可能成立

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

    从古就有 世可救与世不可救的争论

    就中国而言,代表人物:孔子,可救,难救,概率极低,但仍存希望。

    老子:不可救,救了反而添乱。不如(顺其)自然

    结果,两家之言都对后世有着不可估量的影响,也并没有一个定论。人类值不值得造福,世界要不要救,每个人心中自有一套,而我更崇尚的,并非去管世界要不要救,可不可以造福,我要关注的是我自己能不能成为一个真正的人。

    如果宇宙有目的,我相信宇宙的目的就是“变”,但每一样“力”都有阻碍的力,变也是一样。万变不离其宗就是这个意思。科技变了,人心没变,世界看起来变化,而人类社会并没有变。

    永远都有好奇的人去钻研无人能懂的领域,永远有大波的人在自己非专业领域一懒就懒。更有甚者在自己专业领域都不求上进。因为要有“变”的力量,就有稳定的力量。为什么?因为变得太快就会瞬间归于无。

    就好像我们稍微有点科学知识的人都能预测宇宙未来的样子,一片寂静,原子间的距离无限大再没有了生机。这也许是变化的终点。而没有稳定的、懒惰的、一路激进的向前,并不是一个正常的宇宙,他只能更短命。越是变得快,越是短命。

    一如拿破仑的统治,一如希特勒的战败,一如元朝的覆灭。古今中外无不如是。

    正是因为有了惰性气体,才有了“保险”,有了安全范围。人类正式因为有了惰性和奋进的纠缠,才能既不毁灭于冒进,也不死于停滞。追求极致的真理,和拖延懒惰其实缺一不可。

    [0] 评论
  • 89楼
    2015-09-28 21:52 戴草帽的旅人
    引用@方弦 的话:原题是要取和的绝对值的,文章里可能没说清楚。

    取绝对值有可能成立

    [0] 评论
  • 90楼
    2015-09-28 21:58 beiang
    引用@蠢人大晒 的话:评论里不要着急激动与嘲讽,人家只是出于对科学的好奇描述了一个自己关心的问题而已。。。。不要太敏感。。。话说回来,天才们推进科学,但把科学的进步真正造福于人类的,正是那些提出“这个有什么用?”这种问题的...

    提出这种问题的人有两种,一种是诚心请教的,一种纯粹是想表达一下“然并卵”的,所以……


    [2] 评论

显示所有评论

你的评论

登录 发表评论

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

更多科研事,扫码早知道

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

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

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