机械证明可不仅仅是枚举——最近Erdos某猜想特殊情况的证明

前段时间有这么一个新闻,说是有人用计算机证明了Erdos的一个猜想的特殊情况。因为忙,最近才看了这个论文,想给大家说说是怎么搞的。

首先,我们来说说这个问题到底是啥。

我认为这个问题可以归到拉姆赛类型的问题中,粗略来说,这类问题说的是即使在非常无序的结构中,当结构的大小达到一定程度时,必然会有高度有序的子结构出现。比如拉姆赛定理,说的就是对于任意给定的整数k和l,将完全图任意染红蓝两色,当完全图本身足够大时,最后要么出现红色的k阶完全子图,要么出现蓝色的l阶完全子图。也就是说,完全的无序是不可能的。

Erdos的这个问题,叫Erdos差异问题,也是同样的类型。我们取一个由+1与-1组成的数列,然后考虑它的一些子数列。如果是完全随机的话,这些子数列的和应该很接近0。但Erdos认为,只要数列足够长,长到无限长,对于任何的常数C,应该可以找到这样的子数列,它们的和的绝对值超过C。

具体的数学定义如下:对于任意由+1和-1组成的数列(a_n)_{n \in \mathbb{N}},考虑它的前N项。其中对于所有d \leq N,考虑子数列a_d, a_{2d}, \ldots, a_{\lfloor N/d \rfloor d}的和的绝对值S((a_n)_{n \in \mathbb{N}}, N, d) = \left| \sum_{k=1}^{\lfloor N/d \rfloor} a_{kd} \right|,然后取所有d中这个绝对值最大的d,将这个最大的绝对值记作MaxS((a_n)_{n \in \mathbb{N}}, N)。Erdos的问题就是,是否对于任意一个常数C与任意一个数列(a_n)_{n \in \mathbb{N}},当N足够大的时候,MaxS((a_n)_{n \in \mathbb{N}}, N)必定会超过C?也就是说,当数列无穷时,是否必定存在一个上述形式的有限子数列,它的和的绝对值超过C?

这样的子数列在某种意义上也可以看成一种需要每个分项配合的“秩序”,虽然可能比较弱,因为随机游走的结果也可以做到这一点。在这种情况下,我们可以认为这个问题的本质差不多也是“不存在完全的无序”。

当然了,这不是唯一的看法。另一种看法是这个问题实际上说明了,不存在某种可以避开所有子数列的结构,不过我觉得这也跟拉姆赛问题有些擦边。

然后之前一段时间有数学家把C=2的情况做掉了,具体论文在这里:http://arxiv.org/abs/1402.2184。也就是说,必定找到想要的子数列,使得和的绝对值大于2。

他们是怎么做的呢?其实很简单,他们用计算机证明了,只要数列长度超过1161,那么就必定能找到和的绝对值大于2的给定形式的子数列。显然这么长的数列,要人工分析是不太可能的,必须扔给电脑,但是怎么扔呢?

在自动推理的学界,有一样神器,叫SAT Solver。

如果你是计算机系的学生,那么你一定听说过SAT,也就是可满足性问题:给定一个由与、或、非连接布尔变量组成的命题,是否存在一个变量的赋值满足这个命题,也就是说使得这个命题为真?这个问题著名,主要是因为它是第一个NP-完全的问题,很多问题都是通过规约到SAT来证明是NP-完全的。也正因如此,很多工业和数学上遇到的问题,都可以规约为SAT问题。在这里,规约的意思是将问题表达为布尔变量组成的命题,其中命题的解与原问题的解相互对应。所以,如果命题可满足,那么原来问题必定有解;如果命题不可满足,原来的问题就没有解。只要解决了对应命题的SAT问题,那么就解决了原来的问题。

正因为很多问题都可以规约为SAT问题,所以与其对每个特定的问题开发解法,可能直接开发一个SAT问题的通用算法更方便。这就是SAT Solver,专门解SAT问题的程序。你只要给它一个公式,它吭哧吭哧一段时间就可能给你一个答案(对于所谓Complete Solver而言),虽然要多少时间是完全不知道的,取决于问题的难度。

SAT Solver的研究其实还算相当热门,几乎每年都会有一项SAT Solver的竞赛,由SAT Competition与SAT Race轮流,前者比较偏学术,后者比较偏应用,不过形式是类似的,就是选择一大堆问题,然后让很多SAT Solver去解,谁用的时间少谁赢。

SAT Solver一般分两大类,一类是基于推理,另一类基于撞大运……后者就是先随便找一个赋值,然后尝试改进这个赋值,使得满足命题的程度越来越大,最后如果运气好,就能撞上一个能满足命题的赋值。问题是,如果命题本身就是不可满足的,那么就永远不可能出解……

基于推理的SAT Solver则更加有趣。它们基本上就是一个叫DPLL的算法的变种,这个算法会把命题分成很多子句,要每个子句都为真,命题才为真,然后用逻辑与组合这些子句然后根据逻辑规则简化这些组合,不断重复,如果在某一步得到“False”,那么这个命题就是不可满足的,因为从应该为真的子句导出了矛盾。有时候这样的重复不足以揭示问题,所以也会给某些变量赋值,如果得到“False”,证明变量不可能取这个值,比如取另一个值。这样重复下去,直到找到一个满足的赋值,或者证明所有的赋值都是矛盾的所以命题不可满足。对于不可满足的命题,有些Solver会给出一个证书,通过某些证书(比如Backbone variable)可以在不重复相同计算的情况下验证这个命题不可满足。

说了这么多,这个与自动推理又有什么关系呢?

这些子句,在DPLL Solver的术语中也叫引理。组合子句,其实就是通过组合引理导出新的引理,而如果得到了“FALSE”的引理,也就意味着原来引理的组合可以推出“FALSE”,也就是说,原来的命题本身就有矛盾。

这实际上就是自动推理的一种。

当然,这个算法是50年前的了,现在的SAT Solver要更加先进得多。首先,它们有很多不同的优化,可以加速算法本身的运行。而更重要的是,它们有非常精巧的推理方法。要知道,推理方法,也就是在每一步选择哪些引理进行组合,得到新的引理,这一点对于效率非常关键。SAT Solver近几年的常青树之一,glucose,核心就是一种叫glue clause的引理选择。另外,引理的组合是无穷的,但内存是有限的,如何判断哪些引理重要,哪些引理可以舍弃,这本身就不容易。如果舍弃了重要的引理,可能就要兜一个大弯才能解决问题。但有些推理方法,对一类问题很有效,对另一类问题可能就要花比较长的时间,这时候就要进行取舍。这里边的学问非常深,而且与实际操作关系很大,因为SAT Solver设计出来就是要解决现实中的问题的。现在,最好的SAT Solver可以解开需要几百MB的数据才能表达的问题,也能解出一些非常难的问题。这对于工业来说很重要,比如说一些电路设计的线路排布,就需要用到SAT Solver。SAT Solver不仅是研究,而且对生产也是大大的有好处,绝对是非常有用。

好了,兜了这么一个大弯,回到Erdos的问题上。那些数学家是怎么证明C=2的情况呢?很简单:他们把长度为1161的数列用布尔变量编码,然后将对应的问题规约到SAT,也就是说翻译成命题,然后喂给SAT Solver,他们用的是Lingeling和glucose。这两个Solver哼哧哼哧了一段时间,不断把引理倒来倒去,最后报告了这个命题是不可满足的。glucose还顺便给出了一个证书,这个证书很大,大概是13GB。然后这个问题就被证明了。

有人可能觉得方法很暴力,但是从我的经验看来,其实这里边技术含量很高。先不说暗藏在SAT Solver里的技术含量,就算是将问题规约到SAT,也不是件容易的事。同一个问题可以有非常多的规约方式,但不是每种规约方式求解需要的时间都是一样的。我曾经尝试解某个问题,用一种方式死活解不开,另一种更精细的方法Solver就秒解了……有很多组合问题,其实即使用SAT Solver解,不找准问题的结构所在,盲目去规约的话,基本上做不出来。说到底,Solver是一个自动推理程序,如果一开始给的路就不对的话,那当然需要时间;如果一开始就根据问题结构把引理切好,那显然解起来容易得多。所以,这些数学家把问题做出来了,本身就说明他们很好地理解了这个问题。

可以预见,未来用SAT Solver解的离散数学问题会越来越多。但要记住,这其实并不是暴力枚举,而是巧妙的自动推理,其中的智慧,只有一群人经过漫长的积累才能做到。

起码在目前来说,计算机的智慧,其实是人的智慧的延伸。

二十五

五年过去了,看了看自己的想法有什么变化。似乎大方向上没什么改变,只需要多加几笔。

————————————————————————————————————————

萨特说得好,存在先于本质。人存在,然后再去找意义。我找到的,跟别人找到的,都是对的,都是错的,但无可依靠,只能一直走下去。我的“华丽悲剧”理论(姑且先这么叫),也跟几个人讲过,不为什么,只是我觉得从无所依靠中寻找依靠,这仍然算是个貌似可行的理论,也希望少数几个朋友能明白,为什么我向来说着悲观的言论,却没有被悲观压垮。

我向来对作为一个整体的人类没有信心。那么,如何在这个由人类构成的社会中生存下去,就成了一个困难的问题。《乌合之众》之中的论述,虽然有失偏颇,但也有一定的道理。我更希望保持我自身的判断力,虽然在这个信息横流的社会这越来越难做到。何况为了生存,我仍然要想办法从社会中获取需要的资源。

这也是我选择数学的原因之一。首要原因当然是因为我喜欢数学,无论是数学本身还是数学自有的美。另一个原因就是,我做的数学起码在我活着的相当一段时期不会带来实质性的用途。“山木自寇也,膏火自煎也。桂可食,故伐之;漆可用,故割之。”没有价值,才能来去自由。但凭借数学我仍然可以得到报酬,这是一种社会的投资,目的是长远的价值。但只要没有即时的价值,那么就是安全的,况且我对所谓“长远的价值”也抱有很大的疑问,甚至希望这种价值不存在。

除此以外,我实在不想跟人类打交道。特别是在习惯看微博之后,更加惊叹于人类的愚蠢。绝大部分的人仍然用古旧的方式来思考,毫无逻辑只讲气势。社会也许还会继续进步吧,但我相信大众的思想是绝难改变的,鲁迅先生写的东西到现在还栩栩如生,这就说明了一切。毕竟社会在进步,总有领先的,而大部分人总是落后的。如何在这种环境下,不违心地生存下去,这是个复杂的问题。“多闻数穷,不若守于中”,也许某种程度和形式的随波逐流是必须的。

但是,必须时时警惕不忘本心。我自有要做的事,目标即自我。

想成为什么样的人,就要成为什么样的人,就成为什么样的人。

————————————————————————————————————————

我只是一个平凡的人。

所以我不相信运气,不相信奇迹。一切都是概率,从不盼望小概率事件。相对地,一切事情,无论概率多小,发生了就是发生了,先处理,再反思,没有后悔咒骂的余地。

我只是一个平凡的人。

所以我不相信自己对这个世界有什么显著的影响,一切目光可见的改变,迟早会被岁月磨光。我没有期盼,但是对于我相信的事情,我仍然会做下去,即使早已知道不会有结果。

我只是一个平凡的人。

所以世界上像我这样的人多得是,多我一个不多,少我一个不少。只是对我身边的人来说,“我”这个个体才有意义,否则最多是一个符号,甚至是统计数字。我也不认为我有什么优越,只是条件不同。

我只是一个平凡的人。

所以也有喜怒哀乐,也曾经历悲欢离合,只是说或不说而已。

我只是一个平凡的人。

————————————————————————————————————————

朋友们,相信我,我并没有把你们忘掉。我的记忆力还不算坏,虽然不记得昨天午饭吃了什么,但比如多年前在北京谁跟我讲过些什么,很多时候我还是记得的。我只不过不习惯主动说出来。这种习惯是好是坏,我也说不好。

这几年做科研也做科普,有时候外出演讲多了,渐渐发现自己的又一个奇怪的地方。在面对一帮陌生人演讲的时候,情绪似乎特别高涨,好像换了一个人似的,连我自己都觉得吃惊。现在想起来,大概是应激反应吧,或者说学习了父亲那种奇怪的激动?在社会上,这种技能当然是有好处的,这也许也是我的自我的一部分。

但一个人的时候,坐在椅子上,听着歌,想到的东西基本都是悲观的,如果不是不带情绪的话。科研环境会如何恶化,社会舆论会如何反智,经济整体会如何低迷,气候变化会如何恶劣,这些都是关乎自身生存的问题,但我总是持有非常悲观的观点。

当然,这种悲观的想法并不会使我变得脆弱,毕竟这是我的美学观点的立足之处。

也许这就是我的生活方式。

————————————————————————————————————————

这几年读了些书。慕名多年,终于读到了戴蒙德的《枪炮、病菌与钢铁》,还有他的《崩溃》。《裸猿》是好久之前读的了,与之相对的还有一本《盛装猿》。我一直觉得,这一类书对于了解“人类”很有帮助,也推荐过给朋友。《思考,快与慢》也想读,但是据说翻译不行,打算直接买本原文。

人类是很复杂的东西,如果不研究一下,就很难理解现在发生的种种现象。这些现象,背后或多或少有着千百万年前环境在先祖身上留下的印记。

人毕竟是种动物,即使它有理性。

在人类的日常决策中,理性常常缺席。现代社会节奏太快,理性越来越缺席,在一秒不到的功夫里就能做到的事情,人们思考得越来越少。人们“凭感觉”“靠经验”,却鲜少用推理与实证的方法来处理问题。当然,在餐厅选甜点,大可以凭感觉。一次半次的话,凭感觉得到的满足不一定比衡量营养均衡后带来的收益高多少。但事情总是积少成多。在意识到的时候用理性决策,先不说带来的收益,以后在重大决策中发昏了头的概率大概也会小一些。

人毕竟有理性,虽然本质上是种动物。

但是正是理性,是我们与众不同。探索千亿年跨度的事物,思考现实中并无对应的抽象概念,这都是人类独有的。只有在最大程度上利用理性,才能彰显出人类的不同。而理性带来的谋划能力,也许能给生命存续带来一线生机。

可惜,理解到这一点的人,太少,太少。

————————————————————————————————————————

我害怕群众。

他们能量太大,但没有阀门;他们行动迅速,但从不细思。事实经过三个人,可能已经走板荒唐,而造谣撒谎更是无数,为名为利当然有,但更多时候只是因为好玩。他们可以迅速关注一件事情,造成强大的舆论压力,但转移注意力甚至更快,许多事情草草收场。他们的关注,无论一开始是好是坏,最后总会带来无尽的伤害。

群众是强大的,但也是盲目的。没有什么东西比这更危险。

我希望避免这种危险。但我无处可逃。只能尽量避免成为目标,尽量不引人注目。

但有时候这是必须的。这时我只能小心翼翼、谨小微慎。

我可以跟一个人做朋友,但面对群众,我宁愿沉默。

而民主,有时更加可怕。

————————————————————————————————————————

世界上还有一种可怕的事情,我将它称为“无人犯错的过失”。一件给人带来极大伤害的事情,它的发生可以完全由善意的人们通过善意的手段与善意的体系达成。没有人应该受到惩罚,但却有着严重的后果。可能是运气,可能是疏忽,可能仅仅是没有考虑过于特殊的情况。如果这种事情发生,人们甚至无所用其力。由于善意,甚至难以反思。

所以我认为意向并不重要,最重要的是结果。人本来就不能了解别人,只能用范畴的眼光看问题,事物的属性由它与其它食物的互动所完全决定。纵然心存善念,坏事就是坏事,没有借口。

回想当年华附经历,许多伤害的来源并无主观恶意。但这也正是这些伤害的可怕之处。因为主观没有恶意,所以也不会有愧疚,也不会停止。

我宁愿不受这种人的关注。同时,我也倾向于在没有清晰预期之前,不去干扰他人。

我不想受伤,更不愿意伤害别人。

————————————————————————————————————————

我做数学科普,因为我觉得数学很美妙,而让更多的人知晓这种美妙,不失为一件快事。写得漂亮,更是愉悦。

但我并不觉得也不希望我做的科普会带来实质的用途。开启民智,这个词语太大,实在承受不起。但只要大家能领会数学的美感和重要性,即使不懂细节,也是一件好事。

有朋友跟我说,我这样做科普影响可能不大,现在的人是要喻于利的,我写的都是喻于义,没有市场。

这也是不算什么坏事,本来就不需要它赚钱。起码目前不需要。

我只是因为我想写,于是就写了。

唯一一点不好的就是,我大概应该更勤奋。

————————————————————————————————————————

关于真理与有用的问题,我在图灵传的书评里已经讲过了。

我坚持真理,只希望能尽量不违背自己的良心。

仅仅是希望,因为我知道这绝无可能,只是迟早与程度的问题。

希望遇到这种情况,我能更成熟地处理。

————————————————————————————————————————

返璞归真。

如果说是生活方式的话,这是不可能的。

人类发展到现在,早已没有回头路。比如说农业,无论看上去多么天然的做法,实际上都是人类用各种方式操控自然的结果。不这样做,不可能获得足够的粮食。现在看似天然的有机农业,其实还是基于我们操控自然的经验,而且对环境的影响还不一定小。

现代化的脚步已经遍及每个角落,很多人之所以反对现代化,留恋往昔的生活,实际上可能仅仅因为他们的思考不能适应现代化的步伐。他们不能理解生命的神秘,思考仍停留在亚里士多德的年代,所以不能理解新兴的生物技术。他们不能理解抽象的力量,所以数学对他们而言一钱不值。但他们从来不会想到,如果缺少科技,他们的生活将会寸步难行。

于是拆变电站,拆信号塔,反这个,反那个,仅仅因为“不理解”与“宁可信其有,不可信其无”。而他们无法理解他们自己的不足之处,所以也绝不可能更改他们的意见。肤浅的取像类比,加上年资与传统,这就是他们的利器。

殊不知现在是现代,是理性的年代。也许只有世代更替,才能改变这样的局面。

但也许世代更替仍然不够。在中国,传统的力量是无穷的。

但精神上的返璞归真,却是一件好事。在现代,人更要直面本心,才不至于迷失。

————————————————————————————————————————

Life is so hard.

fin.

数学突破奖半解析:告诉你真实的数学

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守。

本文在果壳网发表,有删改,地址:http://www.guokr.com/article/438708/

科学是目前人类探知客观世界最好的方式。对于科学的投入,尽管不一定能一蹴而就得到什么切实有用的成果,但长远来看却是技术发展最好的动力源。与技术开发不同,对科学的投入更像是公益活动,因为科学研究得到的成果属于全人类。而数学作为科学的语言,也有着类似的性质。

在目前富豪争相投身公益事业的社会潮流下,我们能听到的科学相关奖项也越来越多。除去老牌的菲尔兹奖、诺贝尔奖以外,我们时不时还能听到一些新的奖项。在前不久的6月23日,又有一个新的奖项横空出世,它名为“数学突破奖”,它的目标是“认可本领域内的重要进展,向最好的数学家授予荣誉,支持他们未来的科研事业,以及向一般公众传达数学激动人心之处”。

这个奖项引人注目之处之一它的奖金来源:Facebook的创始人扎克伯格以及数码天空科技的创始人之一米尔诺。此前他们还设立了“基础物理突破奖”与“生命科学突破奖”,合作者更包括Google创始人之一布林以及阿里巴巴的创始人马云。他们都是互联网造就的新贵,大概也正因如此,他们也更理解科学的重要性,因为正是科学的飞速发展,带来了日新月异的信息技术,也给他们带来了庞大的财富。

另一个引人注目之处则是高昂的奖金:三百万美元,这是诺贝尔奖的2.5倍有余,与解决3个克雷研究所千年难题所能获得的金额相同。这是科学奖项目前最高的奖金,它很好地完成了吸引公众眼球的任务。

那么,这次的获奖者都有哪些呢?他们的贡献又是什么呢?

西蒙·唐纳森(Simon Donaldson),来自石溪大学以及伦敦帝国学院,他因“四维流形革命性的新不变量,以及在丛以及法诺簇两方面,对其中代数几何与全局微分几何中稳定性之间联系的研究”而获奖。

马克西姆·孔采维奇(Maxim Kontsevich),来自法国高等科学研究院,他因“在包括代数几何、形变理论、辛拓扑、同调代数以及动力系统等在数学众多领域中产生深刻影响的工作”而获奖。

雅各布·劳瑞(Jacob Lurie),来自哈佛大学,他因“有关高阶范畴论和导出代数几何方面基础性的工作,对全扩展拓扑量子场论的分类,以及对椭圆上同调的参模理论解释”而获奖。

陶哲轩(Terence Tao),来自加州大学洛杉矶分校,他因“在调和分析、组合学、偏微分方程以及解析数论中的众多突破性贡献”而获奖。

理查德·泰勒(Richard Taylor),来自普林斯顿高等研究院,他因“在自守形式理论方面的多项突破性工作,包括谷山-韦伊猜想、一般线性群上的局部郎兰兹猜想以及佐藤-泰特猜想”而获奖。

看着这些简介,你现在的脑海里一定充满了各种“这些字每一个我都认识但是合起来是啥”又或者“哇好厉害啊好高深啊他们干的到底是啥”之类的念头。不要急,让笔者带大家分析每一位的主要贡献。


理查德·泰勒:代数数论

J-invariant from Wikipedia

我们从最后一位的理查德·泰勒开始。他的名字可能不太为人熟知,但如果说起费马大定理以及安德烈·怀尔斯,每个人可能都略有耳闻。泰勒是怀尔斯的学生。在当年怀尔斯证明费马大定理的故事中有一个小插曲,怀尔斯最初发布的证明其实是不正确的,其中存在一个漏洞。大家一开始看不出来,但随着数学界慢慢审视这项重要的工作,漏洞很快就被发现了。怀尔斯花了一年的时间找到了绕过漏洞的方法,而与他一起完成这项工作的,就是泰勒。

泰勒主要研究的领域是自守形式理论,这是代数数论——用代数结构研究自然数的一门数学分支——的一个重要部分。要理解自守形式,最好先从模形式开始。模形式是一种特殊的复值函数,它定义在复平面的上半部分,满足一定的增长条件,而最重要的是它有着高度的对称性,在一个被称为“模群”的特殊变换群的各种变换下仍然保持不变。这个群中的元素都是所谓的“默比乌斯变换”:

z \mapsto \frac{az+b}{cz+d}, \, a,b,c,d \in \mathbb{Z}, \, ,ad-bc=1

(有关群论与模形式理论的另一个联系,请参见《有限单群:一段百年征程》)

这里的a,b,c,d都是整数,也正因如此,模形式与数论天生就具有密不可分的关系。许多数论中的问题,甚至最耀眼的黎曼猜想,都能在模形式中找到联系,特别是一类被称为“椭圆曲线”的特殊曲线,与之关系更为密切,而这正是泰勒与他的合作者证明的谷山-韦伊猜想(现在又被称为模性定理)的内容。不仅是费马大定理,许多形式类似的方程解是否存在的问题,最终也能归结到有关某类椭圆曲线与模形式之间的关系,经过谷山-韦伊猜想指示的联系,从而得到解决。

除此之外,椭圆曲线除了是代数数论研究的轴心之一,也是计算数论中重要的研究对象,从而在实际生活中的应用占据着一席之地,特别是与每个人密切相关的密码学。与椭圆曲线有关的不对称加密协议,已经成为密码学的重要分支之一。这类加密协议虽然速度较慢,但在相同的密钥长度下,可以提供更可靠的保护。而这些加密协议的有效性以及具体应用,反过来又与椭圆曲线的理论研究息息相关。有许多加密时使用的工具,比如说泰特配对,就来源于理论研究。另外,椭圆曲线本身就能用于整数的因子分解,这也是RSA密码体系的命门。

至于泰勒研究的自守形式,则是模形式的一种推广,而椭圆曲线的对应推广又被称为超椭圆曲线。对于这些“升级版”的研究可以说根·本·停·不·下·来。它们结构之精致、地位之重要、内涵之丰富,再加上应用的潜力,实在使数学家们欲罢不能。


陶哲轩:解析数论、调和分析

对于陶哲轩,我们熟悉得多。他是华裔,也是神童,研究的领域之一——解析数论——也早已经由陈景润与哥德巴赫猜想而在中国家喻户晓。

同样研究自然数,陶哲轩走的路子跟泰勒的相去甚远。泰勒研究的代数数论,是尝试通过代数结构来理解自然数;而陶哲轩研究的解析数论,则是尝试通过函数的解析性质(例如有关上下界的估计)来进行探索。

在解析数论中,能用到的工具很多。除了经典的微积分(也就是高数中能学到的东西),还涉及更复杂的调和分析、代数数论以及组合中的一些工具。解析数论中的两大方法,筛法与圆法,前者可以看成组合学中容斥原理的巧妙应用,后者则是复分析与调和分析的集大成者。而陶哲轩在解析数论领域的重要贡献之一,就是引入了新的工具与技巧。他与本·格林证明了,存在任意长(而不是无限长)的等差数列,其中的每一项都是素数。在这个证明之中,他们用圆法拓展了组合中一个由斯泽梅雷迪发现的深刻定理,利用了有关加性组合的新思想解决解析数论的问题。这也使人们更多关于有关加性组合的研究。

(要更深入了解解析数论,请参阅《素数并不孤独》以及果壳网对Helfgott的专访

除此之外,陶哲轩在调和分析、偏微分方程方面也有重要的贡献,这两个领域对实际应用的影响更大。在工程中经常使用的小波分析,其实就是调和分析的一种应用。而陶哲轩对调和分析的研究,也直接催生了一门新的技术——压缩感知。在工程学中,我们经常需要测量某些信号,比如在摄影中,测量就是照相,而信号就是要成像的物体。压缩感知,其实就是如果我们知道信号的某些特殊性质,那么即使只进行少量的测量,在合适的情况下仍然能大体还原整个信号。利用这种方法,已经有人制作了只需单个像素感光元件的照相机,效果还不错,而需要记录的数据量则大大降低。这项技术在医疗诊断、人脸识别等广泛的领域都有重要的应用。

陶哲轩在组合学方面的工作,除了与解析数论有关的加性组合以外,还有代数组合。他与艾伦·克努森(Allen Knutson)发现的蜂窝模型给出了李特尔伍德-理查森系数的又一个组合解释,这些系数与一般线性群的表示论以及格拉斯曼簇的上同调有关,他也借此解决了代数组合中的一些猜想。


广阔的数学

还有剩下三位的工作又是什么呢?

很遗憾,笔者也不清楚。

剩下的这三位,笔者仅仅知道他们研究的领域都与“代数几何”这一数学分支有关。虽然代数和几何大家都很熟悉,但“代数几何”作为一个整体,听说过的人可说是寥寥无几。代数几何奠基于希尔伯特的零点定理,之后经过格罗滕迪克之手一发不可收拾,目前已经发展数学中一门非常重要而又高度抽象的分支,与数学的其它分支有着各种各样深刻的联系。笔者虽然也有做代数几何的朋友,但是聊天的时候从来没有听懂过他的工作。

先不要急着用皮鞋追打笔者,也不要揭穿笔者各种打小广告的行为,笔者这样捉急,也是有原因的:

数学的跨度实在太广了,而每个领域都太深奥了,现在,即使穷尽一个人的一生,也难以涉猎数学的所有领域,而这些专家的所有工作横跨各种各样的领域,要一一详细解释更是难上加难。即使是数学系学生,对于很多没有钻研过的领域的理解,也只是“听说过大概是那么一回事”的程度而已。

这并不是数学特有的现象。实际上,现在整个科学体系经过数百年的不断积累,已经发展为一个庞大的整体。在牛顿的时代,一人尚且可以跨越数个不同的学科同时有所建树;在居里夫人的时代,一人最多也只能在一个学科的许多领域都有贡献;在现代,一人最多只能在一个学科的几个领域得到重大的成果,而绝大部分的研究者熟悉的仅仅是他们主攻的一两个领域。学科的细分前所未有,这也是一种必然,科学体系经过一代又一代研究者成年累月的积累,迟早会突破个人能掌握的极限,即使是天才。专业化、细分化,这是唯一的出路。

而数学研究领域之广阔,研究对象之丰富,研究方法之多样,也是其他学科中少见的。这也造成了数学分支之间前所未有的隔膜。研究量子群论的数学家,丝毫不会担心公理集合论中不可达基数的存在性会不会影响他的研究;埋头苦干纳维-斯托克斯偏微分方程的研究生,多半也永远不会用到范畴论中有关自伴逆变算子的结论;即使是代数几何的大拿,如果被问起随机幂律图的直径分布,大概也只能摇摇头。也正因如此,数学中跨领域的合作弥足珍贵,一个领域的数学工具如果能用在另一个领域中,常常也会带来意想不到的惊喜。

除了专门化之外,数学还有一个其它学科少有的特点:高度的抽象化。在欧拉的时代,数学还能表现成那种人人熟悉的数学式子;而在希尔伯特的时代,数学家们早就不满足于这种略显简单的抽象,决意利用更为抽象的语言将数学精确化,于是诞生了公理集合论;而随着代数拓扑与代数几何的发展,公理集合论已经略显繁琐,数学家们又引入了更抽象的范畴,又推广出高阶范畴,在其中,即使是无比复杂的结构,也被抽象为点与箭头、箭头之间的箭头、箭头之间的箭头之间的箭头,层次永无止尽;而到了现在,又兴起了对一种名为“拓扑斯”的特殊而又更为抽象的范畴,某些数学家甚至希望用它来代替公理集合论作为数学的基础。

这也使有关数学的传播难上加难。由于数学固有的抽象性,向一般大众传播有关数学的新知,常见的结局无非两种:传达的信息正确无误,但读者只能不明觉厉;传达的信息过度简化甚至歪曲,读者读得高兴,自以为理解,实际上却是谬种流传。而在科技日新月异的今天,即使是身边的技术,其中的包含的数学也早已非一般人能够掌握。对于现代的数学研究而言,高中数学不过是玩具,而大学中传说挂了无数人的高数,也只不过是基础中的基础。但对于绝大多数人来说,高数已经远远超过他们所需要掌握的数学。在保持正确性的前提下,现代的数学研究即使经过高度简化也难以为大众所理解,这也是非常正常的事情。如何逾越这个障壁,将数学的美、数学的作用以及研究数学的乐趣向大众传达,走出新的道路,这是一个难题,也是一个必须思考的问题。

互联网新贵们设立这个数学巨奖来奖励数学家,也是这种数学传播的一种尝试。他们希望能将公众的注意力吸引到数学研究上,让更多的人关注数学、喜欢数学,从而间接地鼓励未来的数学研究,还有未来的科技发展。“数学突破奖”这个奖项,在奖励数学家以及吸引公众目光这两方面已经胜利完成任务。但君子之泽,三世而斩。接下来,如何将这种对数学的一时关注转变为长期关注,转变为观念,转变为更好的政策,转变为文化,这是同时考验慈善家、数学工作者、媒体工作者、政治家,以及我们每一个人的问题。

计算的极限(五):有限的障壁

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/85861

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬

难料的世事

美国普林斯顿大学,1936年9月底。

离乡别井,总是一种冒险。即使是一衣带水的英国与美国,文化与传统上的微妙差异,不知制造了多少惶惑。而图灵这时来到普林斯顿,可以说是双重冒险。他刚申请了普林斯顿的奖学金,但却受不了漫长的等待:精英荟萃的普林斯顿实在太诱人了。虽然图灵当时已是剑桥国王学院的研究员,每年有一笔比上不足比下有余的薪金,但人在他乡,经济上需要更多余裕。多申请一笔普林斯顿的奖学金,自然也合乎常理。

但图灵没有拿到这笔奖学金。

在现在看来,这是件不可思议的事:即使是可计算性理论的奠基人,在这笔奖学金上竟然都得不到普林斯顿的青睐。但从当时的情况来看,图灵的遭遇又很合情合理。当时他只是一名小研究员,在学术上名气不大,论文也不多。即使关于图灵机的论文是可计算性理论的奠基石,但脱胎于逻辑的这个领域仍需时间洗练。没有人能参透未来,所以普林斯顿只能从现实角度考虑,而这个考虑的结果,就是拒绝图灵的申请。

但即使没有奖学金,普林斯顿对图灵来说,依然有着相当的吸引力。当时普林斯顿大学数学系与高等研究院共用一幢大楼,可谓人才济济。单在数理逻辑,丘奇自不用提,丘奇的学生克林(Kleene)和罗瑟(Rosser)也是一等一的好手,就连前文反复提到的哥德尔,在一年前访问过普林斯顿,而且计划再次访问。当时在普林斯顿的学者常常开这样的玩笑:如果希望瞻仰数学界的某位领头羊,只要呆在普林斯顿就好,他们总会过来的。人才与人才是相互吸引的,图灵选择冒险,自然有他的理由。

可惜人算不如天算。克林与罗瑟刚刚拿到博士学位,在外校取得了一席教职,已经离开了普林斯顿。哥德尔下一次访问要等到1939年。当时普林斯顿在可计算性理论上能拿得出手的,大概就只有丘奇。丘奇的λ演算在日后同样枝繁叶茂,但那将是本系列的另一个故事。

然而,丘奇的研究方式与图灵格格不入,他追求一切概念的严谨与形式化,甚至到达了难以容忍任何模糊描述的地步。从丘奇和图灵各自提出的可计算性的模型,也能看出二人研究风格的差异。丘奇的λ演算从模型本身的描述开始就充满了一种严谨精确、不可更改的气度,如同数学王国中又一块晶莹璀璨的宝石,可望而不可即;而图灵的图灵机则更为灵动直观,似乎在机械工房中就能找到它的身影,每个人都能明白它的原理。

可以想象这两种迥异的研究风格相遇时必然产生的矛盾。当年二人如何合作研究,在今天剩下的文件中只能窥见一鳞半爪,细节已然遗失于历史的尘埃之中。但从图灵的信件可以推测,他们一开始的合作并不顺利。尽管丘奇为人友善,尽管图灵勤勤恳恳,尽管二人都可以说是数理逻辑领域中的佼佼者,但他们首次合作并没有产生什么成果。当然,数学研究就是这样,失败才是正常情况,甚至可以说,数学研究就是在不断的失败上前进的。

幸而,图灵在数学上的兴趣不仅限于数理逻辑。从冯·诺依曼听来的一个有关群论的问题引起了图灵的兴趣,他很快就解决了这个问题,令冯·诺依曼对他大加青眼。也幸亏有了这个群论问题,图灵在普林斯顿的第一年不算颗粒无收。

但图灵最希望做的,还是有关数理逻辑的问题,他希望继续留在普林斯顿,跟随丘奇继续研究,虽然剑桥也有着强烈的吸引力。在再三的劝说后,他又申请了第二年的奖学金。这次,因为有冯·诺依曼的保荐,结果毫无悬念。

值得玩味的是,冯·诺依曼的信中只字未提图灵在数理逻辑方面的成就。但以后见之明看来,图灵在可计算性理论上的工作,远远比他在群论上的工作意义重大而深远。此中对比,意味深长。然而我们不能说奖学金的管理者做错了什么,只能说他们错失了一段佳话。

图灵在普林斯顿的生活踏入第二年。作为博士导师的丘奇,向图灵提出了一个新的题目:探求超越哥德尔不完备性定理的方法。

图灵再次抓住了这个机遇。

一致的扩充

哥德尔的不完备性定理(参见希尔伯特之梦,以及梦的破灭以及计算的极限(零)),其实描述的就是数学本身的界限。在此之前,数学家认为真理必可达到,而希尔伯特的那句“我们必须知道,我们必将知道”,正是这项信念奏出的最强音。但哥德尔打破了这种幻想,他证明了,对于强得足以包含算术而又不自相矛盾的数学系统而言,“真”与“可证明”是两个彻底不同的概念。在这些系统中,存在着无法证明的真理。

哥德尔的不完备性定理有两条。

第一,一个“合适的”包含了算术系统的数学系统不可能同时是一致和完备的,也就是说,如果它没有自相矛盾,那么必定存在这样的命题,它们是真的,但无法证明。

第二,在这样的系统中,我们可以将“系统本身没有自相矛盾”表述为系统中的一个命题,而这个命题正是一个无法被证明的真命题。假设我们有一个包含算术系统,但又没有自相矛盾的数学系统T,我们将表达“T没有自相矛盾”的命题记作Cons(T),那么,哥德尔的第二不完备性定理说的就是Cons(T)在T中无法被证明。

你可能会有这样的疑问:如果把Cons(T)当作一条公理加进T中,那么得到的新系统不就能证明T没有自相矛盾了吗?这是否与哥德尔的定理矛盾?

但如果将Cons(T)作为新的公理,我们研究的公理系统就不再是T,而是另一个系统T_1 = T \cup \{Cons(T)\} 。虽然在新的系统T_1中的确能证明Cons(T),但它只表达了原有系统T没有自相矛盾,而对于新系统T_1,它不能表达这一点。结合了新的公理之后,表达系统本身没有自相矛盾的命题同样会产生变化。这就像一场猫捉老鼠的游戏,我们自以为封死了一切退路,把猎物逼进了墙角,但事实却是按下葫芦浮起瓢,在我们不知道的地方又出现了新的漏洞,狡猾的猎物得以全身而退。

值得一提的是,这种对公理系统的扩充方法有其独特之处:虽然新的系统比原来多了一条公理,阐述了原有体系的一致性,的确使公理系统变得更强大,但在某种意义上,这又是最保守的扩充方法。它仅仅假定了原有系统的一致性,看似没有引入什么新的知识,而得出的新系统的一致性也与原来的系统相同:如果原有系统是一致无矛盾的,阐述这一点的新公理自然不会引发矛盾;而如果原有系统本身就存在矛盾,那么它能证明一切命题,无论是真是假,那么加入新的公理也不会改变这一点。

这可能不是最有趣的扩充方法,但却是最稳妥的。如果随便添加公理,我们得到的更有可能得到的是一个自相矛盾的无用系统。与其矛盾,不如稳健。

但要用这种方法在系统内部证明自身的一致性,实际上并不可行。的确,我们可以多次重复添加公理的过程,得到从T_1T_2开始的一系列理论系统,但它们的一致性是相同的,都依赖于起始的数学系统T,而且这一点是可以证明的。既然在起始的系统中不能证明自身的一致性,那么之后的一系列系统,无论重复多少次,都不可能证明自身的一致性。

那么,如果我们重复无限次,添加无限条公理呢?这样的话,无论使用了多少条公理,总有比它们更大的一条公理将会断言前面公理的一致性,一环扣一环,直至无穷,整个系统岂不是无懈可击?

系统的证明

从某个理论T_0 = T 开始,逐次添加关于新理论一致性的公理Cons(T_i) ,不断得到T_1 = T_0 + Cons(T_0), T_2 = T_1 + Cons(T_1), T_3, \ldots ,一直到最后包含无穷条公理的T_\infty ,其中每一条公理都有更大的公理来断言它的一致性。似乎我们就得到了一个超越哥德尔不完备性定理的数学系统。

但事情当然不会那么顺利。

首先,在包含无穷条公理的数学系统中,如何在系统内部谈论它的一致性,这并非顺理成章。的确,从理论上来说,包含任意的无穷条公理的数学系统是存在的。但如果要在这种系统内思考,很快就会遇到困境。先不说在系统中进行推理,就算是阅读一个证明,也并非显然。要理解这一点,需要对“形式证明”有更具体的理解。

一个数学系统内的形式证明,实际上是一串有限的命题组合,其中的命题要么是系统内的公理,要么是此前命题明白无误的简单逻辑推论,而最后出现的命题就是这个形式证明要得出的结论,也就是要证明的定理。这种一环套一环的组合方式,恰好保证了最后结论的正确性。而我们在阅读一个形式证明时,也只需要顺次检查这些命题,看看每一个命题是否本身就是公理或者此前命题的推论,就能验证这个证明的正确性。

而如果要在系统内部用命题表达系统本身的一致性,就要用到哥德尔在证明他的不完备性定理时用到的技术。简单来说,我们需要“阅读证明”的这个过程能够完全机械化,即使将人脑换成图灵机,也可以完成类似的验证。但如果数学系统本身包含无穷条公理的话,这个机械的阅读过程可能甚至连第一步都无法开始:如果有无穷条公理,那么面对一个命题,又如何知道它是否一个公理呢?

打个比方,数学系统好比是座仓库,里边装的都是公理。现在有人给我们一件东西,比如说一本书,我们的任务则是查看仓库里是否有一模一样的存货。如果仓库里只有有限样东西,一个个清点总能完成任务;但如果仓库容纳了无数物件,即使仓库的确有相应的存货,如果清点的次序不当,也有可能永远也碰不上我们的目标。

同样,要判断某个命题是否给定的数学系统中的公理,如果公理只有有限条,那么一个一个比较,总能在有限时间内判断出来。但对于无穷条公理的情况,这种方法有着严重的缺陷。如果检查的命题的确是公理,那么有朝一日总会停止;但反过来,如果我们检查了很久,仍然没有找到它是公理的证据的话,因为我们没有清点公理的一般方法,所以同样无法断言是否有遗漏。

所以一般而言,在一个包含无穷条公理的数学系统中,我们甚至无法在有限时间内机械地判断一个证明是否正确。尽管形式上仍然可以对形式证明进行定义,但我们几乎无法有效地考察这样的定义。同样,在这类系统中,有关形式证明的概念,尤其是系统本身的一致性,也如同处于矛盾中的说谎者,根本无法被表达。在这些系统中,难以谈及有关证明论的问题。

然而,在数学家们平常使用的数学系统中,不乏包含无穷条公理的例子。其中包括策梅洛-弗兰克公理系统,它被认为是现代数学的公认基础;还有皮亚诺算术的一阶逻辑版本,这个版本在数理逻辑的研究中经常出现。虽然这些系统同样包含无穷条公理,但数学家们在使用这些系统进行证明时没有一丝的踌躇,似乎其中形式证明的意义理所当然,与我们之前的结论背道而驰,这又是为什么呢?

答案很简单:这些数学系统拥有特殊的性质,虽然包括无穷条公理,却能在有限的时间内判断某个命题是否其中的公理。在数理逻辑中,这些系统被称为可有效生成的公理系统。

“可有效生成的公理系统”,顾名思义,这种系统里的公理都是可以“有效生成”的,也就是说,存在一台图灵机,可以“生成”所有的公理,将它们一一打印到纸带上,而打印出来的命题则必定是系统中的公理。可以说,这样的公理系统可以约化为一台图灵机。

回到仓库的比喻的话,一个可有效生成的数学系统同样是公理的仓库,但其中有着某种规律。比如一个包揽全世界所有书的仓库(它的别名叫图书馆),要判断某样物品是否有存货就太简单了:只要是书,那就有存货;如果不是书,那就没有。无需费力找到具体的对应,但同样可以确定仓库中是否存在相同的存货。

如果一个数学系统是可有效生成的,那么可以构造一个图灵机来判断某个证明是否正确。它能仅仅承认那些系统内正确的证明,对于错误的证明则一律拒绝。那么,即使有无穷条公理,我们仍然能通过这台图灵机考察关于形式证明的性质,从而可以谈论所有有关证明论的问题,包括我们关心的系统一致性。

而我们希望讨论的扩充系统,也就是通过无穷次扩充得到的数学系统,的确是一个可有效生成的系统。所以,我们对它一致性的讨论是有意义的。

对于读者来说,可能会感觉这些围绕着无穷条公理的讨论仅仅是一种吹毛求疵。但对于数学,特别是数理逻辑而言,精确性无比重要。在日常生活中,我们使用的语言太模糊太杂乱,人们的本意常常迷失在语言当中,有时连人本身都不理解口中的言说。但在数理逻辑中,一切含糊都被符号明晰,没有歧义,没有矛盾,对就是对,错就是错。这种确定性,正是数学真理性的所在。

有限的障壁

无限扩充得到的公理系统T_\infty ,虽然能在其中表达系统本身的一致性,但它的一致性却不像我们想象中的那么显然。虽然对于其中的每一条新公理Cons(T_k) ,都有比它更强大的另一条公理Cons(T_{k+1}) 保证它的一致性,但这真的能证明包含无数条新公理的系统是一致无矛盾的吗?

我们重温一下一致性的定义:一个公理系统是一致无矛盾的,当且仅当系统中不存在对于假命题的证明。也就是说,无论系统有多大有多复杂,只要系统本身不能证明任意一个假命题,比如说“1=2”,那么这个系统就是一致的。

我们现在尝试考虑无限扩充得到的公理系统T_\infty 。要超越哥德尔不完备性定理,就需要在系统内部证明有关系统本身一致性的命题Cons(T_\infty) 。假设系统中存在一个这样的形式证明P ,这意味着什么呢?

我们知道,形式证明的长度是有限的,毕竟无论是人类还是计算机,都无法完整阅读无限长的证明。所以,证明P 用到的公理也只有有限条。既然有限,那么其中形如Cons(T_k) 的公理也有限,对应的k 必然有一个最大值,不妨设为N 。那么,证明P 中的所有公理,在更小的系统T_{N+1} 中早已存在,所以证明P T_{N+1} 中同样有效。也就是说,仅仅在T_{N+1} 中就可以证明T_{\infty} 的一致性,它也蕴含了更小的系统T_{N+1} 的一致性。

也就是说,因为形式证明的长度是有限的,如果无限扩充后的系统T_\infty 能超越不完备性定理,证明它自身的一致性,那么在之前有限次扩充中,必然已经存在一个系统,它能证明自身的一致性。根据之前的论述,这也表示一开始的出发点——也就是系统T ——也能证明自身的一致性,而这是不可能的。

尽管我们尝试用无限来突破不完备性定理,但名为“有限”的障壁挡住了我们的去路。

在某种意义上,我们能够处理的,只有“有限”,而无法处理真正的“无限”。那些我们看似能抓住的“无限”,实际上也只是通过某种“有限”的手段确立的。而在“无限”的海洋中,我们无法辨别的,远多于我们能认识到的。

我们无法认识一切,相对地,我们永远有着等待探索的世界。

既然从一致性的方向无法突破,那么从另一个方向呢?哥德尔不完备性定理断言,对于合适的数学系统而言,一致性与完备性是两立的,那么,是否可以不停地扩充系统,在保证一致性的前提下,使它能证明越来越多的命题呢?最后又是否能得到一个完备的系统,在其中可以证明所有真命题呢?

为了回答这个问题,图灵将眼光投向了无穷的彼岸。

计算的极限(四):机械计算的圭臬

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/85861

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界

殊途同归

大洋彼岸寄来的论文,对于图灵来说,并不是什么好消息。在看到丘奇的论文后,图灵有过何等反应,至今恐怕已不可考。面对着一位在数理逻辑方面已然小有名气的职业数学家,与自己一起独立发现了相同的突破性结果。往好处想,这说明图灵自己的水平已经达到了当时数理逻辑研究的前沿;往坏处想,重复了别人的结果,哪怕是独立发现的,似乎都有些不对味儿。

然而,在下定论之前,图灵还有一件事情要搞清楚。他和丘奇对“可计算性”的定义,分别建筑在图灵机与λ演算之上。那么,在不同的基础上定义的两种“可计算性”,是貌合神离还是本为一体?

图灵机与λ演算,两者似乎都在平平无奇中暗藏玄机。作为计算模型,它们有很多相似之处,比如自我指涉的能力。但它们看起来又是如此不同,图灵机是一台在工程上能建造的机器,而λ演算则是一个彻头彻尾的数学模型。看起来,要回答这个问题,并非易事。

Lambda演算

图灵机模型

图灵知道,丘奇也知道,他们已经踏入了一个新领域。昔日希尔伯特在他的二十三个问题中,一语带过的那个“机械化的运算”,即将被赋予精确的数学含义。但正因如此,踏出的第一步必须慎之又慎,尤其对于“可计算性”这个最基础的定义,必须做到毫不含糊。为此,为了消除模棱两可之处,图灵机与λ演算是否能力相当,这是个必须回答的问题。

知己知彼,百战不殆。为了解答这个问题,图灵开始钻研λ演算,试图弄清到底λ演算能计算什么。终于,他证明了,所有λ演算能计算的函数,他的图灵机也能计算,反之亦然。也就是说,λ演算与图灵机的计算能力是等价的,两种模型定义的“可计算性”实际上殊途同归。他将这个结果作为附录补充到了他的论文。

对于图灵来说,这既是个坏消息,也是个好消息。坏消息是,他的结果与丘奇的重复了,对于发表文章来说,这不是什么好事情。好消息是,他的结果与丘奇的重复了,但他对可计算性的定义与丘奇的截然不同,而且两种看似毫无关系的定义,在实质上是相同的,这说明,他们对可计算性的定义,这最初的一步踏出的方向是正确的。一个人提出的定义很可能忽视某个方面,但现在两个截然不同的定义引向相同的结果,在交叉印证下,几无出错之虞。

可以说,图灵的工作面世之日,正是可计算性理论呱呱坠地之时。

也难怪纽曼教授一开始不相信图灵的工作。仅仅二十出头,刚刚踏入科学界的年轻人,就解决了如此重要的问题,而且为一个全新的领域立下了奠基石,这种人,即使在剑桥这个英国顶尖学府,也可谓难得一见。倒不如说,一开始不相信,这才是正常的反应。

但即便不相信,数学证明就是证明。即使纽曼教授并不专精于数理逻辑,还是能看出图灵论文的过人之处。他决定为图灵争取发表的机会。

这并非易事。因为从结论上说,图灵重复了丘奇的结果,所以最初联系的几个期刊的编辑都婉拒了纽曼的要求:他们只看到了论文的结论,没看到论文的精髓。最后,纽曼找到了当时伦敦皇家学会学报的编辑,经过三催四劝,终于说服编辑发表图灵的文章。

《论可计算数,及其在可判定性问题上的应用》,图灵的这篇文章,后来被认为是伦敦皇家学会学报发表过的最重要的文章之一。

伦敦皇家学会学报

万变之宗

乘着远洋货轮,图灵的论文很快传到了大洋彼岸,在普林斯顿掀起了一阵旋风。

在普林斯顿高等研究院的哥德尔,与丘奇有过不少碰面的机会。他读过丘奇的论文,大概也听过丘奇本人介绍他的λ演算。但哥德尔对λ演算一直颇有微词。实际上,作为一种计算模型,λ演算从未得到他的认可。它与人们日常接触到的“计算”毫无相似之处,更像是符号的堆砌和推演。虽然其中的计算的确可以机械性地完成,但要证明这一点绝非易事。事实上,这是一个远非显然的定理,证明也相当复杂。总而言之,λ演算并不像机械的计算,更像智慧的推理。

实际上,哥德尔自己也有一套“机械计算”的模型,那正是他在证明哥德尔不完备性定理时发展出来的递归函数体系。这套体系将“机械计算”定义为递归函数能计算的内容,而递归函数,顾名思义,就是可以用某些递归方式定义的整数函数。但哥德尔对他自己的模型同样不满意,原因同样是他的模型似乎需要太多的聪明才智,不像一台机器。

但图灵的论文瞬间就令哥德尔为之折服。

任何人,只要看一眼图灵机的定义,都会认同图灵机的计算完全是机械演算,完全可以造出一台可以运作的实际的图灵机。而更重要的是,图灵机抓住了“机械计算”的神韵。

机械计算是什么?是机器可以做出的计算。但机器可以千奇百怪,要用三言两语抓住本质,似乎不太可能。那么,何不反其道而行之?与其想像这些机器共有的特性,不如寻找它们共有的限制。

这正是图灵在论文中的做法。他总结了以下几个机器计算的限制:

第一:一台机器只有有限个可以分辨的状态;一台机器能分辨的表示数据的符号只有有限种。

开关或开或合,电路或通或断,中间的变化是跳跃式的。即使是连续的电信号,由于不可避免的热噪声影响,通过测量能分辨出的状态同样只有有限个。虽然现代的计算机看似有无限可能,但这只是幻觉。CPU和内存中的电路,数量虽然庞大无比,但总归是有限的,它们的通断形成的不同状态亦是如此。同理,虽然符号、信号在细节上可以有无数种变化,但由于精度等问题,即使是人,也无法事无巨细将所有细节一一分辨出来,更何况机器。

第二:机器的每一步操作需要的时间有一个下限,而每次操作最多只能读入与改写外部有限个符号。在某次操作读写某处的符号后,下一步机器读写的符号与之前符号的距离应该是有界的。

由于物理的限制,不存在速度无限的物体。无论任何机器,都不能在有限的时间内作出无限次操作,当然也不可能有无限次读入与改写。同样,读写头移动的速度是有限的,所以两次操作读写符号的距离当然也有限制。

第三:在某步操作中,机器的行动完全取决于它当时的内部状态以及读取到的符号。

机器就是机器,它应该做的,就是按照预先规划的图纸一步一步执行。没有异想天开,没有灵光一现,只有照章办事,只有步步为营。

这几个限制看起来相当合理,甚至显得理所当然。但就从如此平平无奇的限制出发,图灵用缜密的逻辑说明了,一台服从这些限制的机器能计算的问题,必定可以用一台特定的图灵机解决。也就是说,任何一台服从这些限制的机器,无论设计如何精巧,构成如何复杂,它的计算能力都不可能超越图灵机,无一例外。

我们甚至可以说,图灵机的设计本身,正是这些限制的一种体现。图灵很可能一开始就意识到了这些限制,再由此出发,去定义他的图灵机。哥德尔之所以对图灵机击节叹赏,大概也正因蕴含在它定义中的,图灵对“机械计算”的深刻洞察。相比之下,虽然与之等价的λ演算也尚算精致,但对于“机械计算”只得其形未得其神,显然逊色不少。

现在,希尔伯特在他的问题中那模糊的“机械计算”,终于有了一个精确的定义:机械计算,就是图灵机能做的计算。这又被称为图灵-丘奇论题,正是可计算性理论的奠基石。

除了λ演算与递归函数以外,还有许多计算系统与图灵机等价。波斯特对应问题,计数器机,马尔可夫算法,甚至元胞自动机,这些计算模型都与图灵机等价。但以我们的后见之明来看,图灵机仍然是机械计算最自然最有用的模型之一。

最小的通用图灵机

也正因这篇论文,图灵得到了到普林斯顿读博深造的机会,在丘奇的指导下,得以继续探索可计算性的无限可能。在大洋彼岸等待图灵的,又是可计算性理论的一篇新章。

(如非说明,图片均来自维基百科)

从玩具陀螺到终极理论

本文已于《艺术世界》杂志发表,禁止转载。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/82139

二十年前的小朋友很好哄,一个陀螺就能打发一下午的时间。大江南北,似乎都有这种转啊转的玩具。记得曾在书上读到,东北小朋友在冰上玩的陀螺要用鞭子抽。身处南国的笔者,冰面与鞭子都未曾见过,而见过的陀螺也都是塑料的,用手一拧,在桌上就滴溜溜地转起来,颜色混合而又慢慢分离,变幻摄人眼球。

还记得有一种会倒立的陀螺,一开始大头朝下转着,慢慢地整个陀螺就会翻过来,变成大头朝上。在科普大师马丁·加德纳的书中,也有提到到这种会倒立的陀螺。玩意虽小,也给世界各地的人带来过乐趣。

那么,陀螺为何转而不倒?也许你会回答,角动量守恒。

通俗来说,角动量守恒就是旋转中的物体倾向于绕着相同的旋转轴,以相同方向继续旋转。如果没有外力作用,旋转永不休止。也就是说,旋转本身也有一种惯性。轻轻推一下旋转中的陀螺,它也只会开始摇摇晃晃,而不会立刻倒下来。

地球本身是个更宏观的例子。数十亿年来,地球围绕着太阳公转,围绕着地轴自转,未有一刻歇息。公转而有春夏秋冬,自转而有昼夜晨昏,日常熟悉的这一切变化并非理所当然,它们来自太阳系形成时,星云旋转的角动量。

但在人力所及之处,要归纳出这个看似简单的定理,竟也花了不少时间。究其原因,我们的世界是如此不完美,摩擦力无处不在,不断消磨着各种运动,以至于大贤亚里士多德竟会认为力是维持物体运动的必要条件,并且整个西方世界这样一错就是一千年。

人们第一次窥视到角动量的一鳞半爪,还是在星空中,那里星体的运动没有摩擦力的阻碍。发现者则是一位眼睛不好的天文学家——开普勒。他自己做不了观测,但他的老师第谷留下了需要的所有资料。天行有常,而在纸堆中,他发现了行星的“常”,也就是后人口中的开普勒三定律,阐述了行星围绕太阳旋转的规律。而其中的第二条——无论在轨道何处,行星与太阳的连线在相同时间内扫过的面积相同——实际上就是角动量守恒的体现。

之后的牛顿更是将开普勒的工作发扬光大。他的力学三定律以及万有引力,用可以计算的公式诠释了开普勒的发现。而在牛顿力学中,人类终于完全抓住了旋转的规律,可以随意计算有关旋转的一切,而角动量守恒也成为了理所当然的推论。

对于客观规律,感性认识只是不甚可靠的第一步,可以量化并计算的理论却有着实实在在的用处。发电机和电动机利用旋转的力量,转化着不同形式的能量,构成了现代文明的基石。而在设计中,对旋转的计算直接关系到机械的安全和性能。

陀螺仪则是对于角动量守恒最为直接的应用。强有力的转动使它指向固定的方向,无论是大风大浪还是火箭发射,都不能使它的指向偏离一分半毫。也唯有如此,它才能指引船只、飞机甚至宇宙探测器沿着指定的方向航行,到达最终的目的地。

角动量守恒是如此自然,人们理所当然地接受了它。

但有一位数学家并不接受这种理所当然,她叫埃米·诺特。

Noether

作为一个女数学家,生于19世纪末的德国并不算件好事情。直到20世纪初,男女同校仍被视作会“颠覆学界秩序”的举动,而大学教授仍是男性的专利。对诺特而言,即使她的父亲就是数学教授,即使她才华横溢,求学也并非理所当然。她只能旁听,而且还要取得教授的许可。

即使获得了博士学位,即使指导者是当时有着“不变量之王”美称的大数学家戈尔丹,即使工作受到了广泛的肯定,在毕业后最初的七年,诺特的收入仅仅来自家人的接济。她工作的机构,埃朗根数学研究所,从未向她支付过工资。

一分钱都没有。

在1915年,事情似乎有了转机:两位数学巨擎,希尔伯特与克莱因,邀请诺特到当时数学界的中心——哥廷根大学——工作,研究广义相对论的数学。当时爱因斯坦还在摆弄他的场方程,苦恼于其中的一些异常之处,而希尔伯特也在摆弄相似的场方程。他们希望诺特在不变量理论方面的造诣,能帮助厘清广义相对论中的数学。

这无疑是对诺特才华的肯定。

但当时的哥廷根更关注诺特的性别。希尔伯特希望为诺特谋得一个私人讲师的职位,但哥廷根的教授们显然不希望有女人进入他们“神圣”的大学。他们的借口之一是“不希望我们的士兵回归大学后,发现竟要向女性求学”。向来沉稳的希尔伯特也不禁大动肝火,并说出了那句著名台词:“我不明白候选人性别与私人讲师资格有何相干,毕竟这里是大学,不是澡堂!”但要改变那帮老顽固,一年半载是不可能的。诺特的课程只能挂上希尔伯特的名义才能开讲。她仍然没有职位,仍然没有收入,仍然需要家人接济。

然而希尔伯特毕竟是伯乐,诺特甫一开始在哥廷根的工作,就在数学物理方面崭露头角。

黑洞模拟图

粗略地说,广义相对论的新思想在于“时空会随着物质弯曲”的概念,但要将这些抽象的概念转化为实实在在的数学方程,是件异常困难的事:需要新的数学工具,需要新的数学想法,而且还要排除时不时冒出来的那些物理上不可能的性质。希尔伯特发现他的场方程中,正出现了看似不可能的毛病。在经典物理中理所当然的守恒量,比如能量、角动量,在他的场方程中似乎不再守恒。到底这是致命的缺陷,还是新定律的喻示?希尔伯特期望诺特解决的,就是这样的问题。

也许这种问题正适合诺特来回答。毕竟,她仅仅是踏在科研路上这个事实,就已经冲击了当时多少人心中那陈腐的“理所当然”。

而诺特的回答优美得令人震惊。她发现,守恒量的存在并非理所当然,而是宇宙规律对称性的体现。无论任何物理理论,只要符合某种对称性,那么这个理论中一定有一个对应的守恒量,这个量不会随着时间而变化。如果物理定律在时间长河中的每一个时刻都相同,它就有着所谓的“时间平移不变性”,对应着的守恒量就是能量。如果指向茫茫宇宙任何一个方向,物理定律仍然不变,那么它就有着“旋转不变性”,对应着的守恒量就是旋转的角动量。

无论什么宇宙,无论什么规律,有一个对称性,就有一个守恒量。而角动量,不过是旋转不变性所对应守恒量的名字而已。这就是诺特定理。

希尔伯特的场方程,仍然保有经典物理的对称性,但因为方程本身已改头换面,对称性所对应的守恒量也变得面目全非。经典物理中的守恒量不再守恒,这仅仅因为我们有新的守恒量,而并不构成新物理的障碍。

这就是诺特的答案,一个连爱因斯坦也大加溢美之辞的答案。

诺特定理为现代物理学打开了一扇新的大门。有了诺特定理,物理学家开始学会通过宇宙本身的对称性推测物理定律的性质。人们认识到,对称性是探究物理的指路明灯。

来自http://fafnir.phyast.pitt.edu/particles/conuni6.html

来自http://fafnir.phyast.pitt.edu/particles/conuni6.html

除了时空本身宏观的对称性以外,物理学家还开始探索各种局部的对称性。在量子场论中,人们发现除了时间和空间以外,物理定律在局部还依赖额外的量,有着额外的对称性。这些被称为“规范对称”的对称性,实际上可以看作更为抽象的数学空间中的旋转对称性,而它们也有着相应的守恒量。基于这些新的对称性,人们建立了一整套物理理论,被称为“规范场论”。

这套依赖对称性的物理方法,获得了前所未有的成功。四种基本力中的三种,都能用规范场论来解释,合起来就是目前最为成功的粒子物理理论——标准模型。正因为规范场论如此成功,一些物理学家认为能描述一切的终极理论应该也是一个规范场论,一个比标准模型有着更高对称性、更多对称美的规范场论模型。

没有人知道终极理论会是什么,但每个人都认为它一定拥有高度的对称美。而陀螺转而不倒,只是这种美的一个小小体现而已。

【如非特别说明,图片来自维基百科】

素数并不孤独

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/82114

数学是科学的女王,数论是数学的女王。

——高斯

数论,是研究数字的一门数学分支。如同大海,它清澈透明而又深不见底。它的基础概念,自然数、加法、乘法,每个小学生都清楚;但关于自然数的定理,却可以让人穷尽一生而不得其解。而这篇文章要介绍的,只是这个广阔海洋中一个小小的海域。即便如此,我们仍未知道此处海深几何,尽管最近张益唐的突破性工作,使我们比以往更接近真理,但这远远不够。

尽管笔者才疏学浅,有恐贻笑方家。但如能为读者勾勒出一点点数学之美,也不枉费一番心思。



素数何时成双对



可以说,素数是数论中最基础而最重要的概念。如果一个大于二的正整数,除了1和它本身之外,不是任何数的倍数,那么它就是一个素数。比如说,6不是一个素数,除了1和它本身以外,它还是2和3的倍数;而5则是一个素数。

在古希腊,人们已经有了素数的概念,对素数的研究也略有所得。在欧几里德的《原本》中,第七、八、九篇讲述的是“关于整数及其比值的性质”,实际上也就是数论。在这几卷中,欧几里德指出了今天所说的“算术基本定理”:将自然数分解成素数乘积的方法是唯一的。也就是说,如果用乘法的眼光来看自然数,那么素数就是自然数的最小组成单元。它们不能被分解成更小的数的乘积,而所有自然数都可以分解成它们的乘积。

那么,我们自然要问:素数作为自然数的组成单元,它们有多少个?

有无限个,欧几里德不仅回答了这个问题,还给出了一个经典的证明。

不妨反设只有有限个素数,考虑它们的积N ,它是一个有限的自然数。所以,N+1 也是一个自然数,它也应该是一些素数的积。但根据假设,每一个素数都不整除N+1 ,这不可能!所以,素数必定有无限个。

这个精巧的证明,是人类探寻素数奥秘的第一步。

2、3、5、7、11、13……最初的几个素数,要找出来并不困难,但随着数字增大,如果一个一个数字按照定义去筛选是否素数,工作量会很快变得十分庞大。同为古希腊数学家的埃拉托色尼,给出了一个比较省力的算法,后人称之为埃拉托色尼筛法。

首先,列出从2开始的数。然后,将2记在素数列表上,再划去所有2的倍数。根据定义,剩下的最小的数——在这里是3——必定是素数。将这个数记在素数列表上,再划去所有它的倍数,这样又会剩下一些数,取其中最小的,如此反复操作。最后剩下的都是素数。

埃拉托色尼筛法

当古希腊人用这种方法计算出长长的素数列表时,他们也许也曾惊异于素数分布的秩序缺失。这些自然数的组成单元,在自然数中的排列却毫无规律,时而靠近,时而疏远。用类似欧几里德证明中的构造,我们知道,两个相邻素数之间的距离可以要多大有多大。而随着数目越来越大,相邻素数之间的距离似乎也越拉越长。

在无限延伸的自然数集中,向无穷的地平线望去,虽然仍有无穷的素数,但它们似乎也愈变孤独。

这种孤独甚至是可以度量的。在十八世纪的尾巴,年仅15岁的高斯独立提出了一个猜想:在n附近素数的密度大约是n的对数。也就是说,相邻素数之间的平均距离大概与它们的对数成正比,虽然增长很慢,但却义无反顾奔向无穷。但即使是高斯,也无法严格地证明他的猜想,要等两个世纪后的阿达玛(J. Hadamard)和德拉瓦莱普森(C. J. de la Vallée-Poussin),才能将这个猜想变成现在的“素数定理”。

虽然如此,偶尔也会有成对出现的素数,它们之间只相差2。像这样成对出现的素数,在那些孤独的同伴看来,无疑是异类。

它们被称为孪生素数。



漫天星河难理清



一个自然的问题是,孪生素数有多少?

孪生素数猜想断言,有无限对这样的孪生素数。但还没有人能严格地证明这一点。在1849年,数学家A. de Polignac甚至猜想,对于任意的偶数2k ,都有无数对相邻的素数,它们的差恰好是2k

这不是一个容易的问题。素数是乘法的产物,而孪生素数的定义则涉及到加法。即使只是加上2,也需要同时用到自然数的加法和乘法的性质。而在数论中的很多看似简单但无比困难的问题,比如哥德巴赫猜想和华林问题,核心也在于加法和乘法的交织。这种相互作用给数论学者们带来了无穷的头痛,以及对咖啡的无尽渴求。

与此同时,行外人的评价却似乎异常中肯:“为什么素数要相加呢?素数是用来相乘而不是相加的”。

当然,如果只将素数用在只与乘法有关的问题上,事情当然简单得多。但如果我们想要更多地了解自然数的玄机,那必然涉及到加法和乘法的相互作用。缩在“容易”的圈子里从来无补于事。如同探险家一般,数学家也有着征服难题的渴望,因为在那困难的山巅上,有着无尽的风光。为了难题产生的新方法、新思想,可能会开辟出意想不到的新天地。

素数在二维平面的一种表达

孪生素数的难点在于,它是一个关于素数的具体分布的问题,而我们对素数的具体分布知之甚少。素数定理只告诉我们素数的大体分布,而对于具体一个个素数的位置却无能为力。如同繁星,素数点缀着自然数的夜空,放眼望去,它们朝向无限的地平线愈见稀薄。但要想分清这无限繁星中的每一颗,即使用上最好的望远镜,也无可奈何。

所以,在很长一段时间里,对于孪生素数猜想,人们仍然停留在揣测和估计的层面。

首先尝试直接猜测的,是英国数学家哈代(G. H. Hardy)和李特尔伍德(J. E. Littlewood),他们在1923年开始了一系列的猜测。

G. H. Hardy

素数定理告诉我们,对于足够大的自然数N,在N附近随机抽取一个自然数n,它是素数的概率大概就是(\ln N)^{-1} 。那么,在同样的区间,随机独立选取的两个数都是素数的概率就是之前概率的平方,也就是(\ln N)^{-2}

那么,在N附近随机抽取一个自然数n,n和n+2是一对孪生素数的概率是否就是大概(\ln N)^{-2} 呢?很遗憾,并非如此,因为n和n+2并非完全独立的,所以不能直接应用之前的结果。不过这个估计虽不中亦不远,只要乘上一个修正系数,借此表达两个数相差2的性质,就能得到对孪生素数密度的估计:2 C_2 (\ln N)^{-2} 。在这里,修正系数C_2 是一个关于所有质数的无穷乘积。如果密度确实如此,那么显然有无限对孪生素数,孪生素数猜想应该是正确的。

实际上,这是所谓“第一哈代-李特尔伍德猜想”的一个特殊情况,难度甚至远高于孪生素数猜想:它不仅隐含了孪生素数猜想,而且对具体的分布作出了精细的估计。虽然上面的论证看上去很诱人,但它并不是一个严谨的证明,因为它的大前提——素数是随机分布的——本来就不成立。素数的分布有着深刻的规律,远远不是一句“随机分布”所能概括的。

但哈代和李特尔伍德并非等闲之辈,作为当时英国的学科带头人,既然提出这个猜想,当然经过了深思熟虑。现在看来,依据之一是,望向无限,素数的分布的确看似随机:对于那些“简单”的操作(比如说加上2)来说,数值越大,越靠近无限的地平线,看上去也越“随机”。所以,在考虑各种素数形式的分布时,假定素数按照素数定理的密度随机分布,不失为一个估计的好办法。更为重要的是,数值计算的结果也与哈代和李特尔伍德的猜测所差无几。这更增添了我们对这个估计的信心。

然而,猜测只是猜测,不是严谨的证明。无论用数值计算验证到什么高度,有多符合,对于无限而言,都是沧海一粟。李特尔伍德本人就曾证明过一个类似的结论。

人们此前猜测,小于某一个数N的素数个数\pi(N) 必定小于所谓的“对数积分”函数\mathrm{li}(N) ,而根据素数表,这个规律直到10的14次方都成立。但李特尔伍德在1914年证明了一个惊人的结论:对于足够大的N ,不仅\pi(N) 可以大于\mathrm{li}(N) ,而且它们的大小关系会无穷次地逆转!但直到今天,对于第一次打破这个规律的N,我们仍然不知道它的具体数值,只知道它大概是个有三百多位的数。

这个例子足以说明素数可以多么深不可测而又出人意料,同时提醒我们,面对无限,不能掉以轻心。无论有多少计算的证据,都不能轻易下定论。征服无限的工具,只有严谨的数学证明。



狂沙淘尽始得金



既然难以知道孪生素数具体有多少,那么不妨换个思路:孪生素数最多能有多少呢?

这就是数学家的思路,如果正面久攻不下,那么就从侧面包围。当难以直接得到某个量时,数学家的“本能”会指引他们,尝试从上方和下方去逼近,证明这个量不可能小于某个下界,或者不可能大于某个上界。如此慢慢缩小包围圈,就有希望到达最终的目标。

而在1919年,挪威数学家布伦(V. Brun)走的就是这么一条路:他证明了,孪生素数的密度不可能超过O(\frac{N(\ln\ln N)^2}{(\ln N)^2}) 。籍此,他证明了所有孪生素数倒数的和是有限的。要知道,所有素数倒数的和是无穷大,可见孪生素数在素数中有多么稀少。人们将所有孪生素数的倒数和称为布伦常数,它的具体数值大约是0.87059…。

关于布伦常数,还有个有趣的小插曲。1994年,美国一位教授在计算布伦常数时,无意中发现当时英特尔公司的奔腾处理器在计算浮点除法时,在极稀有的情况下,会产生错误的结果。虽然英特尔声明这种错误对于日常使用来说不足为患,但对于消费者来说,这种托辞实在难以接受。最后,英特尔不得不承诺免费更换有问题的处理器。帮助发现硬件问题,这可算是数论在现实中的一个小小应用。

有FDIV问题的芯片

但布伦的证明意义远不止于此。他的这个证明,正是现代筛法的开端。

布伦所用的筛法,根源可以追溯到古希腊的埃拉托色尼筛法。还记得我们怎么用埃拉托色尼筛法列出素数表吗?每次获得一个新的素数,我们都要划去所有新素数的倍数,然后剩下最小的数又是一个新的素数。用类似的方法,我们可以估计在某个区间中,比如说在N 2N 之间,大约有多少素数。

首先,我们假设手头上已有足够大的素数表(大概到\sqrt{2N} 的所有素数)。用这个素数表,我们打算把从N 2N 的所有合数都划去一遍,剩下的就是素数。对于每个素数p ,我们将所有p 的倍数划去一遍。在N 2N 之间,对于每个素数p ,大约有N/p 个这样的倍数。当然,如果N 不是p 的倍数,这样的估计会有误差,但在数学家看来,只要能把握误差的大小,最终仍然可以得到正确的结论。

这样,剩下的数的个数就是N 减去所有N/p 的和,是这样吗?并不尽然,因为有些数可能被划去了几次。比如说1000,它能被2整除,也能被5整除,于是在处理2和5的倍数时,它分别被划去了两遍。对于每一对素数p_1, p_2 ,每个p_1 p_2 的倍数在之前都被划去了两遍,而我们只希望将它们划去一遍。为了得到正确结果,我们需要对这些数作出补偿:将这些数加回去,一共是N/p_1 p_2 个,加上一点点误差。

但这就是尽头吗?如果考虑三个素数的倍数,我们发现补偿得又太多了,需要重新划去;继续考虑四个素数的倍数,划去得又太多了,需要重新补偿……如此一正一反,损有余,补不足,一项一项估计下去,才能从自然数的海洋中,精确筛选出所有我们想要计算的那些素数。

但我们是否需要做到如此精细呢?在整个计算中,虽然每一项看似简单,但简单的代价是误差。虽然每一项的误差很小,但因为数目巨大,累土而成九层之台,累计误差可以比需要估计的量还要多。所以,在现代的筛法中,过于精细反而是一种累赘。况且,我们的目的是获得上界或者下界,所以结果无需完美,只需误差可控。一般而言,由于越到后面的项贡献越小,往往忽略它们的计算,直接将其计入误差。这样可以有效减少需要计算的项的数目,同时也能间接减少误差。当然,如果忽略的项太多,它们引起的误差又会太大,也会导致不够精确的结果。

布伦相对于前人的改进,正在于此。如果盲目计算所有的项,必然深陷误差的泥沼。而布伦则大胆截去那些贡献很小却占绝大多数的项,而对于剩下的项也果断采用更粗放的近似来简化计算。虽然看似不依章法,但通过仔细调校,布伦得以有效控制总误差,从而获得他想要的结果。

布伦的这个思路,开启了解析数论之中一大类方法的大门。我们不知道怎么数素数,是因为它们的分布实在难以捉摸。而现在,布伦的筛法指出了一条用简单的集合来逼近素数集合的道路,这自然令数学家如获至宝。

在更精细的筛选与更微小的误差之中寻找那一线的平衡,这大概是筛法的醍醐。但这样的平衡,显然依赖于我们如何估计每一项的具体数值。可以每项分开估计,但合起来也无伤大雅。无论做法如何,估计的误差越小,筛选可以越深入,结果也越逼近真实。即使估计方法不变,如果有更好的方法决定每一项的取舍,取贡献大而误差小之项,而舍贡献小而误差大之项,当然也能得到更好的结果。

但为何拘泥于每一项?对于每一项,为什么要么取要么不取,不能站在中间立场吗?只要能控制误差,将每一项拆解开来,根据贡献和误差来赋予不同的权值,再求和,这样的结果岂不是更精细?再者,有时不拘泥于素数,放松限制去筛选那些“殆素数”,也就是那些只有少数几个素因子的数,在某些情况下也能得到更好的结果。在严谨的前提下,只要能做出更好的结果,数学家对于突破原有思路毫不犹豫。

这就像一场对素数的围捕战。数学家们拿着筛法这个工具,不断打磨它、改装它,不断练习,正着用,反着用,与别的领域的工具配合着用,绞尽脑汁发明新的用法,殚精竭力用它来围捕那些调皮的素数。欲擒故纵,反客为主,无中生有,李代桃僵,数学家们在对各种各样素数的围捕中,借着筛法,将一套兵法使得淋漓尽致,精彩之处,三国亦为之失色。

在筛法的力量下,孪生素数终于露出了一鳞半爪:

在1920年,同样是布伦,证明了有无穷对9-殆素数,它们之间只相差2。所谓9-殆素数,或者更一般的k -殆素数,就是那些至多有k 个素数因子的自然数(包括重数)。而1-殆素数就是素数。模仿哥德巴赫猜想的记号,布伦证明的就是(9 – 9)。

在1947年,匈牙利数学家雷尼(A. Rényi)证明了,存在一个常数k ,使得有无穷对自然数m, p ,其中p 是素数,m 是一个k -殆素数,而两者之间只相差2。也就是说,他证明了(k – 1)。

在1950年,挪威数学家塞尔伯格(A. Selberg)证明了,有无穷对整数n n+2 ,它们的素因子一共至多有5个。而孪生素数定理相当于素因子至多有2个的情况。

在1966年,意大利数学家E. Bombieri与英国数学家H. Davenport证明了,孪生素数的密度至多是8 C_2 (\ln N)^{-2} 。也就是说,孪生素数的数量至多是哈代与李特尔伍德所估计的4倍。

陈景润

在1978年,在证明了哥德巴赫猜想的(1 + 2)后,陈景润用相同的筛法改进了雷尼的结果:他证明了,有无穷对自然数m, p ,其中p 是素数,m 是一个2 -殆素数,而两者之间只相差2。也就是说,他证明了(2 – 1)。

而最新的结果则是D. Goldston、J. Pintz和C. Yildirim在2009年发表的。他们证明了,两个素数之间的差距,相比起平均值而言可以非常小。在假定某个强有力的猜想后,他们还证明了,存在无限对素数,它们之间相差不过16,与目标的2只有八倍的差距。但问题在于,即便16这个数目相当诱人,但他们的假定过于强大,强大得不像是对的,也使人们对他们结果的信心打了个折扣。

在整个过程中,数学家们动用了解析数论中的大量工具:L函数、西格尔零点的估计、多种版本的筛法、克鲁斯特曼和的估计、自守形式,如此等等,不一而足。每样工具,都是心血的结晶。但即便如此,我们离孪生素数猜想还很遥远。尽管Goldston、Pintz和Yildirim的结果非常强大,但也不能在无假定的情况下,推出有无穷对素数,它们相差恰好是一个有限的确定值。

虽然只差那么一点点。只要关于所谓“素数分布水平”的引理稍微强一点点,就能得到有无穷对相差不远的素数的结论。但就在这个关口,人们却处处碰壁。希望就在伸手可及之处,却似乎总是差那么一点点。“此路不通”的想法开始弥漫开来。

在众人束手无策之际,当时默默无闻的张益唐向《数学年刊》提交了一份论文。



梅花香自苦寒来



一份三十公分的意大利面包,纵向剖开,抹上金枪鱼泥,放上四片奶酪,放到烤炉烤一分钟,撒上生菜,铺上酸黄瓜和番茄,包起来,切成两半,就是又一个三明治。

这也是张益唐曾经蹉跎的岁月。

张益唐

在博士毕业后,因为种种原因,虽有真才实学,但张益唐未能在学术界找到一份工作。为了生活,他不得不打工维持生计。即使在他的同学帮助他,找到新罕布什尔大学的一份代课讲师工作后,即使在转正成为一名大受学生好评的讲师后,正式而言他仍不是一名研究人员。

时运不齐,命途多舛;冯唐易老,李广难封。

但数学无需官方认可,研究也不需要正式的职位。张益唐受过正式的数学研究训练,有扎实的功底,有充分的能力,知道怎么去做研究,心里也时刻揣着数学。即使没有正式的职位,他骨子里仍然是一位研究数学的学者。

而他心里装着的,正是素数的分布问题,特别是孪生素数。即使没有正式的研究职位,他仍然做着一名研究者会做的事。他紧跟当前解析数论学界的发展,阅读了J. Friedlander和H. Iwaniec在筛法上的突破性工作,阅读了Goldston,Pintz和Yildirim关于素数间隔的工作,还有很多不同的新工作。他思考着新的方法,尝试沿着前人的路径走下去,相信能用新的技巧,把道路走通,证明有无穷对相差不远的素数。

但这谈何容易!即使从Goldston等人强有力的方法出发,要得到想要的结果,也难倒了众多学者。张益唐花了三年时间,不断尝试新的方法,屡战屡败,屡败屡战。数学研究,莫不如是。

终于,在2012年6月,他到朋友家作客时,灵光一闪,找到了开启关键的钥匙。

要说起来,张益唐的方法并非那种横空出世的新构想,而是利用现有的工具,用新的策略将它们组合起来,再加上一点点新的思想。Goldston等人所用的筛法相对精细,但却稍欠回旋余地,而张益唐稍稍放松了这个筛法,虽然能作出的估计稍欠精细,却换来了更大的游刃之余,得以对筛法中误差与精细的天平作出更精巧的调整,结合一些新的结果,特别是Iwaniec等人的工作,反而能获得更好的估计。箇中精彩之处,恕笔者学识浅薄,难以一一尽述。

用他的新筛法,张益唐证明了,有无穷对素数,它们相差不过七千万。他将他的新方法与新结论,用简洁明了的语言,写成了一篇论文,投稿到数学界的顶级期刊《数学年刊》。

这篇论文名为Bounded gaps between primes(《素数间的有界间隔》)。

收到这篇论文的编辑想必十分意外。在一所不起眼的大学做着讲师的工作,在数学的研究共同体中也不活跃,之前一篇论文还是十多年前发表的,这样的一位默默无闻的数学家,突然声称自己解决了一个困扰众多学者几十年的问题,引起的第一反应自然是怀疑。但毕竟,数学证明就是他学识的证明,他的论文写得如此清楚明白,而所用的方法又是如此合情合理,这冲破了原有的一点点怀疑。编辑认为,张益唐的结论很可能是对的,而他的方法对于解析数论而言,也可能是个重要的进步。

因为很多数学证明都相当艰深晦涩,即使是同一个领域的专家,有时也要花上一大段时间来咀嚼揣摩,才能断定证明是否无误。所以,数学论文的审稿时间通常不短,少则数月,多则数年,期间匿名审稿人通常需要通过编辑与作者多次通信,才能决定一篇论文的命运。而张益唐的论文是如此激动人心,编辑认为他们等不起如此漫长的时间,于是对他的论文进行了“特殊对待”。他们请了筛法方面的大家Iwaniec教授与另一位匿名审稿人(可能是Goldston)来审核这篇论文,很快就有了回音。

两位审稿人都认为这篇文章没有明显的错误。实际上,评审报告中写着这样的评价:“论文的主要结果是第一流的”,“在素数分布领域的一个标志性的定理”。从论文寄出到审稿结束,仅仅花了三个星期的时间。

自此,消息不胫而走。在哈佛大学的丘成桐教授,知悉这个消息之后,很快邀请了张益唐来哈佛做关于他的工作的学术报告。消息很快在数学界与新闻界传开,张益唐几乎是一夜之间,从默默无闻变成举世知名。据说,他的妻子听说有记者要采访时,跟张益唐讲的第一件事,就是把发型整理一下。

作为励志故事,这个结尾再好不过了。



路漫漫其修远兮



当然,故事仍未结束。

在数学界中,对于久攻不下的问题,一旦有人打破一个缺口,其他人很快就会跟进,把缺口弄得更大。张益唐的结果也不例外。

在张益唐的论文中,他给出的结果是,存在无数对相邻素数,它们的差相差不过7000万。但这只是一个估计,并非张益唐的方法能得到的最好结果。在论文出炉后,一些数学家吃透了新方法,开始试着改进这个常数。

张益唐的论文在5月14号面世,两个星期后的5月28号,这个常数下降到了6000万。

仅仅过了两天的5月31号,下降到了4200万。

又过了三天的6月2号,则是1300万。

次日,500万。

6月5号,40万,连原来的百分之一都不到。

在笔者写下这行的今天,剩下的只有区区的25万。

(注:截至6月23号的今天,常数已下降到12000,大约是原来的五千分之一

这些结果,可以说是互联网的结晶。这样快的改进速度,对于仅仅依靠一年发行数次的期刊做研究的时代,完全是不可想象的。而在今天,数学家们在网上,你一言我一语,不停发布最新的思考和计算,以最高的速度,汇聚所有人的智慧,才能创造出如此奇观。

张益唐带来的影响不止于此。利用他的新方法,可以解决更多的问题。Pintz指出,从张益唐的工具出发,可以得知存在一个常数C ,使得对于每C 个连续偶数,都存在无穷对相邻的素数,它们的差是这些偶数之一。也就是说,Polignac的猜想,起码对于1/C 的偶数来说是正确的。所以,不仅素数本身难以捉摸,它们之间的差更是剧烈起伏不定。

实际上,大数学家Erdős在1955年就猜测,相邻两对素数差的比值,可以要多大有多大,要多小有多小。而同样借助张益唐的工具,Pintz不仅证明了这个猜想,而且证明了比值之差以不低的速度趋向于两极分化。用他本人的话来说:在刚刚过去的几个月里,一系列十年前会被认为是科幻小说的定理都被证明了。

但孪生素数猜想本身又如何呢?我们知道,如果将张益唐论文中的常数从七千万改进到2,就相当于证明孪生素数猜想。既然现在数学家们将常数改进得如此的快,那么我们是否已经很接近最终的目标呢?

很遗憾,实际上还差很远。

张益唐的方法,本质上还是筛法,而筛法的一大问题,是所谓的“奇偶性问题”。简单来说,如果一个集合中所有数都只有奇数个素因子,那么用传统的筛法无法有效估计这个集合至少有多少元素。而素数组成的集合,恰好属于这种类型。

正因如此,当陈景润做出哥德巴赫猜想的突破性结果(1 + 2)时,他得到的评价是“榨干了筛法的最后一滴油”。因为如果只靠筛法,是无法证明哥德巴赫猜想的。(1 + 2)是筛法所能做到的最好结果。

但数学家们从不固步自封。要想打破“奇偶性问题”的诅咒,可以将合适的新手段引入传统筛法,籍此补上筛法的缺陷。张益唐的出发点——之前提到Goldston,Pintz和Yildirim的结果——正是这种新思路的成果。但对于孪生素数猜想而言,这些进展仍然远远不够。学界认为,虽然不能断定张益唐的方法,即使经过改进,是否仍然不能解决孪生素数猜想,但可能性似乎微乎其微。

但不能低估人类的才智。发明割圆术的刘徽,他对于无知的态度更适合我们:

敢不阙疑,以俟能言者!

参考资料:

Bounded gaps between primes, Yitang Zhang, Annals of Mathematics

Open question: The parity problem in sieve theory, Terence Tao, http://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/

Are there infinitely many twin primes?, D. A. Goldston, http://www.math.sjsu.edu/~goldston/twinprimes.pdf

关于相邻素数之差的笔记(张益唐及其他), 木遥, http://imaginary.farmostwood.net/592.html

Polymath上常数改进的页面:http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes

张益唐和北大数学78级, 汤涛, 数学文化

张益唐的照片来自新罕布什尔大学网站,其余图片来自Wikipedia。