解构与复原:望月新一与他的证明

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

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


fukugen

復原

在伊万·费先科(Ivan Fesenko)的“科普”文章里提到,在关于望月新一证明的讨论中,有一个词经常被提到,就是“復原”。在望月新一构建的崭新数学体系中,他将同时附着在“数字”之上的加法结构和乘法结构拆开,将两者各自变形,然后重新“復原”。这种做法,先从根本上消解,之后再““復原”,即使对于久经抽象推理沙场的数学家而言也相当奇怪。而望月新一的体系,正系于这种“復原”的可行性。

如果他的体系是正确的,如果他的“復原”是成功的,这将带来数学中代数几何分支的变革。比如说,ABC猜想的证明。比如说,最终理解加法和乘法之间的关系。但现在,没多少数学家能读懂他的证明。无论证明是对是错,也许数学界,至少是代数几何,恐怕难以复原为以前的面貌。他的体系,他的证明,已经将数学家拆开成不同的阵营,阵营内部不断发酵变化,引出了新的分歧。即使最后尘埃落定,得到的恐怕也只是望月新一式的“復原”。

但这就是数学前进的必经之路。

破题

望月新一的研究领域,是所谓的“远阿贝尔几何学”。如果只能用几十字解释这个领域的话,我只能这样写:

远阿贝尔几何学研究的是,有理数的绝对伽罗华群,以至任意代数簇的平展基本群,它们“远离阿贝尔”的部分,也就是不符合交换律ab=ba的部分,会如何影响相应代数结构的性质。

看不懂?很正常。要解释这个领域研究的是什么,可能需要整整一篇文章(请参看《小朋友的涂鸦》),还不一定能解释清楚。而为了写这篇文章,还要找一个远阿贝尔几何的专家,而不是像我这样搞组合数学的人。

是的,对于望月新一的体系,我,这篇大部分人很可能读不懂的文章的作者,只理解一点最基础的皮毛。对于一般人来说,我似乎是内行,但在数学界内部,我属于吃瓜群众。所以,如果真正的内行看到我写错了东西,请多多包涵。

但面对这个体系,很多数学家的境况并不比我好得多。包括菲尔兹奖得主陶哲轩,包括望月新一的恩师法尔廷斯,他们都抱怨望月新一的证明太简略太难懂。现在,据说懂得整个证明的,除了望月新一之外,只有十几个人,大部分在日本,其他在美国和法国。

大部分数学家,和这十几个人,就是目前的两个阵营。

抽象的极致

望月新一的体系,名为“宇宙際Teichmüller理論”(inter-universal Teichmüller theory),简称IUTT,有时候也省略对应“理论”的T,写成IUT。

他并没有特意发明这个略显中二气息的名字,这锅要由代数几何的先驱格罗滕迪克(Grothendieck)来背,是他发明了Grothendieck universe这个数学对象。而这个术语可能还要追溯到更久远的集合论先驱,因为它对应着集合论中“所有集合组成的一堆东西”这个概念。是的,所有集合不构成一个集合,只能说成“一堆东西”,或者用“类”这个术语。幸好,中文的翻译“全类”没有那么中二。用上这个翻译的话,中文可以写成“跨全类Teichmüller理论”。但为了原汁原味起见,我们后面还是用“宇宙”这个术语。因为,另一个universe的数学,总有些不一样。

我们从他此前研究的最最基础的结构,p进整数,谈起。

p进整数是什么?对于数学家来说最快捷易懂的定义,就是:

对于素数p,(\mathbb{Z}/p^n\mathbb{Z})_{n \geq 1}的投影极限

我第一次看到这个定义时,一下子就读懂了。这对数学家来说的确是好懂的定义,但对一般人就像外星语言。

绝望了?这就是我读望月新一的论文时,从第三页开始的感受,六百多页之中的第三页。

但p进整数毕竟没那么复杂,下面我试着解释一下。首先,我们来看一个p进整数的例子,取p=7,那么下面这几个数都是p进整数:

……00000000000000000042
……30211045064302335342
……12450124501245012450

是的,你没有看错,省略号在前面。每个p进整数,都可以看成一串向左边高位延伸至无穷的数。但它们并不是无穷,它们每个数都不相同,而这种写法是有意义的。

在p进整数上,可以定义加法和乘法。这里我们可以松一口气,因为它们的计算方式跟我们熟悉的一样(需要模p),从低位开始,然后慢慢进位计算,就像是永远做不完的加法和乘法。减法和除法同样由此定义。所以,p进整数跟我们熟悉的整数一样,都有四则运算。每个整数都对应一个p进整数,只消在整数的p进制表达式前面加上无穷个0,而它们的运算结果也与我们熟悉的运算别无二致。

奇怪的事情现在才开始。

1/5=0.2,显然不是整数。但它是一个7进整数:

1/5 = ……5412541254125412

震惊!图片来自pixabay

实际上,只要一个p进整数x个位不是0,那么它的倒数也是一个p进整数。可以求倒数这一点非常重要,这意味着p进整数,或者它的推广p进数中,拥有完整的加法和乘法结构。

奇怪的事情到这里还没有完。

我们可以定义p进整数的“绝对值”,或者说“大小”。我们来看看在p进整数中,几个自然数的绝对值。我们还是取p=7为例子。

0的绝对值是0,简直必然。

1的绝对值是1,没有问题。

2的绝对值是1……等等,发生了什么事?

什么鬼……图片来自flickr | Denise Mattox

3、4、5、6,它们的绝对值都是1。

7(也就是七进制的10)的绝对值是1/7,突然变小了。

8(也就是七进制的11)的绝对值是1,又回来了。接下来9、10、11、12、13的绝对值都是1。14(也就是七进制的20)的绝对值又变成了1/7。

就这样,如果不是7的倍数,绝对值就是1;如果是7的倍数,绝对值就是1/7。一直到49(也就是七进制的100),它的绝对值变成了1/49。加上一的50,它的绝对值又是1。

简单来说,对于p进整数,从个位开始有几个0,它的绝对值就是p的几次方分之一。对于p的幂,次数越高,数字越大,“绝对值”反而越小。

根据这个奇怪的“绝对值”,我们可以将所有p进整数看成一个空间,它的结构由这个“绝对值”,也就是两点之间的距离给出。但这是个怪异的空间:每个三角形都是锐角等腰三角形,而如果取一个球体的话,球体中每一个点都是球心。

p进数,图片来自Wikipedia

p进数拓扑结构的图示,来自Wikipedia

一个自然的疑问是:这都是什么玩意儿???

有这种疑问很正常,因为这属于抽象而反直觉的数学。但对于数学工作者来说,这种绝对值的定义,恰好呼应了p进整数本身的定义。如果明白一开始那个一句话定义,那么现在这个“绝对值”的概念,就会显得顺理成章,甚至非此不可。这就是对数学概念的理解程度所导致的偏差。初看似乎不明就里的数学概念,一旦掌握了正确的思维方法,就会变得浅显易懂。

但这又谈何容易!数学是如此抽象,必须经过多年的学习,慢慢熟习它的思考方式,才能理解它的内容。

p进整数,以及它的推广p进数,不仅在望月新一以往的工作出现,事实上,它早已是数论中常用的工具。当年怀尔斯对费马大定理的证明也用到了p进数。望月新一此前发展的p进Teichmüller理论,则完全基于p进数,但p进数本身在这个理论中的地位,相当于高考数学中的自然数,只是最基础的砖石。

而望月新一的新理论,“宇宙際Teichmüller理論”,又是另一个层次。他觉察到,用p进数构建的理论仍然不足以抓住他想要研究的那个数论结构,于是他另辟蹊径,找到一个已经证明必定能抓住那个结构的数学对象,然后构建起新的数学理论,研究这个对象的性质,从而导出他寻找的性质。这大体就是宇宙际Teichmüller理论的发展动机之一。

要构建这样的理论,需要同时用到远阿贝尔几何与表示论的工具,然而这两者格格不入,难以调和。为了折中,望月新一需要将理论的基底,也就是最基本的运算,拆成加法和乘法两部分,将它们消解为更复杂更抽象的结构,通过这些结构的互动和变形得到想要的性质,最后证明这些结构能够重新“復原”成某种加法和乘法。在互动和变形的过程中,他要在不同的宇宙(universe、全类)间游走,才能得到足够广泛而一般的结论。加法和乘法结合起来会碰到的障碍,对于它们消解而成的结构却不成问题,当然前提是通过恰当的变形,就像不同坐标系之间的变换。这就是为什么望月新一要将他的理论称为“宇宙際Teichmüller理論”。顺带一提,消解后的加法和乘法面目全非,不像通常的加法和乘法那样基于同一套“数字”,而是形同陌路,望月新一的术语alien ring structure就由此而来。这里的alien,并不是什么“外星”的意思,而是取拉丁语alienus的原意“属于他人、非自身、外来、奇怪”之义。很多地方写的什么“外星算术全纯结构”(alien arithmetic holomorphic structure),都曲解了望月新一的本义。

看不懂?很正常。上面对望月新一理论的描述,来自我查阅相关资料后的总结。但要知道,我主要的研究领域是组合数学,虽然跟通常的Teichmüller理论有那么一丁点关系,但对于一般的代数几何,我也没有正式学习过,只是通过闲谈和阅读懂得些皮毛。望月新一的资料,我只能抓住其中只言片语,描绘大体的图景。

这就是现代的数学,它研究的内容如此广泛如此深入,一个分支上的数学家已经难以理解另一个分支的前沿,更何况是代数几何这一最抽象的领域中耕耘的人特别少的分支远阿贝尔几何,它的最前沿的推广呢?更何况这个理论是如此抽象,处理的又是如此根本的数学结果。可以说,拥有足够的知识储备,有充足时间能够理解并审查望月新一理论的数学家,即使不能说屈指可数,也很可能不超过100人,这还是相当乐观的估计。

望月新一本人这样说过,他的理论在数学界的处境,就像数学本身在整个社会中的处境:过于抽象,以至于人们不愿意去钻研和理解。

争议与迭代

一个新的证明或者理论体系,给数学界带来重大影响,这并不是第一次。

大卫·希尔伯特,图片来自Wikipedia

希尔伯特,就是那个提出20世纪的23个数学问题的著名数学家,他的成名之作,那篇“终结了不变量理论”的论文,在当时就引起了巨大的争议。此前,不变量理论的大多数进展都基于具体的计算,需要给出具体的结果。这样的证明又叫构造性证明。但希尔伯特的证明不属此列,而分属“存在性证明”,能断言某个数学对象的确存在,但对于如何计算却绝口不提。他一开始投稿恰好碰上了当时的“不变量之王”哥尔丹。哥尔丹对这样的证明颇有微词,他的退稿评价是:

这不是数学,这是神学。

但最终希尔伯特幸得克莱因的保荐(“这无疑是这本杂志发表过有关一般代数的最重要的工作”),论文得以发表。正因为无需具体给出构造,存在性证明要比构造性证明要更为简洁有力,也因此逐渐被广泛接受。即使是一开始拒稿的哥尔丹,最后也承认了希尔伯特的工作,“即使是神学也有其价值”。希尔伯特之后也因为公理化的工作以及其他数学成就,跻身当时数学界的顶尖。

另一位为数学界作出巨大贡献的德国数学家康托尔,他的命运却大不相同。在研究傅里叶分析时,康托尔领会到无穷之后仍有无穷的无穷。他从最基础的集合论开始,建立了一个全新体系,描述了超越无穷的无穷,也就是超穷。集合论中的很多基础结果,就出自他的手笔。

格奥尔格·康托尔。图片来自Wikipedia

但他的研究甫一发表,就遭到许多顶尖数学家的攻讦。庞加莱说他的想法就像“严重的疾病”,正在感染数学这一学科。当时执德国数学界牛耳的克罗内克,公开反对康托尔关于超穷的理论,甚至到达了人身攻击的地步。他称康托尔为“科学骗子”、“背叛者”、“腐蚀了青年”,近乎偏执地指责着康托尔和他的理论。

但数学毕竟是数学。经过曲折发展之后,集合论成为了现代数学的基础,成了数学系学生的必修课。正是希尔伯特作出了这样的断言:

身处康托尔跟我们一道展开的天堂内,我们屏息于惊叹之中,知道无人能将我们由此驱逐。

但康托尔本人的命运,却远没有那么光明。也许是因为得不到理解,也许是因为这些无休止的攻击,康托尔患上了抑郁症,一直没有痊愈。他的晚年恰逢第一次世界大战,贫困加剧了战争带来的饥谨。心脏病给他的最后一击,也许是种解脱。

一个人的命运,即使有再多的自我奋斗,始终逃不出历史的进程。领头人的个人好恶,足以令一个人万劫不复。即使他的理论被广泛接受,在生前领受过荣耀,也不过如此。

亚历山大·格罗滕迪克,图片来自上沃尔法赫数学研究所(Mathematisches Forschungsinstitut Oberwolfach)

格罗滕迪克的遭遇,处于康托尔和希尔伯特之间。他的数学风格高度抽象,但却能得出实际的结果。引用我之前写的文字

他谈论的数学实在过于抽象,难以理解。但这就是格罗滕迪克做数学的风格:尽可能从数学对象中将不必要的细节抽象出来,抽象得一般的数学家都会以为剩下的只有“虚空”,然而他仍然能从“虚空”中抓住某些东西,从而建立他的理论,完成他的证明。用格罗滕迪克本人的说法,如果把数学问题比作坚果,大部分数学家做的就是用锤子和凿子把坚果凿开,而他的做法则是将坚果浸在水里,慢慢软化它的外壳,又或者让它经受风吹日晒,然后等待合适的时机,坚果自然就会裂开。

对于大部分数学家来说,这个过程太漫长,也许只有拥有深刻洞察力的格罗滕迪克,才能在能接受的时间内,用这种方法解决问题。这也是他的数学难以被理解的原因之一:他几乎不考虑具体的示例,都是从尽可能抽象的角度出发,思考支配某个数学问题背后的宏大数学结构。有时候这也会闹出笑话。有一次讨论数学的时候,有人向格罗滕迪克提议考虑一个特定的质数作为例子。“你的意思是找一个真实的数字?”格罗滕迪克有点疑惑。对方点了点头。他回答:“好吧,我们考虑57这个质数。”57当然不是质数,但格罗滕迪克大概没有注意这一点,他从来不考虑具体的例子,一切从抽象出发。

格罗滕迪克的这种风格,让他年纪轻轻就全套改写了代数几何所用的数学语言,给这个领域带来了全新的抽象思维方式,让代数几何成为数学中可能是最抽象最深奥但也最有力量的分支。

但在他提出所谓的“标准猜想”之后,情况悄然改变。格罗滕迪克提出这一系列猜想,是为了阐明某些非常深层次的算术结构的存在性,一旦这些猜想得到证明,许多数论中的猜想,比如韦尔猜想,也能得到解决。不幸的是,由于标准猜想本身过于抽象,处理的问题过于广泛,所以久攻不下。雪上加霜的是,他的学生德利涅绕过了标准猜想,取道更“经典”也没那么抽象的技巧完成了最后一个韦尔猜想的证明。这就使很多人的注意力从标准猜想上移开,他之后写出的研究纲领也应者寥寥。最后,他慢慢隐退到比利牛斯山脉之下,在前不久成为了历史。

但格罗滕迪克毕竟留下了庞大的数学遗产。他编写的EGA和SGA是代数几何的入门宝典,他的定理和想法,尤其是标准猜想,仍然留在众多代数几何学者的心头。

当然,新理论新证明被彻底摧毁的例子也比比皆是。在2004年,美国数学家路易·德·布朗奇(Louis de Branges)在自己的个人页面上贴出了一篇124页的论文,声称利用自己发展的基于希尔伯特空间的一套体系,证明了数论中最引人注目的黎曼猜想,跟望月新一的情况相当相似。因为德·布朗奇此前曾证明另一个著名猜想——比伯巴赫猜想(Bieberbach conjecture),所以也有人关注他的证明。但直至现在,论文经过多次修改,似乎仍然站不住脚。目前数学界普遍认为他并未能证明黎曼猜想。

不停有人提出新的想法,即使一开始不被接受,历经时间洗练,终将得到应有的评价,而数学也就此进步。虽然提出新想法的人,他们各自有需要承受的命运,不以他们的贡献为转移。这就是数学史。

而望月新一的理论,就是在当下展开的历史。他的理论是对是错,只能拭目以待。

理论的渗流

闻道有先后,术业有专攻。

新理论总有个渗透的过程,即使是相应领域的专家,也不可能一下子全部理解。而现代数学高度专业化的体系,更使不同分支的数学家难以相互理解。望月新一之前耕耘于代数几何中的远阿贝尔几何,但代数几何方向甚多,而远阿贝尔几何又是一个少人问津的领域,能评判望月新一工作的专家,不消说是少之又少。雪上加霜的是,望月新一这次提出的新理论不仅仅是远阿贝尔几何,而是它的延伸,再加上高度的抽象性和庞大的页数,足以令一部分专家望而却步。

但新理论的确有其吸引力。望月新一本人在代数几何这个领域早已名声在外,他在1996年就证明了格罗滕迪克提出的一个有关远阿贝尔几何的猜想,还因此被邀请在1998年的国际数学家大会上作45分钟演讲。既然他之前的工作证明了他有如此能力,那么他的新工作当然也值得认真对待。何况,望月新一宣称他的新理论能够用于证明数论中悬而未决的ABC猜想,这就更让人期待了。

有些数学家被新理论所吸引,花了大量时间研读,自觉理解了箇中真谛,成为了为新理论摇旗呐喊的人。

有些数学家同样被新理论说吸引,花了大量时间研读,但感觉还是解释不清,难以理解。

有些数学家对新理论有兴趣,但没有时间研读,只能交给别的专家。

有些数学家不懂这个分支,只能围观。

望月新一的“宇宙際Teichmüller理論”(IUTT),就这样将数学界分成了两大阵营:觉得自己读懂的,还有觉得自己没懂的。围观群众不在此列。

觉得自己读懂了的数学家,他们在积极地宣传这个理论,想让更多的人理解它。伊万·费先科也是其中一员。近年来,在世界各地召开了数次讨论IUTT的研讨会,费先科有不少牵线搭桥之功。他和其他数学家也撰写了不少介绍IUTT的文章和综述,试图用不同的视角来讲述这个理论。

觉得自己没有读懂的数学家,有的仍在努力研读,有的尝试用自己知道的数学方法来从侧面验证IUTT的正确性;也有的已经放弃,转而对IUTT的正确性产生了怀疑。

每个新理论都会经历这个阶段,这个等待验证的阶段。只有经过这个阶段,等到大部分专家接受它的正确性,新理论才算是正式确立,数学也得以进步。

只是,对于IUTT来说,这个阶段似乎太长了一点。

同样是代数几何中的新突破,另一位数学家彼得·索尔策(Peter Scholze)在2011年前后提出的perfectoid空间,很快就被数学界所承认,证据就是他从2012开始获得的一系列殊荣。要知道,他提出这个理论的时候还只是博士生,但在2012年答辩之后,没过多久就被母校波恩大学重新聘请为教授,以24岁的身份创下了德国史上最年轻教授的记录。熟悉德国教育系统的人,会更感叹他的成就,因为在德国,教授的地位很高,聘请的条件也因此非常苛刻。这更凸显了他的成就。

彼得·索尔策。图片来自Wikipedia

那么,索尔策和望月新一,两人的理论为何遭遇迥异?

索尔策的理论处于代数几何研究的主流,能理解的专家人数比较多,而望月新一的理论则不算主流,专家也比较少。有时候人多人少,也能决定理论被接纳的速度。索尔策的理论包含的新意,很快就能被读懂并应用到新的问题上;望月新一的IUTT则是全新的系统,略有格罗滕迪克的遗风,看起来波澜不惊,但结论出人意料,需要吃透整个系统,才能判断最后的证明是对是错,但过于浑然一体,也让别人难以进行旁敲侧击式的验证,偏偏这种验证也正是考验新理论最快的方法。

对于望月新一来说,这些都是非战之罪。虽有忮心,不怨飘瓦。

但望月新一自身也并非毫无责任。对于现代数学家的标准而言,他的个性也稍有乖张之处。即使他曾经在美国生活过,在回到日本之后,他就很不愿意到海外与其他数学家交流。他并非不乐意交流,证据就是在2016年的一次IUTT研讨会上,他曾通过视频通话接入会场,为与会数学家解答一些疑难问题。而他窝在京都长时间自己捣鼓这一套理论,也不是数学界通常的做法。一般来说,数学家至少会跟同一个实验室的同事讨论相关问题,在讨论之中,可以获得更多灵感,也能借此检验理论是否正确,或者投石问路,看看是此路不通还是大有可为。上一个口风像望月新一那么严的,还是证明了费马大定理的怀尔斯。当然,数学家经常开学术会议互相交流,少不免走漏风声。我当然不知道望月新一有没有跟同事讨论,很可能有但是同事的保密工作做得很好,也许没有但这个可能性很低,又或者关注远阿贝尔几何的人实在少。但结果就是,当这个证明出现之时,人们毫无心理准备。

另一个可商榷之处,就是他在公开他的理论时,没有选择数学界一般会使用的预印本网站arXiv,而是直接放到了自己的个人页面上。当然,论文放到什么地方,这是他的自由,但也使数学界不能及时了解他的理论。不过话又说回来,这项工作引起的轰动,也很快让他的论文为数学界所知,所以其实问题也不大。

可以说,他的个性或者说偏好,在客观上的确阻碍了他与同行之间的交流。

结果就是,现在即使接受IUTT的专家越来越多(对于一个相对冷门的领域来说,十几个专家不算少数),但这些专家相当一部分是望月新一在日本的同事,还有过从稍密的同行。当然,也有相对独立的学者认为他们同样搞懂了望月新一的证明,但人毕竟也会犯错,很多旁观的数学家认为,现在认同的人数还不够多。

数学这门学科虽然有无可辩驳的逻辑作为守门人,但它仍然是一种人类活动。新理论无论是对是错,总要有足够的人承认,才得以确立。确立后的理论也不一定正确,确立后被推翻的证明虽不多,但也有。只有当大部分专家都理解了这个理论,再也挑不出毛病,从而站到了“自认为懂”的阵营里,甚至能由此生发出新的结果,理论才算真正确立。没有相应专业知识,或者不肯花时间的人,都只是局外人,没有权利对理论的正误说三道四。

但事情毕竟在进展。据说,目前IUTT的四篇论文中,前两篇构建的体系已经被许多专家认为成立,即使是那些觉得没有读懂整个证明的专家。目前争议的焦点之一,在于第三篇论文的推论3.12,也就是Szpiro猜想的证明关键。Szpiro猜想能推出ABC猜想,也难怪大家特别关注这个推论。据说,在之前的版本,推论3.12的证明只有几行,语焉不详,但我看到的几天前(2017-12-14)的新版本中,望月新一加上了好几页的注解。我只能希望这些注解能消除某些专家的疑惑。

发表与审阅

在验证证明的这个节骨眼上,从日本传来了一段诡异的新闻:据说望月新一关于ABC猜想的论文即将发表,发表的期刊是《数理解析研究所公刊》(Publications of the Research Institute for Mathematical Sciences),简称PRIMS。

欧洲数学协会网站上有关PRIMS杂志信息的截图

这段消息来自日本的《朝日新闻》,算是老牌媒体,而且近水楼台,也难怪消息出来之后,引起了数学界的轰动。

在数学界,评定一个证明是否正确的标准之一,就是“在同行评议的正规学术期刊上发表”。要想做到这一点,就要把论文寄到期刊的编辑部(现在通常用网页系统),接受之后的一连串审核。

首先,编辑部在接到论文之后,会指派一位相关领域的编辑处理这篇论文。个别期刊可以由作者指定编辑。编辑会先进行初审,初步考量这篇论文是否适合在本期刊发表。绝大部分明显有问题的论文会在这一步被筛选排除。这一步不需要花多少时间。

然后,编辑会指定几位较为资深、在论文相关领域中有过贡献的同行,邀请他们进行审稿。这一步主要是审查证明的正确性和内容的原创性。到底选几位,不同的期刊面对不同的文章也有所不同。有单选一位的,也有12人委员会的先例,但大多数情况是两到三位。审稿人精读论文之后,会给出各自的意见,编辑负责将这些意见整合,得出一个结论。结论有这几种可能:拒稿、大修(major revision)、小修(minor revision)、发表。如果结果是拒稿或者发表,审稿人的工作就此完成;否则,编辑会将审稿人的意见和结论发给论文作者,让作者进行修改后,提交新的版本。新的版本会让审稿人重新审读,如此往复,直到最终拒稿、最终发表或者作者自行撤回论文。

这也是论文发表需时最长的阶段。越好的期刊,能请到的审稿人水平越高,审理也越严格。因为要有深入的理解,才能判定正确性,所以审稿人通常会花上很长的时间来审读,确保每个细节都没有问题。我自己当然投过稿,每次审稿意见回来都会惊叹于审稿人的细致,许多细微的笔误都会一一指出;我自己也替一个不算特别好的期刊审过稿,精读那篇论文花了我一个月电车上下班的时间,那还只是一篇十几页的文章。正因为严格,所以来来回回拖上三四年的例子也不算罕有。

这就是论文发表能作为金标准的原因之一:能发出来,证明至少有两三个跟你没什么关系的同行,差不多理解了你的论文,而且相当细致地确认了你的证明是对的。一般来说,无法通过这一阶段的论文并不多,因为大多数数学论文在投稿之前,作者都会先与同事交流,再于预印本网站(如arXiv)发表,也会在一些学术会议上宣讲。如果论文有严重的问题,通常在这些阶段的交流之中就会被指出。作者敢于投稿的,大部分都起码不会有严重的问题。

这场审稿的拉锯战,最大的得益者是之后希望研读的数学家。既然已经有人读过,说明论文是可以理解的,而拉锯过程中作者对论文的修改,更会让其中的理论和证明更易于理解。可以说,审稿人、编辑和作者在这个阶段的来来回回,就是在不断打磨论文本身,使其更晶莹通透,能让人一览无遗。

最后,编辑在得出结论后,如果决定这篇文章可以发表,那么就会将文稿交给出版社的编辑,进入最终的文稿编辑流程。值得一提的是,在整个过程中,无论是编辑还是审稿人,他们所做的大量工作,全都一文不取。

但望月新一这次却有点蹊跷,因为望月新一的工作单位,正是数理解析研究所,而他本人,就是PRIMS这个期刊的主编。一时舆论哗然,很多人觉得,这种行径可能在伦理上说不太过去,有些人更是作起了无端的恶意猜测。

因为新闻实在太大,Nature的Davide Castelvecchi给PRIMS编辑部发了一封电子邮件求证,而PRIMS很快作出了回应:

望月教授有关宇宙际Teichmuller理论的几篇论文仍未被期刊接收发表,因此我们很抱歉,RIMS无法对此评论。

The papers of Prof. Motizuki on inter-universal Teichmuller theory have not yet been accepted in a journal, and so we are sorry but RIMS have no comment on it.

措辞很审慎,也有点奇怪。根据最后一句,期刊的回复似乎站在RIMS,也就是数理解析研究所的立场。这样的话,难以判断望月新一的论文是否的确投给了PRIMS。但如果这些论文不在PRIMS手头上的话,那么他们又如何知道论文仍未被接收发表,也就是说仍未通过审议过程呢?但望月新一本人就是主编,他自己肯定知道自己论文的情况,所以也不能排除论文没有投到PRIMS,而是望月新一本人或者知道内情的同事所作的回复。

这也难怪望月新一不喜欢媒体。在他的主页底部,有一句话,用很大的艺术字体写着:本站点的内容和图片不得用于媒体报道。所以,这篇文章不能有他的照片。看看现在,新闻即使在日本发表,在不当的翻译下,传来传去也惹出了大风波。

但即使望月新一的确将论文投到了PRIMS,一般来说也无需担心利益冲突的问题。原因之一,是数学界早已有一套相当完备的系统,用以避免利益冲突。在选定编辑和审稿人时,一般来说,与任何一名作者在五年内合作发表过文章的,指导过任何一名作者研究的,还有与任何一名作者共处一个实验室甚至一个学校的,为了避嫌都不能参与。有些领域研究的人太少,要是全避嫌了可能也不剩什么人,这时候编辑也会慎之又慎,有时候甚至会为了避嫌,邀请研究领域稍远,但可能对论文内容有所了解的研究人员进行审稿。即使是主编,这套系统也会照常运作,不给情面。

也许你会说,那既然望月新一本人是主编,那么他不是更应该避嫌,不要将论文投到PRIMS,以免瓜田李下?我觉得他也许就是这样做的,因为我们还不知道他论文的去向。但也有一种可能,就是他并不在意论文在什么地方发表。毕竟他已经发布了自己的新理论,也吸引了专家研读。证明是否正确,领域内部自有定夺。即使投稿,也不过是一种寻找审读者确认的方式。在哪个期刊,并不重要。数学界也了解现在的情况,所以只是颇有微词,并没有群起而攻之。

说一点我个人的想法。我个人完全不担心望月新一所谓的利益冲突和学术伦理问题,最大的理由就是他没有动机。他已经功成名就,不需要什么文章。数学这种东西,对就对,错就错,不存在编数据或者实验造假,一切细节都在文章里。要是错了,无论强行发表在什么期刊上,也终有一天会被发现,而一发现就无可抵赖,只能重新修补。而且数学家对于证明的疑心很重,甚至到了偏执的地步。别人可能觉得差不多对了,数学家考虑的却是有什么地方可能出问题。在这种高标准下,疏失犯错固情有可原,故意造假则得不偿失。另外,正常的学术评价体系也不会过多考虑文章的发表,而是会综合考虑同行的评价,多发几篇文章并没有什么用。况且,一个造假发现就会身败名裂,甚至有人会以死谢罪的国家和体系,我觉得不能跟大部分读到这篇文章的人身处的环境相比。很多人的担忧,也许只是从此处自身感受作出的一种投射。

对于数学来说,文章发表并不是研究的终点。尤其是对于像望月新一的新理论那样重要的结果而言,数学家会前仆后继地研究它、理解它、挑剔它,尝试在其上生发出新的结果,或者找出它的错误。广中平佑当年需要两百多页才完成的奇点消解定理,在经过许多数学家的理解和简化之后,现在有了不少的简化证明,其中有些只需要二十页,原来的十分之一,而数学界对奇点消解的理解也远胜以往。数学是活着的,数学有它的生命,而发表并不是它的终点。

当然,我不是说数学家都白璧无瑕。数学界自有它的阴暗角落,就算是“自认为懂”望月新一新理论的阵营内部,也有各种奇怪的事情在发生,而两个阵营之间的争吵也很有难说谦谦君子之处。但证明总在日光之下。

况且,做纯数学的人,如果没有一点热爱数学的心,恐怕也很难久坐数学研究这一钱少活难的冷板凳。也许望月新一并不介意数学界甚至他自己领域之外的人如何看待他。他只要能做出好的数学,就可以了。

想想佩雷尔曼。

证明与理解

从目前的迹象来看,望月新一应该已将论文投向某个学术期刊,而且也应该断断续续收到了一些审稿意见,间接证据就是他的论文不断在更新,当然大多数是他与同事同行讨论的结果,但一些澄清概念的注解也很有可能是为了回应审稿的意见而写下的。

那么,如果期刊收到像望月新一的论文那么难读的投稿,应该怎么审稿?

世上数学家不少,总有几个在相关的研究领域钻研。如果投稿处在期刊的专业范围内,那么编辑肯定能找到能够审核论文的专家。当然,专家是否愿意审稿又是另一回事,但只要接受了审稿,那基本的专业素养就有了保证。既然审稿人是专家,就不会完全读不懂。也许会有一些不太理解的地方,但这时审稿人可以通过编辑向作者反映情况,要求更详细的解释。这样一来二去,慢慢地也就读懂了,可以作出评判。论文的终审稿通常会比初稿容易理解得多,这就要归功于审稿人、编辑和作者的共同努力。

当然,论文有两种难度。有些论文,例如佩雷尔曼对庞加莱猜想的证明,本身不长,但是因为高度抽象,以及作者各种跳步省略,导致文章极其难读。有些论文,例如Almgren某篇关于几何测度论的论文,本身就很长,一共1728页,差不多是望月新一四篇论文合计页数的三倍。这么长的文章,即使不需要检查正确性,慢慢地读下去也很费劲。

望月新一的论文也许两种难度兼具,但原则上并非不可逾越。不要低估数学家的耐心。

那有没有可能作者也没有办法解释,导致专家也不明白呢?

你可能会觉得,作者不也是人么,只要是人,就肯定有办法解释啊。人又不是机器。

对啊,但如果机器也参与了证明呢?

这就是计算机辅助证明,虽然稀少,却也存在。最有名的例子就是1976年美国数学家阿佩尔和哈肯对四色定理的证明。

法国大区的四色染色,图片来自Wikipedia

四色定理,说的是任何地图都能用四种颜色涂抹,使得相邻的区域颜色不同。这个陈述看起来人畜无害,似乎不难解决,而许多知名的数学家也被它的外表迷惑,比如闵可夫斯基就曾在课堂上夸下海口,一边说这个问题没被证明只是因为没有一流数学家去做,一边就在黑板上开始推导,推了一节又一节课,最终只能食言。当然,哥德巴赫猜想和费马大定理看起来也人畜无害,这也不妨碍它们难倒一大片顶尖数学家。但与两者不同的是,四色定理的证明很难说是重大突破。它属于组合数学,但这个领域因为着眼点相当分散,能统领一大片不同课题的体系少之又少。

阿佩尔和哈肯的证明被历史记住,主要因为这是第一个计算机辅助完成的重大证明。他们的证明基于所谓的“放电法”。首先,他们利用计算机,设计了一些“放电规则”,这些规则能用于证明任意的平面地图必然包含1936种构型之一。这1936种构型,又被称为放电规则对应的“不可避免构型集”。然后,他们利用计算机证明了,所有这1936个构型都是可以约化的。也就是说,所有平面地图都能被约化,变成区域数更少的平面地图,而小地图能用四色染色,当且仅当大地图同样如此。如果存在不能用四色染色的平面地图,取这种地图中区域数最少的地图,通过约化,能导出区域数更少但同样无法用四色染色的地图,引发矛盾。阿佩尔和哈肯就是这样,证明了四色定理。

但这篇论文却让想要验证的数学家犯了难。论文由两种截然不同的体裁合成:数学家熟悉的人工证明,还有计算机熟悉的计算过程。人工证明虽然繁复,但还在数学家熟悉的范畴里。但计算机的计算过程应该怎么验证呢?

虽然具体的算法属于人工证明的部分,但机器毕竟不认识算法,它只认识能执行的代码,所以还要验证具体的算法实现代码是否正确。而从代码到具体的运算结果,又是另一回事,虽然原则上可以逐一验证,但长度实在超出了人类能接受的范畴。但不去验证具体的计算,又如何能确定所有结果都准确无误?也许有些编写上的细节没有注意到,或者当时计算的硬件有问题?

所以这个证明的验证,花了很长时间。

验证所有构型都能被约化的部分相对简单。虽然计算量大,但这主要用于寻找具体的约化方法,验证约化成立倒是不费多大功夫。为了检查,可以重新由不同的人在不同的硬件上用不同的语言重新编写这部分的代码,然后进行计算。一次计算可能有问题,但两次细节完全不同的计算同时出错的可能性就低得多。

问题是验证放电规则和不可避免构型集。计算部分由电脑完成,但验证却必须手工进行。如此庞大的证明,一开始有漏洞几乎是必然的。在几年后,德国的一位硕士生检验了整个证明的40%,发现在放电规则中有一个严重错误。其他人也陆续发现了一些小问题。阿佩尔和哈肯花了不少时间处理这些问题,最后出版了一本专著,共计七百多页。随后,许多数学家陆续尝试简化这个证明,提出了许多不同的证明。虽然这些证明都需要计算机的辅助,但毕竟这么多独立证明全都出错的可能性很小,大家也就都接受了四色定理。

另一个受到类似“礼遇”的,是托马斯·黑尔斯(Thomas Hales)对开普勒猜想的证明。他证明的是,在三维空间中堆砌大小相同的小球时,最密集的方式是面心立方和六方最密堆积。

两种最密堆积,图片来自Wikipedia

黑尔斯的证明可谓暴力穷举的典范。他利用计算机,将所有可能的情况一一分类,总数超过五千,然后利用计算机算法逐一否定这些可能性,这需要解开共计约十万个线性规划问题。如果没有计算机,这恐怕是不可能完成的任务。证据就是,最终证明共计250页,却还要外加3GB的计算机程序和数据。

由于开普勒猜想的重要性,黑尔斯的证明也相当引人注目。他将论文投到了数学界的顶级期刊《数学年鉴》(Annals of Mathematics)。在数学界,只要你说出Annals这个词,人人都知道你指的是《数学年鉴》。编辑部自然也不敢怠慢,毕竟这是个长久悬而未决的猜想,而计算机在证明中的角色无比重要,编辑也希望能完全确认计算正确性。他们组织了一个12人委员会来审查这篇文章,只有12个人意见完全一致,这篇文章才算通过。为了详细验证整个证明的正确性,有些委员还在自己的实验室里召开了研讨班,准备细细检查证明的方方面面。

委员会花了4年,结论是他们“99%确定”证明是正确的。他们虽然完成了大部分证明的检查,但仍未到彻底的地步。以数学家的标准来说,这还是不太令人满意,但证明太长太麻烦,委员们实在干不动了。最后,《数学年鉴》发表了这篇审稿标准史无前例,审稿结果也史无前例的文章。

这些计算机辅助证明,即使计算机只起到了辅助计算的作用,也足以让希望确认证明正误的数学家烦恼不已。这么长的计算,人花一辈子也不可能完全验证,怎么才能确定计算没有出错?

既然人不能验证,那么机器怎么样?

只要将证明完全形式化,写成机器能明白的格式,那么就可以让机器去验证整个证明。好在验证总不会比计算难,既然机器能完成计算,那么也能完成证明。于是,要确认形式化证明的正确性,只需要先让机器去验证,然后人工检查机器验证代码的正确性。这样的代码通常很短,而且可以用于许多证明,可以说用力少而建功多。

问题在于,证明的精华部分是由人类完成的,而人类的语言机器显然读不懂。要想让机器验证证明,就要把这部分完全形式化。这是个艰巨的工作。

对于四色定理和开普勒猜想的证明,因为它们非常重要,所以即使明知很难,数学家还是去做了。2005年,Werner和Gonthier给出了四色定理的一个完全形式化的证明,并用软件Coq完成了验证。从2003年开始,黑尔斯开始了一个合作项目Flyspeck,旨在将他自己的证明完全形式化,然后用机器来检验,从而确立证明的正确性。与21位合作者花了十一年多的时间,他终于完成这个项目,而现在开普勒猜想已被公认获得证明。(关于形式证明,请参见木遥的《形式证明:机器的光荣与人的梦想》

所以说,即使读不懂,还是有办法审稿。当然,需要如此大费周章的论文少之又少,也只有非常重要的论文才会获得这种待遇。但数学家对证明正确性的执着,由此可见一斑。

但对很多数学家来说,知道一个证明站得住脚还不够,他们希望能理解整个证明。对于四色定理和开普勒猜想的证明,他们也许会说:“好,我知道那是对的,但它为什么对?”

这种对理解的渴求,也是推动数学前进的动力。数学家追求证明,但从来不单追求证明。他们的真正目的,是通过证明去理解为什么这个定理是对的,为什么那个理论要以如此方式建立。机器证明也是数学,但谈不上是好的数学,或者更准确地说,谈不上是美妙的数学。

也许终有一天,人工智能也会懂得做数学,它们也许会拥有能大幅抛离我们的能力。就像姜峯楠(Ted Chiang)的短篇科幻《人类科学之演化》(The Evolution of Human Science,首发于《自然》期刊)那样,也许有一天,人工智能做的数学会达到人类无法理解的地步,仅仅皮毛也足以让人类最顶尖的数学家钻研一生。当然,原著中拥有超人能力的并非人工智能,而是植入芯片的人类,但道理是一样的。

然而,即使人工智能超越了我们,对数学的理解以及它给我们带来的美感也不会消失。我们做数学,为的不仅是追求真理,还为了理解这些真理。

而望月新一的证明,只是历史长河中前仆后继的又一步。

后记

我一直觉得,写这篇文章的不应该是我。我做的是组合数学,对于代数几何所知甚少,写关于望月新一的文章,简直是赶鸭子上架。

但了解更多的人在哪里?

比我更懂的人肯定多得是。任何一个做代数几何的博士生,肯定都比我更适合写这篇文章。但似乎没有听见他们的声音。

我理解他们。这毕竟是一个高度抽象的学科,要向研究方向不同的同事解释尚且很有难度,更何况向一般人解释?

这也许也是望月新一拒绝媒体的理由。媒体肯定不懂他的理论,只知道这可能是一个重大突破,可以搞个大新闻。但这些媒体何尝愿意了解他的理论?写成报道,焦点多半在个人的私生活上,要么就是各种八卦。看的人是很多,但看完之后,给人们又留下了什么教益?

但这个事情毕竟不能不做。正如他的新理论也需要知音来帮助宣讲,数学本身也要靠科普才能传播,人们才会认识到数学的重要性,而不是问出“微积分有什么用,又不能买菜”这种问题。怀有恶意的媒体固然会断章取义,但让更多人更了解数学的美妙也是件好事,值得再三权衡。

这篇文章,由于本人知识所限,难免有许多疏漏,权当抛砖引玉。希望与远阿贝尔几何关系更密切的专业人士,能写出更深入准确的文章,让大家分享数学最前沿的这一大事。

本文删减版曾发布于果壳网,地址在这里

参考文献

Ivan Fesenko, Fukugen, Inference Review, http://inference-review.com/article/fukugen

Mochizuki Shinichi, Inter-universal Teichmuller Theory I: Construction of Hodge Theaters, http://www.kurims.kyoto-u.ac.jp/~motizuki/Inter-universal%20Teichmuller%20Theory%20I.pdf

Mochizuki Shinichi, The Mathematics of Mutually Alien Copies: From Gaussian Integrals to Inter-universal Teichmüller Theory, http://www.kurims.kyoto-u.ac.jp/~motizuki/Alien%20Copies,%20Gaussians,%20and%20Inter-universal%20Teichmuller%20Theory.pdf

Advertisements

小朋友的涂鸦

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

本文在科学松鼠会分节发表,地址:
http://songshuhui.net/archives/96565
http://songshuhui.net/archives/96581
http://songshuhui.net/archives/96601
http://songshuhui.net/archives/96606


从8和9说起

看到题目,你也许会问:8和9,两个普通的数字,又有什么可说的呢?但在数学家眼中,这两个数字可不寻常:9比8大1,8是一个立方数,它是2的立方,而9是一个平方数,它是3的平方。8和9,就是一个立方数紧紧挨着平方数的例子。那么,数学家自然会问:还有没有别的立方数,它紧紧挨着一个平方数呢?

八号球九号球

或者用数学的语言来说,x^2 - y^3 = 1 这个方程,除了x = 3, y = 2 之外,还有别的正整数解吗?

我们先在直觉上探索一下,平方数和立方数,当它们越变越大的时候,在所有正整数当中也会越来越稀疏。就像两个越来越不喜欢出外的人,即使是邻居,也许一开始会打个照面,但之后出门的次数越来越少,也就越来越不可能碰上面。数学家们甚至猜测,即使不限定于平方数和立方数,就算是任意大于1的次方数,它们“碰面”也只有8和9这一回。用严谨的数学语言来说,就是方程x^a - y^b = 1 ,在a b 大于1的条件下,只有一组解,就是x=3, a=2, y=2, b=3 。这又被称为卡特兰猜想(Catalan’s conjecture)。

直觉上,卡特兰猜想应该是对的,但直觉毕竟是直觉,它不是数学证明。虽然平方数和立方数它们越来越稀疏,但是正整数有无限多个,它们有无数次碰面的机会,谁知道它们会不会在通向无限地平线的路途中就抓住了又一次机会呢?所以,我们需要数学证明,只有数学证明,才能从逻辑上根本地否决这种可能性。

我们来看看数学家是怎么思考的。

数学家们想要的是一个数学证明。我们重新考虑方程x^a - y^b = 1 。在这个方程里什么东西最麻烦呢?减法很简单,等于号很简单,剩下的就是乘幂操作了。那么,有什么办法能去掉乘幂这个麻烦事呢?这个办法就是对数,大家在中学都学过。对数能将乘幂转化为更简单的乘法:\ln(x^a) = a\ln(x) 。我们先将方程改写成x^a=y^b+1 ,然后两边取对数,就得到了a\ln(x)=\ln(y^b+1)

现在,方程里最麻烦的又是什么呢?就是对数里边的加法,因为对数和乘法很友好,但跟加法实在谈不来,\ln(x+y) 并没有一个好的表达式。有什么方法可以绕过去呢?我们想到,y^b 是一个次方数,它可以非常大,要多大有多大,而相比之下,加上去的这个1非常小非常小,小得几乎可以忽略不计。而对数函数增长得又非常慢非常慢,ln(20)大概是3,ln(400)大概是6,要想对数值增加3,原来的数要增加20倍,要等到10^13,也就是万亿,对数值才达到30。而对于一万亿来说,这个小小的1实在是零头中的零头。

对数函数的增长

对数函数的增长,由方弦制作

但数学是严谨的,虽然这个1很小,带来的影响更小,但我们不能直接说可以把1去掉。但这难不倒数学家:既然不是直接相等,划个界限总可以吧?用一点简单的高等数学,我们可以得到如下的不等式:

\displaystyle{b\ln(y) < \ln(y^b+1) < b\ln(y) + y^{-b}}

也就是说,去掉1和不去掉1,对于对数值的影响只有y^{-b}y^b 的倒数。因为y^b 可以非常大,它的倒数也就非常小。如果它增长十倍,它的倒数就会变成原来的十分之一。我们刚才说到,y^b 要达到万亿,它的对数值达到30,这时候它的倒数,也就是加1造成的误差,只有万亿分之一。这是个什么概念呢?相当于在测量地球到太阳的距离时,不小心多加了根头发丝。在现实世界中,即使多么严谨的测量,这种程度的误差可能也就放过去了。但在数学中,无论多小的误差,不应该舍弃的时候就不能舍弃。

将这个误差的结论代入原来的方程,我们得到:

\displaystyle{|a \ln(x) - b \ln(y)| < y^{-b}}

也就是说,我们要寻找两个正整数,它们的对数值的某个倍数非常接近。这就需要对正整数的对数进行深入的研究。在1966年到1967年,数学家阿兰·贝克(Alan Baker)写出了一系列的文章,其中给出了正整数乃至所谓“代数数”(也就是多项式方程的解),它们的对数的倍数之间距离的一个下界。也就是说,上面的不等式左边其实不会太小,它会大于某一个关于a,b,x,y 的函数,可以写成:

C(x,y,a,b) < |a \ln(x) - b \ln(y)|

那么,如果我们能证明对于绝大部分的x,y,a,b 都有C(x,y,a,b) > y^{-b} ,那么两个不等式就会产生矛盾,方程也就不可能有整数解,这不就解决了卡塔兰猜想了吗?

阿兰·贝克

阿兰·贝克,图片来自上沃尔法赫数学研究所(Mathematisches Forschungsinstitut Oberwolfach)

当然,实际上这种简单粗暴的方法并不能解决问题。C(x,y,a,b) 这个函数,虽然可以明确计算出来,然而得出的函数太小,不足以解决问题。但引出矛盾的方法不只一种。为了证明这类型的结论,贝克发明了一种方法,可以在不同的角度上引出矛盾。而另一位数学家Tijdeman利用贝克的方法,找到了一个巧妙的角度,证明了当a b 足够大的时候,方程必定没有解。而此前人们已经证明了,当a b 固定的时候,关于x y 的方程最多只有有限个解,而且给出了这些解的一个上界。结合两个结果,数学家们证明了,整个关于a,b,x,y 的方程最多只有有限个解。现在在波尔多大学的数学家米歇尔·朗之万(Michel Langevin)计算出了一个明确的上界:

\displaystyle{e^{e^{e^{e^{730}}}}}.

也就是说,只要检查比这个数小的所有正整数,如果没有找到别的解,那么就说明8和9是唯一一对靠在一起的次方数。但这个任务看起来容易,做起来却是无计可施。e^{e^{e^{e^{730}}}} 有多大?在现实中,能与其相比的数字根本不存在,即使是1后面添上宇宙里所有的原子当作0,这样得到的无量大数,还是连零头的零头都赶不上。对于这么大的数字,表达它都有困难,更何况检查!

银河

数目远超银河中原子个数,图片来自Wikipedia

你可能觉得,这样找正整数的对数之间的关系,又有什么用呢?好不容易得出一个结果,却只是“原则上可以验证”,根本不能实际计算,这种方法又有什么用?但不要忘记,方法之所以是方法,就是因为它能应用到许多问题上。贝克的这套方法,可以应用到所谓的“丢番图方程”,也就是系数和解都是正整数的方程。大家耳熟能详的费马大定理,可能大家不太熟悉的完美长方体问题,都是悬而未决的丢番图方程。而对这类方程的研究,涉及数论的方方面面。贝克的方法给丢番图方程地研究带来了全新的工具,他也因此获得了1970年的菲尔兹奖,那时离他发表相关论文还不到四年。

但卡特兰猜想仍然悬而未决。要等到2002年,罗马尼亚的数学家Preda Mihăilescu才最终证明了卡特兰猜想。他的方法大量用到了分圆域与伽罗华模的知识,这些都是代数数论中的艰深概念,哪怕是稍稍涉猎,恐怕也需要本文十倍以上的篇幅才能讲个大概。但无论如何,我们现在终于可以确定,8和9在自然数中的确是绝无仅有的一对,在无限的可能中,唯一一对能紧靠在一起的次方数。

卡特兰猜想还有别的变体,比如说人们猜想,对于任意的正整数k,间距为k的次方数对只有有限个。对这些变体的探索也非常引人入胜。

但这不是这篇文章的主题。


从整数到多项式

我们在中学里就学过多项式。对于一个变量x,我们取它的一些次方x^a, x^b 等等,乘上系数,然后加起来,就得到了一个多项式,比如说x^7+6x^3+4 ,就是一个关于x的多项式。在这里,我们考虑那些系数都是复数的多项式,也就是复系数多项式。

数学家们很早就发现,这些多项式与正整数有一种神奇的相似性:可以做加法、减法、乘法,也可以分解因数,可以求最大公约数和最小公倍数,同样有着唯一分解定理:正整数可以唯一分解成素数的乘积,而多项式也能唯一分解成所谓“不可约多项式”的乘积。基本上,在数论中对正整数性质的研究,很多都可以直接搬到多项式上来。于是,遇上有关正整数的问题,把它迁移到多项式之中,未尝不是一个提出问题的好办法。自然,因为多项式本来结构就比较复杂,相关的问题也更难解决,但这不妨碍数学家的步伐,毕竟他们要攻克的就是难题。

注:更准确地说,因为正整数和多项式都组成了所谓的“欧几里德整环”(Eucliean domain),所以它们共享非常多的数论性质,比如说,它们都是所谓的“主理想整环”,它们的所有理想都是主理想,也就是某个元素的倍数组成的理想。
此处插播一则笑话:为什么QQ只有QQ群?因为QQ没有理想……

在1965年,Birch、Chowla、Hall和Schinzel问了一个问题:如果有两个多项式P Q ,它们是互质的,那么P 的平方和Q 的立方之间的差距,也就是说P^2-Q^3 ,可以有多小?这个问题很显然是卡塔兰猜想的延伸。卡塔兰猜想最原始的版本问的是,除了8和9以外,平方数和立方数的距离能不能达到1。而Birch等人现在问的是,多项式平方和立方的距离最小能达到多少?

当然,要回答这个问题,首先要想办法衡量多项式的大小。对于不同的多项式P(x) ,当x 趋向于正无穷时,P(x) 趋向无穷的速度各有千秋,而决定这个速度的主要因素,就是多项式的次数,也就是多项式中x 的最高次方是多少。所以,我们选择多项式的次数作为衡量多项式大小的标尺。现在,我们可以用更严谨的方式叙述那四位数学家的问题:

对于某个正整数k ,假设有两个互质的多项式P,Q ,其中P 的次数是3k Q 的次数是2k 。那么,多项式R=P^2-Q^3 的次数最小可以有多小?

我们能看出来,在这个问题中P Q 的次数不是随便选取的。如果P 的平方和Q 的立方次数不一样的话,那么R 就跟P,Q 一样大。只有上面的选择方法,才能至少使两者的最高次项互相抵消,使问题变得不那么无聊。另外,对于任何一个例子,我们只要将所有多项式都乘上一个合适的常数,就能得到另一个本质上相同的例子。所以,我们只考虑本质上不同的那些例子。

在论文中,四位数学家给出了一个k=5 的例子:

\displaystyle{P = \frac{1}{27} t^{15} + \frac{1}{3} t^{12} + \frac{4}{3} t^9 + \frac{8}{3} t^6 + \frac{5}{2} t^3 + \frac{1}{2}}

\displaystyle{Q = \frac{1}{9} t^{10} + \frac{2}{3} t^7 + \frac{5}{3} t^4 + \frac{4}{3} t}

\displaystyle{R = \frac{1}{36} t^6 + \frac{7}{54} t^3 + 4}

在这个例子里,P, Q, R 的次数分别是15、10和6。虽然P^2 Q^3 的次数都是30,但是它们凑巧在前24项的系数都相同,而它们的差仅仅只是一个六次多项式,真是一个难得的巧合。但数学家总是有些贪心,面对这个例子,他们想的是:能不能把R 的次数再压低一点?能不能找到差距更小的平方多项式和立方多项式?这个想法非常自然,但在反反复复的尝试中,似乎找不到次数更低的例子了。于是,这四位数学家就猜想:这个例子是不是已经无法改进了呢?他们提出了这样的猜想:

对于两个互质的多项式P,Q ,假设其中P 的次数是3k Q 的次数是2k 。那么,多项式R=P^2-Q^3 的次数至少也有k+1 ,而且总能找到使R 的次数恰好是k+1 的例子,也就是说这个下界是紧的。

在刚才的例子中k=5 ,而R 的次数恰好就是5+1=6,符合猜想。数学家们想寻找更多的这样达到最小差距的例子,尝试在其中寻找规律。但出人意料的是,k=5 的第二个例子,要到35年之后的2000年,才被Elkies发现,而且这个例子的复杂度远远超出了预期。在上面的例子中,我们看到的系数都是相对简单的分数。而现在,请看Elkies的这个例子:

\displaystyle{P = x^{15} - 3x^{14} + 51x^{13} - 67x^{12} + 969x^{11} + 33x^{10} + 10963x^9 + 9729x^8 + 96507x^7}

\displaystyle{\quad + 108631x^6 + 580785x^5 + 700503x^4 + 2102099x^3 + 1877667x^2 + 3904161x + 1164691}

\displaystyle{Q = x^{10} - 2x^9 + 33x^8 - 12x^7 + 378x^6 + 336x^5 + 2862x^4 + 2652x^3 + 14397x^2 + 9922x + 18553}

\displaystyle{R = - 2^6 3^{15}(5x^6 - 6x^5 + 111x^4 + 64x^3 + 795x^2 + 1254x + 5477)}

在这个新例子中,多项式的系数大大膨胀了,这就解释了为什么寻找第二个例子花了这么长的时间。我们也能从另一个侧面窥见这个问题的难度。比方说,我们希望用待定系数法寻找例子:先将多项式P, Q 的系数都设为未知数(最高次的系数设为1),然后计算R 的所有系数,它们都是之前未知数的多项式。在k=5 的情况下,我们要求R x^{29} x^7 的这23个系数都是0,这样就得到了23个方程。将它们联立起来,就得到了一个关于25个变量的23个方程组成的高次方程组,理论上只需要解出这个方程组,就能得到所有的例子。但问题是,这个方程组的总次数是6198727824,大约是六十亿!这样的方程,不要说是人脑,就是计算机也几乎无法解开。但至少,我们知道这些系数都是所谓的“代数数”,也就是代数方程的解。这样庞大而困难的问题,难免令人望而却步。寻找新的例子已经如此困难,更不要说穷尽所有例子了。

但有一帮数学家,光是看了看问题,在餐巾纸上随手涂鸦了一下,就拍着胸脯宣称:k=5 的情况一共就只有4个例子,还有两个就继续找吧;不光这样,对于任意k 的情况,我们都能证明你们的猜想是对的,而且还能帮你们计算所有本质上不一样的例子一共有多少个。

这是什么魔法?


球面覆盖

我们每天睡觉亲密接触的被褥,它的卫生状况值得重视,偶尔就要把被套拆下来洗一洗,洗完再套上去。但这不是个顺当的活计,尽管有系绳,但固定还是相当困难,手艺不好的,实在是难以把它弄得服服帖帖,总是会有些褶皱。这时候难免萌生出偷懒的想法,懒得把被套拉链拉开然后把内芯塞进去了,就随便用被套把内芯当粽子捆了,反正严格来说,的确也是用被套把内芯“套住了”,被套也完成了自身的责任:把内芯的每一处都“挡住”,不让睡觉的人把内芯弄脏。可惜被套一般没有弹性不能延伸,包起来的“粽子”实用面积实在太小,否则这也不失为一个好办法。

无论是正常的还是包粽子的方法,我们都可以说,被套把内芯“覆盖”了。最完美的当然是从头到尾平整光滑的覆盖,内芯上每个地方都被一层被套覆盖;稍差一些,有点皱褶的话,皱褶的地方就会有至少三层被套覆盖着内芯的同一个地方,而且还会有一些“分支点”,皱褶在这些点上开始,又在这些点上终结。如果是包粽子的话,那就不好说了,不过可以肯定的是,内芯上每个点至少有两层被套覆盖。

覆盖的折痕

覆盖的折痕,来自Wikipedia

在数学家眼中,被套可以看成一个球面:假设被套有弹性,那么在里边装一个气球,再把气球吹起来,被套自然会鼓起来变成球面。同样,内芯也可以看成一个球面。如果我们先在内芯放一个气球,然后把内芯和覆盖它的被套缝起来,不让它们移位,最后将气球吹起来,那么我们就得到了被套这个球面对内芯这个球面的一个覆盖。这样的覆盖变化多端,可以是平滑的,也可以有皱褶,在每一点处,覆盖可以是单薄的,也可以是多重的。

把这些直观印象翻译成数学概念,这是数学家们的拿手好戏。球面之间的覆盖,用数学术语来说,就是从一个球面(被套)到另一个球面(内芯)的连续满射函数f ,如果x 是被套上的一点,那么f(x) 就是内芯上被x 这一点覆盖的点。我们要求函数是连续的,因为我们不想把被套扯坏,所以要求被套上的一小块“保护”的也是内芯上的一小块,而不是“分隔异地”的两块;我们要求函数是满射,因为我们希望保护内芯不被弄脏,所以要求内芯上的每一点都有被套保护。当然,数学毕竟是数学,比现实要更天马行空一些。现实中的被套不能穿过自身,而数学中的覆盖则可以。正因为如此,在数学中我们可以把覆盖的皱褶“抚平”,只留下一个个孤立的分支点,这在现实中是不可能的。而我们要求除了分支点以外,球面上的其他点被覆盖的次数都相同,这个次数又被称为球面覆盖的次数。

视频原作者:Dugan Hammock,他的Youtube频道上有更多关于曲面的精美视频。

然而,这些东西跟多项式又有什么关系呢?

对于数学家来说,关系非常大。因为他们知道,复数组成的复平面,差不多就是一个球面。有一种叫“球极平面投影”的方法,可以将复平面转化为只缺一个点的球面。而如果我们将“无穷大”也加到复平面里,就能把球面缺的点补上,得到的就是所谓的“黎曼球面”。而黎曼球面上的有理函数,也就是两个多项式的商,实际上就是一个球面覆盖。通过研究球面覆盖的性质,数学家们就能间接得知对应的有理函数的性质。

球极平面投影

球极平面投影,来自Wikipedia

我们接下来考虑有理函数给出的球面覆盖。球面覆盖的许多性质都被它的分支点所决定,因为分支点以外的地方都非常平滑,到了乏善可陈的地步,而分支点正是曲面“叠起来”的地方,自然包含了我们想要的性质。我们可以说,球面覆盖的分支点越少,它就越简单。

那么,对于有理函数来说,怎么寻找它的分支点呢?还是拿被套作例子。当被套有皱褶时,皱褶的部分实际上是三层被套覆盖同一点,但同样应该属于皱褶一部分的分支点上,却只有一层被套。也就是说,分支点覆盖的层数比正常的要少一些。如此类推,对于函数f(x) 引出的球面覆盖来说,假设它的覆盖次数是d ,那么说某个点a 是分支点,就相当于说f(x)=a 这个方程的解值少于d 个,因为这个方程的每一个解其实都是“被套”上覆盖a 的一点。换句话说,a 是分支点当且仅当f(x)=a 有重根。

举个实际的例子。我们考虑函数

\displaystyle{f(x) = -\frac{(x-1)^3 (x-9)}{64x}}

显然方程f(x)=0 有三次重根x=1 ,所以0是它的一个分支点;而稍微令人意想不到的是,如果我们将它减去1,就会得到

\displaystyle{f(x) - 1 = -\frac{(x^2-6x-3)^2}{64x}}

可以看出来,方程f(x)-1=0 有两个二次重根,分别是二次方程x^2-6x-3 的两个解,所以1也是一个分支点。最后还有一个分支点比较难想像,那就是无穷远点,因为当x 趋向无穷或者0时,f(x) 也趋向于无穷,所以无穷远点也是一个分支点。可以证明,这个函数再也没有别的分支点了。

最简单的球面覆盖,一个分支点都没有,就是最标准的把内芯塞进被套里的方法。球面到自身的恒等映射f(x)=x 就是这样的一个例子。可以证明,不存在只有一个分支点的球面覆盖,也就是说,接下来第二简单的情况就是拥有两个分支点的球面覆盖。可以证明,所有拥有两个分支点的球面覆盖,都可以利用适当的变换来“拉扯”变形到f(x) 是多项式的情况。

数学家们接下来要研究的,自然就是拥有三个分支点的球面覆盖。利用有名的莫比乌斯变换

\displaystyle{z \mapsto \frac{az+b}{cz+d}},

我们可以将三个分支点分别移动到0、1和无穷远点(∞),而莫比乌斯变换不会改变球面覆盖的本质。所以说,我们只需要研究分支点分别在0、1和∞的球面覆盖,而能产生这样的球面覆盖的函数又叫别雷函数(Belyi function,正确地说是球面上的特殊情况),它的名字来源于20世纪的俄罗斯数学家别雷(G. V. Belyi)。但实际上,别雷并不是第一个研究别雷函数的人。早在19世纪末,大数学家菲利克斯·克莱因(Felix Klein)就已经利用别雷函数构造过一些特殊的球面覆盖(更精确地说,是单值群为有限单群PSL(2,11)的球面覆盖,它是一个11次覆盖)。

但球面覆盖毕竟太抽象,即使是数学家,不借助适当的工具也难以“脑补”某个具体函数引出的覆盖,而对于一般人来说,光是球面可以穿过自身这一点就足够喝一壶的了,更不要说想像那些“折痕”都集中在几个分支点上的高次覆盖。要研究这些球面覆盖,似乎是难于登天。

但数学家却说,三个分支点的球面覆盖,其实简单得连小朋友都能画出来。


小朋友的涂鸦

要讨论别雷函数,就要对球面覆盖和复分析有些更深入的了解。接下来的内容可能有一点抽象,如果实在不适应,可以跳过,直接看本节最后的结论。

我们要研究的,是分支点分别在0、1和∞的球面覆盖,或者说某个别雷函数f(x) 。既然球面覆盖的所有玄妙之处都蕴藏在分支点里,那么肯定要抓住这些分支点来研究。我们之前考虑过一个例子:

\displaystyle{f(x) = -\frac{(x-1)^3 (x-9)}{64x}}

它是一个别雷函数,对应着一个球面覆盖。用一点点复分析的知识(代数基本定理),容易知道除去一些特殊情况外,对于任意的常数a f(x)=a 都有4个解。也就是说,这个别雷函数对应着一个次数为4的球面覆盖。我们再来看看这个函数的分支点。它在f(x)=0 处有一个分支点,因为x=1 是这个方程的三重根,但它还有另一个根x=9 ,也就是说,0这个分支点实际上对应两个不同的点:三重根x=1 和单根x=9 。同理,1这个分支点同样对应两个不同的点,两个都是双重根。我们能看到,两个分支点的分支方式不同,但既然它们从属于同一个球面覆盖,那么之间必然有某种联系。怎么样才能考察它们之间的联系呢?

办法很简单:直接把两个点连起来就好了。也就是说,我们希望观察这两个分支点的每一层覆盖分支之间是如何连接起来的。

更具体地说,因为球面覆盖就是一个球面覆盖着另一个球面,只要在被覆盖的球面上连结0和1两个点,在得到的线段上涂上极浓重的颜料,等到颜料渗透到覆盖的每一层之后,再将覆盖展开,得到的就是球面上的一幅图。用术语来说,就是研究f^{-1}([0,1]) 。那么,我们得到的图像会是怎么样的呢?还是用刚才的函数来举例,我们得到的图像如下:

反函数图像

由方弦使用Maple制作

在上图中,黑点代表0对应的点x=1 x=9 ,而白点代表1对应的点x=3+2\sqrt{3} x=3-2\sqrt{3} 。因为这个球面覆盖的次数是4,所以线段[0,1]上的点实际上被覆盖了四次,也就是说,当覆盖展开之后,我们将会看到四段曲线(四条边),它们连接着0对应的两个点x=1 x=9 ,还有1对应的两个点x=3+2\sqrt{3} x=3-2\sqrt{3} 。三重根x=1 上连着三条边,单根x=9 只有一条,而两个双重根x=3+2\sqrt{3} x=3-2\sqrt{3} 各自连接两条边。函数在x=0 x=\infty 两个点上发散,而这个图恰好又有两个面,外部的面对应x=\infty ,而内部的面对应x=0 ,而这些面的度数(也就是边界的长度)与函数在对应点上发散的度数相关。也就是说,单单从这幅图像里,我们就能读出函数本身的许多代数性质。如果把顶点连接的边的数目称为顶点的度数的话,图像性质与代数性质的对应可以归纳成下面的列表:

别雷函数 平面二部地图
覆盖的次数 边的条数
0处的分支点 黑色顶点
1处的分支点 白色顶点
∞处的分支点
0处和1处分支点的重数 顶点的度数
∞处分支点的重数 面的度数的一半

实际上,对于所有的别雷函数,展开对应的球面覆盖后,线段[0,1]的图像总是包含着我们想要的很多代数性质:边的数目对应着覆盖的次数,黑点对应着f(x)=0 的分支,白点对应着f(x)=1 的分支,面对应着无穷大的分支,而每一个点和每一个面连接多少条边,都对应着球面覆盖在对应的分支上“折叠”起来的方法。

那么,别雷函数对应的这些图像,到底又是什么呢?

我们先忽略那些点和线的具体位置和形状,而只关注它们是如何在球面上连结起来的。用数学术语来说,就是先忽略它们的几何性质,而专注于它们的组合性质。首先,因为每条边实际上都来自线段[0,1],所以它们连结的必定是一个对应着f(x)=0 的黑点和一个对应着f(x)=1 的白点。也就是说,别雷函数对应的图像,实际上可以抽象成一个二部图,这类图的顶点,一黑一白,而每条边的两端恰好是一黑一白两个顶点。但这些图像跟一般所说的二部图不完全一样。在数学中,一个图就是一堆顶点加上连结顶点的一些边,但连结同一个顶点的边之间并没有什么特别的关系。但别雷函数对应的图像实际上是一个画在了球面上的图,所以连结同一个顶点的边会在围绕在顶点周围,这就给它们赋予了顺序关系。这样画在了球面(或者别的封闭曲面)上的图,又叫组合地图。而别雷函数对应的图像,正式的名称是平面上的二部地图。在这里,组合地图即使画歪了一点,只要保持顶点、边以及边之间的关系,还算是同一个地图。

二部地图

一个亏格为1的二部地图,由方弦制作

现在我们知道,每个别雷函数都对应着一个平面上的二部地图,那么是不是所有这样的地图都对应着一个别雷函数呢?事实上,利用一些复分析方面的知识,可以证明别雷函数与球面上的二部地图有着一一对应的关系。不仅如此,我们还能把这些别雷函数限定为系数是代数数的分式(代数数就是整系数多项式方程的解)。这实际上就是别雷的贡献:他在1979年证明了,对于一大类重要函数(所谓的“光滑代数曲线”),它们(的适当的等价类)与别雷函数引出的球面覆盖有着一一对应的关系。这些“光滑代数曲线”可以粗略理解为分支点只有0、1和∞,系数是代数数的分式。也就是说,如果我们要找分支点满足某些条件的分式,只需要看看根据这些条件能不能在平面上画出一个二部地图就可以了。

总结一下:三个分支点的球面覆盖,等价于所谓的“平面上的二部地图”,在这个地图上有黑色和白色两种顶点,而每条边都连接一黑一白两个顶点,从而把所有顶点连成一片。而球面覆盖的许多性质,都能反映在地图上的顶点、边和面上。别雷证明了,“光滑代数曲线”(大概就是某一类系数是代数数的分式)与三个分支点的球面覆盖有着一一对应的关系。所以,要寻找分支点满足某些条件的分式,只需要看看能不能画出满足对应条件的二部地图。而任意一个二部地图,哪怕是小朋友的涂鸦作品,也必然存在对应的分式,它的球面覆盖展开之后就是这个二部地图。

涂鸦的例子

涂鸦的例子,作者为Laurent Bartholdi

说了半天,云里雾里的,这又有什么意义?


地图的魔术

我们先回到一开始的问题:对于某个正整数k ,假设有两个互质的多项式P(x),Q(x) ,其中P(x) 的次数是3k Q(x) 的次数是2k 。那么,多项式R(x)=P(x)^2-Q(x)^3 的次数最小可以有多小?

我们现在用别雷函数、球面覆盖和二部地图的眼光来看这个问题。首先,我们来考虑分式f(x)=\frac{-Q(x)^3}{R(x)} 。可以证明,如果f(x) 除了0、1和∞以外还有别的分支点的话,我们就得不到最优解。所以,我们可以假设f(x) 是别雷函数。

函数f(x) 在0处的分支点就是Q(x)^3 的根,也就是Q(x) 的根(计算重数的话,一共有2k 个),但每个根的重数要乘以3。同样的道理,它在∞处的分支点就是R(x) 的根,再加上无穷远点x=\infty ,因为R(x) 的次数比Q(x)^3 要小,所以当x 趋向于无穷时,f(x) 也会趋向于无穷。那么,它在1处的分支点又怎么样呢?这就是我们选取f(x) 的目的:f(x)-1 就等于\frac{-P(x)^2}{R(x)} ,所以,f(x) 在1处的分支点,就是P(x) 的根(计算重数的话,一共有3k 个),但每个根的重数要乘以2。我们可以假定f(x) 没有别的分支点。我们要问的问题实际上就是:f(x) 在∞处的分支点至少有多少个?

我们重温一下球面覆盖和二部地图概念之间的翻译表。

别雷函数 平面二部地图
覆盖的次数 边的条数
0处的分支点 黑色顶点
1处的分支点 白色顶点
∞处的分支点
0处和1处分支点的重数 顶点的度数
∞处分支点的重数 面的度数的一半

如果将所有这些要求翻译成二部地图的概念,我们实际上要解决的是这样的一个问题:

如果一个二部地图,它的白色顶点度数都是偶数,并且加起来是6k ,而黑色顶点的度数都是3的倍数,加起来也是6k ,那么,它至少有多少个面?(在这里,我们不能说白色顶点的度数都是2,因为P(x) 可能有重根,黑色顶点同理)

如果k 很小的话,试着画画也就可以了。但因为现在k 可以要多大有多大,乱试一通大概不太管用。这就是借助别的数学工具的时候了。18世纪的大数学家欧拉(顺带一提,按博士导师的师承关系的话,他是笔者以及很多人的祖师爷)在开辟图论这一领域时,证明了下面的等式:如果一个平面地图有v 个顶点、e 条边和f 个面(最外面的也算一个面)的话,那么必然有

\displaystyle{v-e+f=2}.

我们把这个等式套到我们的问题上,看看会得到什么。容易知道,我们的二部地图必定有3k 条边,也就是说e=3k 。把等式改写一下,我们得到f=2-v+e 。因为我们想知道至少有多少个面,所以我们应该尝试寻找最大可能的v ,也就是最大化顶点的个数。因为白色顶点的度数都是偶数,并且加起来是6k ,要获得最多的顶点,最好的方法就是要求每个顶点的度数都是2,这样就能拿到最多的3k 个顶点。同理,对于黑色顶点,最好的情况就是每个顶点的度数都是3,这样能拿到最多的2k 个顶点。所以,顶点的总数合起来最多是5k 个,也就是v \leq 5k 。代入欧拉的等式,得到的就是f \geq k+2 ,也就是说这样的平面地图至少有k+2 个面。考虑到其中一个面对应的是无穷远点x=\infty ,这就意味着R(x) 的度数至少是k+1 ,而且要达到这个度数,R(x) 必须不能有重根,也就是说每个面(除了最外边)的度数都是2。

我们得到了想要的下界,但还要证明这个下界能够达到,而我们又不想计算无穷个满足条件的多项式,怎么办呢?这就是别雷定理出场的时候了:它告诉我们,只要对应的二部地图能画出来,那么满足要求的分式必定存在,而且系数都是代数数。所以,我们根本不需要计算,只需要画出满足条件的二部地图就足够了。这样的地图画法非常简单:首先画出一棵有2k 个黑色顶点的三叉树(也就是没有圈的地图,而分叉的顶点度数都是3),在每个叶顶点(也就是度数为1的顶点)上画一条跟自身连接的边,然后在每条边中间插入一个白色顶点,就得到了满足条件的二部地图。可以证明,满足条件的二部地图必定能用这样的方法构造出来。根据别雷定理,既然二部地图能画出来,那么满足要求的分式存在,也就是说使R(x) 达到最小度数k+1 P(x),Q(x) 是存在的。

三叉树的构造

三叉树的构造,蒙A. Zvonkine惠允

实际上,我们可以给P(x),Q(x) 施加更复杂的限制,用同样的办法,也能得到R(x) 的最小度数。这个推广首先由U. Zannier在1995年给出,后来A. Zvonkine利用二部地图的方法给出了简单得多的证明。

不仅如此,根据别雷定理,二部地图和分支点只有0、1和∞的分式有着一一对应的关系,所以,要知道有多少组P(x),Q(x) 能使R(x) 达到最小度数,只需要知道有多少个由2k 个顶点组成的三叉树地图。我们之前考虑k=5 的情况,截至2000年,数学家找到了两组解。但要知道一共多少组,只要在纸上随便画画,很容易数出来一共有四组解:

k=5的四组解

k=5的四组解,蒙A. Zvonkine惠允

通过这些地图,我们不仅能知道解的个数,还能部分推断出解的性质。树a和d各自拥有镜像对称性,所以它们对应的解的系数应该都是实数;树b和c分别是各自的镜像,所以它们对应的解的系数可能不是有理数,而是各自的复共轭。因为已知的两组解的系数都是有理数,它们对应的必定是树a和d,而未知的两组解应该向复数领域寻找。果不其然,剩下的两组解在2005年被日本数学家盐田徹治给出,这些解的系数在\mathbb{Q}(\sqrt{-3}) 中,一如预测。

这些预测又从何而来?镜像对称跟系数又有什么关系?要说清楚,就不得不提及二部地图的另一个名字——儿童涂鸦(dessin d’enfant),还有这个术语的创造者,也是现代代数几何的奠基者,伟大的数学家,亚历山大·格罗滕迪克。


一个规划的大纲

亚历山大·格罗滕迪克

亚历山大·格罗滕迪克,图片来自上沃尔法赫数学研究所(Mathematisches Forschungsinstitut Oberwolfach)

“由于目前在大学里教学和研究方面的结合于我而言愈发虚无飘渺,我决定申请加入CNRS,为的是能够将我的精力奉献于发展某些工作和视点,因为现在来看,明显以后找不到会代替我发展它们的学生(似乎连同行的数学家也没有)。”

(Comme la conjoncture actuelle rend de plus en plus illusoire pour moi les perspectives d’un enseignement de recherche à l’Université, je me suis résolu à demander mon admission au CNRS, pour pouvoir consacrer mon énergie à développer des travaux et perspectives dont il devient clair qu’il ne se trouvera aucun élève (ni même, semble-t-il, aucun congénère mathématicien) pour les développer à ma place.)

亚历山大·格罗滕迪克在蒙彼利埃写下这几行文字的时候,正是1984年的某一天,他已经57岁了,经历了太多太多。70年代与嬉皮士为伍,与体制和战争展开激烈但劳而无功的抗争;60年代在法国高等研究所日夜奋战,马不停蹄用深刻的洞察力重塑代数几何,引领法国最尖端的数学人才解决那些最难的问题;50年代投入法国数学界温暖的怀抱,凭借高度抽象的思维崭露头角;还有颠沛流离的童年和青年时期。所有这些都已经过去了,现在他回到了他作为数学家的起点——蒙彼利埃大学——当一名教授,但他也开始厌倦教学了。

他有千言万语要说,但他也很清楚,现在面前的这几页纸,并不适合回忆。旁边厚厚的《收获与播种》(Récoltes et Semailles)的书稿,才是这些反思的去处。他现在要写的,是对今后科研的计划,直白地说,就是一份求职文件,申请的是CNRS的研究员职位,这可以让他免去教学的义务,专心于他的数学研究。他获得过菲尔兹奖,拒绝过克拉福德奖,这些数学界的最高荣誉,对他来说微不足道,他只要继续他的探索。

他并不喜欢体制。纳粹将他的童年破坏得支离破碎,这也许是他反体制反战争思想的来源。正是因为当年法国高等研究所接受了几笔来自军方的资助,他才愤而离开那个数学的乐园,转身投入轰轰烈烈的社会活动。现在又要回到体制,他心里大概也有些挣扎。但他决定了,即使回到体制,也要坚决拒绝腐蚀,绝对不履行那些违反良心的所谓“义务”。

但对数学真理的好奇和渴求大概根植于他心灵的更深处。当年同样的渴求让他出发重新构建了代数几何——那可是一整个数学分支——沿途还得到了无数深刻的结果。现在,他看到了一片肥沃的处女地,但却没人愿意跟他一起耕耘。他大概有些不适应。在法国高等研究所的日子里,他可是领军人物,多少人为听他一席话专程赶到巴黎郊外的Bures-sur-Yvette,那可是一段连现在的轻轨也要花上半小时以上的小旅行。他不知道,70年代他那些鲁莽的抗争,在一定程度上损害了他的声誉。既然没有人来做,那就只能自己来了,他大概是这样想的。

法国高等研究所

法国高等研究所,图片来自Wikipedia

Teichmüller层级(tour de Teichmüller)、绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}} / \mathbb{Q}) 的作用、有限域上的正则多面体、驯顺拓扑(topologie modérée)……他笔下倾泻出近年他关心的数学领域和数学对象,这一写就是48页,还没算上注记。

所有这些想法,其实已经被他写在了另一份文件上,那就是《穿越伽罗华理论的长征》(La Longue Marche à Travers la Théorie de Galois)。但这份完成于1981年,长达1300页的手稿,仅仅为了他自己一个人而写,即使向别人展示,大概也没多少人会有耐心读下去吧。1300页也许很长,但对于一直艰苦工作的格罗滕迪克来说,并不算什么。在他的黄金岁月里,有时候为了节省时间,他仅仅以香蕉和牛奶度日,终日除了休息就是研究代数几何,但这并不影响他思维的敏锐以及清晰的文笔。然而,对于求职文件而言,直接从《穿越伽罗华理论的长征》引述的话,显然不太合适。他面对的评审委员会不可能对他研究的细枝末节都了如指掌,他需要从基础说起,简洁地铺陈出他的想法。

这份求职文件,就是《一个规划的大纲》(Esquisse d’un programme)。也许数学史上再也没有别的求职文件像它那样充满真知灼见了。它很长一段时间没有被正式发表,只在数学圈子里私下流传,但它对数学的影响大概比大部分正式发表的数学论文要更大。它开创了代数几何的一个新领域,这个领域叫远阿贝尔几何(anabelian geometry)。对的,就是望月新一研究的那个远阿贝尔几何。

而对他建立这一套体系起了关键推动作用的,就是二部地图和别雷定理。所有二部地图都能给出一条对应的光滑代数曲线,但这样能否得到所有的光滑代数曲线呢?

“这样的假设当时似乎很离谱,我甚至不敢向这方面的行家询问这个问题。我问过德利涅,他也觉得确实很离谱,但手头上没有反例。不到一年之后,在赫辛斯基的国际数学家大会上,苏联数学家别雷就宣布了这个结果,他的证明简洁得不合常理,在德利涅的信里只占了两页——也许从来没有过如此深刻而奇妙的结果能用那么少的行数来证明!”

(Une telle supposition avait l’air à tel point dingue que j’étais presque gêne de la soumettre aux competences en la matière. Deligne consulté trouvait la supposition dingue en effet, mais sans
avoir un contre-exemple dans ses manches. Moins d’un an après, au Congrès International de Helsinki, le mathematicien sovietique Bielyi annonce justement ce résultat, avec une demonstration d’une simplicite deconcertante tenant en deux petites pages d’une lettre de Deligne – jamais sans doute un résultat profond et déroutant ne fut demontre en si peu de lignes!)

值得一提的是,德利涅(Deligne)是格罗滕迪克的学生,同样是菲尔兹奖获得者。在格罗滕迪克离群索居的岁月里,德利涅几乎是他获取数学新进展的唯一来源。可以看出,别雷定理给格罗滕迪克带来了多大的震动!他把别雷定理对应的二部地图称为“儿童涂鸦”(dessin d’enfant),连小朋友都能随手画出的东西,竟然蕴含着这么丰富的数学内涵!这也为他打开了一道新想法的大门:也许通过研究像组合地图这样非常简单易懂的数学对象,就能探究代数几何这门艰深学科中更深层的结构。在《一个规划的大纲》中,他探讨的就是这个可能性。

在代数数论中,所谓的“有理数的绝对伽罗华群”\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 在研究中占据了重要的地位。不要被看似复杂的符号吓倒,这就是个代号而已。可以说,代数数论中的大部分研究最终都可以跟这个群扯上关系。我们知道,群描述的是对称性,而绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 描述的则是所有代数数(也就是整系数方程的根)的对称性,它的每一个元素都是代数数集合的对称变换,惟独保持每个有理数不变。这样的对称变换又叫有理数的伽罗华变换。但到目前为止,我们仍无缘一睹这个群的全貌。对于那些“交换”(也就是满足ab=ba)的部分,我们已经理解得相当透彻,但这个群的精妙之处在于它“非交换”,也就是“非阿贝尔”的部分,而我们对此仍然所知甚少。对整个绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 结构的研究,是代数数论以至代数几何的重要课题之一。格罗滕迪克的“远阿贝尔几何”,实际上就是尝试研究绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) ,甚至是任意域的绝对伽罗华群,又或者更广泛的“任意代数簇的平展基本群”(étale fundamental group of algebraic varieties),它们“远离阿贝尔”的部分到底如何影响相应的代数结构的几何性质。

代数数

代数数,方程系数越小光点越大,来自Wikipedia,原作者Stephen J. Brooks

格罗滕迪克指出,绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 可以作用在所有儿童涂鸦上,因为每个儿童涂鸦对应着一个光滑代数曲线,也就是一个系数是代数数的多项式,而绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 作为代数数的对称群,当然可以通过对系数的对称变换间接作用在二部地图上。不仅如此,这个作用还是“忠实”的,也就是说,可以通过研究绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 在所有儿童涂鸦上的作用来研究这个群本身。

在绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 中最简单的不平凡变换就是复共轭,也就是将虚数单位i 换为-i 的变换。根据高中的数学知识,在复平面上,复共轭就是沿实数轴的镜像对称,所以它作用在儿童涂鸦上,得到的也是儿童涂鸦的镜像对称。如果一个儿童涂鸦的镜像对称还是它自己,根据别雷定理,复共轭作用到相应的代数曲线上必定得到原来的代数曲线,也就是说所有系数都是实数。如果两个儿童涂鸦互为镜像对称,它们对应的代数曲线的系数必定互为共轭,也就是说起码有一些系数是虚数。这就是我们之前猜测的理论依据。

共轭对称的两个例子

共轭对称的两个例子,蒙A. Zvonkine惠允

但复共轭毕竟是最简单的变换,别的对称变换的结构更为复杂。光滑代数曲线(也就是儿童涂鸦)本身有着许多对称性,对于某种对称性,有没有办法得知它是否来自绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 呢?如果能知道这一点,就相当于刻画了绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 本身。但这是个极端困难的问题。格罗滕迪克当时有一些初步的想法,但这远远不够。如果仅仅依靠儿童涂鸦的组合性质,就能刻画绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 的话,这将会震动代数几何学界:代数几何中深刻的结论,竟然可以从更简单基础的组合数学得出。

儿童涂鸦有着不少的组合不变量,它们在绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 的变换下保持不变:顶点个数、顶点度数、面的个数、面的度数、等等。除了这些看似简单的不变量,我们还可以给每个儿童涂鸦赋予一个群,这个群被称为“儿童涂鸦的单值群”,有时也被直接称作“地图群”。这些地图群拥有更为复杂的结构,但同样在绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 的变换下保持不变。格罗滕迪克的希望,就是在众多的组合不变量中能找到合适的组合,来刻画绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})

注:然而事不如人愿。实际上,单纯的组合不变量不足以做到这一点。A. Zvonkine举出了一个例子,说明要判断两个不同的儿童涂鸦能否通过绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 的作用联系在一起,有时还需要考虑一些数论方面的性质。数学家正在研究这样的情况何时会出现,原因又是什么。

但这还只是故事的开端。格罗滕迪克考虑了所谓的Teichmüller层级(tour de Teichmüller),它的定义非常抽象,但绝对伽罗华群\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}) 同样可以作用于其上。这个Teichmüller层级由无穷个复杂的数学对象一层一层构成。格罗滕迪克认为,要研究有理数上的远阿贝尔几何,从Teichmüller层级入手可能是比较好的方法。他认为,Teichmüller层级所有更高的部分都可以由前两层组合而来,第一层提供的是元素,第二层提供的是元素之间的关系。而这前两层恰好对应着光滑代数曲线(也就是儿童涂鸦),第二层对应的则是在数论中有着广泛应用的椭圆曲线。这就给儿童涂鸦的研究提供了充足的动机。

读到这里的读者,大概都会有一种不明觉厉的感觉。这非常正常,笔者也花了相当的时间,向不同的人请教过,才勉强捉摸到格罗滕迪克整个远阿贝尔集合计划的轮廓。格罗滕迪克写作时,文笔优美思路清晰,这份《一个规划的大纲》也不例外。但他谈论的数学实在过于抽象,难以理解。但这就是格罗滕迪克做数学的风格:尽可能从数学对象中将不必要的细节抽象出来,抽象得一般的数学家都会以为剩下的只有“虚空”,然而他仍然能从“虚空”中抓住某些东西,从而建立他的理论,完成他的证明。用格罗滕迪克本人的说法,如果把数学问题比作坚果,大部分数学家做的就是用锤子和凿子把坚果凿开,而他的做法则是将坚果浸在水里,慢慢软化它的外壳,又或者让它经受风吹日晒,然后等待合适的时机,坚果自然就会裂开。

松鼠

当然坚果要放在合适的地方,否则……图片来自Wikipedia,作者Peter Trimming

对于大部分数学家来说,这个过程太漫长,也许只有拥有深刻洞察力的格罗滕迪克,才能在能接受的时间内,用这种方法解决问题。这也是他的数学难以被理解的原因之一:他几乎不考虑具体的示例,都是从尽可能抽象的角度出发,思考支配某个数学问题背后的宏大数学结构。有时候这也会闹出笑话。有一次讨论数学的时候,有人向格罗滕迪克提议考虑一个特定的质数作为例子。“你的意思是找一个真实的数字?”格罗滕迪克有点疑惑。对方点了点头。他回答:“好吧,我们考虑57这个质数。”57当然不是质数,但格罗滕迪克大概没有注意这一点,他从来不考虑具体的例子,一切从抽象出发。

现在,以同样的抽象风格,格罗滕迪克在《一个规划的大纲》中留下了远阿贝尔几何这一宏伟理论的框架,而儿童涂鸦在其中也占据了一席之地。他的计划,就是慢慢充实这一理论的血肉。

可惜他没有等到理论完善的那一天。


失之东隅

即使他的这份研究计划充满洞见,格罗滕迪克向CNRS递交的职位申请可是让CNRS的管理者伤透了脑筋。在职位申请的档案中,他特地写了一封信,列出了如果被CNRS雇用,他将会拒绝执行的一些CNRS雇员的义务。他的数学能力无可置疑,在60年代就职法国高等研究院之前他也曾经是CNRS的研究员(maître de recherche),但大概没有政府组织会乐意接受像他这样反体制的刺儿头。最后,在许多数学家同行的斡旋下,CNRS以一种特殊的形式“雇用”了格罗滕迪克:他仍然保留在大学的职位,但由CNRS负责他的薪水。于是,他名义上还是大学教授,但因为薪水来自CNRS,他不需要承担任何的教学义务;而又因为他名义上还是大学教授,他不需要负担CNRS雇员的义务。自此之后,他就越来越少踏足大学,直到四年后的1988年他正式退休。

在晚年,他的心灵在混乱中挣扎不休。在1990年,他将一些数学论文、通讯和手稿转赠给了他的学生Malgoire,与此同时,他烧毁了大部分的与数学无关的手稿,总共大概二万五千页,全部付诸一炬。因此,我们现在无法得知他童年的具体经历。他逐渐切断了与数学界的联系,躲进了比利牛斯山脉脚下的某个小村庄,过着隐居避世的生活。而他在远阿贝尔几何上,没有什么进展。

最后,在2014年11月13日,他永远切断了与这个世界的联系。

比利牛斯山脉

比利牛斯山脉,图片来自Wikipedia

在《一个规划的大纲》里,格罗滕迪克提出,要通过研究儿童涂鸦来研究远阿贝尔几何。但对儿童涂鸦的研究并没有预期的那么成功。有许多数学家被《一个规划的大纲》中的深邃视野所吸引,投身于儿童涂鸦的研究中,也取得了一些成果,但远远不足以达成原来的目标。

这也不是格罗滕迪克的研究计划第一次遭受挫折。早在他的黄金年代——上世纪60年代——他就曾提出一系列被称为“标准猜想”(standard conjectures)的猜测,实际上猜测所谓的“代数簇”背后存在某些非常深层次的算术结构。一但标准猜想被证明,许多代数数论中的猜想,例如著名的韦伊猜想(Weil’s conjectures),就能被轻松证明。实际上这也是格罗滕迪克提出标准猜想的目的。他的学生德利涅在1973年最终证明了最后一个韦尔猜想,但并没有取道标准猜想。德利涅想到了一个办法绕过标准猜想,使用一个更为“经典”的技巧完成了证明。而时至今天,标准猜想仍然悬而未决,也没有任何人能看到解决的曙光。

尽管与计划有所出入,远阿贝尔几何本身仍然取得了长足的进展。日本数学家望月新一在1996年证明了《一个规划的大纲》中格罗滕迪克提出的一个远阿贝尔几何的猜想的特殊情况,很快就闻名于数学界,还被邀请在1998年的国际数学家大会上作45分钟报告,这在数学界是一项殊荣。在积蓄了一段时间的力量后,在2012年,望月新一在他的个人主页上挂出了四篇文章,宣布解决了数论中一个悬而未决的重要猜想——ABC猜想。而他所用的工具,正是远阿贝尔几何,但又不单是远阿贝尔几何。

望月新一

望月新一,图片来自他的学术主页http://www.kurims.kyoto-u.ac.jp/~motizuki/top-english.html

望月新一在他的四篇文章中,基于他对远阿贝尔几何的研究,提出了一套全新的理论:宇宙际Teichmüller几何(inter-universal Teichmüller geometry)。还记得格罗滕迪克的Teichmüller层级吗?望月新一的这个理论,大概就是说,考虑单一的Teichmüller层级还不够,需要利用某种方法,引入不同的“变体Teichmüller空间”(更准确地说,是“p进制Teichmüller空间”的变形),再去考虑它们以及它们之间的关系,才能更好地理解整个结构。当然,实际的情况没有听起来那么简单,要定义这些数学对象,甚至要对“乘法”这样基础的数学概念进行“变形”。为了研究这些结构,望月新一还发展了许多工具,填满了四篇文章,加起来超过500页。

在发展这套理论时,望月新一的风格与格罗滕迪克如出一辙:将问题慢慢溶解在抽象的结构中,直到解决方法变得水到渠成。这也使他的论文格外难以理解,因为要理解他对ABC猜想的证明,就要先理解他的宇宙际Teichmüller几何,而这套理论正如其名,就像是用外星语言写就,高度抽象,根本难以入手。据说除了望月新一本人以外,目前世界上只有四名数学家看懂了证明。我们仍不知道望月新一的证明到底是对是错,但在讨论对错之前,他在远阿贝尔几何上发展的这套新理论,无疑值得赞叹。

至于儿童涂鸦,虽然它对于远阿贝尔几何研究的贡献不大,但在其他领域它却大显神通。

我们回顾一下别雷定理:每个儿童涂鸦唯一对应着一个光滑代数曲线。这是一个存在性定理:它只告诉我们对应的光滑代数曲线是存在的,但却没有具体的计算方法。许多需要具体例子的数学家对于这种“管杀不管埋”的定理颇有微词,于是他们开发出了一些具体的计算方法。这些方法现在还不能处理规模太大的儿童涂鸦,但对于许多数学家需要的例子来说绰绰有余。有了具体的计算方法,数学家就能将儿童涂鸦用于更多的数论问题上,尤其是那些与多项式相关的问题。

儿童涂鸦的另一个名字是二部地图。早在格罗滕迪克给它赋予儿童涂鸦这个名字之前,组合学家早就开始了对二部地图,以及更一般的组合地图的研究。二部地图可以推广到所谓的“星座地图”(constellation),它们对应拥有更多分支点的球面覆盖(详见参考文献中S. Lando和A. Zvonkine的著作)。对这些星座地图的研究牵涉到组合表示论、矩阵积分和弦论等高深的数学和物理分支。

星座地图

星座地图,图片由方弦制作

组合学家对于枚举二部地图(更严格地说是所谓的“有根二部地图”)也颇有兴趣,不论是球面上的二部地图,还是任意曲面上的二部地图。每个曲面都有一个叫做“亏格”(genus)的参数。球面的亏格是0,环面的亏格是1,然后每往曲面上多加一个“把柄”,曲面的亏格就多加1。亏格越高的曲面,它上面的二部地图当然也越复杂。在矩阵积分的研究过程中,两位物理学家B. Eynard和N. Orantin发展了一套被称为“拓扑递归”(topological recursion)的方法,他们又发现,这套方法似乎也能用于与矩阵积分息息相关的二部地图的枚举,而且适用于任意亏格曲面上的二部地图。俄罗斯数学家M. Kazarian和P. Zograf首先将这套方法用到了儿童涂鸦的枚举上。后来,法国数学家G. Chapuy以及他的学生通过借用拓扑递归方法中的某些套路,证明了对于某个亏格大于1的曲面,它上面的二部地图的生成函数都能表达成一些简单函数的分式。值得一提的是,在拓扑递归方法中,最重要的一步就是计算亏格为0以及亏格为1的情况的生成函数,之后更高亏格的情况都能由这两种情况计算出来。这与格罗滕迪克对于整个Teichmüller层级能由最底两层产生的想法不谋而合。

亏格为2的二部地图

亏格为2的二部地图,由方弦制作

这就是数学的美妙之处:每个领域与别的领域之间都有着千丝万缕的联系,也许换一个视角问题就会变得深邃而重要,再换一个视角,问题又会变得无比简单。

峰回路转,柳暗花明;失之东隅,收之桑榆。这就是数学。


后记

这是一篇纪念性的文章,试验性质非常重。读到这里的读者,非常感谢你们容忍我的任性,以及所有这些不明觉厉的数学术语。这篇文章讲到的数学既简单又复杂,如果我感受到的数学之美能够向你们传递到一点点的话,我就很满足了。

我对代数几何并不熟悉。在本文写作的过程中,不愿透露姓名的金先生和欧先生给了我很大的帮助。因为他们的研究领域与代数几何相关,所以我曾多次请教他们相关的问题,而他们也很耐心地向我解释了别雷定理以及格罗滕迪克的工作,在这里要再次谢谢他们。当然,如果文章中仍然存在疏漏,那仍然是我个人才疏学浅的责任。

这篇文章的灵感来自Alexandre Zvonkine在波尔多的演讲《Weighted trees》。他是我所在的研究团队的一员,大家都叫他的爱称Sacha,而他今年就要退休了,所以整个团队为他办了一场送别活动,请到了他的合作者和家属讲述他的工作和生活,《Weighted trees》就是他在送别活动上作的演讲。他高水平的演讲生动地说明了儿童涂鸦和别雷定理结合之后可以产生许多有趣的结果。这篇文章就是受他演讲的启发而写的,也用到了他幻灯片中的不少例子。我到波尔多时间不长,但也感受到他的友好。他听说我要写这么一篇文章之后,立刻问我有什么他能帮忙的,之后还关心文章什么时候写好,尽管他看不懂中文。很惭愧,跟他的演讲相比,我只做了一点微小的工作,而且还拖延了这么久。尽管有点迟,这篇文章就作为他退休之际,我送上的一点薄礼吧!

Merci beaucoup Sacha ! Bonne retraite !

Alexandre Zvonkine

Alexandre Zvonkine,图片来自他的学术主页https://www.labri.fr/perso/zvonkin/


参考文献

Alexandre Zvonkine. Weighted trees, Journées Combinatoires de Bordeaux, 2016

Sergey Lando and Alexander Zvonkin. Graphs on surfaces and their applications, volume 141 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, 2004.

Alexandre Grothendieck. Esquisse d’un programme, 1984

Allyn Jackson. Comme Appelé du Néant —— As If Summoned from the Void: The Life of Alexandre Grothendieck, Notices of the AMS, Volume 51, Number 9 and 10, 2004. Part 1, Part 2

Wenjie Fang. Aspects énumératifs et bijectifs des cartes combinatoires : généralisation, unification et application, PhD Thesis, 2016.

概率:了解不确定性

本文已发表于《科学·24小时》2015年11月号,未经书面许可,禁止转载。本文同时在科学松鼠会发表,地址:http://songshuhui.net/archives/93539

“概率”这两个字,除了课本以外,最常出现的地方也许就是天气预报中的“降水概率”,也就是未来几天下雨的可能性有多大。在数学中,概率论是专门研究“可能性”的一门分支。它涉及的问题非常广泛,内容远远超出了中学课本里那些刻板的习题。一切随机或者不确定的事件,都是概率论研究的范畴。上至气象下至金融,甚至连“磁铁的磁性怎么来的”这种物理问题,都可以用概率的方法来研究。

但这门学科的诞生却有些“不太光彩”。


来自赌博的问题

在1654年的一天早上,法国数学家布莱兹·帕斯卡收到了他的朋友贡博的一封来信。这位朋友自称“来自梅雷的骑士”,也算是一位业余数学家。他向帕斯卡提出了类似如下的问题:

两位贵族A与B正在进行一场赌局,赌注是每人500法郎,两人轮流掷硬币,得到正面则A得一分,反面则B得一分,每一局两人得分的机会相等,谁先得到6分谁就得到1000法郎。两人激战正酣,比分达到2比4之际,B突然有事需要终止赌局。赌注应该如何分配才最公平。

这一类问题被称为点数分配问题,早在16世纪就被研究过,但数学家当时的答案并不令人满意,在一些极端情况下会给出非常不合理的分配方案。也许这位“梅雷骑士”也见识过现实中这种赌局引起的矛盾,他希望帕斯卡能够解决这个问题。

帕斯卡对这个问题也很感兴趣。他向另一位业余数学家皮埃尔·德·费马发去一封信讨论这个问题。作为“业余数学家之王”,费马很快就给出了一个答案。他认为,不能单靠赌局停止时的比分或者各自获胜需要的分数来决定赌注的分配,而是应该考虑所有比赛的可能性中,双方获胜的比例。但列举所有的可能性的计算量非常大,帕斯卡继而提出了一个简化算法,完美地解决了点数分配问题。

实际上,他们的解答相当于计算两位玩家胜利概率的大小。在研究中,帕斯卡提出了“数学期望”的概念和著名的“帕斯卡三角形”(杨辉三角)。某个结果为实数的随机事件的数学期望,也就是所有结果按照发生概率加权之后的平均值。数学期望这个概念,掀开了概率论研究的序幕。


什么是概率?

很多概率问题有着特别的结构。对于某个非常简单的随机事件,比如说掷硬币,我们知道每种结果出现可能性的大小,这样的事件被称为“基本事件”。我们可以多次重复这些基本事件,假定它们发生的可能性不会改变,而且这些重复没有相互影响。如果我们将这些基本事件以合适的形式组合起来,就能得到一个更为复杂而有趣的系统。许多概率问题实际上就是对这些随机系统的各种性质的研究。比如说,在点数分配问题中,基本事件就是硬币的投掷,而系统则是赌局的具体规则,最后我们希望知道的则是每一方胜利的可能性大小。

在概率论发展的早期,数学家研究的问题大多比较简单,基本事件只有有限几种结果,组合的方式也相对简单。这样构成的随机系统又叫古典概型。随着数学的发展,数学家开始考虑更复杂的模型。18世纪的法国数学家布丰提出了这样一个问题:在数条间隔相等的平行线之间,随机投下长度与间距相等的一根针,它与这些平行线相交的概率是多少?在这里,因为角度与距离都是连续的值,基本事件有无数不同的结果,这样的随机系统被称为几何概型。

早在19世纪,概率论已经成为了一门枝繁叶茂的数学分支。有趣的是,“概率”这个概念的严格定义要等到20世纪才出现。对于古典概型,因为结果数量有限,概率的定义并没有含糊之处,但几何概型的情况更为复杂。考虑这样的一个问题:圆中的一条随机的弦,它的长度比圆内接正三角形的边长更长的概率是多少?这个问题又叫贝特朗悖论,它奇怪的地方在于,对于不同的选取“随机的弦”的方法,得到的概率也不相同,到底谁是谁非?要等到1933年,俄国数学家柯尔莫哥洛夫为概率论建立公理体系之后,这个问题的解答才变得昭然若揭。柯尔莫哥洛夫将概率模型建立在某一类所谓的“σ代数上的测度”上,这样的测度可以有很多种,不同的测度对应着不同的“随机”。而在贝特朗悖论中,选取随机弦的方法实际上对应着不同测度的选取,也就是不同的“随机”概念,那自然会得到不同的结果。

而到了现在,概率模型的种类越来越多也越来越复杂,系统可以包含无限个基本事件,而具体的组织方式也更复杂更有趣。随机图、渗流模型、自回避行走,这些概率模型早已不能用古典概型和几何概型来概括。也正因为有了这些复杂的模型,我们才能用概率论解决现实世界的种种难题。


无处不在的分布

如果让数学家评选概率论中最重要的定理,桂冠可能非中心极限定理莫属。它不仅是概率论中许多重要结果的基石,在别的学科中,尤其是计算机科学,它也有重要的应用,而在现实生活中,它是整整一个行业赖以生存的理论基础。

中心极限定理其实不止一个,可以说它是一连串定理的总称。它可以看作所谓“大数定理”的细化与推广。假设我们有一枚硬币,它掷出正反面的概率相等。那么,如果我们连续抛掷这枚硬币一万次,常识告诉我们其中大概有五千次是正面。这就是大数定理:对于某个基本事件独立地重复多次的话,某个可能性发生的次数占总数的比例会趋近于这个可能性发生的概率。

与大数定理不同的是,中心极限定理处理的是那些结果是实数的随机基本事件。它告诉我们,如果将许多相同而又独立的基本事件的结果取平均的话,这个平均值会趋向某个概率分布。根据大数定理,这个分布的数学期望就是基本事件的数学期望。而中心极限定理额外告诉我们的,就是这个概率分布必定是一个所谓的“正态分布”,而它的方差,也就是概率分布的“分散”程度,是基本事件的方差除以事件数目的平方根。也就是说,基本事件越多,平均值的不确定性就越小。将这个正态分布画成曲线的话,它就像一个大钟,中间高,但两头呈指数衰减,这也为它赢得了“钟形曲线”这个形象的名字。中心极限定理可以推广到取值范围是高维空间中一点的情况,“相同的基本事件”这个要求也可以被更弱的条件代替,只需要基本事件满足某些要求,而不需要完全相同。

正态分布在自然界中随处可见,比如说人的身高和智力都服从正态分布。这是因为自然界中的很多现象都由各种因素千丝万缕的联系而决定,其中没有特别突出的因素。比如说人的身高,除了由许多不同的基因调控以外,后天的营养、环境、健康,甚至偶然的意外,都有着各自的影响。在这种情况下,如果将每个因素看成一个基本事件,并且假定这些因素各自的影响都差不多,将这些因素综合考虑,根据中心极限定理,得到的结果就非常接近正态分布。

中心极限定理也是保险这一整个行业的基础。每个人都会遇到各种各样的风险,比如事故、疾病等等,这些风险发生的概率都很低,但一旦发生,后果非常严重,并非每个人都能承受。而保险业,实际上就是通过保费与保险赔付的方式,将上千万人连结起来,每人付出相对小的代价,在万一不幸袭来时,就能获得一定的保障。由中心极限定理,这样由数量庞大的个案相加而成的保险业务,由于偶然因素导致无法赔付的概率非常小,而且参与的人数越多,风险就越小。为了确定保费与赔付,保险公司要做的就是根据大量统计数据精确地确定意外发生的概率,然后根据意外概率与收益确定保费与赔付的金额。这也是为什么现代的保险公司越来越重视概率与统计。


理解复杂世界

除了与不确定性相关的问题之外,概率论也与物理息息相关。法国物理学家皮埃尔·居里在攻读博士学位时,就发现了磁铁的一个有趣的性质:无论磁力多强的铁制磁铁,在加热到770摄氏度时,都会突然失去磁性。这个温度后来被称为铁的居里点。为什么磁铁会突然失去磁性?通过概率论与统计物理,我们现在明白,这种现象与冰雪消融、开水沸腾相似,都属于相变的范畴。

我们可以将磁铁里的铁原子想象成一个一个的小磁针。在磁铁还有磁性时,这些小磁针齐刷刷地指向同一个方向,但因为分子热运动的关系,每个小磁针都会时不时地动一下,但很快会被旁边的小磁针重新同化。物理学家将这个场景抽象成所谓的伊辛模型,通过对伊辛模型的研究,概率学家发现,当温度达到某个临界值时,整个体系就会由于热运动而不能保持统一的指向,也就是失去磁性。这个临界值就是居里点,而这样的对伊辛模型的研究也部分揭示了磁铁的一些微观结构的成因。

相变不仅仅局限于物理现象。流言的传播,传染病的爆发,还有微博的转发,都是一种相变过程,都存在某种临界值。比如说传染病,在适当的模型下,如果每个病人传染人数的平均值低于某个临界值,那么疾病就能被控制;如果高于临界值,就很可能导致疫病的全面爆发。对于疾病传播的研究,属于流行病学研究的范畴,而在概率论被引入流行病学研究之后,我们对如何防止与控制疫病爆发有了更深入的了解,这是能挽救成千上万人的知识。

概率论的应用远远不止这些,大至飞机失事搜救,小至垃圾邮件过滤,都能在其中找到概率论的身影。这个复杂的世界充满了不确定性,有些无伤大雅,有些却能致命。要驾驭这些不确定性,就要从了解它们开始。这就是概率论的意义。概率论不能为我们带来一个没有风险的世界,但它却能教会我们如何与风险和平共处。它带来的仅仅是关于不确定性的知识。

但知识,往往就是力量。

编织宇宙的三角形

本文已发表于《科学·24小时》2015年11月号,未经书面许可,禁止转载。本文同时在科学松鼠会发表,地址:http://songshuhui.net/archives/93549

这是一枚行将就木的恒星,在发出黯淡红光的虚胖外壳之下,犹如洋葱般一层套一层,而最深处核心中的燃料早已消耗殆尽,再也释放不出任何能量。外壳失去了支撑后,被恒星引力拉向核心,坍缩开始了。由铁组成的高密度内核不堪重负,电子被压进原子核,在弱相互作用力下,与质子结合变成中子,放出中微子。内核就此被压缩成由中子构成的中子星,而多余的能量被转化为高能粒子,形成一道向外的激波,直面向内坍缩的外层。两者冲击,迸发出摧毁整个恒星的力量,外层被吹散到星际空间之中,散发着媲美千亿个太阳的光芒。在这个过程中,由核反应产生的中子、质子和α粒子,克服着电磁斥力,射进了形形色色的原子核中,在强相互作用力下融合为更大更重的原子核,为生命提供了材料。

超新星遗迹

超新星爆发,宇宙中最壮丽的景象,但演员只有四个:引力、电磁力、强相互作用力、弱相互作用力。不仅如此,世界上所有的现象,不外乎是这四种力的演出。

苹果落地,瀑布激扬,在生活中最常察觉到引力,但引力却最难捉摸。对于其余三种力,物理学家都已经发展出近乎完美的理论,揭示出它们量子化的本质,这些理论能解释许多实验现象,但唯有引力格格不入。爱因斯坦的广义相对论是目前关于引力最好的理论,但数十年来物理学家绞尽脑汁,都无法将它与描述其余三种力的量子场论融合起来。这是当今物理学中最引人注目的难题:如何将广义相对论量子化。

广义相对论告诉我们,引力不过是时空的反映。要将它量子化,最自然的想法就是建立一个量子时空的模型。


平面上的引力

我们的时空有四维,三维空间加一维时间。要一下子建立四维的量子时空太困难,事情要从简单的做起,物理学家于是将目光投向了二维空间。要建立量子时空,第一步就是将时空分割成一个个很小的单元,也就是“时空量子”。量子力学的一大特点就是不确定性,在最小的普朗克长度之下,只有概率分布的存在。所以,时空量子的分割方式必须是概率性的,而量子时空在本质上必然不是一个确定的实体,而是不停改变的一种概率模型,这就是概率学家大显身手的地方。

最简单的想法,就是将二维平面分割成一个个小三角形,这又叫平面的三角剖分。时空无限,所以这样的剖分必定包含无数个小三角形,而由量子力学的不确定性,不同的分割方式出现的概率应该相等。但既然小三角形有无限个,分割方式也有无限种,怎么确保它们出现的概率相等呢?概率学家先从给定个数的三角形出发,这时剖分只有有限个,自然可以给它们赋予相同的概率。然后,只要让三角形的个数趋向无限,可以证明,在某种意义上,这些三角剖分的概率分布会趋向某个连续的极限。概率学家将这个极限称为“一致无限三角剖分”,简称UIPT,这就是物理学家们需要的模型。

三角剖分

概率学家们发现,UIPT拥有很多有趣的性质。首先,它拥有某种分形结构,如果将它的一部分适当地放大,会得到与原来相似的三角剖分,我们甚至可以计算它的分形维度。但这也仅仅是相似而已,因为如果任取一部分,其中几乎必然仅仅包含有限个小三角形,但原本的UIPT拥有无限个三角形。与此相对的是,即使很小的区域,其中也可能包含数量庞大的小三角形。如果将UIPT画成球状,它就像一只刺猬,凸出来的“刺”实际上就是这些三角形密集的地方。

你也许会问,为什么要分割成三角形,而不是四边形或者别的多边形?实际上,概率学家也研究别的分割模型,比如四角剖分。但物理学家认为,无论选取什么样的最小单元,最终得到的极限的物理性质都是相似的。也就是说,这些“无限剖分”模型的许多性质有着一种普适性,无论最小单元有着什么特殊的性质,一旦将镜头拉到无限远,整个空间拥有的性质并不因此改变。也就是说,概率学家可以选择任意的模型来研究,得出的结果大部分也能应用到其他模型。


从平面到时空

但时空量子化的方式不止一种。量子场论向来是物理学家手头的利器,引力之外的其余三种力都属于量子场论管辖的范畴。对于在二维平面上的量子引力,他们猜想它会遵循所谓的“共形量子场论”。虽然处理的对象仍然是空间中的某种概率分布,但在场论的框架下,物理学家手头能用的工具却要多得多。他们发现,有一种被称为“高斯自由场”的共形场论,它不仅能满足物理学上的要求,而且与UIPT有着许多共同的性质。概率学家家猜想,两者也许是同一种量子引力模型的不同表达,外表的分歧仅仅来源于侧重点的不同。对于物理学家来说,这也许已经是公认的事实,但目前还欠缺严格的数学证明。物理学家还有另外一个猜想:无论是高斯自由场还是UIPT,两者也许都服从同一个被称为KPZ关系的概率模型。这也许就是证明前一个猜想的钥匙。

高斯自由场

当然,我们生活在四维时空,而不是二维。研究者当然不会止步于二维量子引力。近年来,一些研究者正在向高维量子引力发起攻势。他们将三角剖分中处于平面内的小三角形,换成处于四维空间中的所谓“单纯复形”,然后用相似的方法将这些小砖块粘合成空间整体,构建起一个高维空间量子化的概率模型。因为维度更高,这样的概率模型研究起来更为复杂,需要解决许多技术性问题。

作为研究领域,量子引力还很年轻。它连接着概率论与物理学,现在已经成为热门的研究方向之一。这个领域有着光辉的前景,也有许多需要解决的难题。但我们相信终有一天,物理学家与概率学家会携手告诉我们,宇宙是由什么样的概率结构编织而成的。


所有图片来自Wikipedia

计算的极限(十一):黄金时代

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

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

计算无处不在。

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

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

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

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬
计算的极限(五):有限的障壁
计算的极限(六):无穷的彼岸
计算的极限(七):宛如神谕
计算的极限(八):符号的框架
计算的极限(九):叹息与奋斗
计算的极限(十):无限绵延的层级


“我要借了阿尔志跋绥夫的话问你们:‘你们将黄金时代的出现豫约给这些人们的子孙了,但有什么给这些人们自己呢?’”

——鲁迅

黄金时代

但波斯特并没有能够亲眼在《数学年报》看到他和克林的这篇论文。

双相情感障碍一直困扰着他,即使每天只工作三小时,即使用尽办法平伏情绪,每得到一些新的数学结果,这些发现和创造都让他激动不已,处于症状发作的边沿。对于数学家来说,这可能是最扭曲最恶毒的诅咒。数学家的使命在于发现新的数学,这种发现必然带来的喜悦,对于波斯特来说,却会危及他为了发现数学所必须的清醒头脑。

在1954年初,又一次的发作将他带到了纽约的一家精神病院。当时治疗精神疾病的主要疗法有两种,波斯特接受的是电休克疗法(http://songshuhui.net/archives/7382),而同样受精神疾病困扰的另一位数学家纳什接受的则是胰岛素休克疗法。电休克疗法在当时还很原始,虽然以相当高的症状缓解率得到了医生的青睐,但原始的疗法过程痛苦可怕,也有一定的副作用。

在1954年4月21日,波斯特接受了又一个疗程的电休克治疗。在他不停抽搐之时,他的心脏失去了控制。

他没有挺过去。

刊登着他和克林的论文的《数学年报》,则是在5月出版,只差不到一个月。

除了波斯特以外,可计算性理论这个领域的其他开拓者,哥德尔、图灵、丘奇这些先驱,他们的结局又如何呢?

由于二战即将爆发,哥德尔在1939年偕同家人移居到了普林斯顿,恰好在图灵回英国之后。之后,他一直作为普林斯顿的教授活跃在数理逻辑学界。但在四十年代后期,他的关注点渐渐从数理逻辑转移到了哲学,也不再发表他的数学工作。可以说,这就是他的数学生涯的终点。而他的人生的终点要等到近四十年之后。在晚年,他的心理变得不稳定,总是怀疑别人要毒害他。在他的妻子因病入院六个月时,他竟然不接受任何人的食物,活活饿死在普林斯顿的医院里。

图灵在1939年博士毕业后回到剑桥,旋即被英国军方聘用,专注破译德军密码,为二战胜利立下了汗马功劳。在战争结束后,他尝试制造一台计算机,但在英国政府的不作为,被在美国的冯·诺依曼抢了先。除此之外,图灵还提出了有关人工智能的图灵测试,并且一直思考前沿的数学问题。作为一名同性恋者,在被警方发现之后,图灵被迫接受治疗。最后在1954年6月8日,他的生命永远地终止了,床边放着一个沾着氰化物的苹果。

丘奇可能是最幸运的人。他一直在数理逻辑这个领域里奋斗,直到生命的尽头,并且硕果累累。这也许是一名数学家能希望拥有的最好结局。他也是一位优秀的博士导师,门下的31位博士中,就有图灵、克林和罗瑟这样的大师。在生命中困扰着他的,也只有晶状体混浊导致的视力问题,与其他几位先驱相比,实在无足轻重。

正因为丘奇卓越的成果,以及其他人的缺席,他以及他的学生在当时的数理逻辑学界中有着举足轻重的影响。自然,丘奇那种过分追求严谨的作风以及他的λ演算在当时也支配了整个学界。但作为计算模型,λ演算不仅不直观,而且过分形式化,很多实际上很简单的结论,用λ演算证明的话会无比繁复。数理逻辑本来就是一门艰深的学科,证明稍稍复杂一些也相对正常。但当图灵机这样直观的模型出现之后,许多定理换用图灵机模型就能被更直观更容易理解地证明,但许多人由于惯性仍然使用λ演算做研究,即使他们对此也颇有微词。

λ演算在当时的影响之大,就连图灵当时在丘奇门下攻读博士时,毕业论文中用到的计算模型也完全是丘奇的那一套λ演算,尽管他自己提出的图灵机概念更加清晰直观。有些数理逻辑学家甚至认为,图灵的序数逻辑当时不受关注,部分原因要归结于用到了λ演算这套形式语言。就连克林,他自己作为丘奇的学生,也对λ演算很不满意,可能是因为他的文章总是遭到读者的冷遇。他在1935年之后很快就抛弃了λ演算,改为用递归函数的模型来阐述结果,读者的反响果然迅速改善。而丘奇过分严谨的作风对学界的统治,使得图灵和波斯特那种诉诸直观(但能被轻易严格化)的证明,在当时被视为异类。

学界的惯性是强大的。丘奇在1935年提出λ演算,而他追求完全严谨的作风对学界的统治要直到五十年代中后期才开始慢慢松动。其中有两个原因:第一是随着可计算性理论的发展,这个领域的定理越趋复杂,λ演算这个框架在严谨性方面带来的好处,逐渐被它的复杂性所抵消;第二是随着基于图灵机模型的现代计算机的发展,人们对图灵机越来越熟悉,对图灵机的研究也越来越深入,人们对于图灵机模型的使用也越来越得心应手。这两个因素一推一拉,渐渐改变了学界的风气。时至今天,在可计算性理论中,人们更偏向于使用图灵机,而λ演算早已不见踪影。但λ演算并没有就此消失于学术界,人们很快就发现它的另一个用武之地,但这是后话,留待后文详述。

哥德尔、图灵、丘奇、波斯特、克林……这些开创者们,告诉了我们“计算”到底是什么,而计算之外又有什么。我们今天能惬意地躺在床上用平板电脑看视频打游戏,能与千里之外的朋友互通消息,也都部分地归功于他们打下的理论基础。但平心而论,我们给这些开拓者的颂扬还远远不够。在一般人心中,他们仍然寂寂无名。这些开拓者们,生前大多没有什么好的结局,就连死后也没有得到多少廉价的赞赏。他们为我们开拓了一个信息化自动化的黄金时代,但他们又得到了什么呢?

但也许他们也并不在乎。就像少年的波斯特那样,也许在他们眼里,数学比尘世间的一切都要美丽,只有万亿光年外宇宙的奇迹才能与之媲美。

这就是信息时代开拓者们的故事。

当然,数学家并不会停止他们探索的脚步。可计算性理论的下一篇章,将会在大洋彼岸被揭开。但在继续追寻之前,我们先来看看,这些开拓者们的遗产到底给我们的生活带来了什么。

计算的极限(十):无限绵延的层级

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

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

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

计算无处不在。

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

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

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

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬
计算的极限(五):有限的障壁
计算的极限(六):无穷的彼岸
计算的极限(七):宛如神谕
计算的极限(八):符号的框架
计算的极限(九):叹息与奋斗


交错的存在所有

波斯特在演讲中谈到了关于自然数集之间归约的问题,而克林当时也正在研究类似的问题:用不同的逻辑公式定义的自然数集,它们是否不同,又有什么不同?如果在一个关于自然数的逻辑公式P(x)中,只有一个自由变元x,那么,使这个公式成立的所有值组成的集合就是P(x)定义的自然数集。每个自然数集又对应一个判定问题:某个自然数n在这个自然数集中吗?

用这种方法定义的自然数集,它们有着什么样的性质呢?

我们知道,在逻辑公式中,除了我们熟悉的变量和加减乘除,还有一种符号叫“量词”。量词分两种,存在量词\exists 和全称量词\forall ,每个量词都带着一个变元。不要将它们视为洪水猛兽,它们不过是又一些符号而已。存在量词的意思是,只要对应变元的某一个取值能满足命题余下的部分,那么整个命题就为真。比如说,“存在一道菜肴,我可以就着吃三碗饭”,那么只要举出一个例子(当然例子很多,白切鸡、清蒸鱼,不一而足),就能说明这个命题为真。而全称量词的意思恰好相反,它需要对应变元的每个取值都能满足命题余下的部分,那么整个命题才是真的。只要有一个反例,命题就被否定了。比如说,“对于所有的菜肴,我可以就着吃三碗饭”,只要举出一个例子(比如仰望星空派),就能否定整个命题。如果我们否定一个开头是存在量词的命题,得到的命题开头就是全称量词,反之亦然。而克林要研究的,就是这些量词会如何影响命题定义的自然数集。

我们知道,所有一阶逻辑的命题都可以将所有量词整理到命题的开头,对于现在的数学系学生来说,这只不过是一道小小的练习题。所以,我们可以假定所有命题都有着这样的形式。按照开头量词的具体形式,克林将所有有关自然数的命题分成了无穷个类别。没有量词的命题被称为零阶命题,而有量词的命题,它们开头必定由存在量词和全称量词交错组成,这样交错的段数,就是命题的阶数。对于一个n阶命题,如果它的开头是存在量词,我们就称它为n阶存在命题,反之则是n阶全称命题。根据这个定义,我们能轻易看出一个性质:n+1阶存在命题,其实就是n阶全称命题开头加上一些存在量词得到的。而在这个性质中,将“存在”和“全称”两个词反过来,它仍然成立。

(注:在关于自然数的逻辑命题中,还有一种特殊的量词,被称为“有界存在量词”。在n阶命题的定义中,我们忽略这些有界存在量词。)

来自Wikimedia

来自Wikimedia

我们来看一个实际的例子。著名的哥德巴赫猜想说的是,对于每一个大于等于4的自然数,都能被写成两个素数的和。对于某个特定的偶数2n+4,我们能将“2n+4能写成两个素数的和”写成以下的逻辑命题:
\forall a \forall b \forall c \forall d \exists p \exists q. n*2=p+q \wedge (\neg (p+2=a*b) \vee (a = 1) \vee (b=1)) \wedge (\neg (q+2=c*d) \vee (c=1) \vee (d=1))
这个命题是一个2阶全称命题,因为它的量词分两截,而开头是一个全称量词。

克林考虑了所有这些类别的命题能定义的自然数集。他将0阶命题定义的自然数集组成的集合称为\Delta_0 ,而将n阶存在命题和n阶全称命题定义的自然数集组成的集合分别称为\Sigma_n \Pi_n 。克林证明了,这些集合组成了一个向上无限绵延的层级,每一层都是自然数集组成的集合,阶数越高,命题能定义的自然数集也越多,表达能力也越强。对于每一层,总有存在这样的集合,它只能被这一层及以上的命题定义,而不能被下方更弱的层定义。也就是说,层级之间的包含关系是严格的。

也许不出大家的意料,克林证明这一切的方法,仍然是康托尔的对角线法。他定义的这个层级,今天被称为算术层级(Arithmetic Hierarchy),是数理逻辑中的一个重要概念。

arith-hierarchy

克林的这项工作,给了波斯特非常大的启发。这是为什么呢?

我们先来看看\Delta_0 到底是什么。假设集合S是\Delta_0 中的元素,那么存在一个只有单个自由变元的但没有量词的命题P(x),某个自然数x属于S当且仅当P(x)为真。那么,对于某个特殊的自然数,比如说42,要判断它是否属于S,只需要将42代入命题P(x)中检查即可。既然P(x)没有量词,那么只要硬算,就必然能得到答案。也就是说,我们有一个算法,它一定会停止,而当它停止时,就能得到答案。记忆力好的读者能观察到,这种算法就是所谓的递归函数。

那么,\Sigma_1 是什么呢?它涉及的命题拥有\exists a. P(x,a) 的形式,其中P(x,a)是一个\Delta_0 中的命题,如果将a看成一个符号的话。那么,要判断这个命题对于某个特殊的x值是对是错,最直接的方法就是先将x值代入命题中,然后对于存在量词中的变量a,从0开始枚举每一个值,然后将这个值代入P(x,a)中,命题中就再也没有自由变量,可以直接硬算它是对是错。一旦找到了某个a的值,使得P(x,a)为真,那么根据存在量词的定义,我们就能判定整个命题为真;但如果命题对于我们的x值来说不为真,那么这样的a值不存在,我们就得一直枚举下去。这是一个不一定会停止的算法,但它仍然是一个算法,而它定义的集合也就是可计算的。

那么,不可计算的问题,比如说停机问题,它又在哪个层级呢?可以证明,停机问题相关的命题可以在更高的\Sigma_2 层级中表达出来。既然层级无限绵延,那么我们自然会提出这样的问题:更高的层级中的问题到底是什么?换句话说,既然有些问题的层级比包含停机问题的\Sigma_2 更高,那么,这是否说明有些问题比停机问题更难?

波斯特之前的工作聚焦于难度处于可计算问题与停机问题之间的问题,但克林的工作促使他将目光投向另一个方向:难度比停机问题更高的计算问题,在图灵归约之下,它们有着怎样的结构?


无法触及的世界

我们先复习一下图灵归约的概念:考虑一台谕示机M,假设它带有问题A的谕示,如果它能解决某个问题B,那么我们说问题B能被图灵归约到A,记作B \leq_T A 。这跟开卷考试很类似,一位学生如果参加关于问题B的开卷考试,却带错了关于问题A的参考书,如果这位学生仍然能借助这本参考书完美地完成考试,那么我们可以说问题B不比问题A难。如果问题B能被图灵归约到A(B \leq_T A ),同时A也能被图灵归约到B(A \leq_T B ),那么我们说A和B是图灵等价的,记作B =_T A

图灵等价是一种等价关系:如果A图灵等价于B,而B图灵等价于C,那么A也图灵等价于C。我们可以将那些相互之间图灵等价的问题归为同一类(数学术语是等价类)。这些类别,被称为“图灵度”,它们之间可以通过图灵规约来比较难度,可以说,在同一个图灵度中的判定问题,在图灵规约的意义下,难度都是相同的,而带有其中任意一个问题的谕示,给谕示机带来的能力都是相同的,可以互相置换。

那么,这些图灵度到底看起来是什么样子的呢?

显然所有的可计算的判定问题都是图灵等价的,因为“可计算”的定义就是“存在图灵机可以解答”,既然一般的图灵机足以解答,那么任意的谕示机当然也可以。因为这些判定问题对于图灵机来说过于简单,不需要谕示就能完成,所以谕示的内容反而变得不重要,带有一个可计算谕示与没有谕示,对于图灵机来说是一样的。同样,任意的可计算判定问题都能图灵规约到任意的判定问题。可以说,在图灵规约的框架下,可计算判定问题就是那些最“简单”的问题,它们组成了最“容易”的图灵度,被记作\boldsymbol{0}

那么,停机问题又如何呢?图灵证明了任意的图灵机都不能解决停机问题,同样,带有一个可计算谕示的谕示机当然也不能解决,因为这样的谕示机与一般的图灵机的计算能力是相同的。也就是说,停机问题不能规约到任何一个可计算的判定问题,也就是说,停机问题比那些可计算的问题要严格地难,或者说,停机问题与可计算问题不在同一个图灵度。所以,我们至少有两个图灵度,一个是可计算的\boldsymbol{0} ,另一个是停机问题所在的图灵度,记作\boldsymbol{0}'

那么,如何构筑更难的问题呢?

图灵在他的博士论文中发现,在停机问题不可计算的证明中,将所有的“图灵机”全部换成“带有‘数论问题’的谕示机”,其他部分不易一字,得到的证明仍然正确。从而他证明了所谓的“数论问题”并不包含所有的计算问题。在这里,图灵选取了“数论问题”这个谕示,但实际上,无论选取什么计算问题的谕示,将它代入原来的证明,得到的证明仍然成立。也就是说,对于任意的判定问题A,带有问题A谕示的谕示机是否会停机,这个判定问题是不能用带有问题A谕示的谕示机解决的。如果问题A是某个图灵度\boldsymbol{a} 中的判定问题之一,刚刚的判定问题必定属于某个更高的图灵度,我们将它记作\boldsymbol{a'}

(注:顺带一提,类似这样可以将“图灵机”换成“谕示机”的证明被称为可相对化的证明(relativizable proof)。这个概念的变体在P与NP问题中占据着重要的地位。更精确地说,在所谓的“多项式归约”的概念下,解决P与NP问题的证明不可能是可相对化的。这个结论又被称为“可相对化障碍”。)

这就是波斯特构筑越来越难的图灵度的方法。对于某个图灵度\boldsymbol{a} ,考虑带有其中问题之一的谕示的谕示机,有关的停机问题处于另一个更高的图灵度\boldsymbol{a'} ,这个图灵度被称为原来图灵度的图灵跳跃(Turing jump)。从可计算问题\boldsymbol{0} 开始,通过图灵跳跃,波斯特能够一步步构建与克林的算术层级相似的图灵度层级,除了最底层的\boldsymbol{0} 以外,每一个层级都对应着那些不可计算的问题,而且层级越高,问题越难。

实际上,波斯特的图灵度层级与克林的算术层级之间的联系,比我们想象中的更深刻。我们定义\boldsymbol{0}^{(n)} 为从最底层的\boldsymbol{0} 出发,经过n次图灵跳跃得到的图灵度。波斯特证明了,如果将判定问题与自然数集等同起来,那么可以说\boldsymbol{0}^{(n)} 恰好处于\Sigma_{n+1} \Pi_{n+1} 的交集之中。也就是说,图灵度层级实际上与算术层级紧密地缠结着,图灵度层级中的每一层恰好处于算术层级的两层之间。

但图灵度层级实际上比算术层级延伸得更远。在算术层级的定义中,第n层是由那些拥有n段不同量词的命题构成的,因为命题的长度有限,所以n只能是自然数。在这里,n表达的是数量,也就是基数。但在图灵度层级中,定义的方法则是通过图灵跳跃,是一种顺序关系。在\boldsymbol{0}^{(n)} 这一层中,编号n实际上是一个序数。实际上,与康托尔的导集以及图灵的序数逻辑相似,图灵度层级实际上可以延伸到“无穷之外”,只有用超穷的序数才能表达所有这些层级。

也就是说,尽管人力能及的只有可计算的问题,但通过逻辑推演,我们能认识到,在那些我们无法解答的问题中,竟然还存在着一个精巧的结构。而正是波斯特,向我们首次展示了这个无法触及的世界。


无限绵延的层级

波斯特很快就将他的部分发现以摘要的形式发表在1948年的《美国数学学会通报》上。克林读到了这篇摘要,自然为波斯特的新发现而兴奋,但他对这份摘要并非毫无意见。

数学家尽管做的都是数学,但他们的处事方式却是各式各样。在提笔写作方面,有的数学家勤于下笔,每获得了新的结果,就会很快写出论文,并通过期刊或者私下流通预印本的形式让同行尽快知道他的结果;有的数学家却惜字如金,即使有了一整套新结果,也记录了相关的定理和证明,但却迟迟不肯下笔,也许是希望更好地打磨这些结果。著名数学家埃尔德什和欧拉是前者的典型代表,两者分别是数学史上发表论文第一和第二多的数学家。而同样著名的高斯和怀尔斯则是后者的典型代表。高斯是个完美主义者,他希望他的著作中毫无瑕疵,“将所有的脚手架去掉”,于是他发现的结果往往在抽屉里一躺就是几年,直到高斯终于满意他的写作,或者别的数学家再次发现这个结果为止。而怀尔斯独自一人在八年时间内钻研,完成费马大定理的证明主体,这早已传为佳话,被认为是怀尔斯坚韧性格的证明。这些不同的风格,也许在不同的环境下有着不同的适应性,但却没有绝对的对与错之分。

波斯特属于惜字如金的那个类别,但与高斯和怀尔斯不同,他喜欢在发表的论文中提及他已经得到的结果,承诺会写出相关的论文,但这个承诺却迟迟不见兑现的踪影。在他发表的这篇摘要里,他除了提到上述超穷的层级结构之外,还提示了更多的结果。也许波斯特是想吊一下别的数学家的胃口,但对于同样在这个领域工作的人,这很不公平。如果你也是研究这个方向的学者,你读了波斯特的这篇文章,可能希望在这些结论上生发出更深入的定理。但因为这些结论的证明并没有正式发表,你并不知道波斯特的这些结论到底是有凭有据,还是仅仅是虚张声势,从而陷入想用但没法用的两难境地。更糟糕的是,如果你发现了相同的结论,希望发表的话,又会出现优先权之争,而这是大家都不希望看到的。无论如何,仅仅提示结果而长久拖延正式论文的发表,对学术整体的发展相当不利。

克林对波斯特这篇摘要的意见也正在于此。他给波斯特写了一封信,除了赞扬他的结果以及一些讨论之外,还提及了不发表的这个问题。克林的信也许使波斯特的良心有些不安,他很快给克林寄去了一份包含他的新结果的手稿。这份手稿延续着波斯特一直以来的风格:依赖直觉,不太严谨,结构也很凌乱。因为这是一份手稿,混乱程度更甚。波斯特自己可能也知道这一点,他给克林的建议是:找个研究生,让他把内容整理出来,然后以合作者的身份一起发表这篇文章。克林依计行事,但这份手稿实在是太难理解,克林找来的研究生实在无能为力,最后克林只好捋起袖子自己动手。

克林是丘奇的学生,也继承了丘奇的那种追求严谨的研究风格。当年丘奇对严谨性的要求曾经让更依赖直觉的图灵吃了不少苦头,这次轮到克林被波斯特的手稿中的各种直觉描述所困扰了。但最终,克林还是将手稿中的内容整理出来,将缺少的证明补齐,并且做了一些延伸的研究,最后写成了一篇论文:

《递归不可解度的上半格》(The upper semi-lattice of degrees of recursive unsolvability)。

所谓的“递归不可解度”,其实就是不可计算的那些图灵度。而“上半格”是一种序结构。波斯特与克林证明了,所有图灵度其实组成了一个非常复杂但有序的结构。我们此前看到,通过图灵跳跃得到的图灵度层级与算术层级关系非常密切,但与算术层级不同的是,在每个图灵度层级之间,还有更加令人惊讶的结构存在,也就是说,阶梯与阶梯之间并不是空无一物,还有更多的结构蕴含其中。这也是显然的,因为自然数的子集有不可数无穷个,但每个图灵度中最多包含可数个子集。所以,图灵度的个数是不可数的,比我们想象中的无穷还要多得多。图灵度层级必然不能概括所有图灵度的结构,那么,必然有更多的结构存在于层级之间。

假设\boldsymbol{a} 是一个图灵度,而\boldsymbol{a'} 是它的图灵跳跃,我们来看看这两层阶梯之间到底有些什么。波斯特与克林证明了,\boldsymbol{a} \boldsymbol{a'} 之间,存在可数无穷个图灵度,它们之间互相不能比较,但都处于两层阶梯之间(用数学术语来说,就是两个图灵度之间至少存在一条可数无穷的反链)。同样在这两层阶梯之间,存在至少一条由图灵度构成的链,其中每个图灵度都可以相互比较,而更有趣的是,对于其中任意两个不同的图灵度,比如说\boldsymbol{c} \boldsymbol{d} ,假设\boldsymbol{c} \boldsymbol{d} 要难,那么这条链之中必定存在另一个图灵度,它的难度处于两者之间,比\boldsymbol{c} 要简单,但比\boldsymbol{d} 要难。用数学的术语来说,就是这条链是稠密的。也就是说,在图灵度层级之中的每两层之间,不仅存在着无数种方法从一层逐级攀登到另一层,而且在某些路径上,有一部分的路程不是常见的一级一级分立的阶梯,而是连续的无可割裂的斜坡。所有图灵度组成的结构,比我们能想像的还要复杂得多。

这篇论文,最终发表在久负盛名的《数学年刊》(Annals of Mathematics)上。可以说,它开创了图灵度研究这个新领域。到现在,图灵度理论已经成为了数理逻辑中非常活跃的一门分支,而其中主要的研究方法——被称为“优先方法”——它的一种雏形同样起源于这篇文章。

这就是作为数学家的波斯特,他的数学研究的顶峰。

计算的极限(九):叹息与奋斗

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

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

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

计算无处不在。

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

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

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

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬
计算的极限(五):有限的障壁
计算的极限(六):无穷的彼岸
计算的极限(七):宛如神谕
计算的极限(八):符号的框架


时代逝去的叹息

波斯特断言,存在一些形式系统,我们无法在有限的时间内知道其中某个命题能不能被证明或否证。可以说,他的断言与10年后哥德尔的不完备性定理非常相似。那么,为什么在数学史中,“不完备性定理”前面的名字不是波斯特,而是哥德尔呢?因为波斯特虽然在1921年得到这个结果,但要等到1943年,在哥德尔、图灵、丘奇的黄金时代过去之后,才得以在极省略的篇幅下发表。

他没有跟上时代的节拍。

当时的美国数学界普遍对数理逻辑没有太大的兴趣,波斯特与他的导师凯泽在当时算是异类。要等到第二次世界大战前夕欧洲数学家大幅迁移到美国,这种状况才开始改变。波斯特曾经将他的想法写成上下两篇论文,并且将上篇提交到《数学年刊》(Annals of Mathematics)。但他得到的回复十分令人失望,同行评议的报告对是否应该发表各执一词,而编辑部也没有给出具体的决定。如果没有上篇的理论奠基,那么下篇就仅仅是空谈。

但无人问津还不是最致命的问题。实际上,波斯特根本没有一个实打实的证明。也就是说,他并没有实际证明他的结论,那只是一种推测再加上关于证明的一些想法而已。虽然以我们的后见之明来看,他的结论与想法都是正确的,但他毕竟没有一个能让别人详细检验的证明。

在数学界,证明就是一切。没有证明,即使看上去再确定无误的结论,哪怕拥有再多的间接证据,哪怕是最优秀的数学家的想法,都只能是猜想,而不是定理。要确立一个定理,就必须有一个滴水不漏的证明。这就是数学界的规则。而很不巧,波斯特的研究风格比图灵更依赖直觉,换种说法就是更不严谨。波斯特的直觉足以预见超越时代的结论,但他却没有对应的能力来将他的直觉在当下整理为严谨而有条理的证明。他的雄心壮志超越了哥德尔,甚至超越了图灵与丘奇,但他当时没有足够的工具,也没有足够的能力来完成这样远大的目标。

但也许波斯特多花些时间整理他的思路,就能写出完整的证明来说服数学界。可惜命运没有给他这样的机会。

就在波斯特取得突破之后不久,也许是由于这个结果的冲击性太大,他的心理失去了平衡。而论文未能成功发表更是为这种失常雪上加霜。他患上的是双相情感障碍,患者会在无端愉悦与无故抑郁中震荡。此后十多年,他一直受双相情感障碍的困扰,在数学上毫无产出,申请到的大学教职也因为发作而不得不放弃。这段时期,他只能当一名中学教师聊以糊口。直到1935年,他才算是回到了学术界。

从1921到1935,波斯特错过了哥德尔,错过了图灵和丘奇。在他迷惘之时,时代巨轮已经呼啸而过,他错过了数理逻辑的黄金年代。在1941年,他写了一篇文章,详细叙述了他此前在逻辑的不完备性方面的工作,投往了《美国数学期刊》。时任编辑赫尔曼·外尔(Hermann Weyl)拒绝了这篇文章:

我毫不怀疑在二十年前你的工作,部分由于它的革命性,没有得到应有的尊重。但我们无法将时针往回拨;在这段时间,哥德尔、丘奇与其他人完成了他们的工作,而美国数学期刊并不是发表历史回顾的地方。

作为编辑,外尔的决定是正确的。探索的前线并不是向迷失者施予救济的地方,历史才是。历史不会忘记这些被忽视的探索者,他们所有的功绩、辛劳与忧伤。波斯特厚厚的研究笔记,就是历史的见证。当时发生的一切将化为铅字,被人们一遍一遍以不同的形式复述,成为集体记忆的一部分。

为传说撰写诗篇,并一直传颂下去,这就是我们能做的一切。

来自Wikipedia

来自Wikipedia


衡量难度的归约

对波斯特来说,错过时代节拍还不算是最大的打击。

当时人们对精神疾病的认识尚浅,没有确实有效的药物,没有确实有效的疗法,一切只能靠摸索。波斯特的双相情感障碍,同样没有标准疗法。当时的想法是,既然发作时出现的是狂喜和抑郁的极端情绪,那么就应该尽量避免这种极端情绪的发生,最好的方法就是限制会导致极端情绪的活动,对于波斯特来说就是数学。他的医生开出的疗法,就是限制波斯特做数学的时间:从下午四点到下午五点,用餐,然后从晚上七点到晚上九点,每天共计三小时。对热爱数学的数学家来说,这简直是能与精神疾病媲美的折磨,就像让美食家用牙签吃最爱的肉酱意粉,我不知道波斯特是如何忍受这种焦灼感的。

幸而波斯特并没有止步不前。他在症状缓解后很快重新投入到数理逻辑的研究中。在图灵刚发表他论述图灵机的论文后,波斯特在对图灵的研究毫不知情的情况下,发表了另一个与图灵机非常相似的模型,现在被称为波斯特机,它与我们常用的计算机更相似,驱动计算的与其说是状态的转移,不如说是语句的执行。他猜想波斯特机的计算能力与λ演算相同,这是个正确的猜测,但他当时无法证明这一点。图灵的桂冠并未因此旁落。而波斯特在看到图灵的构造与证明后也心服口服,他的探索再次失去了意义。他后来也考虑过图灵机在多维上的扩展,与后来的“元胞自动机”颇有相似之处。著名的“生命游戏”就是元胞自动机的一个例子。可惜他并没有发表这个想法。

之后,波斯特转到了布尔函数的研究,也就是那些变量与值都是“真”或者“假”的函数。在1941年,他发表了一个非常重要的结果:对于函数复合封闭的布尔函数类的分类定理。这些类别构成了一个被称为“格”的数学结构,现在被称为波斯特格。对于当时的研究者来说,波斯特的这个结果虽然很有意义,但研究的对象有些偏门,再加上波斯特典型的那种含混晦涩的行文风格,波斯特格这项成果在当时并没有得到太多的重视。要等到几十年后,人们研究约束满足问题时,波斯特格才重新回到人们的视线中。

来自Wikipedia

来自Wikipedia

这项结果虽然一开始不太受重视,但毕竟也是正经的研究结果。就这样,通过不懈的努力,波斯特一点一点重新追上了当时数理逻辑的研究潮流,即使每天只能做三个小时的研究。

在1944年,波斯特应邀在美国数学协会做了一场演讲。后来他将演讲的内容写成了论文并发表。他自己可能没有想到,这篇论文会成为他最有影响力的论文之一。这篇论文的题目是《递归可枚举的正整数集合与它们的判定问题》(Recursive enumerable sets of positive integers and their decision problems),它希望回答的问题非常简洁:停机问题有多难?有比停机问题容易的不可计算问题吗?

有时候错过时代节拍可能也是一件好事,起码对于波斯特而言,与主流的疏离给他带来了一种与众不同的视角。对他而言,判定问题的计算就是形式系统的推演证明,而形式系统的相互包含是一个非常自然的问题。比如说定义自然数的皮亚诺公理体系,就是一种形式系统,而这个系统中的所有命题都能翻译到集合论的策梅洛-弗兰克(ZF)公理体系中,能用皮亚诺公理证明的数学命题,在翻译后都能在ZF中证明。可以说,ZF体系包含了皮亚诺公理体系。那么,给定两个不同的公理体系A和B,我们自然希望考察它们的包含关系,比如说B是否包含A。也就是说,我们希望知道,是否存在一种方法,能将A中的命题翻译到B中,并且希望翻译后,在A中能证明的命题在B中仍然能证明。

波斯特的另一个优势,就是他之前的研究已经涉及到这样一些具体的翻译问题,只不过用的术语不是翻译,而是归约。从一般的形式系统到正则形式A,再到正则形式B,再到一种非常特殊的推演规则,这些都是归约。在关于形式系统不完备性的研究中,波斯特早已自己构造过许多这样的归约。从特殊的归约到一般的“归约”这个概念,对于数学家来说,仅仅是一步之遥。

为了简洁起见,波斯特并没有使用他的正则形式的概念,而是将计算问题表达为一个个由自然数组成的集合。对于数理逻辑学家来说,无论是形式系统、判定问题还是自然数组成的集合,本质上并没有什么不同。形式系统的命题可以用字符串表达,所以可以化为自然数,判断某个命题是否能从公理推演出来,也就相当于判断对应的自然数是否属于可推演命题对应的集合。而一个集合对应的判定问题,就是某个输入作为自然数是否处于这个集合中,所以,指定一个由自然数组成的集合,与指定一个判定问题是等价的。在这个框架下,归约的定义更方便更直观。

归约也有很多不同的种类,它们有强有弱。波斯特在研究形式系统是用到的归约,也就是上面所说的“公理体系之间的翻译”,是其中能力比较弱的一种,又叫“多一归约”(many-one reduction)。而最强的图灵归约在判断A中命题的正误时,可以在可计算的范围内任意生成B中的命题并得到解答,再从这些任意多的解答中提取结论。能获取的解答数目多了,自然也能解决更多问题,也就是说能力越强。

图灵归约是波斯特研究的最终目标,但它的能力太强,很难研究。所以在1944年的这篇论文中,波斯特主要研究的是更简单的多一归约和另一种稍微更强大的“真值表归约”。他证明了,在这两种归约方法定义的难度概念下,存在这样的计算问题,它们是不可计算的,但却比停机问题更容易。也就是说,如果按照这些归约定义的难度来排序,在可计算问题与停机问题之间,存在无数的“中间层级”。从可计算问题到停机问题迈出的这一步,实际上跨过了无数的层级。

波斯特在论文的结尾猜想,对于更强大的图灵归约,这样的“中间层级”也存在,不仅如此,其中有无数个中间层级是计算可枚举的。这并不显然,因为越强大的归约,越能填补不同问题之间难度的差距。比如说,多一归约认为问题A比问题B要难,但这可能是因为它本身太弱,如果换用图灵归约,也许就能通过多问几个问题得出答案。波斯特关于计算可枚举的“中间层级”是否存在的这个问题,又被称为波斯特问题。

波斯特的这篇论文的新观点和新结果最终引起了美国逻辑学家的注意,他终于获得了作为一个数理逻辑学家应有的赞赏。也许,他并不需要什么救济。

在那场演讲之后,在美国数学协会的聚会上,有个人叫住了波斯特。这个人叫克林,也是一位数理逻辑学家(一些读者可能还记得提出λ演算的丘奇就是他的博士导师)。他对波斯特说,有些东西想让他看看,并将波斯特邀请到了他的家中。

这就是波斯特与克林伟大合作的开端。

来自Wikipedia

来自Wikipedia