素数的分布

第 1 章 素数的分布：跨越两千年的接力

一八九六年夏天，巴黎科学院的《通报》上先后出现了两篇短文。六月的那篇出自三十一岁的雅克·阿达马，题目直译过来是「关于函数ζ(s)的零点分布及其算术推论」；七月的那篇来自卢万的夏尔·德·拉·瓦莱-普桑，篇幅也不长。两个素不相识的人，用不同的技巧，在几周之内各自证明了同一个悬了一百年的定理：当x趋于无穷时，不超过x的素数个数渐近等于x除以ln x。消息传开，数学界长出了一口气。素数这个最古老的数学对象，第一次向人类交出了它的宏观规律。可是要讲清楚这条规律是怎么来的，我们得把钟表拨回到两千三百年前，从一位在亚历山大城里教书的先生说起。整本书的路线在这一章就定了调：数论的每一次大突破，几乎都源于有人不肯把一个显然的事实当成理所当然。

欧几里得的证明：一份没有起皱的遗产

欧几里得大约生活在公元前三百年，他编写的《几何原本》有十三卷，其中第七、八、九卷讲的是数论。素数无穷的证明出现在第九卷的第二十个命题，原话的希腊文直译是：素数的个数比任何给定的素数集合都要多。注意这个表述，它没有说「素数有无穷多个」，因为希腊人面对无穷这个概念时格外小心，他们用的是一种有限的说法，你给我多少个，我都能再找出一个来。证明本身短得可以在几行内讲完。假设素数只有有限个，把它们记作A、B、C等等，取这三个数的最小公倍数DE，再在DE上加一个单位得到EF。现在问EF被谁整除。EF除以A、除以B、除以C都会余一，所以给定清单里的任何素数都不整除EF。可是EF要么自己是素数，要么有一个素因子，而这个素因子必然不在清单里。清单外还有素数，与假设矛盾，命题得证。

这个证明常被后人复述成一个更直白的版本：把有限个素数全部乘起来再加一，得到的新数要么是素数，要么含有新素因子。这样讲意思没错，但要小心一个流传极广的误解。把清单里的素数乘起来加一，得到的数并不一定是素数。头几个例子很唬人，二加一得三，二乘三加一得七，二乘三乘五加一得三十一，全是素数。可是往下走一步就露馅了，二乘三乘五乘七加一等于二百一十一，这确实是素数，但再走一步，二乘三乘五乘七乘十一加一等于二千三百一十一，还行，而把十三也乘进去，三万零零三十一等于五十九乘五百零九，是个合数。欧几里得本人根本没做这种乘法，他取的是最小公倍数，而且他从没断言那个新构造的数是素数，他只说它的素因子不在清单里。这个细节值得较真，因为它说明了好的证明长什么样：结论恰好够用，一步不多，一步不少。

哈代在《一个数学家的辩白》里专门表扬过这份证明。他说这份证明历经两千年而没有起一道皱纹，依然是初等数论的第一课。我在这里想替欧几里得再添一句赞美。这个证明的力量在于它完全不依赖素数的任何具体性质，它甚至不需要知道任何一个素数是多少。你把整份清单抹掉，换成随便一组素数，论证照样运转。这是一种罕见的普遍性，后来的数学家管这种结构叫「对角线式」或者「自指式」的论证，康托尔证明实数比自然数多、哥德尔证明不完备定理、图灵证明停机问题不可判定，骨子里都是这一招的变体。欧几里得在没人想到无穷该怎么说的时候，就写下了无穷的第一份操作手册。

《原本》数论卷的写作动机里还藏着一条有趣的支线，值得顺路看一眼。欧几里得在第九卷第三十六个命题证明了，如果从二开始连续翻倍，翻p次得到二的三次方那种形状的数，减去一之后恰好是素数，那么用这个素数去乘前面翻倍出来的那一串数，得到的就是一个完全数，一个恰好等于自身全部真因子之和的数。六和二十八是头两个例子，四百九十六和八千一百二十八是后两个。这条定理把素数和一种诱人的不定方程搅在了一起，欧拉后来证明了所有偶完全数都是欧几里得的这个形状，而奇完全数到底存在不存在，到今天仍然无人能答。一个两千三百年前的素数命题挂着一个至今没剪断的线头，这种事在数论里俯拾皆是，我们在第十二章讲梅森素数和计算数论的时候还会再遇见它。

还有一层意思值得说破。欧几里得的证明告诉你素数无穷，但没告诉你素数长什么样。无穷是一张空头支票，你拿着它仍然算不出第一万个素数在哪。数学从这里分出了两条路：一条往下钻，研究单个素数的结构；一条往上看，研究全体素数的分布。本章走的是第二条路，而这条路上的一切工具，微积分、复变函数、傅里叶分析，都是欧几里得死后两千多年才发明出来的。素数问题是块硬骨头，它等得起。

素数到底有多稀：从直觉到数据

要谈分布，先得会数数。数学家习惯用π(x)表示不超过x的素数个数。这个记号和圆周率没有任何关系，纯粹是希腊字母里挑了一个顺手的。π(10)等于4，就是二、三、五、七。π(100)等于25。π(1000)等于168。到了一百万，π(10的6次方)等于78498。十亿以内有50847534个素数。一万亿以内，37607912018个。这串数字单独看没什么节奏，但拿它们和x本身一比，一个模式立刻浮出来：素数在数轴上越走越稀。头一百个数里素数占了四分之一，头一万亿个数里只占百分之零点零零四还不到。可是稀疏的方式非常有规律，不是断崖式的枯竭，而是像一锅汤慢慢熬浓的那种渐变。

对这种渐变，欧拉在一七三七年给出过第二种味道的素数无穷证明。他发表了论文《关于无穷级数的若干观察》，证明所有素数的倒数之和发散。论证的灵魂是他发明的恒等式：把1加上二分之一加三分之一一直加下去的级数，写成对所有素数的一个连乘积，每个素数贡献一个因子。调和级数发散，而连乘积要发散，素数就必须多到某种程度，多到它们的倒数加起来都压不住。一八七四年梅滕斯把这个结果磨得更亮，不超过x的素数的倒数之和，渐近等于log log x加上一个常数。这个证明比欧几里得的强在哪儿？强在它给了无穷一个定量维度：素数不但无穷多，而且不许稀，稀到倒数和收敛的那种稀法是被明令禁止的。从这个意义上说，欧拉是把「素数有多少」从哲学问题改造成了计算问题，本章后面的一切都可以看成这条路的延伸。

直观地感受一下这种稀疏：相邻素数的间隔平均在变大。二和三之间隔一，三和五隔二，一百附近平均隔四五，一百万附近平均隔十三左右。头一个超过一百的素数间隔出现在三十七万附近，从370261直接跳到370373，中间一百一十二个数全是合数。往大了走，这种大洞越来越多，可以证明任意长的间隔都存在，一百个连续合数、一万个连续合数，要多少有多少，构造简单得近乎无赖，从一百零一的阶乘加二开始，连续一百个数挨个都能被二、三、四一直到一百零一整除。可另一方面，素数又抠门地不肯断顿，隔三差五总又冒出来一个。怎么同时刻画「越来越稀」和「永远不会断」这两件事，就是素数分布理论的核心问题。

这里我必须先泼一盆冷水，免得后文显得太顺理成章。素数在个体层面毫无纪律可言。孪生素数有没有无穷多对，到现在没人知道；两个素数间隔会不会任意大，会；素数会不会突然挤成一团，会，可以证明有比平均间隔密得多的素数团块。素数像一群各自为政的散兵游勇，可正是这群散兵游勇加在一起，呈现出整个数学里数一数二的规律性。个体混沌，总体清明，这八个字是理解素数的钥匙，也是理解后面十四章的钥匙。数论的深层结构，很大程度上就是研究如何在个体的不可预测里读出总体的可预测。

在往下走之前，还得给「素数」这个词本身立个案。欧几里得在第七卷开头的定义清单里给出了说法，素数是只能被一个单位量尽的数，翻译成白话就是一个大于一的数，除了一和它自己，谁也除不动它。这个定义里有两个容易被现代人忽略的细节。其一，希腊人不把一当成数，数是从二开始的，所以「一」在他们的体系里扮演的是今日乘法单位元的角色，这个安排意外地干净，避开了把一算作素数的所有麻烦。其二，定义素数需要先有整除的概念，而整除的定义又依赖更基本的「量尽」，也就是量了几次恰好量完，欧几里得用的是一套从度量经验里提炼出来的语言，非常贴近现场。两千年后的我们把定义压缩成一行符号，代价是忘了它原本长在数数的动作里。素数论的一切辉煌，起点不过是对「除得尽除不尽」这件事的较真。

顺便交代一下这些数字是从哪儿来的。数素数这件事在纸笔时代是一门正经手艺。维加一七九七年把素数表推到四十万；奥地利人库利克从一八二五年干到一八六三年，前后三十八年，编出八卷本的因子巨表，覆盖到一亿零三百万，四千二百多页手稿，去世后捐给了维也纳科学院，第二卷后来不翼而飞，成了数学文献史上一桩著名的悬案。电子计算机登场之后，这件事的规模换了量级，二零零八年，奥利维拉-席尔瓦等人把不超过十的十八次方的素数个数一字不差数了出来；再往后，人们干脆不再硬数，而是用ζ函数零点自由区的理论把π(x)夹在两条极窄的缝里核实，到二零一零年代，π(x)已经被这样核实到了十的二十三次方。手艺人换成了机器和定理，但干活的逻辑没变：想要规律，先得有账本。

十五岁少年的表格：高斯与勒让德

第一个摸到总体规律的人是个十五岁的中学生。一七九二年前后，不伦瑞克少年卡尔·弗里德里希·高斯弄到了一张素数表，兰伯特一七七零年出版的对数表附录里带着一张到十万零两千的素数清单。这孩子干了一件极不像十五岁的事：他把素数千个一段千个一段地数，记下每一千个数里素数的个数，然后盯着这些数字看。看着看着他发现，素数的密度大概和一个量的倒数差不多，这个量就是自然对数ln x。一七九三年他在一张对数表的封底用铅笔写下了一行小字，素数小于a时约等于a除以ln a。这行字后来被数学史家反复引用，因为它是素数定理的第一个版本，写它的人还没上大学。

高斯没有发表这个猜测。他一辈子都把它当成一个私人玩具，陆续用手头的素数表和自算的数据反复检验，越验越有信心，并且把猜测打磨得更精细：不超过x的素数个数应当近似等于对数积分li(x)，也就是从二到x对1/ln t做积分。这个li(x)比x/ln x更准，因为它把1/ln t的递降也算进去了。直到一八四九年十二月二十四日，七十二岁的高斯给天文学家恩克写了一封信，圣诞前夜，老头兴致很好，把五十七年前的少年发现原原本本讲了一遍，说他从没认真试图证明这件事，因为「无聊的时候随手玩玩」就足够了，还说倘若这猜测是对的，那真是值得所有数学家庆幸的美事。这封信在高斯死后多年才被整理发表，成了素数定理史上最重要的文献之一。一个人把一个猜想养了五十七年而不声张，这种从容后世再难见到。

高斯的玩法值得再描述得具体一点，因为他的做法里藏着后来一百多年素数研究的方法论胚胎。他不是简单地数一个总数，而是把数轴切成一千个一段的「千数段」，一段一段数，头一段一到一千有一百六十八个素数，下一段一千到两千有一百三十五个，再往下一段一百二十七个。他注意到每一段里素数的频率，大致等于那段中点处自然对数的倒数。用今天的话说，他猜的是素数的密度函数是1/ln x。恩克收到信后认真回了信，两人还讨论了这能不能理解成一个概率陈述，从一个数附近随手抓一个整数，抓到素数的可能性大约是ln分之一。把分布问题改写成概率语言，这一步在高斯手里是自发的，要到二十世纪才被柯尔莫哥洛夫的概率论和素数的随机模型正式接过去。

把猜测写成公式印成铅字的是勒让德。一七九八年，勒让德在《数论随笔》里给出了拟合公式：π(x)近似等于x除以ln x减去一点零八三六六，那个常数是他用数据凑出来的。一八零八年该书第二版他又把公式摆了出来。单纯从拟合精度看，勒让德的公式在当时的数据范围内表现相当好，甚至有人觉得比高斯的li(x)还好。可后来的计算分出了高下。拿十亿这个量级说，π(10的9次方)的真值是50847534，勒让德公式给出的偏差是几十万的量级，而li(x)只差大约一千七百。再往后差距越拉越大，勒让德那个尾巴上挂个常数的做法终究是凑出来的，高斯的积分才是对的形态。高斯本人对勒让德的优先权之争向来冷淡，但历史在这一局上毫不含糊地站在了他这边：素数定理的标准表述，是π(x)渐近于li(x)。

公平起见，得给勒让德记一功，因为单看小数字，他的公式其实更准。拿一百万做裁判：真值78498，高斯的li(x)给出78628，偏了一百三十；勒让德的公式给出78543，只偏了四十五，在当时的素数表范围内，勒让德是更好的拟合。可是把x推到十亿，局面就翻了：真值50847534，li(x)给出50849234，偏一千七百；勒让德公式给出大约五千零九十一万，偏了七万上下，而且偏差的相对比例还在继续恶化。原因说穿了很朴素，勒让德那个一点零八三六六是用有限数据凑出来的常数，它经不起无穷的追问；li(x)的形态则来自对1/ln t的积分，自带逻辑骨架。数学里外推是最危险的游戏，拟合与规律的区别，要到数据够不着的地方才真正显形。

值得停下来咂摸一下这件事的味道。高斯的猜测不是从逻辑里推出来的，是从数据里看出来的。他没有证明，也没有指望短期内有人能证明，因为证明它需要的工具当时整个数学还没有造出来。从一七九二年的封底铅笔字到一八九六年的《通报》短文，中间隔着整整一百零四年，隔着一个微积分严格化、复变函数论从无到有的一百零四年。数学史上反复出现这种局面：正确的猜想先于必要的工具几十年甚至几百年诞生。猜想是种子，工具是土壤，土壤没到季节，种子就安安静静躺着。

切比雪夫的铁腕：差一点就够着了

在阿达马之前，把这个问题推进得最远的人是俄国的切比雪夫。一八四八年他证明了若π(x)与x/ln x的比值有极限，极限只能是1；一八五零年他又发表了更强硬的结果，存在充分大的x，使得不等式零点九二一乘x除以ln x小于π(x)、π(x)小于一点一零六乘x除以ln x成立。也就是说，x/ln x这个量对π(x)的估计顶多偏差百分之十上下，误差因子被死死摁住了。他还顺手证明了贝特朗假设，任何大于一的整数和它的两倍之间至少有一个素数。切比雪夫用的是初等方法加上他特别擅长的精巧估计，把二项式系数的算术性质当杠杆使，硬生生在没有复分析的情况下把素数的宏观行为夹在了两块钢板中间。

切比雪夫的工作在圣彼得堡形成了一个传统，后来叶尔马科夫、马尔可夫、沃罗诺伊都在这个圈子里。有趣的是，切比雪夫离素数定理其实只差一层窗户纸。他证明了比值若有极限必为一，剩下的只是证明极限存在，而这恰恰是初等方法够不着的那一步。极限的存在性藏在素数与对数之间更深的耦合里，要用复变函数的语言才能表述清楚。有数学史家说切比雪夫是「用锤子干绣花活干到了极限」，我深以为然。他的失败不是能力问题，是装备问题。这段插曲给全书写下了一个反复出现的主题：数论的重大进展，常常要等数学别处先发生革命。

切比雪夫还留下了一套沿用至今的记号。他发现直接对付π(x)很别扭，就造了两个替身：θ(x)是不超过x的所有素数乘起来取对数，ψ(x)则把素数的幂也按权数算进去。这两个函数和π(x)在渐近意义上互相等价，谁摸清了谁就都清楚了，而它们天生适合做分析估计。后来人翻解析数论的论文，嘴上讲的是素数定理，手上算的全是ψ(x)减x这一项，追根溯源都是切比雪夫的手笔。一个数学家的贡献有时候不在定理而在记号，好的记号把问题搬到顺手的地形上，功劳不比证明小。

切比雪夫那批成果里最出名的反而是顺手证掉的贝特朗假设。一八四五年，法国数学家贝特朗在研究乘方组合时留意到一个现象并把它公之于众：任何大于一的整数和它的两倍之间必有一个素数。他本人核查到几百万也没找到反例，但给不出证明。切比雪夫一八五二年把它变成了定理，从此「下一个素数不超过两倍远」成了数学家口袋里最常用的工具之一，素数定理的许多应用场景实际上只需要这条便宜得多的事实。一九一九年，拉马努金在病中给出了一个漂亮的新证明，顺手发现了一个更精细的现象：存在一串如今叫拉马努金素数的临界值，保证从那以后任何x到x的一半之间至少有n个素数。这条线索如今已长成素数分布研究的一个小分支，源头就是一次养病时的消遣。

另外一位必须提名的人物是黎曼的前辈、柏林的狄利克雷。一八三七年，狄利克雷证明了算术级数中的素数无穷多，只要首项与公差互素，比如四n加一这样的序列里素数就有无穷多个。为了证明它，他引入了后来以他命名的L函数，把欧拉的ζ函数推广到带特征的情形。这是解析方法第一次在数论里立下大功，素数分布问题从此有了自己的分析工具箱。可以说，素数定理的证明是在狄利克雷开的路上走完最后一程的，这一点后面第七章还会细讲。

黎曼的一八五九：八页纸的施工图

一八五九年十一月，三十三岁的波恩哈德·黎曼被聘为柏林科学院通讯院士，按惯例新院士要提交一篇论文。他交上去的论文只有八页，题目是《论小于给定数值的素数个数》。就是这八页纸，把素数分布问题连根拔起，搬到一片全新的数学大陆上。黎曼做了一件当时看来惊世骇俗的事：他给欧拉的ζ函数，也就是1加二分之一加三分之一一直加下去的那个级数，当变量s大于1时它才收敛，硬是做了两件扩展。第一，他把ζ(s)解析延拓到整个复平面上，让s可以是任何复数，只在s等于一处留一个极点。第二，他证明了ζ函数满足一个漂亮的函数方程，s和1减s两个方向的值被一个精确的公式锁在一起。

然后黎曼问了一个前无古人的问题：ζ函数的复零点都在哪里？他先指出负偶数上全是零点，这些后来被叫作平凡零点；剩下的非平凡零点全都在零和一之间的带状区域里，这叫临界带。接着他写道，所有非平凡零点很可能全都位于实部为二分之一的直线上，虽然他没能给出证明。这条直线后来叫临界线，这个猜测就是黎曼猜想。对素数分布来说，零点的位置就是误差的控制旋钮。黎曼给出了一个精确公式，把π(x)表示成li(x)加上一系列由零点决定的振荡项，每一个非平凡零点贡献一次波动，零点离临界线越近，素数的分布就越驯服。素数定理本质上等价于「ζ在实部为一的直线上没有零点」，而黎曼猜想给出的是误差的最优境界。

这份八页纸的可靠性问题也值得一笔。黎曼写得太省，很多关键论断只给了思路甚至只给了断言。零点个数的渐近公式，是冯·曼戈尔德特一八九五年补出完整证明的；ξ函数按零点做乘积展开的合法性，靠的是阿达马一八九三年的整函数理论；显式公式的严格版同样出自曼戈尔德特之手。换句话说，一八九六年登顶的两位并非只走了最后一里路，他们还替黎曼把地基重新浇了一遍。黎曼这篇论文因此在数学史里占着一个奇怪的位置：它既是纲领又是债务，先知式的断言与欠账的证明缠在一起，逼着此后半个世纪的解析数论边还债边前进。

黎曼一八六六年死于肺结核，年仅三十九岁。他没有留下这篇论文的完整细节，很多论断只写了「从我的一个尚未发表的研究中可以看出」。直到一九三二年，西格尔在哥廷根图书馆翻检黎曼的手稿，才发现黎曼生前已经算出了第一批零点的近似位置，还创造了一套计算零点的公式。这桩公案后面第八章再展开。这里只强调一点：黎曼的八页纸是一张施工图，素数定理、黎曼猜想、零点与素数的精确对应，全部工程都在图上画好了，一八九六年的两位证明者，不过是照图施工的头两个工人。

一八九六年：两个证明与一种巧合

现在可以回到本章开头的那两篇短文了。阿达马一八九六年的路线是：先研究整函数的亏格与零点分布，这是他一八九二年博士论文攒下的本事，再用这些一般定理卡住ζ函数，证明它在实部为一的直线上取不到零值。瓦莱-普桑走的是另一条路，直接对对数导数做精细估计，证明实部为一、虚部很大的地方ζ不消失，还给出了更明确的零点自由区。两人用的框架不同，落点相同：实部为一的直线上没有零点，素数定理随之成立。当时阿达马三十一岁，瓦莱-普桑二十九岁，素数定理这座一百多年的冰山，被两个年轻人在同一个夏天凿开了。

阿达马晚年在《数学领域中的发明心理学》里回忆过