献给约翰·纳什 素数 你还记得素数,对吧?它们无法被其他自然数整除?OK。于是我们有了一个 3000 多年的问题:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, p。p 是多少?31。下一个p呢?是 37。之后的 p呢?41。接着呢?43。但是……你怎么知道下一个 p 是什么?
若你能提出一个论点或公式(甚至仅在任何给定的数列中)能预测到下一个素数是什么,你的名字就会与人类思想中最伟大的成就之一永远联系在一起,与牛顿、爱因斯坦和哥德尔比肩。如果能解决素数为何表现出如此的性质,你就永远不用再做任何事情了,永远。
引言 历史上曾有多位数学巨匠研究过素数的性质。从欧几里得对素数无限性的第一个证明,到欧拉将素数与 zeta 函数联系起来的乘积公式;从高斯与勒让德提出的素数定理公式,到它被阿达马和德拉瓦莱普森证明;依旧占据主导地位的数学家波恩哈德·黎曼则独立为素数理论做出了最大的突破。他对素数的分布做出了新的,前无古人的发现,所有这些都包含在一篇 1859 年出版的 8 页论文里,它至今仍是数论中最重要的论文之一。
自该论文出版以来,黎曼的论文一直是素数理论的中心,它确实是素数定理在 1896 年被证明的主要原因。自此之后,数学家们又找到了几个新的证明,包括塞尔伯格和埃尔多斯的基本证明。然而黎曼关于 zeta 函数根的猜想依旧成谜。
素数有多少? 先来点儿简单的。我们都知道(除 0 和 1 外)一个自然数不是素数就是合数。所有合数都由素数构成,且可被因数分解为一些素数的乘积。素数则是该构建过程中的“积木”或“基本元素”。欧几里得在公元前 300 年证明了素数有无限个。
欧几里得定理 设素数集有限。建立一个所有素数的列表。令 P 为该列表中所有素数的积(将列表中的所有素数相乘)。将结果数字加一,Q = P + 1。同所有数字一样,数字Q不是素数就是合数: 若 Q 为素数,你就找到了一个不在“所有素数的列表”中的素数。 若Q非素数,则为合数,即在列出的所有素数中,存在素数p可整除Q(因为所有合数都是一些素数的乘积)。每个构成 P 的素数 p 显然整除 P。若 p 能同时整除 P 和 Q,那么它应当也能整除二者之差,即 1。然而没有素数能够整除 1,因此 p 必定不在该素数列表中,这与该列表包含所有素数矛盾。 总存在另一个能整除 Q 的素数 p 不在该列表中,因此素数必有无限个。
为何素数如此难以理解? 任何初学者都能理解我前面提出的问题,仅此一点就足以说明它有多么困难。甚至在进行过大量研究后,我们对素数的代数性质仍然知之甚少。科学界十分确信我们缺乏理解素数行为的能力,大数的因式分解(即找出一个数是由哪两个素数相乘所得)便是加密理论的基础之一。下面就是一种寻找它们的方法:
我们已经很好地理解了合数,即所有的非素数。它们由素数构成,你很容易就能写下一个式子来预测和/或生成合数。这样的“合数过滤器”称作一个数筛,最有名的例子便是约公元前 200 年的“埃拉托斯特尼筛法”。它所做的就是简单地在一个有限集中标记出每个素数的倍数。所以,先取素数 2,并标记出 4,6,8,10 等,接着取素数 3,然后标出 6,9,12,15 等等,最后就只剩素数了。虽然很好理解,但正如你所料,埃拉托斯特尼筛法并不高效。
函数 6n ± 1 能显著简化此工作,这个简单的函数会产生除2和3之外的所有素数,并移除所有3的倍数和所有偶数。将 n = 1,2,3,4,5,6,7 代入会产生结果:5,7,11,13,17,19,23,25,29,31,35,37,41,43。该函数生成的非素数只有 25 和 35,它们分别可被分解为 5 × 5 和 5 × 7。如你所料,之后的非素数为 49 = 7 × 7、55 = 5 × 11 等等。挺的简单吧?
为了从视觉上展示它,我使用了自己称为“合数梯”的东西,它能直观地展现出该函数生成的合数相对于每个素数的布局和组合。在下图的前三列中,你可以清晰地看到素数 5, 7, 11 与它们各自的合数梯一直到 91。第四列的混乱则展示了此筛子如何移除素数以外的所有的数字,它清楚地展现了为何素数如此难以理解。
<img src="https://pic2.zhimg.com/v2-a5d1810315db596d2daf69d5902ba4f5_b.jpg" data-caption="" data-size="normal" data-rawwidth="897" data-rawheight="760" class="origin_image zh-lightbox-thumb" width="897" data-original="https://pic2.zhimg.com/v2-a5d1810315db596d2daf69d5902ba4f5_r.jpg"/> 合数梯子
基础资源 所以这一切都与你可能听说过的“黎曼猜想”有关?嗯...简单来说,为了更好地理解素数,数学家们在 19 世纪便不再尝试预测素数的精确位置,转而将素数的现象视为一个整体。这种分析 的方法就是黎曼所擅长的,他著名的猜想也由此得出。不过在解释它之前,我们有必要先熟悉一些基础资源。
调和级数 调和级数是个无限级数,它首先由尼科尔·奥雷斯姆在 14 世纪研究。其名字与音乐中谐波的概念有关,即高于基音基本频率的泛音。该级数如下:
<img src="https://pic4.zhimg.com/v2-c58d942968d3d770852d5af04eeb9c6b_b.jpg" data-caption="" data-size="normal" data-rawwidth="659" data-rawheight="155" class="origin_image zh-lightbox-thumb" width="659" data-original="https://pic4.zhimg.com/v2-c58d942968d3d770852d5af04eeb9c6b_r.jpg"/> 无限调和级数的第一项
该和式被奥雷斯姆证明是不收敛的(即不存在极限,不接近/趋向于任何特定的数字,而是一直增长到无穷大)。
Zeta 函数 调和级数是一个更一般形式的,被称为 zeta 函数 ζ(s) 的一个特列。zeta 函数的实际值由给定的 r 和n 两个实数决定:
<img src="https://pic2.zhimg.com/v2-38622a122f78745e766531f3b4c19e51_b.jpg" data-caption="" data-size="normal" data-rawwidth="775" data-rawheight="135" class="origin_image zh-lightbox-thumb" width="775" data-original="https://pic2.zhimg.com/v2-38622a122f78745e766531f3b4c19e51_r.jpg"/> zeta 函数
若将 n = 1 代入,就会得到调和级数,它是发散的。然而对于 n > 1 的所有值, 该级数是收敛的,这意味着当 r 递增时,其和趋向于某些数,即它不会增长到无穷大。
欧拉乘积公式 zeta 函数和素数间的第一个联系是由欧拉发现的,当时他发现了 n 和 p 两个自然数(大于零的整数)之间的关系,其中 p 为素数:
<img src="https://pic2.zhimg.com/v2-44216ad0d56eb337a8e8579c975d1a55_b.jpg" data-caption="" data-size="normal" data-rawwidth="332" data-rawheight="122" class="content_image" width="332"/> 欧拉乘积公式,其中 n,p 均为大于零的数字且 p 为素数
该表达式首先出现在 1737 年一篇题为 Variae observationes circa series infinitas(无穷级数的各种观察)的论文中。该表达式陈述了 zeta 函数的求和等于一减去素数的 -s 次方的倒数的求积。这种惊人的联系奠定了现代素数理论的基础,即使用 zeta 函数 ζ(s) 作为研究素数的方法。
此公式的证明是我最喜欢的证明之一,因此我在这里收录了它,即便它对我们的目的而言并非严格必须的(它太优雅了!):
欧拉乘积公式的证明 欧拉从一般的 zeta 函数开始
<img src="https://pic1.zhimg.com/v2-762dcfafc1c964923e4a20d2ef8e9c48_b.jpg" data-caption="" data-size="normal" data-rawwidth="523" data-rawheight="97" class="origin_image zh-lightbox-thumb" width="523" data-original="https://pic1.zhimg.com/v2-762dcfafc1c964923e4a20d2ef8e9c48_r.jpg"/> zeta 函数 首先,他将等式两边同时乘以第二项:
<img src="https://pic3.zhimg.com/v2-ebbc462648f09cdea28562ec7a244a52_b.jpg" data-caption="" data-size="normal" data-rawwidth="671" data-rawheight="97" class="origin_image zh-lightbox-thumb" width="671" data-original="https://pic3.zhimg.com/v2-ebbc462648f09cdea28562ec7a244a52_r.jpg"/> zeta 函数乘以
接着他从 zeta 函数中减去结果表达式:
<img src="https://pic4.zhimg.com/v2-313062c0ce169edd353c61efc1a41e87_b.jpg" data-caption="" data-size="normal" data-rawwidth="660" data-rawheight="94" class="origin_image zh-lightbox-thumb" width="660" data-original="https://pic4.zhimg.com/v2-313062c0ce169edd353c61efc1a41e87_r.jpg"/> zeta 函数减去 乘以 zeta 函数
他重复这个过程,紧接着在两边同时乘以第三项:
<img src="https://pic3.zhimg.com/v2-21cb71c2c9ad265c9962ce272ea90e66_b.jpg" data-caption="" data-size="normal" data-rawwidth="706" data-rawheight="99" class="origin_image zh-lightbox-thumb" width="706" data-original="https://pic3.zhimg.com/v2-21cb71c2c9ad265c9962ce272ea90e66_r.jpg"/> zeta 函数减去 乘以 zeta 函数,再乘以
接着从 zeta 函数中减去结果表达式:
<img src="https://pic3.zhimg.com/v2-0d78247b0d652cff206b3265d3309fc6_b.jpg" data-caption="" data-size="normal" data-rawwidth="806" data-rawheight="95" class="origin_image zh-lightbox-thumb" width="806" data-original="https://pic3.zhimg.com/v2-0d78247b0d652cff206b3265d3309fc6_r.jpg"/> zeta 函数减去 乘以 zeta 函数,减去 再乘以 zeta 函数
无限重复此过程,最后会留下表达式:
<img src="https://pic4.zhimg.com/v2-f0733939ea6ed6432a748076118efc53_b.jpg" data-caption="" data-size="normal" data-rawwidth="927" data-rawheight="97" class="origin_image zh-lightbox-thumb" width="927" data-original="https://pic4.zhimg.com/v2-f0733939ea6ed6432a748076118efc53_r.jpg"/> 1 减去所有素数的倒数,乘以 zeta 函数
如果你觉得这个过程很眼熟,那是因为欧拉实际上构造了一个筛子,它和埃拉托斯特尼筛法很像。它将非素数从 zeta 函数中筛了出去。接着,将该表达式除以所有素数的倒数项,就得到了:
<img src="https://pic4.zhimg.com/v2-7affc2ed31c63330f2d29b5d76a72afb_b.jpg" data-caption="" data-size="normal" data-rawwidth="962" data-rawheight="102" class="origin_image zh-lightbox-thumb" width="962" data-original="https://pic4.zhimg.com/v2-7affc2ed31c63330f2d29b5d76a72afb_r.jpg"/> zeta 函数与素数的函数关系,对于前五个素数 2,3,5,7 和 11
简化后,就是:
<img src="https://pic2.zhimg.com/v2-44216ad0d56eb337a8e8579c975d1a55_b.jpg" data-caption="" data-size="normal" data-rawwidth="332" data-rawheight="122" class="content_image" width="332"/> 欧拉乘积公式,该恒等式展示了素数与 zeta 函数间的联系
是不是非常漂亮?将 s = 1 代入,就得到了无限调和级数,再次证明了素数的无限。
莫比乌斯函数 奥古斯特·费迪南德·莫比乌斯之后重写了欧拉乘积公式,创造了一个新的求和。除了包含素数的倒数外,莫比乌斯函数也包含了所有可分解为奇数或偶数个质因数的乘积的自然数。他的数中留下的的数字可以被某些素数的平方整除。和式用 μ(n) 表示如下:
<img src="https://pic4.zhimg.com/v2-3e4d8a2de9c3b2c45b888874f65e388b_b.jpg" data-caption="" data-size="normal" data-rawwidth="253" data-rawheight="106" class="content_image" width="253"/> 莫比乌斯函数,欧拉乘积公式的一个修改版,在所有的自然数上定义
该和式包含了以下数的倒数:
所有素数; 所有可写为奇数个不同素数的乘积的自然数,前缀一个负号;以及 所有可写为偶数个不同素数的乘积的自然数,前缀一个正号。 以下为第一项:
<img src="https://pic4.zhimg.com/v2-2eee2142517c1dc426c503e30b1df09b_b.jpg" data-caption="" data-size="normal" data-rawwidth="711" data-rawheight="102" class="origin_image zh-lightbox-thumb" width="711" data-original="https://pic4.zhimg.com/v2-2eee2142517c1dc426c503e30b1df09b_r.jpg"/> 1除以 zeta 函数 ζ(s) 的级数/求和
此和式不包含能够被某些素数的平方(如 4,8,9 等等)整除的倒数。莫比乌斯函数 μ(n) 的值只有三种可能,除了前缀(1 或 -1)外,就是从该和式中移除项(0):
<img src="https://pic2.zhimg.com/v2-75fb5f27051ef96cc26ef7c9c74420e1_b.jpg" data-caption="" data-size="normal" data-rawwidth="1054" data-rawheight="137" class="origin_image zh-lightbox-thumb" width="1054" data-original="https://pic2.zhimg.com/v2-75fb5f27051ef96cc26ef7c9c74420e1_r.jpg"/> 莫比乌斯函数 μ(n) 三个可能的取值
尽管莫比乌斯给出了第一个形式化定义,然而这个诡异的和式来自于比它早 30 多年的高斯的一个旁注,他认为这很不寻常,他写道:
“该和式(对于一个素数p)的所有原根要么 ≡ 0(当 p-1 可被一个平方数整除时),要么 ≡ ±1 (mod p)(当 p-1 为不相等的素数的乘积时);若它们的个数为偶数,其符号为正;若它们的个数为奇数,则符号为负。” 素数计数函数 我们回到素数的问题上。为了理解随着数值的升高素数是如何分布的,我们无需知道它们在哪,只需知道到一个具体的数字为止它们的数量。
高斯引入的素数计数函数 π(x) 就是做这件事的,它会给出小于或等于一个给定实数的素数的数量。鉴于目前没有已知的寻找素数的公式,我们只能通过图像或每当 x 为素数时阶跃函数加 1 的方式来了解素数计数公式。下图显示了 x = 200 时的函数。
<img src="https://pic4.zhimg.com/v2-29ca438a66c3e41e0571bc80ad63a5fb_b.jpg" data-caption="" data-size="normal" data-rawwidth="1066" data-rawheight="670" class="origin_image zh-lightbox-thumb" width="1066" data-original="https://pic4.zhimg.com/v2-29ca438a66c3e41e0571bc80ad63a5fb_r.jpg"/> 素数计数函数 π(x) ,其中 x = 200
素数定理 素数定理也由高斯(和勒让德独立地)阐述:
<img src="https://pic1.zhimg.com/v2-b9436187c613b5718adab92c6ab24ff0_b.jpg" data-caption="" data-size="normal" data-rawwidth="224" data-rawheight="108" class="content_image" width="224"/> 素数定理
在汉语(原文英语)中,它被陈述为:“当x增长到无穷大时,素数计数函数 π(x) 会近似于 x/ln(x) 函数。换句话说,若你的计数足够大,且将素数数量的图绘制到一个非常大的数 x,接着绘制 x 除以 x 的自然对数,二者会临近相同的值。两函数图像如下,取 x = 1000:
<img src="https://pic2.zhimg.com/v2-ac06bdf50da14cd35c14f9133b6e97ad_b.jpg" data-caption="" data-size="normal" data-rawwidth="1095" data-rawheight="704" class="origin_image zh-lightbox-thumb" width="1095" data-original="https://pic2.zhimg.com/v2-ac06bdf50da14cd35c14f9133b6e97ad_r.jpg"/> 素数计数函数 π(x) 以及素数定理的估计,绘制到 x = 1000
从概率的角度来说,素数定理说明若你随机选择一个自然数 x,那么 P(x),即该数字为素数的概率约为 1/ln(x)。这意味着前x个整数中连续素数之间的平均间隙约为 ln(x)。
对数积分函数 函数 Li(x) 在除了 x = 1 之外的所有正实数上定义。它以一个从 2 到 x 的积分定义:
<img src="https://pic1.zhimg.com/v2-4fe2352badf87a90646a53df82ab9ae0_b.jpg" data-caption="" data-size="normal" data-rawwidth="292" data-rawheight="97" class="content_image" width="292"/> 对数积分函数的积分表示
将此函数与素数计数函数和素数定理公式一起绘制,我们会看到其实 Li(x) 比 x/ln(x) 近似得更好:
<img src="https://pic1.zhimg.com/v2-97f5e0ffb4b3cf3a13aa49dbe30e2cf8_b.jpg" data-caption="" data-size="normal" data-rawwidth="1035" data-rawheight="669" class="origin_image zh-lightbox-thumb" width="1035" data-original="https://pic1.zhimg.com/v2-97f5e0ffb4b3cf3a13aa49dbe30e2cf8_r.jpg"/> 对数积分函数 Li(x),素数计数函数 π(x) 和 x/ln(x) 一起绘制
若我们做一个表格,其中包含足够大的x值、到x为止的素数个数以及旧函数(素数定理)与新函数(对数积分)之间的误差,就能看出它近似得有多好:
<img src="https://pic3.zhimg.com/v2-71740d24a988b5df3c441fc5fe8ecc1e_b.jpg" data-caption="" data-size="normal" data-rawwidth="1139" data-rawheight="491" class="origin_image zh-lightbox-thumb" width="1139" data-original="https://pic3.zhimg.com/v2-71740d24a988b5df3c441fc5fe8ecc1e_r.jpg"/> 到一个给定的 10 的幂的素数个数以及两种估计对应的误差项
从这里可以很容易看出,对数积分函数的近似值远远好于素数定理函数,对于 x = 10^14只“猜多了” 314,890 个素数。然而,这两个函数都只能向素数计数函数 π(x) 靠拢。Li(x) 靠拢得更快,但随着 x 增长到无穷大,素数计数函数与 Li(x) 和 x/ln(x) 的比率趋向于 1。如图所示:
<img src="https://pic2.zhimg.com/v2-a9c3804e4fab92c08f4eb236cd9e21ad_b.jpg" data-caption="" data-size="normal" data-rawwidth="1750" data-rawheight="994" class="origin_image zh-lightbox-thumb" width="1750" data-original="https://pic2.zhimg.com/v2-a9c3804e4fab92c08f4eb236cd9e21ad_r.jpg"/> 将两个估计和素数计数函数的比率收敛到 1,其中 x = 10,000
Gamma 函数 自丹尼尔·伯努利和克里斯蒂安·哥德巴赫在 1720 年代研究如何将阶乘函数扩展到非整数参数的问题以来,Gamma 函数 Γ(z) 一直是一个重要的研究对象。它是阶乘函数 n!(1×2×3×4×5×...×n)延拓后向下移1:
<img src="https://pic2.zhimg.com/v2-07af41ac9d4884bd3595b84b0017e5e5_b.jpg" data-caption="" data-size="normal" data-rawwidth="231" data-rawheight="59" class="content_image" width="231"/> Gamma 函数,在 z 上定义
它的图像非常古怪:
<img src="https://pic1.zhimg.com/v2-b50da1c4311261c773d34cf845727438_b.jpg" data-caption="" data-size="normal" data-rawwidth="1058" data-rawheight="653" class="origin_image zh-lightbox-thumb" width="1058" data-original="https://pic1.zhimg.com/v2-b50da1c4311261c773d34cf845727438_r.jpg"/> Gamma 函数 Γ(z) 绘制在范围 -6 ≤ z ≤ 6 内
Gamma 函数 Γ(z) 在所有实部大于零的复数 z 上定义。你可能知道,复数是带虚部的一类数,写作 Re(z) + Im(z),其中 Re(z) 为实部(普通的实数),Im(z) 为虚部,以字母 i 表示。一个复数通常写成 z = σ + it 的形成,其中 σ 为实部,it 为虚部。复数非常有用,因为它们允许数学家和工程师求解和处理普通实数不允许的问题。视觉上,复数将传统的一维“数轴”扩展成二维“数平面”,称之为复平面,其中复数的实部绘制在 x 轴上,虚部绘制在 y 轴上。为了能够使用 Gamma 函数 Γ(z),通常将其形式重写为
<img src="https://pic4.zhimg.com/v2-b0a5bbc4ecbde32ba3f7a740eadadc83_b.jpg" data-caption="" data-size="normal" data-rawwidth="239" data-rawheight="92" class="content_image" width="239"/> Gamma 函数 Γ(z) 的函数关系
通过该恒等式可获得实部小于等于零的 z 的值。然而它不会给出负整数的值,因为它们没有定义(从技术上说它们是奇异点或简单的极点)。
Zeta 与 Gamma zeta 函数与 Gamma 函数的联系由以下积分给出:
<img src="https://pic1.zhimg.com/v2-b05180cd1a7a2e0e7ab7fde2bb7ced00_b.jpg" data-caption="" data-size="normal" data-rawwidth="683" data-rawheight="98" class="origin_image zh-lightbox-thumb" width="683" data-original="https://pic1.zhimg.com/v2-b05180cd1a7a2e0e7ab7fde2bb7ced00_r.jpg"/>
黎曼猜想,及其解释(下)
译注 译者本人非数学专业,英语刚蹭过四级,所以文中大概存在相当多的翻译和理解问题。若有发现此类问题,恳请斧正。(咱不翻译文章,只是Google翻译+词典的搬运工= =||)
本文已征得原作者 Jørgen Veisdal 翻译授权,译文采用 CC-BY-SA 4.0 方式共享。
题图来自 Visualizing the Riemann zeta function and analytic continuation ,一个非常棒的视频,它以动画的方式讲解了黎曼 zeta 函数及其解析延拓,强烈推荐!(另有官方中英双语版 )
156 条评论
【Gamma 函数 Γ(z) 在所有大于零的复数 z 上定义。】(这里严格来说应该加上“实部”吧)
【使用该恒等式可获得对于零以内的z的值。】(“对于零以内”是“实部小于或等于零”)
还有前面有些语句也有不严谨之处,不知是翻译问题还是原文如此。
【Gamma 函数 Γ(z) 在所有大于零的复数 z 上定义。】(这里严格来说应该加上“实部”吧)
【使用该恒等式可获得对于零以内的z的值。】(“对于零以内”是“实部小于或等于零”)
还有前面有些语句也有不严谨之处,不知是翻译问题还是原文如此。