热点 前沿 数学

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

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)
  • 121楼
    2015-09-29 18:07 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:为什么不让他们认为你的学科多么的有用呢?科学不普都会被认为没用。

    那你以为我为什么要做数学科普?

    数学科普有两种方式:说心里话和说漂亮话。而一般人愿意看的都是说漂亮话的,也就是说数学多么有用的,而且还不一定看得懂。说漂亮话的科普,我做得算是多了,因为说心里话的没人看,而一般平媒编辑要的都是说漂亮话的。但大部分数学,尤其是那些前沿的,基本上不可能有什么用,有些结果甚至必定不会有什么用,比如我正在写的波斯特-克林关于不可计算图灵度的研究,因为人力根本无法达到,所以不可能在现实中用到。但数学家们还是去做了。

    而特别对这篇文章来说,更加如此,漂亮话根本写不出来,要能写出来的,Nature他们的编辑早就自己写上了,轮不到这里的评论。所以,对于这种数学文章来说,有没有用一眼就能看出来。

    [0] 评论
  • 122楼
    2015-09-29 19:06 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:恰恰相反,我第一眼看到的时候反而是觉得有用的,因为它可能是基于条件变量的一个定义,如果有满足其条件的也许可以构成一个有效率的条件判断,也许运用在程序,也许运用在方法论。然而仔细思考以后并不能界定其具体...

    你觉得有用,那是因为你看的数学以及数学的应用还不够多。还是那句话,如果真的有用,一早忙不迭写上去了。

    证明出来数学家会兴奋,这是真心话,不是漂亮话,因为人们其实对数学家兴不兴奋的没什么兴趣,写出来的话,爱看的人不多,证据就是平媒选择转载从来不选那些真心话的文章,哪怕写得再好。

    [0] 评论
  • 123楼
    2015-09-29 19:22 小co

    我对陶哲轩大大的崇拜又上了一个档次,做图像压缩感知的飘过~

    [0] 评论
  • 124楼
    2015-09-29 19:23 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:不能共感则不能起到交流的效果,而传达的一个核心就是共感。如果你认为数学研究者会有孤立感,这实际上是其在交流上的缺陷自找的。

    一个巴掌拍不响,如果听众不愿意听,那么就算讲者如何慷慨激昂,也毫无作用。你的想法并不新鲜。作为半个科普工作者,经验告诉我,即使已经将这些想法都落到实处了,仍然没有用。这是客观的现象,不是我个人的意见。

    当然,你可以说我做得不够好。但如果一件事情,没有一个人做得足够好的话,那么这个“好”的标准是否有可能达到,就是一个问题。

    [0] 评论
  • 125楼
    2015-09-29 19:27 xml123
    引用@方弦 的话:那你以为我为什么要做数学科普?数学科普有两种方式:说心里话和...

    对于我能理解的数学,我认为分两种:我能看出它有用的以及限于自己的水平看不出它的用处的,我不理解的就不妄加评论了。但是听到您这样说多少还是有些失落。

    PS:很喜欢您写的一系列数学科普,个人认为非常棒。

    [0] 评论
  • 126楼
    2015-09-29 19:30 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:既然大家来看你的文章了,就说明他们是抱着想听什么东西的心态来的。慷慨激昂也有方法,为何媒体造谣如此有效率?因为传媒精于共感之道,而科学家正好是弱项。为何数学家孤立感很强?因为他们是纯逻辑的大脑,感性往...

    这只说明你没看过我的文章。我不敢说我做得有多好,但还没有笨到连这一点都看不出。

    然而并没有什么用。

    [0] 评论
  • 127楼
    2015-09-29 19:35 方弦 科学松鼠会成员,信息学硕士生
    引用@xml123 的话:对于我能理解的数学,我认为分两种:我能看出它有用的以及限于自己的水平看不出它的用处的,我不理解的就不妄加评论了。但是听到您这样说多少还是有些失落。PS:很喜欢您写的一系列数学科普,个人认为非常棒。

    谢谢,有人看我已经非常高兴了。

    其实不理解也无所谓。我写东西的时候往往尝试兼顾两个层次,外行能看个热闹,内行也能挖到些干货,但比例如何,每篇文章不一定一样。所以基本上有些看得出来有些看不出来是很正常的。说漂亮话不代表说假话,只是说数学家做数学的时候可能并不会想到这些,而说漂亮话的时候,往往持的是科学甚至工程领域方面的视点,这样也显亲切。

    [0] 评论
  • 128楼
    2015-09-29 19:38 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:我可以说我看过以后觉得很枯燥吗?

    当然可以,如果你真的那么想的话。

    但我也说了,如果一个标准鲜少有人达到,那么这个标准的价值就存疑。如果你心中有一篇符合你的这个标准的数学科普文章,或者更一般的科普文章,请指出,也好让我们学习一下。

    [0] 评论
  • 129楼
    2015-09-29 19:41 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:具体一点,您说了真心话,您觉得看到这些已经足够兴奋,但是您并没有把兴奋点用语言表达出来,因此别人并不能理解你有多兴奋,只能看到您在叙事。

    因为我的评论不是科普文章,写的时候只考虑了信息的传播。另外文末链接的那个文章严格来说也不是科普,只是我随便写了写。

    [0] 评论
  • 130楼
    2015-09-29 19:52 百炼成钢.

    反正我没看懂

    [0] 评论
  • 131楼
    2015-09-29 19:52 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:是的,所以仅限于行内交流,举个例子如NASA,如果他们把实在的研究论文拿来发表,是断然拿不到钱的,所以宁可不要节操也必须弄一个有传媒效应的新闻稿。

    这话不假,但你之前就此断言数学家们感觉孤独的原因就是因为没有感性,但世界上有着拥有感性的数学家或者数学科普工作者,他们的工作也没有得到太多的认同。于是我认为,传播需要双方配合,一方的确要有些感性,但也要另一方肯侧耳倾听,然而,这大概也是一种奢望吧。

    [0] 评论
  • 132楼
    2015-09-29 22:08 巴德

    首页看到标题是什么埃尔德什,点进来一看原来就是鄂尔多斯(Erdos)这个大牛啊!

    [0] 评论
  • 133楼
    2015-09-29 23:07 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:就我的接触范围来说确实没有遇到能把数学讲得趣味横生的,即使对方真的想要理解点什么。当然这个也是数学这门科学的极端逻辑性导致的,但是因为对方没有听进去就产生了对方不接受自己的想法也是有问题的。比如对方问...

    也许对于每一个个例来说并非如此,但试想一下,一位学生在一段相当长的时间内,遇到的每个人在说完A之后,大部分情况下会再说B。现在,他遇到了另一个陌生人,这位陌生人说了A,那么他是否有理由猜测这位陌生人接下去会说B?这是简单的贝叶斯学习。

    要避免这个问题,最好的方法就是这位陌生人先了解这个现象的来源,再用额外的信息表明自己是一个例外。

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

    这种人类固然不值得造福,但是这种人类也可以提供社会的其它功能不是吗?不能因为这种人的存在而放弃更多愿意被造福的人啊。

    感觉你是对转基因没信心了啊~害怕被反转狗们控制舆论了?淡定~

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

    还有就是,,,虽然不是数学专业,但也一直很喜欢看你的《计算的极限》,突然看见你这么过激,略有点失望呃= =!

    [0] 评论
  • 136楼
    2015-09-29 23:48 Dr.Shubert
    引用@阴月 的话:不能共感则不能起到交流的效果,而传达的一个核心就是共感。如果你认为数学研究者会有孤立感,这实际上是其在交流上的缺陷自找的。

    你难道没有发现自己表达上的自相矛盾之处吗?

    你的那句“然这个定理的实际用处在哪?”被这么多回答的人误解(如果真的是误解的话),难道不是你“在交流上的缺陷自找的”么?

    [0] 评论
  • 137楼
    2015-09-29 23:55 Dr.Shubert
    引用@蔡蔡不是你的菜 的话:还有就是,,,虽然不是数学专业,但也一直很喜欢看你的《计算的极限》,突然看见你这么过激,略有点失望呃= =!

    也算不上过激。

    少不更事的我也相信毛泽东的“人民,只有人民,才是创造世界历史的动力”的论断。但现在越来越觉得人类进步的历史完全是“天才引导下的历程”。

    群众就是群盲,大众就是庸众,乌合之众。

    [0] 评论
  • 138楼
    2015-09-29 23:57 方弦 科学松鼠会成员,信息学硕士生
    引用@蔡蔡不是你的菜 的话:还有就是,,,虽然不是数学专业,但也一直很喜欢看你的《计算的极限》,突然看见你这么过激,略有点失望呃= =!

    当然这里的论述是有些意气用事了,我之前的那篇书评(《现代技术的根源》)可能是一个更加客观的观点描述,当然编辑改过了很多部分,但大体上是差不多的。

    还是谢谢你喜欢我的《计算的极限》,这个系列是我最喜欢的(虽然不是每篇都足够好),花心思最多的(买了至少三本相关主题的英文教材,还不算我已经学过的),也是报酬最少的(没人约稿,只靠自己动力支撑,所以几个月一篇……),拖得最长的(才刚完成一开始三分之一弱的内容)。说实话,如果没有底下的评论在支持和鼓励,也许哪天就悄悄弃坑了……

    [0] 评论
  • 139楼
    2015-09-29 23:57 Dr.Shubert
    引用@阴月 的话:“这么多人”实际上就只有几个。而且基本都是没仔细看字的。

    呵呵,是啊。

    这里发言反对你的不超过10个。全国13亿人,12亿9999万9990人是赞成你的。

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

    你这叫新型大帽子,反扣那些反扣大帽子的人。

    [0] 评论
  • 141楼
    2015-09-30 03:52 看六界风飘
    引用@方弦 的话:没什么实际用处,您满意了吗?或者说,大部分干数学的人基本上都不会想到自己做的事情会有什么实际用处。英国数学家哈代甚至对这一点非常骄傲。一开始就想有什么实际用处的人,去做工程就好了。

    别这么激动……

    [0] 评论
  • 142楼
    2015-09-30 07:19 爨灨鬰饔

    为什么是大于任意大的有限数而不是可数无穷大

    [0] 评论
  • 143楼
    2015-09-30 08:52 Cl_S
    引用@阴月 的话:然这个定理的实际用处在哪?

    对!实际用处在哪?但问这句话的人已经表明自己看不到实际用处。有人问研究数论有什么实际用处?一堆数字而已。但是现代信息加密却和数论紧密相连。我是学物理的,我也看不到数论有什么用处,所以看到别人谈论数论界的发现,我是否也该问句“实际用处在哪”?实际用处在哪?如果数学家一眼就能看出实际用处,那这个数学家必然也是一个应用学家,但是大部分数学家不喜欢应用,他们只是为那些应用学家铺平道路,告诉你世界上和逻辑里存在种种美妙的事实,让一个应用渴望十分强烈人与这些事实更顺利的结缘,这就是它始终存在的实际用处。

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

    对于“然而并没有卵用”的评论,我个人觉得,很多事都是没用的,但没用不代表无趣。非要扯到数学应用上,说现在没有用,以后就用上了。没用的东西是普遍存在的,数学里肯定也有。


    一条无限的随机正负1数列,有没有一条有限等差子列的和大于C。

    一条无限的随机正负1数列,有没有可能存在连续C个的1概率?

    [0] 评论
  • 145楼
    2015-10-03 12:38 基因重组中
    引用@阴月 的话:就我的接触范围来说确实没有遇到能把数学讲得趣味横生的,即使对...

    一些数学概念几乎无法用日常语言准确描述,以至于想要准确描述只能用数学语言。在传播的时候如果硬要牵强附会的转换成日常语言描述,对于知根知底的数学家来说这是非真实的传播(欺骗),一辈子求真的数学人这事心理不太好接受。更别说在此基础上把它弄得妙趣横生了。数论的乐趣和兴奋,需要的门槛太高,以至于只有数学爱好者们的内心才能真切感受。

    我等凡人只可仰望……

    [1] 评论
  • 146楼
    2015-10-05 19:20 旅行者3号

    是部分证明?

    [0] 评论
  • 147楼
    2015-10-07 19:05 确认密码

    我为什么觉得这问题有点像抽屉原理?10个球放在9个抽屉里,至少有一个抽屉里的球大于等于2。1个球放到10个抽屉里,至少有1个抽屉不为空。

    对一个任意大的常数,先构造一个只有(-1,1)组成的数列a,然后这个数列等间距的插入到(-1,1)的无穷数列A中。因为A是无穷数列,所以在A中不仅能找出等间距的a,而且还能找出无穷多组等间距的a.

    无穷数列A包含所有子序列,那就必然含有等距的各项和等任意常数C的有限子数列。

    我觉得这个道理是不言自明的,为什么还要证明?



    [0] 评论
  • 148楼
    2015-10-08 02:03 猫立刻
    引用@确认密码 的话:我为什么觉得这问题有点像抽屉原理?10个球放在9个抽屉里,至少有一个抽屉里的球大于等于2。1个球放到10个抽屉里,至少有1个抽屉不为空。对一个任意大的常数,先构造一个只有(-1,1)组成的数列a,然后...

    你这只是证明任意大的数可以被“打散”插入到任意一个数列,

    但是陶哲轩证明的是相反的操作:对于任意一个(1,-1)序列,都可以找到有限一个子序列使其和大于给定的任意常数。

    另外“无穷”和“所有”不是一回事。有理数有无穷多个,但并不是所有的数都是有理数。

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


    然卵这句话本身的含义跟你想表达的不一样 然卵能兴起 正因为社会问题 那是一种沉默很久的声音 尽管如此 然卵本身就然卵 你这么一说就更然卵了 从统计数字来看(我自己统计) 很少人会认为数学家研究问题是然卵 但同样用我自己统计来看 很多研究出来的东西的确挺然卵 甚至研究者本人自己都觉得然卵 但这并不妨碍数学家做自己本行 要说几年几十年几百年 那也是然卵 我本人期待人类能有研究高效率的年代 应用高效的年代 但目前来看的确然卵

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

    是啊,你今天拿着的无线电话,有卵用扔了吧,微波炉有卵用,扔了吧,汽车有卵用,扔了吧,这些东西最初都只是一些人的猜想,然后演变成理论,数据,和N多次试验最后才发明的,当一个理论还在刚萌芽你就说然并卵,那你可以把你身上所有别人发明的东西都扔掉,有啥用呢?你可以活在原始社会,裸体上街,刀耕火种,毛如饮血。。。你有啥尊严用着别人发明的东西呢?

    [0] 评论

显示所有评论

你的评论

登录 发表评论

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

更多科研事,扫码早知道

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

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

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