MathLabs

算术与数论

哥德巴赫猜想

尚未被证明的论断:每个大于2的偶数都是两个素数之和。

直观每个偶数都能拆成两个素数吗?

动手试试:4=2+24=2+2、6=3+36=3+3、8=3+58=3+5、10=3+7=5+510=3+7=5+5、100=3+97=11+89=17+83=29+71=41+59=47+53100=3+97=11+89=17+83=29+71=41+59=47+53。人们检验过的每一个偶数——多达数万亿个——都能拆成两个素数,通常还不止一种方式。断言这对每个偶数 n>2n>2 永远成立,就是哥德巴赫猜想;至今没有人找到反例,也没有人证明不存在反例。

小于n的素数图,高亮的边标出和为n的素数对,展示哥德巴赫表示。
通过埃拉托斯特尼筛法高亮为绿色的 6060 以内素数:在网格上验证任意偶数 2k≤602k \le 60 都可以写成两个绿色素数格之和。

大学精确陈述与变体

定义: 哥德巴赫表示数

对偶数 nn,设 r(n)=#{(p,q):p,q prime, p≤q, p+q=n}r(n) = \#\{(p,q) : p,q \text{ prime},\, p\le q,\, p+q=n\} 为将 nn 表示为两个素数之和的无序表示个数。强(二元)哥德巴赫猜想断言,对每个偶数 n>2n>2,n=p1+p2n = p_1 + p_2 都有素数解 p1,p2p_1,p_2,即 r(n)≥1r(n)\ge1。

r(n)=#{(p,q):p,q prime, p≤q, p+q=n}r(n) = \#\{(p,q) : p,q \text{ prime},\, p\le q,\, p+q=n\}

另一个较弱的论断是三元(或"弱")哥德巴赫猜想:每个奇数 n>5n>5 都是三个素数之和,n=p1+p2+p3n = p_1+p_2+p_3。历史上,哥德巴赫1742年致欧拉的信提出了三元版本的说法(当时 11 仍被视为素数);欧拉将其改述为如今标准的二元表述。这两个猜想如今的状态大不相同,归纳于下表。

n=p1+p2+p3,n odd, n>5n = p_1+p_2+p_3, \qquad n \text{ odd},\ n>5
二元与三元哥德巴赫:当前状态
标准二元(强)三元(弱)
陈述n=p1+p2n = p_1 + p_2n=p1+p2+p3n = p_1+p_2+p_3
状态未解决已证明(赫尔弗戈特,2013)
最佳无条件部分结果陈氏定理(1973):素数+半素数对所有 n>5n>5 已完全解决

大学通往哥德巴赫猜想道路上的两个已证明定理

存在 N0N_0,使得对每个偶数 n>N0n>N_0,有 n=p+mn = p + m,其中 pp 是素数,mm 是素数或恰好两个素数的乘积(半素数)。

为什么成立?

这是人类迄今用完全严格、无条件的论证最接近证明二元哥德巴赫猜想的结果:它把一侧的"素数"放宽为"素数或半素数",这正是筛法能够处理的情形,尽管筛法无法精确分离出素数本身。

证明

证明是一个加权筛法论证。固定一个较大的偶数 nn,对每个素数 p≤np\le n,考察 n−pn-p 的素因子是否很少。朴素的筛法(塞尔伯格上界筛)可以证明使 n−pn-p 至多有两个素因子的 p≤np\le n 的个数不会太小——但单靠朴素筛法无法强有力地区分"n−pn-p 是素数"与"n−pn-p 有 3,4,…3,4,\dots 个素因子",从而无法得出结论。

陈氏的关键工具——加权筛(即"转换原理")——为每个候选 pp 赋予一个由两个不同筛水平构成的权重:一个上界筛用于"坏"事件,即 n−pn-p 在阈值 z≈n1/3z\approx n^{1/3} 以下有三个或更多素因子;一个下界筛用于计数 n−pn-p 与所有小于 zz 的素数互素的 p≤np\le n 总数。用第二者减去第一者的适当加权倍数,得到一个可证明当 nn 充分大时为正的组合和——这说明存在某个 pp,使 n−pn-p 在阈值以上至多有 22 个素因子,即 n−pn-p 是素数或半素数。

要使"可证明为正"成立,需要估计源自筛法余项的一个双线性型,用到关于素数在大模数等差数列中分布的Bombieri–Vinogradov型结果(对模数平均到约 n1/2−εn^{1/2-\varepsilon});这是最深的解析输入,也是该定理需要 nn "充分大"而非从一开始就对所有 nn 成立的原因。

该定理止步于"素数或半素数"而非"素数或素数",是因为筛法存在奇偶性问题:标准筛权重按其构造无法区分素因子个数为偶数与奇数的数,因此这类论证永远无法单独筛出素数——半素数是筛法理论目前所能达到的最锐利目标。

每个奇数 n>5n>5 都满足 n=p1+p2+p3n = p_1+p_2+p_3,其中 p1,p2,p3p_1,p_2,p_3 为某些素数。维诺格拉多夫于1937年证明了这一点,适用于所有充分大的奇数 nn;赫尔弗戈特于2013年完成了证明,去掉了"充分大"的限制,对每个奇数 n>5n>5 都建立了该结果。

为什么成立?

这是圆法直接应用于素数所取得的最深刻的无条件成功,它使二元哥德巴赫猜想从一个完全开放的问题,变成了至少其奇数和类比版本已被彻底解决的问题。

证明

证明完全遵循本节前面概述的圆法,应用于冯·芒戈尔特加权指数和 F(α)=∑p≤nlog⁡p  e(pα)F(\alpha)=\sum_{p\le n}\log p\; e(p\alpha),表示数由 ∫01F(α)3e(−nα) dα\int_0^1 F(\alpha)^3 e(-n\alpha)\,d\alpha 加权计数。

在主弧(围绕分母 qq 较小的有理数 a/qa/q 的短区间)上,关于等差数列中素数分布的西格尔–瓦尔菲兹定理——对直到 log⁡n\log n 任意固定幂的模 qq 一致成立——使我们能在那里显式求值该积分,得到主项 12S(n) n2\tfrac12\mathfrak S(n)\,n^2,其中"奇异级数" S(n)\mathfrak S(n) 是各素数局部密度的乘积,衡量 nn 模该素数可解为 p1+p2+p3p_1+p_2+p_3 的频率。对奇数 nn 而言,每个局部条件都可解(不存在类似困扰二元情形的奇偶性障碍),因此 S(n)\mathfrak S(n) 有远离 00 的下界,主项确实为正且量级为 n2n^2。

在次弧上,维诺格拉多夫关于素数的指数和估计——一个在此处成立的高度非平凡的界 ∣F(α)∣≪n(log⁡n)4/q1/2|F(\alpha)|\ll n(\log n)^4/q^{1/2}——表明其贡献为 o(n2)o(n^2),严格小于主项,因而不能抵消主弧带来的正贡献。将两者结合,得到当 nn 充分大时表示数为正,这就是维诺格拉多夫1937年的定理。

赫尔弗戈特2013年的完成工作使上述每一步都变得完全显式,而不仅是"充分大":更精细的主弧与次弧估计(包括对狄利克雷 LL 函数零点到特定高度的显式、经计算机验证的界)弥合了解析论证生效的显式阈值与已由计算机直接搜索验证的范围之间的差距,从而对真正每一个奇数 n>5n>5 都给出了无条件的证明。

大学实际应用与典型例题

哥德巴赫式的素数和结构在密码学密钥生成中充当合理性检验(由素数组合构造的大数不应意外地被简化),而为寻找哥德巴赫表示而开发的分段筛算法,直接进入了用于为RSA类密码系统搜索大素数的同一套计算数论工具箱。用计算机对不超过 4×10184\times10^{18} 的每个偶数验证该猜想,本身就是算法工程与分布式计算领域的一项里程碑成就,需要在众多机器上精心并行化分段筛法。

例题: 数一数100的表示

求 r(100)r(100),即把 100100 写成两个素数的无序和的方法数。

解答

逐一检查素数 p≤50p\le50,判断 100−p100-p 是否也是素数。p=3p=3:9797 是素数。p=11p=11:8989 是素数。p=17p=17:8383 是素数。p=29p=29:7171 是素数。p=41p=41:5959 是素数。p=47p=47:5353 是素数。检查 5050 以下其余素数(2,5,7,13,19,23,31,37,432,5,7,13,19,23,31,37,43)得到的对应数都是合数(分别为 98,95,93,87,81,77,69,63,5798,95,93,87,81,77,69,63,57)。

汇总成功的情形:100=3+97=11+89=17+83=29+71=41+59=47+53100=3+97=11+89=17+83=29+71=41+59=47+53。

数一数这些无序对,得到 r(100)r(100) = 66,与 n=100n=100 广为人知的值相符。

例题: 陈氏定理的实际运用

以 n=98n=98 为例说明陈氏定理:找出素数 pp,使 98−p98-p 为素数或半素数,并指出属于哪种情形。

解答

试 p=19p=19:98−19=7998-19=79 是素数,这已经满足了更强的二元哥德巴赫陈述(这是额外收获,因为 9898 足够小,两个猜想都可通过直接搜索验证,而不仅仅依赖陈氏较弱的保证)。

为了展示陈氏定理在一般情形下具体保证的"素数或半素数"这一选项,试 p=7p=7:98−7=91=7×1398-7=91=7\times13,恰好是两个素数的乘积——一个半素数。因此 p=7p=7 展示了陈氏定理的半素数分支:98=7+9198=7+91,其中 9191 是半素数,本身不是素数。

这一区分很重要:陈氏定理只保证存在这样的 pp,使 n−pn-p 为素数或半素数;它本身并不保证更强的"素数或素数"结果。对 n=98n=98,我们恰好同时找到了真正的哥德巴赫对(19+7919+79)和真正的半素数见证(7+917+91),但仅凭陈氏的证明方法,对于直接搜索不可行的天文数字般巨大的 nn,原本也只能给出后一种保证。

哪一个陈述是强(二元)哥德巴赫猜想?

把 100100 写成两个素数无序和的方法数 r(100)r(100) 是多少?

以下哪一项是陈氏定理实际证明的内容?

对不超过 4×10184\times10^{18} 的每个偶数用计算机验证哥德巴赫猜想,这在计算机科学中说明了什么?

参考文献

  1. H. A. Helfgott (2013). The ternary Goldbach conjecture is true · arXiv:1312.7748
  2. J. R. Chen (1973). On the representation of a larger even integer as the sum of a prime and the product of at most two primes · DOI:10.1360/ya1973-16-2-157
  3. T. Oliveira e Silva, S. Herzog, S. Pardi (2014). Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4×10184\times10^{18} · DOI:10.1090/S0025-5718-2013-02787-1