第一部分　数学

孪生素数猜想 ^[1]

2003年3月28日，在美国数学研究所（American Institute of Mathematics）位于加州帕洛阿尔托（Palo Alto）的总部，一群来自世界各地的数学家怀着极大的兴趣聆听了圣荷西州立大学（San José State University）数学教授戈德斯通（Daniel Goldston）所做的一个学术报告。在这个报告中，戈德斯通介绍了他和土耳其海峡大学（Bo ğ aziçi University）的数学家伊尔迪里姆（Cem Yıldırım）在证明孪生素数猜想（twin prime conjecture）方面所取得的一个进展。这一进展——如果得到确认的话——将把人们在这一领域中的研究大大推进一步。

那么，什么是孪生素数（twin prime）？什么是孪生素数猜想？戈德斯通和伊尔迪里姆所取得的进展又是什么呢？本文将对这些问题做一个简单介绍。

要介绍孪生素数，首先当然要说一说素数（prime number）这一概念。素数是除了1和自身以外没有其他因子的自然数。在数论中，素数可以说是最纯粹、也最令人着迷的概念。关于素数，一个最简单的事实就是：除了2以外，所有素数都是奇数（因为否则的话，除了1和自身以外还会有一个因子2，从而不满足定义）。由这一简单事实可以得到一个简单推论，那就是：大于2的两个相邻素数之间的最小可能的间隔是2。所谓孪生素数指的就是这种间隔为2的相邻素数，它们之间的距离已经近得不能再近了，就像孪生兄弟一样。不难验证，在孪生素数中，最小的一对是（3，5），在100以内则还有（5，7）、（11，13）、（17，19）、（29，31）、（41，43）、（59，61）和（71，73）等另外7对，总计为8对。进一步的验证还表明，随着数字的增大，孪生素数的分布大体上会变得越来越稀疏，寻找孪生素数也会变得越来越困难。

那么，会不会在超过某个界限之后就再也不存在孪生素数了呢？

这个问题让我们联想到素数本身的分布。我们知道，素数本身的分布也是随着数字的增大而越来越稀疏的，因此也有一个会不会在超过某个界限之后就再也不存在的问题。不过幸运的是，早在古希腊时代，著名数学家欧几里得（Euclid）就证明了素数有无穷多个（否则的话——即假如素数没有无穷多个的话——今天的许多数论学家恐怕就得另谋生路了）。长期以来数学家们普遍猜测，孪生素数的情形与素数类似，虽然其分布随着数字的增大而越来越稀疏，总数却是无穷的。这就是与哥德巴赫猜想（Goldbach conjecture）齐名、集令人惊异的表述简单性与令人惊异的证明复杂性于一身的著名猜想——孪生素数猜想。

孪生素数猜想：存在无穷多个素数 p ，使得 p +2也是素数。

究竟是谁最早明确地提出这一猜想我没有考证过，但1849年法国数学波利尼亚克（Alphonse de Polignac）曾提出过一个猜想：对于任意偶数2 k ，存在无穷多组以2 k 为间隔的素数。这一猜想被称为波利尼亚克猜想（Polignac's conjecture）。对于 k =1，它就是孪生素数猜想。因此人们有时把波利尼亚克作为孪生素数猜想的提出者。值得一提的是，人们对不同的 k 所对应的素数对的命名是很有趣的： k =1（即间隔为2）的素数对我们已经知道叫做孪生素数； k =2（即间隔为4）的素数对被称为cousin prime（表兄弟素数），比“孪生”稍远；而 k =3（即间隔为6）的素数对竟被称为sexy prime！这回该相信“书中自有颜如玉”了吧？不过别想歪了，之所以称为sexy prime，其实是因为sex正好是拉丁文中的“6”（因此sexy prime的中文译名乃是毫无联想余地的“六素数”）。

孪生素数猜想还有一个更强的形式，是英国数学家哈代（Godfrey Hardy）和李特伍德（John Littlewood）于1923年提出的，有时被称为哈代-李特伍德猜想（Hardy-Littlewood conjecture）或强孪生素数猜想（strong twin prime conjecture） ^[2] 。这一猜想不仅提出孪生素数有无穷多组，而且还给出其渐近分布为

其中 π 2 （ x ）表示小于 x 的孪生素数的数目， C 2 被称为孪生素数常数（twin prime constant），其数值为

强孪生素数猜想对孪生素数分布的拟合程度可以由表1看出。很明显，拟合程度是相当漂亮的。假如可以拿观测科学的例子来作比拟的话，如此漂亮的拟合几乎能跟英国天文学家亚当斯（John Couch Adams）和法国天文学家勒维耶（Urbain Le Verrier）运用天体摄动规律对海王星位置的预言，以及爱因斯坦（Albert Einstein）的广义相对论对光线引力偏转的预言等最精彩的观测科学成就相媲美，可以算同为理性思维的动人篇章。这种拟合对于纯数学的证明来说虽起不到实质帮助，却大大增强了人们对孪生素数猜想的信心。

在这里还可以顺便提一下，强孪生素数猜想所给出的孪生素数分布规律可以通过一个简单的定性分析来“得到” ^[3] ：我们知道，素数定理（prime number theorem）表明对于足够大的 x ，在 x 附近素数的分布密度大约为1/ln（ x ），因此两个素数位于宽度为2的区间之内（即构成孪生素数）的概率大约为2/ln 2 （ x ）。这几乎正好就是强孪生素数猜想中的被积函数——当然，两者之间还差了一个孪生素数常数 C 2 ，而这个常数显然正是哈代和李特伍德的功力深厚之处 ^[4] 。

除了强孪生素数猜想与孪生素数实际分布之间的漂亮拟合外，对孪生素数猜想的另一类“实验”支持来自于对越来越大的孪生素数的直接寻找。就像对大素数的寻找一样，这种寻找在很大程度上成为了对计算机运算能力的一种检验。1994年10月30日，这种寻找竟然使人们发现了英特尔（Intel）奔腾（Pentium）处理器浮点除法运算的一个瑕疵（bug），在工程界引起了不小的震动。截至2002年底，人们发现的最大的孪生素数是：

(33 218 925 × 2 169 690 - 1，33 218 925 × 2 169 690 + 1）

这对素数中的每一个都长达51 090位。许多年来这种纪录一直被持续而成功地刷新着，它们对于纯数学的证明来说虽也起不到实质帮助，却同样有助于增强人们对孪生素数猜想的信心 ^[5] 。

好了，介绍了这么多关于孪生素数的资料，现在该说说人们在证明孪生素数猜想上所走过的征途了。

迄今为止，在证明孪生素数猜想上的成果大体可以分为两类。第一类是非估算性的，这方面迄今最好的结果是1966年由中国数学家陈景润利用筛法（sieve method）所取得的 ^[6] 。陈景润证明了：存在无穷多个素数 p ，使得 p +2要么是素数，要么是两个素数的乘积。这个结果的形式与他关于哥德巴赫猜想的结果很类似 ^[7] 。目前一般认为，由于筛法本身所具有的局限性，这一结果在筛法的范围之内已很难被超越。

证明孪生素数猜想的另一类结果则是估算性的，戈德斯通和伊尔迪里姆所取得的结果就属于这一类。这类结果估算的是相邻素数之间的最小间隔，更确切地说是：

翻译成白话文，这个表达式所定义的是两个相邻素数之间的间隔与其中较小的那个素数的对数值之比在整个素数集合中所取的最小值。很明显，孪生素数猜想要想成立，△必须为0。因为孪生素数猜想表明 p n+1 - p n =2对无穷多个 n 成立，而ln（ p n ）→∞，因此两者之比的最小值对于孪生素数集合——从而对于整个素数集合也——趋于零。不过要注意，△=0只是孪生素数猜想成立的 必要条件 ，而不是充分条件。换句话说，如果能证明△≠0，则孪生素数猜想就被推翻了；但证明了△=0，却并不意味着孪生素数猜想一定成立。

对△最简单的估算来自于素数定理。按照素数定理，对于足够大的 x ，在 x 附近素数出现的几率为1/ln（ x ），这表明素数之间的平均间隔为ln（ x ），从而（ p n+1 - p n ）/ln（ p n ）给出的其实是相邻素数之间的间隔与平均间隔的比值，其平均值显然为1 ^[8] 。平均值为1，最小值显然是小于等于1，因此素数定理给出△≤1。

对△的进一步估算始于哈代和李特伍德。1926年，他们运用圆法（circle method）证明了假如广义黎曼猜想（generalized Riemann hypothesis）成立，则△≤2/3。这一结果后来被苏格兰数学家兰金（Robert Alexander Rankin）改进为△≤3/5。但这两个结果都有赖于本身尚未得到证明的广义黎曼猜想，因此只能算是有条件的结果。1940年，匈牙利数学家埃尔德什（Paul Erdös）利用筛法率先给出了一个不带条件的结果：△<1（即把素数定理给出的结果中的等号部分去掉了）。此后意大利数学家里奇（Giovanni Ricci）于1954年，意大利数学家蓬皮埃利（Enrico Bombieri）、英国数学家达文波特（Harold Davenport）于1966年，以及英国数学家赫克斯利（Martin Huxley）于1977年，分别将△的估算值推进到了△≤15/16，△≤（2+ ）/8≈0.466 5，以及△≤0.442 5。戈德斯通和伊尔迪里姆之前最好的结果则是德国数学家梅尔（Helmut Maier）于1986年得到的△≤0.248 6。

以上这些结果都是在小数点后面做文章，戈德斯通和伊尔迪里姆的结果将这一系列努力大大推进了一步，并且——如果得到确认的话——将在一定意义上终结对△进行数值估算的长达几十年的漫漫征途。因为戈德斯通和伊尔迪里姆所证明的结果是△=0。当然，如我们前面所述，△=0只是孪生素数猜想成立的必要条件，而不是充分条件，因此戈德斯通和伊尔迪里姆的结果即便得到确认，离最终证明孪生素数猜想仍有相当的距离，但它无疑将是近十几年来这一领域中最引人注目的结果。

一旦△=0被证明，下一个努力方向会是什么呢？一个很自然的方向将是研究△趋于0的方式。孪生素数猜想要求△～[ln（ p n ）] -1 （因为 p n+1 -p n =2对无穷多个 n 成立）。戈德斯通和伊尔迪里姆的结果所给出的则是△～[ln（ p n ）] -1/9 ，两者之间还有不小的差距 ^[9] 。但是看过戈德斯通和伊尔迪里姆手稿的一些数学家认为，戈德斯通和伊尔迪里姆所用的方法还存在改进空间。也就是说，他们的方法还有可能对△趋于0的方式作出更强的估计。从这个意义上讲，戈德斯通和伊尔迪里姆这一结果的价值不仅仅在于结果本身，更在于它有可能成为一系列未来研究的起点。这种带传承性的系列研究对于数学来说有着双重的重要性，因为一方面，这种研究可能取得的新结果将是对数学的直接贡献；另一方面，这种研究对戈德斯通和伊尔迪里姆的结果会起到反复推敲与核实的作用。现代数学早已超越了一两个评审花一两个小时就可以对一个数学证明做出评判的时代。著名的四色定理（four color theorem）和费马大定理（Fermat's Last Theorem）都曾有过一个证明时隔几年、甚至十几年才被发现错误的例子。因此，一个复杂的数学结果能成为进一步研究的起点，吸引其他数学家的参与，对于最终判定其正确性具有极其正面的意义 ^[10] 。

2003年4月6日写于纽约

2014年9月15日最新修订

魔方与“上帝之数” ^[1]

2008年7月，来自世界各地的很多优秀的魔方玩家聚集在捷克共和国（Czech Republic）中部城市帕尔杜比采（Pardubice），参加魔方界的重要赛事：捷克公开赛。在这次比赛上，荷兰玩家阿克斯迪杰克（Erik Akkersdijk）创下了一个惊人的纪录：只用7.08秒就复原了一个颜色被打乱的魔方。无独有偶，在这一年的8月，人们在研究魔方背后的数学问题上也取得了重要进展。在本文中，我们就来介绍一下魔方以及它背后的数学问题。

一、风靡世界的玩具

1974年春天，匈牙利布达佩斯应用艺术学院（Budapest College of Applied Arts）的建筑学教授鲁比克（Ernö Rubik）萌生了一个有趣的念头，那就是设计一个教学工具来帮助学生直观地理解空间几何中的各种转动。经过思考，他决定制作一个由一些小方块组成的，各个面能随意转动的3×3×3的立方体。这样的立方体可以很方便地演示各种空间转动。

这个想法虽好，实践起来却面临一个棘手的问题，即如何才能让这样一个立方体的各个面能随意转动？鲁比克想了很多点子，比如用磁铁或橡皮筋连接各个小方块，但都不成功。那年夏天的一个午后，他在多瑙河畔乘凉，眼光不经意地落在了河畔的鹅卵石上。忽然，他心中闪过一个新的设想：用类似于鹅卵石表面那样的圆形表面来处理立方体的内部结构。这一新设想成功了，鲁比克很快完成了自己的设计，并向匈牙利专利局申请了专利。这一设计就是我们都很熟悉的魔方（magic cube），也叫鲁比克方块（Rubik's cube） ^[2] 。

6年后，鲁比克的魔方经过一位匈牙利商人兼业余数学家的牵头，打进了西欧及美国市场，并以惊人的速度成为了风靡全球的新潮玩具。在此后的25年间，魔方的销量超过了3亿个。在魔方的玩家中，既有牙牙学语的孩子，也有跨国公司的老总。魔方虽未如鲁比克设想的那样成为一种空间几何的教学工具，却变成了有史以来最畅销的玩具。

魔方之畅销，最大的魔力就在于其数目惊人的颜色组合。一个魔方出厂时每个面各有一种颜色，总共有6种颜色，但这些颜色被打乱后，所能形成的组合数却多达4 325亿亿 ^[3] （1亿亿=1×10 16 ）。如果我们将这些组合中的每一种都做成一个魔方，这些魔方排在一起，可以从地球一直排到250光年外的遥远星空——也就是说，如果我们在这样一排魔方的一端点上一盏灯，那灯光要在250年后才能照到另一端！如果哪位勤勉的玩家想要尝试所有的组合，哪怕他不吃、不喝、不睡，每秒钟转出10种不同的组合，也要花1 500亿年的时间才能如愿（作为比较，我们的宇宙目前还不到140亿岁）。与这样的组合数相比，广告商们常用的“成千上万”、“数以亿计”、“数以十亿计”等平日里虚张声势、忽悠顾客的形容词反倒变成了难得的谦虚。我们可以很有把握地说，假如不掌握诀窍地随意乱转，一个人哪怕从宇宙大爆炸之初就开始玩魔方，也几乎没有任何希望将一个色彩被打乱的魔方复原。

二、魔方与“上帝之数”

魔方的玩家多了，相互间的比赛自然是少不了的。自1981年起，魔方爱好者们开始举办世界性的魔方大赛，从而开始缔造自己的世界纪录。这一纪录被不断地刷新着，截至2013年，复原魔方的最快纪录已经达到了令人吃惊的5.55秒。当然，单次复原的纪录存在一定的偶然性，为了减少这种偶然性，自2003年起，魔方大赛的冠军改由多次复原的平均成绩来决定 ^[4] ，截至2013年，这一平均成绩的世界纪录为6.54秒。这些纪录的出现，表明魔方虽有天文数字般的颜色组合，但只要掌握窍门，将任何一种给定的颜色组合复原所需的转动次数却很可能并不多。

那么，最少需要多少次转动，才能确保 无论什么样的颜色组合 都能被复原呢 ^[5] ？这个问题引起了很多人，尤其是数学家们的兴趣。这个 复原任意组合 所需的最少转动次数被数学家们戏称为“上帝之数”（God's number），而魔方这个玩具世界的宠儿则由于这个“上帝之数”而一举侵入了学术界。

要研究“上帝之数”，首先当然要研究魔方的复原方法。在玩魔方的过程中，人们早就知道，将任何一种 给定的颜色组合 复原都是很容易的，这一点已由玩家们的无数杰出纪录所示范。不过魔方玩家们所用的复原方法是便于人脑掌握的方法，却不是转动次数最少的，因此无助于寻找“上帝之数”。寻找转动次数最少的方法是一个有一定难度的数学问题。当然，这个问题是难不倒数学家的。早在20世纪90年代中期，人们就有了较实用的算法，可以用平均15分钟左右的时间找出复原一种 给定的颜色组合 的 最少转动次数 。从理论上讲，如果有人能对每一种颜色组合都找出这样的最少转动次数，那么这些转动次数中最大的一个无疑就是“上帝之数”了。但可惜的是，“4 325亿亿”这个巨大数字成为了人们窥视“上帝之数”的拦路虎。如果采用上面提到的算法，用上面提到的速度寻找，哪怕用一亿台计算机同时进行，也要用超过1 000万年的时间才能完成。

看来蛮干是行不通的，数学家们于是便求助于他们的老本行：数学。从数学的角度看，魔方的颜色组合虽然千变万化，其实都是由一系列基本操作——即转动——产生的，而且那些操作还具有几个非常简单的特点，比如任何一个操作都有一个相反的操作（比如与顺时针转动相反的操作就是逆时针转动）。对于这样的操作，数学家们的“武器库”中有一种非常有效的工具来对付它，这工具叫做群论（group theory），它比魔方问世早了140多年就已出现了。据说德国数学大师希尔伯特（David Hilbert）曾经表示，学习群论的窍门就是选取一个好的例子。自魔方问世以来，数学家们已经写出了好几本通过魔方讲述群论的书。因此，魔方虽未成为空间几何的教学工具，却在一定程度上可以作为学习群论的“好的例子”。

对魔方研究来说，群论有一个非常重要的优点，就是可以充分利用魔方的对称性。我们前面提到“4 325亿亿”这个巨大数字时，其实有一个疏漏，那就是未曾考虑到魔方作为一个立方体所具有的对称性。由此导致的结果，是那4 325亿亿种颜色组合中有很多其实是完全相同的，只是从不同的角度去看——比如让不同的面朝上或者通过镜子去看——而已。因此，“4 325亿亿”这个令人望而生畏的数字实际上是“注水猪肉”。那么，这“猪肉”中的“水分”占多大比例呢？说出来吓大家一跳：占了将近99%！换句话说，仅凭对称性一项，数学家们就可以把魔方的颜色组合减少两个数量级 ^[6] 。

但减少两个数量级对于寻找“上帝之数”来说还是远远不够的，因为那不过是将前面提到的1000万年的时间减少为了10万年。对于解决一个数学问题来说，10万年显然还是太长了，而且我们也并不指望真有人能动用一亿台计算机来计算“上帝之数”。数学家们虽然富有智慧，在其他方面却不见得富有，他们真正能动用的也许只有自己书桌上那台计算机。因此为了寻找“上帝之数”，人们还需要更巧妙的思路。幸运的是，群论这一工具的威力远不只是用来分析像立方体的对称性那样显而易见的东西，在它的帮助下，更巧妙的思路很快就出现了。

三、寻找“上帝之数”

1992年，德国数学家科先巴（Herbert Kociemba）提出了一种寻找魔方复原方法的新思路 ^[7] 。他发现，在魔方的基本转动方式中，有一部分可以自成系列，通过这部分转动可以形成将近200亿种颜色组合 ^[8] 。利用这200亿种颜色组合，科先巴将魔方的复原问题分解成了两个步骤：第一步是将任意一种颜色组合转变为那200亿种颜色组合之一，第二步则是将那200亿种颜色组合复原。如果我们把魔方的复原比作是让一条汪洋大海中的小船驶往一个固定目的地，那么科先巴提出的那200亿种颜色组合就好比是一片特殊水域——一片比那个固定目的地大了200亿倍的特殊水域。他提出的两个步骤就好比是让小船首先驶往那片特殊水域，然后从那里驶往那个固定目的地。在汪洋大海中寻找一片巨大的特殊水域，显然要比直接寻找那个小小的目的地容易得多，这就是科先巴新思路的巧妙之处。

但即便如此，要用科先巴的新思路对“上帝之数”进行估算仍不是一件容易的事。尤其是，要想进行快速计算，最好是将复原那200亿种颜色组合的最少转动次数（这相当于是那片特殊水域的“地图”）存储在计算机的内存中，这大约需要300兆（300MB）的内存。300兆在今天看来是一个不太大的数目，但在科先巴提出新思路的年代，普通计算机的内存连它的十分之一都远远不到。因此直到3年之后，才有人利用科先巴的新思路给出了第一个估算结果。此人名叫里德（Michael Reid），是美国中佛罗里达大学（Unversity of Central Florida）的数学家。1995年，里德通过计算发现，最多经过12次转动，就可以将魔方的任意一种颜色组合转变为科先巴新思路中那200亿种颜色组合之一；而最多经过18次转动，就可以将那200亿种颜色组合中的任意一种复原。这表明，最多经过12+18=30次转动，就可以将魔方的任意一种颜色组合复原。

在得到上述结果后，里德很快对自己的估算作了改进，将结果从30减少为了29，这表明“上帝之数”不会超过29。此后随着计算机技术的发展，数学家们对里德的结果又作出了进一步改进，但进展并不迅速。直到11年后的2006年，奥地利开普勒大学（Johannes Kepler University）符号计算研究所（Research Institute for Symbolic Computation）的博士生拉杜（Silviu Radu）才将结果推进到了27。第二年（即2007年），美国东北大学（Northeastern University）的计算机科学家孔克拉（Dan Kunkle）和库伯曼（Gene Cooperman）又将结果推进到了26，他们的工作采用了并行计算系统，所用的最大存储空间高达700万兆（7×10 6 MB），所耗的计算时间则长达8 000小时（相当于将近一年的24小时不停歇计算）。

这些计算表明，“上帝之数”不会超过26。但是，所有这些计算的最大优点——即利用科先巴新思路中那片特殊水域——同时也是它们最致命的弱点，因为它们给出的复原方法都必须经过那片特殊水域。可事实上，很多颜色组合的最佳复原方法根本就不经过那片特殊水域，比如紧邻目的地，却恰好不在特殊水域中的任何小船，显然都没必要像中国大陆和台湾之间的直航包机一样，故意从那片特殊水域绕一下才前往目的地。因此，用科先巴新思路得到的复原方法未必是最佳的，由此对“上帝之数”所做的估计也极有可能是高估。

可是，如果不引进科先巴新思路中的特殊水域，计算量又实在太大，怎么办呢？数学家们决定采取折中手段，即扩大那片特殊水域的“面积”。因为特殊水域越大，最佳复原路径恰好经过它的可能性也就越大（当然，计算量也会有相应的增加）。2008年，研究“上帝之数”长达15年之久的计算机高手罗基奇（Tomas Rokicki）运用了相当于将科先巴新思路中的特殊水域扩大几千倍的巧妙方法，在短短几个月的时间内对“上帝之数”连续发动了四次猛烈攻击，将它的估计值从25一直压缩到了22——这就是本文开头提到的人们在研究魔方背后的数学问题上取得的重要进展。罗基奇的计算得到了电影特效制作商索尼图形图像运作公司（Sony Pictures Imageworks）的支持，这家曾为《蜘蛛人》（ Spider-Man ）等著名影片制作特效的公司向罗基奇提供了相当于50年不停歇计算所需的计算机资源。

由此我们进一步知道，“上帝之数”一定不会超过22。但是，罗基奇虽然将科先巴新思路中的特殊水域扩展得很大，终究仍有一些颜色组合的最佳复原方法是无需经过那片特殊水域的，因此，“上帝之数”很可能比22更小。那么，它究竟是多少呢？种种迹象表明，它极有可能是20。这是因为，人们在过去这么多年的所有努力——其中包括罗基奇直接计算过的大约4 000万亿种颜色组合——中，都从未遇到过任何必须用20次以上转动才能复原的颜色组合，这表明“上帝之数”很可能不大于20；另一方面，人们已经发现了几万种颜色组合，它们必须要用20次转动才能复原，这表明“上帝之数”不可能小于20。将这两方面综合起来，数学家们普遍相信，“上帝之数”的真正数值就是20。

2010年8月，这个游戏与数学交织而成的神秘的“上帝之数”终于水落石出：研究“上帝之数”的“元老”科先巴、“新秀”罗基奇，以及另两位合作者——戴维森（Morley Davidson）和德斯里奇（John Dethridge）——宣布了对“上帝之数”是20的证明 ^[9] 。他们的证明得到了谷歌公司（Google）提供的相当于英特尔（Intel）四核心处理器35年不停歇计算所需的计算机资源。

因此，现在我们可以用数学特有的确定性来宣布“上帝之数”的数值了，那就是：20。

2008年11月2日写于纽约

2014年9月18日最新修订