小朋友的涂鸦

本文遵守首页的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.

计算的极限(十二):不会出错的程序

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

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

计算无处不在。

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

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

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

相信每个人都见识过Windows那令人忧郁的蓝屏或者黑屏吧。有时因为它,一个上午的工作一瞬间毁于一旦,这就不仅是令人忧郁而是令人抓狂了。在这个时候,你是否会在心中大声咒骂那帮写程序不小心让蓝屏一而再再而三出现的程序员呢?但程序员也不是铁打的,他们也会犯错误。而且对于商业软件来说,在上市之前会进行大量的测试,即使有程序错误溜过去了,大多也可以通过打补丁来修复。

但是对于某些软件来说,情况就麻烦得多了。


无妄之灾

在1996年的一个不能说的日子,欧洲航天局第一次发射了新研制的Ariane 5运载火箭。在起飞37秒之后,新火箭很想不开地开花了。这令砸了几亿欧元进去的欧洲航天局非常不爽。经过调查,专家组发现,事故的罪魁祸首竟然是短短的一段代码。

Ariane

在Ariane 5的软件中,有一部分代码是直接来自它的前辈Ariane 4。由于Ariane 4当时非常成功,所以大家觉得这样做没什么问题,根据新的参数稍微修改一下代码就好了。问题是,修改并不完全。有一行代码需要将64位浮点数转换成16位整数,他们认为不会出现什么问题,所以没有进行修改。也没有测试这段代码。

就是这行代码,因为Ariane 5比前辈Ariane 4强力得多,于是在Ariane 4上没有问题的这行代码,在Ariane 5上发生了溢出错误:那个64位的浮点数代表的数值超出了16位整数可以表达的范围。在出错后,备用代码系统被启动,其中包含着同样的一行代码。结果就是整个系统被锁死了。更为讽刺的是,这行代码所在的函数,对于Ariane 5来说是不必要的。这场事故完全就是人祸。

经过这场事故之后,欧洲航天局大为震怒,决定要一劳永逸地解决Ariane 5的问题。他们的要求相当大胆:Ariane 5的软件代码,正式使用前要证明它们不会出现毁灭性的错误,比如不会溢出,不会死循环等等。

这其实并非易事。


停机定理

我们复习一下停机问题:是否存在一种算法,给定任意的程序和输入,都能在有限的时间内判断该程序在给定的输入下是否会停止?正是图灵,证明了这一点是不可能做到的。于是,要编写一个能判断程序会不会进入死循环的算法,这是不可能的。但对于其他类型的程序错误,能否用算法判定呢?

很可惜,这也是不可能的。实际上,我们可以将停机问题规约为检测错误的问题。假设我们有一个程序P,能检测某段代码是否会出现除以零的错误,而我们想要借助这个程序判断某个图灵机在给定的输入下会不会停止。我们可以怎么做呢?首先,对于给定的图灵机和输入,我们可以机械化地将它们转化为一段不用除法但能够模拟该图灵机的代码,然后在模拟结束之后,强行计算1/0。我们将这段代码称为T。代码T在执行时会出现除以零的错误,当且仅当图灵机会停机。然后,我们将代码T输入程序P。于是,既然程序P能判定任意的代码会不会出错,那么就相当于它能判定任意的图灵机会不会停机,而这是不可能的。停机问题不存在普遍的算法,也就是说证明代码无误同样没有普遍算法。

但是,欧洲航天局的任务是否完全不可能完成呢?那倒也不是。停机定理只是说明了不存在程序能正确判定所有程序是否会停止,但欧洲航天局只需要证明Ariane 5的软件代码这一个程序不会出错,所以这条路也没有完全被堵死。

那么,有什么办法呢?


抽象释义

虽然我们不能判定所有程序是否不会出错,但我们能有效判定某些程序不会出错。比如说,如果一个程序没有任何循环语句或者跳转语句,那么这个程序最终肯定停止。但如果程序有循环语句又怎么办?这时,我们并不能确定程序会不会停止,而最保险的办法就是说“我不知道”。

这就是抽象释义(Abstract Interpretation)方法的根本:先抽象出程序的某些信息,再对这些信息进行自动分析,来尝试确定程序是否有着我们想要的性质,比如说不会死循环、不会溢出等等。我们不强求完美的分析,不强求能够识别出所有不出错程序。但为了安全起见,我们要求这种分析是可靠的,也就是说,如果分析的结果认为程序有着我们想要的性质,那么这个结论就不会出错。正是因为这样的权衡取舍,抽象释义方法才能正确有效地实行。

Galois Connection

根据抽象出来的信息多少,不同的抽象释义方法判断同一种性质的效果也不一样。一般来说,抽象出的信息越详细,能识别的拥有某种性质的程序就越多,相应地计算时间也越长。如何在性能和识别率之间做取舍,也是一门复杂的学问,对于不同的应用和数据结构,需要开发不同的抽象方法和自动分析算法。

多种抽象方法还有另一个优点。如果某个程序有着我们想要的性质,但是手头上的抽象释义方法又不能确定时,我们可以换用更精细的、利用更多信息的抽象方法。直接改写代码也是一种规避分析失败的方法。例如,我们想要证明某段代码不会出错,但某种抽象释义方法指示在某句代码上可能会有问题,那么我们可以通过修改代码,换用更加谨慎的处理方法,来保证抽象释义方法能确认新的代码不出问题。

抽象释义方法的奠基者是法国的Patrick Cousot和Radhia Cousot。这对夫妻档总结了一些对程序进行自动形式证明的方法,在此之上提出了抽象释义方法,将其形式化严格化。他们对抽象释义方法的推广也功不可没。除了Ariane 5的代码之外,在别的一些关键应用处的代码也利用抽象释义方法进行了至关重要的验证。一个例子是空中客车A380的控制代码,经过Patrick Cousot的一个小组开发的抽象释义软件Astrée验证,证明了这些控制代码运行时,不会产生像死循环、溢出或者被零除之类的一些软件问题,从而也给安全系数多加了一层保险。

Patrick CousotRadhia Cousot

不过,抽象释义方法只能证明程序有着某种我们想要的性质,不能说明程序是否完成了我们希望的任务。有没有办法做到这一点呢?


形式证明

有一种激进的做法:让程序员在编写代码的同时,给出这段代码确实完成了给定任务的数学证明

要给出这种证明,首先要解决的就是如何将“代码完成了给定任务”转换成数学命题。程序代码可以相当容易用逻辑表达,但代码需要完成什么任务,这只有程序员才知道。所以,要让程序员在编写代码的同时给出证明,为的是让程序员能用逻辑的形式确定这个函数的功能,如此才能得到要证明的命题。这种想法不仅仅是数学家的纸上谈兵。对于某些关键系统,多么微小的疏失都会导致极其严重的后果,人们愿意几乎不惜一切代价防止错误的发生,而对于计算机程序而言,又有什么比数学更坚实的基础呢?

要贯彻这种想法,在编写程序之前,必须先选择一种逻辑体系以及描述它的一种形式语言。这种形式语言必须贯穿整个代码编写的过程:先用形式语言描述程序的输入、输出、功能与限制,然后利用这种与形式语言相近的编程语言去具体编写代码,最后还要利用形式语言给出编写的代码能完美无瑕疵地实现所需功能的数学证明。这种做法又被称为演绎验证(deductive verification),是所谓的“形式化验证”(formal verification)的手段之一。

但数理逻辑毕竟不是一门容易的学科,数学证明对于很多人来说大概比编写代码要困难得多。所以,演绎验证多数也只会用在那些不容有失的关键系统,比如说牵涉人数众多的公共交通设施。例如,在1998年开始运营的巴黎地铁14号线,就是一条全自动的地铁,列车上没有司机,安全行驶也全靠传感器和软件,调度也只需要在控制室点点鼠标就能增加或减少投入运营的列车数量。于是,安全在很大程度上在于软件的可靠性。在控制列车的计算机中,某些与乘客安全休戚相关的关键代码是利用演绎验证编写的。在2012年,巴黎历史最悠久的地铁1号线也从人工运营转到与14号线同系列的全自动化系统。现在,这两条地铁线每天接待的人数加起来超过一百万,但从未因为自动化系统的错误导致乘客伤亡。从笔者的经验来说,它们可以算是巴黎最可靠的地铁线。

Paris Metro 14

但仅有代码的正确性可能还不足以保证程序同样正确,因为代码毕竟不是程序,计算机不能直接执行代码。我们需要另一种名为“编译器”的程序。编译器是将程序员写的代码翻译成计算机能读懂的、用机器语言写就的程序。即使代码是正确的,如果编译器有问题,得出的程序还是可能出错。要避免这个问题,我们同样需要利用数学方法加固编译器这一环。

贯彻这种设计理念的一个例子是一个叫CompCert的C编译器,它由法国计算机科学家Xavier Leroy和他的小组编写。编译器的任务就是进行忠实的代码翻译,确保源代码和目标代码的行为一致。这一点至关重要,否则即使代码是正确的,也不能保证编译生成的程序不出问题。然而,现代的编译器在优化模式下,其实并不能确保忠实的编译。CompCert要解决的就是这个问题。在编写CompCert的时候,对于编译程序的每一步操作,都附带一个数学证明,确保代码的语义不变。因此,数学证明的正确性保证了CompCert编译器会完全忠实地将代码翻译成机器语言。

但即使机器语言是正确的,也还不能完全保证最后执行结果的正确性,因为程序总需要输入输出,而这些功能是由操作系统保证的。如果操作系统本身有错误,即使执行的程序本身是正确的,由于操作系统的问题,也不能保证我们看到的结果是正确的。如果想将数学证明的保证贯彻到底,还需要对操作系统下工夫。这就是seL4所做的事情。seL4是一个微内核,可以看成操作系统的核心。它的每一个功能都附带一个数学证明,在对硬件做一定的假设之后,数学证明的正确性可以保证它提供的功能都会产生我们预先设定的行为。只要硬件不出错,seL4就会正确运行。

当然,一个自然的问题是,如果硬件出错怎么办?硬件的错误可以分为逻辑性错误和物理性错误。前者例如Intel当年在芯片上除法的错误,现在主流硬件厂商早已吸取教训,用演绎验证的方法加固他们的硬件设计;后者例如宇宙射线令硬盘数据出错,这即使是多复杂的证明也避免不了,只能自求多福。尽管数学方法不能保证错误不存在,但至少将可以避免的问题全数避免,这本身就有着莫大的价值。

Real programmers, xkcd
(或者可以利用宇宙射线……?)

概率:了解不确定性

本文已发表于《科学·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