素数定理

在数论中，素数定理（英语：Prime number theorem）描述素数在自然数中分布的渐进情况，给出随著数字的增大，质数的密度逐渐降低的直觉的形式化描述。1896年法国数学家雅克·阿达马和比利时数学家德·拉·瓦莱布桑先后独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。

素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为素数计数函数，亦即不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。

\pi (x)\approx {\frac {x}{\ln \,x}}

其中 ln x 为 x 的自然对数。上式的意思是当 x 趋近无限，π(x)与x/ln x的比值趋近 1。但这不表示它们的数值随著 x 增大而接近。

下面是对π(x)更好的估计：

\pi (x)={\rm {Li}}(x)+O\left(xe^{-{\frac {1}{15}}{\sqrt {\ln \,x}}}\right)

，当x 趋近∞。

其中 ${\rm {Li}}(x)=\int _{2}^{x}{\frac {dt}{\ln \,t}}$ （对数积分），而关系式右边第二项是误差估计，详见大O符号。

叙述

定义 π(x) 为素数计数函数，也就是小于等于x 的质数个数。例如 π(10)=4，因为共有 4 个质数小于等于 10，分别是 2、3、5、7。质数定理的叙述为：当 x 趋近无限，π(x) 和 ${\frac {x}{\ln x}}$ 的比值趋近 1。其数学式写做

\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}=1

。

浅白的说，当 x 很大的时候，π(x) 差不多等于 ${\frac {x}{\ln x}}$ 。该定理被认为是质数的渐进分布定律，以渐进符号可简化为

\pi (x)\sim {\frac {x}{\ln x}}

。

注意到，上式并不是说指随著 x 趋近无限， $\pi (x)$ 与 ${\frac {x}{\ln x}}$ 的差趋近于 0。而是随著 x 趋近无限， $\pi (x)$ 与 ${\frac {x}{\ln x}}$ 的相对误差趋近于 0。

因此，质数定理也可以被想像成描述从正整数中抽到素数的概率：从不大于 n 的正整数中随机选出一个数，它是素数的概率大约是 ${\frac {1}{\ln n}}$ 。

质数定理有一个相关的定理，是关于第 $n$ 个素数 $p_{n}$ 的下界，也就所谓的Rosser定理：

p_{n}>n\ln \,n

关于 $π (x)$ 、 $x / ln x$ 和 $li(x)$ 的数值

下表比较了π(x)，x/ln x和Li(x)：

$x$	${\boldsymbol {\pi }}(x)$ ^[1]	${\boldsymbol {\pi }}(x)-{\frac {x}{\ln x}}$ ^[2]	${\frac {{\boldsymbol {\pi }}(x)}{\frac {x}{\ln x}}}$	${\rm {Li}}(x)-{\boldsymbol {\pi }}(x)$ ^[3]	${\frac {x}{{\boldsymbol {\pi }}(x)}}$
10	4	−0.3	0.921	2.2	2.500
10²	25	3.3	1.151	5.1	4.000
10³	168	23	1.161	10	5.952
10⁴	1,229	143	1.132	17	8.137
10⁵	9,592	906	1.104	38	10.425
10⁶	78,498	6,116	1.084	130	12.740
10⁷	664,579	44,158	1.071	339	15.047
10⁸	5,761,455	332,774	1.061	754	17.357
10⁹	50,847,534	2,592,592	1.054	1,701	19.667
10¹⁰	455,052,511	20,758,029	1.048	3,104	21.975
10¹¹	4,118,054,813	169,923,159	1.043	11,588	24.283
10¹²	37,607,912,018	1,416,705,193	1.039	38,263	26.590
10¹³	346,065,536,839	11,992,858,452	1.034	108,971	28.896
10¹⁴	3,204,941,750,802	102,838,308,636	1.033	314,890	31.202
10¹⁵	29,844,570,422,669	891,604,962,452	1.031	1,052,619	33.507
10¹⁶	279,238,341,033,925	7,804,289,844,393	1.029	3,214,632	35.812
10¹⁷	2,623,557,157,654,233	68,883,734,693,281	1.027	7,956,589	38.116
10¹⁸	24,739,954,287,740,860	612,483,070,893,536	1.025	21,949,555	40.420
10¹⁹	234,057,667,276,344,607	5,481,624,169,369,960	1.024	99,877,775	42.725
10²⁰	2,220,819,602,560,918,840	49,347,193,044,659,701	1.023	222,744,644	45.028
10²¹	21,127,269,486,018,731,928	446,579,871,578,168,707	1.022	597,394,254	47.332
10²²	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1.021	1,932,355,208	49.636
10²³	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	1.020	7,250,186,216	51.939
10²⁴	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	1.019	17,146,907,278	54.243
10²⁵	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	1.018	55,160,980,939	56.546
OEIS	A006880	A057835		A057752

历史

1797年至1798年间，法国数学家勒让德根据上述的质数表猜测， $\pi (x)$ 大约等于 ${\frac {x}{A\ln x+B}}$ ，其中 $A$ 、 $B$ 是未知的函数。勒让德于1808年出版一本关于数论的书的第二版，书中他给出更精确的猜测： $A=1$ ， $B=-1.08366$ 。根据高斯自己在1849年的回忆，他在15岁或16岁(1792或1793年)的时候就已经考虑过类似的问题了^[4]。1832年，狄利克雷经过跟高斯的交流之后，给出了一个新的逼近函数 $li(x)$ ，(事实上他是用一个有点不一样的级数表达式)。勒让德和狄利克雷的式子皆等价于现在的版本，但如果考虑逼近式与 $\pi (x)$ 的差，而不是比值的话，狄利克雷的式子是准确许多的。

俄国数学家切比雪夫参考了欧拉在1731年的工作，引进了定义在实数轴上黎曼ζ函数，企图证明质数分布的渐进式，并将他所得到的结果写成两篇论文，分别在1848和1850年发表。切比雪夫可以证明，如果 $\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}$ 存在且有限，则它一定是1^[5]。此外，在没有假设任何结果之下，他也证明当 x 足够大， ${\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}$ 会界在两个很靠近 1 的数字之间^[6]。虽然切比雪夫的论文没办法证明质数定理，但它对 $\pi (x)$ 已经可以推论出伯特兰-切比雪夫定理：对任何大于 $1$ 的正整数 $n$ ，存在一个质数介于 $n$ 和 $2n$ 之间。

1859年，黎曼提交了一篇关于质数分布的非常重要的报告《论小于给定数值的质数个数（英语：On the Number of Primes Less Than a Given Magnitude）》，这也是黎曼在这个领域的唯一一篇文章。黎曼在报告中使用了创新的想法，将 $\zeta$ 函数的定义解析延拓到整个复数平面，并且将质数的分布与 $\zeta$ 函数的零点紧密的联系起来。因此，这篇报告是历史上首次用复分析的方法研究实函数 $\pi (x)$ 。1896年法国数学家雅克·阿达马和比利时数学家夏尔-让·德拉瓦莱·普桑先后独立给出证明。两个证明延著黎曼的思路继续拓展，且都使用复分析的工具，其中的关键步骤是证明如果复数 $s$ 可以写成 $1+it$ 的形式，且 $t>0$ ，则 $\zeta (s)\neq 0$ ^[7]。

进入20世纪之后，阿达马和普桑证明的定理经常被称作质数定理，定理的其他不同证明也陆陆续续被发现，这之中包括1949年阿特勒·塞尔伯格和艾狄胥·帕尔发现的“初等证明”。原本的证明是既冗长，又复杂，于是有很多后面发现的证明使用了陶伯定理（英语：Tauberian theorem）让证明变得比较简短，但却变得让人比较难以消化。1980年，美国数学家唐纳德·J·纽曼（英语：Donald J. Newman）发现了一个简洁的证明^[8]^[9]，这可能是目前已知最简单的证明。不过，证明中使用了柯西积分公式，因此一般不被视为是为初等的证明。

因为黎曼ζ函数与 $\pi (x)$ 关系密切，关于黎曼 $\zeta$ 函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家海里格·冯·科赫证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为

\pi (x)={\rm {Li}}(x)+O\left({\sqrt {x}}\ln \,x\right)

至于大O项的常数则还未知道。^{[来源请求]}

初等证明

素数定理有些初等证明只需用数论的方法。第一个初等证明于1949年由匈牙利数学家保罗·艾狄胥和挪威数学家阿特利·西尔伯格合作得出。

在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的“深度”。他认为只用到实数不足以解决某些问题，必须引进复数来解决。

参考资料

^ A006880
^ A057835
^ A057752
^ C. F. Gauss. Werke, Bd 2, 1st ed, 444–447. Göttingen 1863.
^ Costa Pereira, N. A Short Proof of Chebyshev's Theorem. American Mathematical Monthly. August–September 1985, 92 (7): 494–495. JSTOR 2322510. doi:10.2307/2322510.
^ Nair, M. On Chebyshev-Type Inequalities for Primes. American Mathematical Monthly. February 1982, 89 (2): 126–129. JSTOR 2320934. doi:10.2307/2320934.
^ Ingham, A. E. The Distribution of Prime Numbers. Cambridge University Press. 1990: 2–5. ISBN 978-0-521-39789-6.
^ Newman, Donald J. Simple analytic proof of the prime number theorem. American Mathematical Monthly. 1980, 87 (9): 693–696. JSTOR 2321853. MR 0602825. doi:10.2307/2321853.
^ Zagier, Don. Newman's short proof of the prime number theorem. American Mathematical Monthly. 1997, 104 (8): 705–708 [2019-05-03]. JSTOR 2975232. MR 1476753. doi:10.2307/2975232. （原始内容存档于2021-04-20）.

外部链接

[1] A006880

[2] A057835

[3] A057752

[4] C. F. Gauss. Werke, Bd 2, 1st ed, 444–447. Göttingen 1863.

[5] Costa Pereira, N. A Short Proof of Chebyshev's Theorem. American Mathematical Monthly. August–September 1985, 92 (7): 494–495. JSTOR 2322510. doi:10.2307/2322510.

[6] Nair, M. On Chebyshev-Type Inequalities for Primes. American Mathematical Monthly. February 1982, 89 (2): 126–129. JSTOR 2320934. doi:10.2307/2320934.

[7] Ingham, A. E. The Distribution of Prime Numbers. Cambridge University Press. 1990: 2–5. ISBN 978-0-521-39789-6.

[8] Newman, Donald J. Simple analytic proof of the prime number theorem. American Mathematical Monthly. 1980, 87 (9): 693–696. JSTOR 2321853. MR 0602825. doi:10.2307/2321853.

[9] Zagier, Don. Newman's short proof of the prime number theorem. American Mathematical Monthly. 1997, 104 (8): 705–708 [2019-05-03]. JSTOR 2975232. MR 1476753. doi:10.2307/2975232. （原始内容存档于2021-04-20）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

查论编质数类
公式	卡罗尔（ $（2 n －1） 2 －2$ ）费马质数（ $2 2 n ＋1$ ）梅森质数（ $2 p －1$ ）双重梅森质数（ $2 2 p －1 －1$ ）瓦格斯塔夫质数 $（2 p ＋1）／3$ 普罗斯质数（ $k \cdot2 n ＋1$ ）阶乘质数（ $n ！\pm1$ ）质数阶乘质数（ $p n ＃\pm1$ ）欧几里得数（ $p n ＃＋1$ ）毕达哥拉斯质数（ $4 n ＋1$ ）皮尔庞特质数（ $2 m \cdot3 n ＋1$ ） Quartan质数（ $x 4 ＋ y 4$ ）（英语：Quartan prime）索利纳斯质数（ $2 m \pm2 n \pm1$ ）（英语：Solinas prime）卡伦质数（ $n \cdot2 n ＋1$ ）胡道尔质数（ $n \cdot2 n －1$ ）立方质数（ $x 3 － y 3 ）／（ x － y$ ）莱兰质数（ $x y ＋ y x$ ）塔别脱质数（ $3\cdot2 n －1$ ）威廉姆斯素数（ $（ b -1）\cdot b n －1$ ）（英语：Williams number）米尔斯质数（［ $A 3 n$ ］） Kynea质数（ $（2 n ＋1） 2 －2$ ）
整数数列	斐波纳契素数卢卡斯质数佩尔质数 NSW质数佩兰伪质数
属性	维费里希质数质数对（英语：Wieferich pair）沃尔-孙-孙质数沃尔斯滕霍尔姆质数（英语：Wolstenholme prime）威尔逊素数幸运质数 Fortunate质数（英语：Fortunate number）拉马努金质数皮莱质数正则质数强质数斯特恩质数超奇异质数（椭圆曲线）（英语：Supersingular prime (algebraic number theory)）超奇异质数（月光理论）好质数超质数希格斯质数高互补欧拉商数唯一质数
基数相关	回文素数反素数循环单位质数 $（10 n －1）／9$ 可交换质数环状质数可截短质数极小质数精致质数（英语：Delicate prime）原始质数全循环质数唯一质数快乐质数自我质数 Smarandache–Wellin质数 Strobogrammatic质数（英语：Strobogrammatic prime）二面质数四面质数（英语：Tetradic number）
图形	孪生质数（ $p ， p ＋2$ ）孪生倍链（ $n \pm 1，2 n \pm 1，4 n \pm 1，\dots$ ）（英语：Bi-twin chain）三胞胎质数（ $p ， p ＋2 或 p ＋4， p ＋6$ ）四胞胎质数（ $p ， p ＋2， p ＋6， p ＋8$ ）质数k元组（英语：Prime k-tuple）表兄弟质数（ $p ， p ＋4$ ）六质数（ $p ， p ＋6$ ）陈质数索菲·热尔曼／安全质数（ $p ，2 p ＋1$ ）坎宁安链（ $p ，2 p \pm 1，4 p \pm 3，8 p \pm 7，...$ ）（英语：Cunningham chain）等差数列（ $p ＋ a\cdotn ， n ＝0，1，2，3，...$ ）（英语：Primes in arithmetic progression）平衡质数（ $连续的 p － n ， p ， p ＋ n$ ）
数量级	超大质数（1,000,000+以上）（英语：Megaprime）已知最大质数列表（英语：List of largest known primes and probable primes）
复数	艾森斯坦质数高斯质数
合数	伪质数卡塔兰（英语：Catalan pseudoprime）椭圆（英语：Elliptic pseudoprime）欧拉欧拉-雅可比费马弗罗贝尼乌斯（英语：Frobenius pseudoprime）卢卡斯（英语：Lucas pseudoprime）佩兰索默尔–卢卡斯（英语：Somer–Lucas pseudoprime）强卡迈克尔数殆质数半质数楔形数 Interprime 有害数（英语：Pernicious number）
相关	准质数（英语：Probable prime）产业等级质数非法质数质数公式质数间隙 $X 2 ＋1$ 质数质数定理素数计数函数素性测试
前60个质数	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
质数列表

叙述

关于 .mw-parser-output .serif{font-family:Times,serif}π(x)、x / ln x 和 li(x) 的数值

历史

初等证明

相关条目

参考资料

外部链接

关于 $π (x)$ 、 $x / ln x$ 和 $li(x)$ 的数值