質數定理

<image>

在數論中，素數定理（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(x e^{-\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)$｜$\boldsymbol{\pi}(x)-\frac{x}{\ln x}$｜$\frac{\boldsymbol{\pi}(x)}{\frac{x}{\ln x}}$｜${\rm Li} (x) - \boldsymbol{\pi} (x)$｜$\frac{x}{\boldsymbol{\pi}(x)}$

10｜4｜−0.3｜0.921｜2.2｜2.500

102｜25｜3.3｜1.151｜5.1｜4.000

103｜168｜23｜1.161｜10｜5.952

104｜1,229｜143｜1.132｜17｜8.137

105｜9,592｜906｜1.104｜38｜10.425

106｜78,498｜6,116｜1.084｜130｜12.740

107｜664,579｜44,158｜1.071｜339｜15.047

108｜5,761,455｜332,774｜1.061｜754｜17.357

109｜50,847,534｜2,592,592｜1.054｜1,701｜19.667

1010｜455,052,511｜20,758,029｜1.048｜3,104｜21.975

1011｜4,118,054,813｜169,923,159｜1.043｜11,588｜24.283

1012｜37,607,912,018｜1,416,705,193｜1.039｜38,263｜26.590

1013｜346,065,536,839｜11,992,858,452｜1.034｜108,971｜28.896

1014｜3,204,941,750,802｜102,838,308,636｜1.033｜314,890｜31.202

1015｜29,844,570,422,669｜891,604,962,452｜1.031｜1,052,619｜33.507

1016｜279,238,341,033,925｜7,804,289,844,393｜1.029｜3,214,632｜35.812

1017｜2,623,557,157,654,233｜68,883,734,693,281｜1.027｜7,956,589｜38.116

1018｜24,739,954,287,740,860｜612,483,070,893,536｜1.025｜21,949,555｜40.420

1019｜234,057,667,276,344,607｜5,481,624,169,369,960｜1.024｜99,877,775｜42.725

1020｜2,220,819,602,560,918,840｜49,347,193,044,659,701｜1.023｜222,744,644｜45.028

1021｜21,127,269,486,018,731,928｜446,579,871,578,168,707｜1.022｜597,394,254｜47.332

1022｜201,467,286,689,315,906,290｜4,060,704,006,019,620,994｜1.021｜1,932,355,208｜49.636

1023｜1,925,320,391,606,803,968,923｜37,083,513,766,578,631,309｜1.020｜7,250,186,216｜51.939

1024｜18,435,599,767,349,200,867,866｜339,996,354,713,708,049,069｜1.019｜17,146,907,278｜54.243

1025｜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

## 歷史

1797年至1798年間，法國數學家勒讓德根據上述的質數表猜測，$\pi(x)$大約等於 $\frac{x}{A\ln x +B}$，其中$A$、$B$是未知的函數。勒讓德於1808年出版一本關於數論的書的第二版，書中他給出更精確的猜測：$A = 1$，$B = -1.08366$。根據高斯自己在1849年的回憶，他在15歲或16歲(1792或1793年)的時候就已經考慮過類似的問題了。1832年，狄利克雷經過跟高斯的交流之後，給出了一個新的逼近函數 $li(x)$，(事實上他是用一個有點不一樣的級數表達式)。勒讓德和狄利克雷的式子皆等價於現在的版本，但如果考慮逼近式與 $\pi(x)$ 的差，而不是比值的話，狄利克雷的式子是準確許多的。

俄國數學家切比雪夫參考了歐拉在1731年的工作，引進了定義在實數軸上黎曼ζ函數，企圖證明質數分布的漸進式，並將他所得到的結果寫成兩篇論文，分別在1848和1850年發表。切比雪夫可以證明，如果$\lim_{x\to\infty}\frac{\;\pi(x)\;}\frac{x}{\ln(x)}$存在且有限，則它一定是1。此外，在沒有假設任何結果之下，他也證明當 x 足夠大，$\frac{\;\pi(x)\;}\frac{x}{\ln(x)}$會界在兩個很靠近 1 的數字之間。雖然切比雪夫的論文沒辦法證明質數定理，但它對 $\pi(x)$ 已經可以推論出伯特蘭-切比雪夫定理：對任何大於$1$的正整數$n$，存在一個質數介於$n$和$2n$之間。

1859年，黎曼提交了一篇關於質數分布的非常重要的報告《論小於給定數值的質數個數》，這也是黎曼在這個領域的唯一一篇文章。黎曼在報告中使用了創新的想法，將$\zeta$函數的定義解析延拓到整個複數平面，並且將質數的分布與$\zeta$函數的零點緊密的聯繫起來。因此，這篇報告是歷史上首次用複分析的方法研究實函數 $\pi(x)$。1896年法國數學家雅克·阿達馬和比利時數學家夏爾-讓·德拉瓦萊·普桑先後獨立給出證明。兩個證明延著黎曼的思路繼續拓展，且都使用複分析的工具，其中的關鍵步驟是證明如果複數$s$可以寫成 $1 + it$ 的形式，且 $t>0$，則 $\zeta(s)\neq 0$。

進入20世紀之後，阿達馬和普桑證明的定理經常被稱作質數定理，定理的其他不同證明也陸陸續續被發現，這之中包括1949年阿特勒·塞爾伯格和艾狄胥·帕爾發現的「初等證明」。原本的證明是既冗長，又複雜，於是有很多後面發現的證明使用了陶伯定理讓證明變得比較簡短，但卻變得讓人比較難以消化。1980年，美國數學家唐納德·J·紐曼發現了一個簡潔的證明，這可能是目前已知最簡單的證明。不過，證明中使用了柯西積分公式，因此一般不被視為是為初等的證明。

因為黎曼ζ函數與$\pi(x)$關係密切，關於黎曼$\zeta$函數的黎曼猜想對數論很重要。一旦猜想獲證，便能大大改進素數定理誤差的估計。1901年瑞典數學家海里格·馮·科赫證明出，假設黎曼猜想成立，以上關係式誤差項的估計可改進為

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

Schoenfeld在1976年證明了在黎曼猜想成立的狀況下，對於任意的$2657\le x$而言，有以下關係式，以下的$\log{x}$是自然對數：

$$\big|\pi(x) - \operatorname{li}(x)\big| < \frac{\sqrt x \log x}{8\pi}$$

在同一篇論文中，Schoenfeld還證明了在黎曼猜想成立的狀況下，有以下跟切比雪夫函數有關的關係式，以下的$\log{x}$是自然對數：

$$\begin{align} |\vartheta(x)-x| &< \frac{1}{8\pi}\sqrt{x}\log^2{x}, \forall 599\le x\\ |\psi(x)-x| &< \frac{1}{8\pi}\sqrt{x}\log^2{x}, \forall 73.2\le x \end{align}$$

而在不假定黎曼猜想的情況下，在2016年，Timothy Trudigan證明了對於任意的$x \ge 229$而言，有以下明確公式，以下的$\log{x}$是自然對數：

$$\big| \pi(x) - \operatorname{li}(x) \big| \le 0.2795 \frac{x}{(\log x)^{3/4}} \exp \left( -\sqrt{ \frac{\log x}{6.455} } \right)$$

## 證明

質數定理的證明最初在1896年由法國數學家雅克·阿達馬和比利時數學家夏爾-讓·德拉瓦萊·普桑先後獨立給出證明；而之後許多數學家給出了不同的證明。

### 初等證明

素數定理有些初等證明只需用數論的方法。第一個初等證明於1949年由匈牙利數學家保羅·艾狄胥和挪威數學家阿特利·西爾伯格合作得出。

在此之前一些數學家不相信能找出不需藉助艱深數學的初等證明。像英國數學家哈代便說過素數定理必須以複分析證明，顯出定理結果的「深度」。他認為只用到實數不足以解決某些問題，必須引進複數來解決。