动机
欧几里得(Euclid)证明了素数永远没有尽头,但这几乎没有说明素数究竟有多丰富。在一个很大的界以下,素数只有寥寥数个,还是占全部整数的相当比例?初等估计已经能确定正确的量级:不超过 的素数个数,被 的正常数倍从上下两侧夹住。
证明的方法是在中心二项式系数中计数素数幂。该系数的大小大致随其指标呈指数增长,因此它的素因数分解必须含有足够多的对数权重。我们先估计这一权重,再去掉高次素数幂带来的额外贡献,最后才把它转化为素数的个数。另一个有限乘积的论证则证明素数倒数之和发散。这一切都不假设素数定理。
所用工具为唯一分解、阶乘、二项式系数及对数的基本性质。所有对数均为自然对数。最后的某些渐近比较用到一个初等事实:对数的增长慢于正的幂函数;这是实变量估计,并非关于素数的未经证明的断言。
定义
定义 9.2.1
(素数计数与素数的对数权重)
设 为正素数全体。对实数 ,定义
最后一个和式对每个素数,按其不超过 的每一个正整数次幂各计一次。因此它是有限和,且 。两个加权和在 时均为零。它们在非整数处的值等于在对应的下取整处的值。
概念视角代数
素数幂权重作为最小公倍数的对数
同一个函数有一个封闭的乘法描述:
素数 在该最小公倍数中的指数,是满足 的最大 ,而 恰好把 加上这么多次。例如 ,而 。这说明了:尽管我们最终关心的是素数本身,计数素数幂仍然是有用的。
为什么素数幂权重也属于算术函数
定义 9.2.2
(素数幂权重 )
当 ( 为素数, 为正整数)时,定义 ;其余情形(包括 )定义 。于是 。
这就把同一个加权计数问题写成了一个求和型算术函数,从而与除数和单元联系起来。
若 ,则使 不为零的 的因数,恰为每个素因数 的 。它们的贡献之和为 。于是 ,再由已证明的莫比乌斯(Möbius)反演公式得 。这两个恒等式都不涉及极限或解析延拓。素数幂之所以出现,是因为对数会计入分解中一个素数的每一份重复;若略去高次幂,就会丢掉这些重复。下面的二项式证明正是通过阶乘的赋值来做同样的记账。
定理
定理 9.2.3
(中心二项式系数控制素数幂权重)
对每个整数 ,
并且
因此,对每个实数 ,
这些常数有意取得较宽松,以保持估计的初等性与显式性。
定理 9.2.4
(素数计数的初等量级)
对每个实数 ,
若 为第 个素数,则对所有充分大的 , 被 的正常数倍从上下两侧界住。此外 发散。这些结论并不断言 ,也不断言其精确的极限常数,更不断言一致的素数间隔界。
证明思路
先求精确指数,再估计系数
证明
(中心系数的赋值与大小)
对素数 ,计数阶乘中 的倍数,得
每个被 整除的整数因子,在前 个计数中各贡献一次,恰为其指数。因此
对任意实数 , 为 或 :把 写成整数部分加小数部分即可看出。所以每个素数幂位置至多向该系数的对数贡献一份 ,而 的位置没有贡献,由此证明了以 为上界。若 ,则上式的差恰为 ,由此证明了以 为下界。较小的素数幂位置也可能有贡献;因此这个下界一般并不是等式。
二项式定理给出 。中心系数是其中最大的:相邻系数之比为 ,在中间之前大于 ,在中间之后至多为 。因此最大的系数至少等于平均值 ,而没有任何系数超过总和 。取对数即证明两个大小估计。
对二进增量求和得上界,用一个大系数得下界
证明
( 的线性界)
在二的幂处取 ,第一个不等式与二项式上界估计给出
从 起逐项向上求和,并利用 ,得 。对实数 ,取满足 的最小的幂 ;它小于 。由单调性,。
下界方面,令 。则 ,,再由系数的下界估计得
当 时,这至少为 。为严格验证最后这一数值比较,考察其差 。它在 处等于 ,由于 而为正。其导数 在该点及其后均为正。因此所述的界中不存在隐藏的大 例外。
高次素数幂的贡献小于主要的线性权重
证明
(从 到 再到 )
只有 的素数,才可能贡献超过其首项 的部分。对任何这样的 ,它的全部贡献为 ,所以额外的贡献之和小于 。这样的素数至多有 个,这里甚至用的是对所有整数计数的粗略界。因此
对 ,有 。事实上,这个比值在 时递减,而在 处它等于 ,小于所声称的界。将此与 的估计结合,得到
每个素数 都有 ,所以 。这证明了素数计数的下界。至于上界,低于平方根的素数至多有 个,而其余每个素数对 的贡献都大于 。因此
这里在此范围内 ,且 。必须先分出小素数:若给每个素数都赋权 ,则对上界而言方向是错的。
证明透视
加权计数需要两个不同方向的不等式
从 过渡到 用到两个方向相反的权重比较。计数下界把 除以最大可能的权重:每个 都不超过 ,所以 。计数上界则需要最小可能的权重,唯一不显然的一步,即在 处分割,正是在这里出现。若不分割,最小权重是 ,只能得到 ,量级是错的。在 以上,每个权重都大于 ;而 以下的素数只作粗略计数,代价仅为 。
门槛 在两侧各用一次。在下界一侧,高次幂误差 必须不超过 ,即 下界常数的一半,才能在 中保留 的一个正倍数。在上界一侧,它保证 ,而常数之所以能够收拢,是因为 。
把量级反过来,得到第 个素数的量级
证明
(第 个素数的界)
记 ,。对充分大的 ,取 ,其中 。则 ,所以 ,从而 。反过来,令 。当 充分大时,,且 ,所以 ,从而 。这就给出了所述的两个常数倍。这些限定条件来自初等的对数比较;前一个定理中显式的门槛 并没有被悄悄地当作指标 的门槛来使用。
有限欧拉(Euler)乘积迫使素数倒数之和发散
证明
( 的发散)
对固定的实数 ,展开有限乘积
每个因子都是收敛的几何级数。由于因子个数有限且所有项非负,它们的乘积恰好是所有素因数都不超过 的正整数的倒数之和。唯一分解保证每个这样的整数恰好出现一次。特别地,它包含每个整数 ,所以该乘积至少等于 ,而这个调和和随 趋于无穷。
然而,若 收敛,则乘积的对数将有界:对 ,有 ,这可由把 从 到 积分得到;每个 都在此范围内。因此它的对数至多为 ,在该假设下有界。取指数后与调和下界的无界性矛盾。这就在没有操作未经证明的无穷乘积、也没有假设素数密度极限的情况下,证明了发散。
例题详解
例题 9.2.5
(一个小系数说明素数幂的界为什么是不等式)
当 时,中心系数为 ,其素因数分解为 。而 ,因为不超过 的素数幂有 ;并且 。于是定理给出 。区间 提供了被迫出现的素数幂位置 和 。 的额外一份来自较小的位置 ,那里 ;素数 尽管被计入 ,对该系数却毫无贡献,因为 。赋值公式恰好解释了这两处差异。
例题 9.2.6
(显式常数是证书,而不是接近真值的预测)
在 处,计数的下界为 ,所以到该点至少有 个素数。上界为 。这个区间有意取得很宽。它的价值在于:两个端点都来自只用初等估计的证明,且同样的常数对所有更大的实数 都成立。该定理确定的是一个增长量级,而不是相对误差很小的数值逼近。
例题 9.2.7
(有限欧拉乘积包含超出其截断的整数)
对素数 ,乘积为 。调和和 为 ,严格较小。该乘积还包含 以及每个仅由 构成的整数的倒数,即使该整数超过 。因此它是支配截断调和和,而不是等于它。这份额外的正质量是无害的,而这恰好说明了为什么下界对发散的证明已经足够。
反例模式
无穷多个正项的和未必发散
素数的平方给出一个无穷级数,但 收敛:它以 为上界,而最后一个级数是裂项相消的。因此仅凭欧几里得的素数无穷性,不能证明素数倒数之和发散;有限乘积的论证提供了真正额外的信息。
常见错误
常见错误
(以素数幂自身的对数作权重)
函数 给每个素数幂 的权重是 ,而不是 。在 处,正确的值是 ,即 的对数;错误的权重则给出 。赋值也须同样小心:一个素数幂可以在阶乘计数的不止一层上有贡献,所以估计之前须保留精确的下取整公式。
常见错误
(在计数上界中丢掉小素数修正)
把 除以 只给出 的下界。计数上界需要每个权重的下界,而这只对 成立。其余小素数的 一项有其确定的作用,不能不加替代地丢弃。
常见错误
(把常数倍的界读成渐近定律)
以 的两个常数倍为界,并不能确立 ,甚至不能确立任何极限。该证明也不表明每个固定长度的区间都含有素数。同样,有限欧拉乘积包含由不超过 的素数构成的任意大整数,因此不应与截断相同的调和和等同。
总结
中心二项式系数把阶乘赋值转化为 的线性界。高次素数幂只贡献较小的误差,由此得到 的线性界,以及素数计数的 量级。把这些界反过来,得到第 个素数的 量级。有限几何乘积与唯一分解则独立地证明了素数倒数之和发散。
练习
快速检查
(在 处,通过计算 ,验证 的素数幂解释。)
解答 · 答案
不超过 的极大素数幂为 ,所以最小公倍数为 。它的对数等于 ,即 。而 对这四个素数的对数各只含一份,剩下的额外权重为 。
快速检查
(由所述的初等误差估计证明 。并说明为什么仅凭这一点不能证明素数定理。)
解答 · 答案
把误差估计除以 ,得到以 为界,它趋于零。因此这两个加权函数相差一个次线性的量。但它们已证明的主要界的常数不同:对其中任何一个,都没有证明它与 之比为 。两个未知的线性量级函数之间的微小差距,并不能确定它们共同的极限系数。
快速检查
(证明有限乘积 趋于零,并解释它们的倒数在发散证明中的含义。)
解答 · 答案
它们的倒数支配调和和,因而趋于无穷。每个因子都为正,所以取倒数后可见乘积趋于零。这并不断言任何一个有限乘积为零;每一个都是严格为正的有理数。极限表达的是越来越多的素数倒数贡献。
快速检查
(为什么 给出的是 的下界而不是上界?利用平方根分割修正这个错误的上界论证。)
解答 · 答案
将不等式除以正数 ,得 。要给出上界,低于平方根的素数至多有 个,而每个更大的素数都有 。因此它们的个数至多为 ,再加上小素数的余量,就得到已证明的上界估计。同一个加权和之所以能在两个相反的方向上给出计数估计,只是因为作了这两种不同的最大权重与最小权重的比较。