热点 前沿 数学

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

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)

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

 

拓展阅读

埃尔德什差异问题特殊情况的证明

热门评论

  • 2015-09-27 00:27 FreeYourMind
    引用@阴月 的话:然这个定理的实际用处在哪?

    数学这些及其抽象的理论,很多都是当下看不到甚至很长时间段内看不到实际用处的。但是有谁知道,几年,几十年,几百年……后,很多“然并卵”的理论将会绽放出耀眼的光芒。

    你说原子裂变聚变有个卵用?没事干去研究这些看不到的东西干啥?有时间还不如多种一亩地?种地当然需要,不然吃不饱还研究个屁。

    但是,总要有人去研究些“然并卵”的东西。

    这不是当下有用没用决定的。

    要扣大帽子的话,中国的落后就在于此。


    [125] 评论
  • 2015-09-27 16:16 方弦 科学松鼠会成员,信息学硕士生
    引用@蠢人大晒 的话:评论里不要着急激动与嘲讽,人家只是出于对科学的好奇描述了一个自己关心的问题而已。。。。不要太敏感。。。话说回来,天才们推进科学,但把科学的进步真正造福于人类的,正是那些提出“这个有什么用?”这种问题的...

    说句不好听的,人类值得造福吗?

    无论多好的技术,最终只有极少数人知道它的来源和细节,而绝大多数人沉浸在用自己的钱买了个好玩意儿,如果由于他们自身的原因,将技术用到了适用范围以外,他们不会去尝试理解,而是一股脑儿将责任推到开发这项技术的人身上,丝毫不会考虑这可能是自己的错,然后开发这项技术的人就被口诛笔伐,继而众口铄金,最后只好封诸名山。

    无论多好的技术,只要被大众知道,基本上都逃不过这个下场。这种人类,值得造福吗?

    [59] 评论
  • 2015-09-27 15:35 Metaverse 录音爱好者,万有青年养成计划入围选手

    先贴个标签:#不明觉厉系列#

    要 说这些基础到不能再基础的研究有什么用?这么说吧,自然数是人的脑子(心智)从客观实物的序列中抽象出来的模型,这种模型跟客观世界有着必然的联系,然后 从这个序列出发扩展出来的模型所深挖出来的规律,相当部分都有外部世界对应存在的自然定律(确切来说是用来描述这些定律的工具)——最后,你们现在用到的所有的从简单得你们认为是一目了然的到复杂得如同魔法无异的工具,全都是利用自然定律的结果——然而没有当初那些数学的物理的以及其他更上一层一点(但仍然很基础离应用很远)的“没用”的研究,根本就造不出这些工具。

    所以,轻视鄙夷基础研究无卵用的话,先问问自己的见识有多浅薄。

    (然而我还是相信越无知越傲慢狂妄的人是普遍存在的)


    [36] 评论

显示所有评论

全部评论(161)
  • 1楼
    2015-09-26 22:46 客K

    好牛掰的样子。。。前排

    [0] 评论
  • 2楼
    2015-09-26 23:07 客K

    千禧年还有多少钱啦

    [0] 评论
  • 3楼
    2015-09-26 23:33 Mymathlife

    抢前排!为埃尔德什、陶哲轩两位我的偶像点赞!

    [0] 评论
  • 4楼
    2015-09-27 00:27 FreeYourMind
    引用@阴月 的话:然这个定理的实际用处在哪?

    数学这些及其抽象的理论,很多都是当下看不到甚至很长时间段内看不到实际用处的。但是有谁知道,几年,几十年,几百年……后,很多“然并卵”的理论将会绽放出耀眼的光芒。

    你说原子裂变聚变有个卵用?没事干去研究这些看不到的东西干啥?有时间还不如多种一亩地?种地当然需要,不然吃不饱还研究个屁。

    但是,总要有人去研究些“然并卵”的东西。

    这不是当下有用没用决定的。

    要扣大帽子的话,中国的落后就在于此。


    [125] 评论
  • 5楼
    2015-09-27 06:33 继续存在

    这个跟酒鬼回家那个问题是不是很像

    [0] 评论
  • 6楼
    2015-09-27 07:54 梧桐清声 生理学博士
    引用@阴月 的话:然这个定理的实际用处在哪?

    参考:何夕《伤心者》


    [6] 评论
  • 7楼
    2015-09-27 15:13 大头目
    引用@阴月 的话:我问个实际用处在哪您激动个卵

    的确

    我也很好奇在激动什么

    [1] 评论
  • 8楼
    2015-09-27 15:17 廃驛

    裱起来…………

    [0] 评论
  • 9楼
    2015-09-27 15:17 廃驛

    话说tao还真是什么都搞啊……

    [0] 评论
  • 10楼
    2015-09-27 15:27 晓月夜空
    引用@梧桐清声 的话:参考:何夕《伤心者》

    啊啊啊我也刚想说这篇!高中在科幻世界上看到,印象十分深刻!

    [0] 评论
  • 11楼
    2015-09-27 15:35 Metaverse 录音爱好者,万有青年养成计划入围选手

    先贴个标签:#不明觉厉系列#

    要 说这些基础到不能再基础的研究有什么用?这么说吧,自然数是人的脑子(心智)从客观实物的序列中抽象出来的模型,这种模型跟客观世界有着必然的联系,然后 从这个序列出发扩展出来的模型所深挖出来的规律,相当部分都有外部世界对应存在的自然定律(确切来说是用来描述这些定律的工具)——最后,你们现在用到的所有的从简单得你们认为是一目了然的到复杂得如同魔法无异的工具,全都是利用自然定律的结果——然而没有当初那些数学的物理的以及其他更上一层一点(但仍然很基础离应用很远)的“没用”的研究,根本就造不出这些工具。

    所以,轻视鄙夷基础研究无卵用的话,先问问自己的见识有多浅薄。

    (然而我还是相信越无知越傲慢狂妄的人是普遍存在的)


    [36] 评论
  • 12楼
    2015-09-27 15:36 方弦 科学松鼠会成员,信息学硕士生
    引用@阴月 的话:我问个实际用处在哪您激动个卵

    没什么实际用处,您满意了吗?

    或者说,大部分干数学的人基本上都不会想到自己做的事情会有什么实际用处。英国数学家哈代甚至对这一点非常骄傲。一开始就想有什么实际用处的人,去做工程就好了。

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

    您这地图炮开的好啊,

    [1] 评论
  • 14楼
    2015-09-27 15:40 huiji
    引用@阴月 的话:然这个定理的实际用处在哪?

    事实上很多搞数学研究的根本不会想自己研究的有什么用处

    [3] 评论
  • 15楼
    2015-09-27 15:42 方弦 科学松鼠会成员,信息学硕士生

    这个问题我之前写过,不过肯定不像人话,而且结果也没有那么强:

    http://www.guokr.com/blog/747669/

    陶哲轩的论文我稍微看了开头一点,因为后面实在是看不懂,不过大概可以知道这是用N上的离散傅里叶分析做的,他举的那几个疑似反例也都是很傅里叶的,比如说character性质,而且猜想本身也很浓的傅里叶味道。不过具体怎么估计各种项的话,这方面就不清楚了,可能还是做解析数论的人会更加清楚,毕竟跟筛法之类的关系比较接近,或者加性组合的人应该也清楚,离散傅立叶他们也比较熟。

    [3] 评论
  • 16楼
    2015-09-27 15:53 lyounger 粒子天体物理博士生

    其实不就是「等距子列」这个说法有点儿文绉绉(不讲人话)么

    等距子列是说

    第一项,第二项,第三项,……,第N项

    第一项,第三项,第五项,……,第2N-1项

    第一项,第四项,第七项,……,第3N-1项

    ……

    进而普遍到项数本身是一个等差数列

    第a项,第(a+d)项,第(a+2d)项,……,第(a+(N-1)d)项

    然后陶证明的就是

    这些项之和的绝对值可以大于任意的数

    这个命题很难理解么……

    [9] 评论
  • 17楼
    2015-09-27 15:54 蠢人大晒

    评论里不要着急激动与嘲讽,人家只是出于对科学的好奇描述了一个自己关心的问题而已。。。。不要太敏感。。。

    话说回来,天才们推进科学,但把科学的进步真正造福于人类的,正是那些提出“这个有什么用?”这种问题的人吧。。。。

    [2] 评论
  • 18楼
    2015-09-27 16:10 方弦 科学松鼠会成员,信息学硕士生
    引用@lyounger 的话:其实不就是「等距子列」这个说法有点儿文绉绉(不讲人话)么等距子列是说第一项,第二项,第三项,……,第N项第一项,第三项,第五项,……,第2N-1项第一项,第四项,第七项,……,第3N-1项……进而普遍...

    嗯,项数的确是等差数列,但在这个问题中,强制了a_0是第一项。

    [1] 评论
  • 19楼
    2015-09-27 16:13 incons

    数论可以用于加密算法和网络安全传输上。战争时期:用来推算德军潜艇位置。和平时期:用来给洋葱圈升级骗过方校长。

    [3] 评论
  • 20楼
    2015-09-27 16:16 方弦 科学松鼠会成员,信息学硕士生
    引用@蠢人大晒 的话:评论里不要着急激动与嘲讽,人家只是出于对科学的好奇描述了一个自己关心的问题而已。。。。不要太敏感。。。话说回来,天才们推进科学,但把科学的进步真正造福于人类的,正是那些提出“这个有什么用?”这种问题的...

    说句不好听的,人类值得造福吗?

    无论多好的技术,最终只有极少数人知道它的来源和细节,而绝大多数人沉浸在用自己的钱买了个好玩意儿,如果由于他们自身的原因,将技术用到了适用范围以外,他们不会去尝试理解,而是一股脑儿将责任推到开发这项技术的人身上,丝毫不会考虑这可能是自己的错,然后开发这项技术的人就被口诛笔伐,继而众口铄金,最后只好封诸名山。

    无论多好的技术,只要被大众知道,基本上都逃不过这个下场。这种人类,值得造福吗?

    [59] 评论
  • 21楼
    2015-09-27 16:24 已退休少先队员
    引用@阴月 的话:然这个定理的实际用处在哪?

    航天、黑洞研究目前以及将来也看不出有什么实际用处....

    [3] 评论
  • 22楼
    2015-09-27 17:03 天降龙虾

    不可用者为道,可用者为器,器为小用,道为大用。大道恒久不变,是以无用,无用之用,方为大用。。

    逻辑和抽象知识,本身都没什么用处嘛。。。

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

    值得。。。否则那些人眼里的科技就更没用了。。。。。好歹可以让他们抱怨一下。

    [1] 评论
  • 24楼
    2015-09-27 17:56 AI油泳的鹰 勘查技术与工程专业,编程爱好者
    引用@方弦 的话:说句不好听的,人类值得造福吗?无论多好的技术,最终只有极少数人知道它的来源和细节,而绝大多数人沉浸在用自己的钱买了个好玩意儿,如果由于他们自身的原因,将技术用到了适用范围以外,他们不会去尝试理解,而是...

    所以留下那极少数人,其他的全都杀光算了

    [1] 评论
  • 25楼
    2015-09-27 18:03 AI油泳的鹰 勘查技术与工程专业,编程爱好者
    引用@Metaverse 的话: 先贴个标签:#不明觉厉系列#要 说这些基础到不能再基础的研究有什么用?这么说吧,自然数是人的脑子(心智)从客观实物的序列中抽象出来的模型,这种模型跟客观世界有着必然的联系,然后 从这个序列出发扩展出...

    这个解释挺好,数学是客观世界的抽象模型。

    [1] 评论
  • 26楼
    2015-09-27 18:03 三千里的小丫杈

    我第一次看完果壳去翻原文看...这样的翻译挺好的,毕竟理解和深度是博弈啊...

    [0] 评论
  • 27楼
    2015-09-27 18:29 方弦 科学松鼠会成员,信息学硕士生
    引用@AI油泳的鹰 的话:所以留下那极少数人,其他的全都杀光算了

    太过激了,发展出AI就行了。

    [2] 评论
  • 28楼
    2015-09-27 18:58 天天天天天天天天天

    说几百年后有用的,我觉得就不是学数学的。尽管我似乎听过微积分在几百年前被认为没用,尽管现代数学确实有点运用,然而那些拓扑,抽代,流型,数论离我们生活实在太远了,不管有用没用,几百年内我都不觉得它会有运用。

    [0] 评论
  • 29楼
    2015-09-27 20:12 enbuger

    纯数学没用是因为人类智商过低

    [0] 评论
  • 30楼
    2015-09-27 21:22 Royx85
    引用@天天天天天天天天天 的话:说几百年后有用的,我觉得就不是学数学的。尽管我似乎听过微积分在几百年前被认为没用,尽管现代数学确实有点运用,然而那些拓扑,抽代,流型,数论离我们生活实在太远了,不管有用没用,几百年内我都不觉得它会有运...

    也不能这么说,其实你发现没有,科学的革新感觉间隔是越来越短了。或许之前的研究发挥作用是几百年的间隔,说不定现在是几十年或十几年。

    [3] 评论

显示所有评论

你的评论

登录 发表评论

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

更多科研事,扫码早知道

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

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

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