热点 前沿 数学

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

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)
  • 151楼
    2015-10-12 12:08 砖家叫兽终结者
    引用@确认密码 的话:我为什么觉得这问题有点像抽屉原理?10个球放在9个抽屉里,至少有一个抽屉里的球大于等于2。1个球放到10个抽屉里,至少有1个抽屉不为空。对一个任意大的常数,先构造一个只有(-1,1)组成的数列a,然后...

    草根都是这么想的……

    [0] 评论
  • 152楼
    2015-11-09 09:32 温柔的方程

    七楼的说法与我相同,但是其他评论者好像没反应啊?是不知道吗?


    [0] 评论
  • 153楼
    2015-11-22 19:38 eulershi

    数学家也要混饭吃,没大活的时候,塞牙缝也可以

    [0] 评论
  • 154楼
    2015-12-30 10:52 pop_Vassili

    这个好,炒股总是赢啊,定投

    [0] 评论
  • 155楼
    2016-02-02 21:34 wals

    有的情况小于或者等于2,是因为无限的数列里并没有规定有几个1,或是几个-1,也就是说这个无限的数列可以由1个1和其他无限个-1组成,也可以是2个1和其他无限个-1组成,对吗?这样的话,再怎么加,只有1个1或只有2个1,加到最大和只有2,那么任意大的常数是加不出来的...

    [0] 评论
  • 156楼
    2016-04-28 00:37 manabout
    引用@阴月 的话:我问个实际用处在哪您激动个卵

    不要把自己的话吞回去,你应该明白你为什么会招人嘲笑!

    [0] 评论
  • 157楼
    2016-04-28 00:38 manabout
    引用@大头目 的话:的确 我也很好奇在激动什么

    语文没学好

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

    一个然字倒尽了他的真实想法——NB个屁,不是还是没有用处吗?

    [0] 评论
  • 159楼
    2016-05-18 01:26 manabout


    引用@阴月 的话:你好,刚注册的垃圾ID。

    难道你是老垃圾?发出恶臭的那种?


    [0] 评论
  • 160楼
    2016-08-02 20:28 wxw0924

    美国吸引全世界各行业的精英

    [0] 评论
  • 161楼
    2016-11-21 03:35 灯泡_41048
    引用@方弦 的话:说句不好听的,人类值得造福吗?无论多好的技术,最终只有极少数...
    引用@方弦 的话:说句不好听的,人类值得造福吗?无论多好的技术,最终只有极少数...

    所以说呢,您不如毁灭全人类,迎接三体大军的到来

    [0] 评论
  • 162楼
    2019-01-11 09:01 jian-jian

    第三段是说是 1+1>2 ? 莫不是我看错了?

    大于 2 的莫不是在这个序列找到三个等距的1,得到1+1+1>2 ?例如取2 4 6 位

    [0] 评论

显示所有评论

你的评论

登录 发表评论

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

更多科研事,扫码早知道

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

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

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