動機
歐幾里得(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
(有限歐拉乘積包含超出其截斷的整數)
對質數 ,乘積為 。調和和 為 ,嚴格較小。該乘積還包含 以及每個僅由 構成的整數的倒數,即使該整數超過 。因此它是支配截斷調和和,而不是等於它。這份額外的正質量是無害的,而這恰好說明了為甚麼下界對發散的證明已經足夠。
反例模式
無窮多個正項的和未必發散
質數的平方給出一個無窮級數,但 收斂:它以 為上界,而最後一個級數是裂項相消的。因此僅憑歐幾里得的質數無窮性,不能證明質數倒數之和發散;有限乘積的論證提供了真正額外的資訊。
常見錯誤
常見錯誤
(以質數冪自身的對數作權重)
函數 給每個質數冪 的權重是 ,而不是 。在 處,正確的值是 ,即 的對數;錯誤的權重則給出 。賦值也須同樣小心:一個質數冪可以在階乘計數的不止一層上有貢獻,所以估計之前須保留精確的下取整公式。
常見錯誤
(在計數上界中丟掉小質數修正)
把 除以 只給出 的下界。計數上界需要每個權重的下界,而這只對 成立。餘下小質數的 一項有其確定的作用,不能不加替代地丟棄。
常見錯誤
(把常數倍的界讀成漸近定律)
以 的兩個常數倍為界,並不能確立 ,甚至不能確立任何極限。該證明也不表明每個固定長度的區間都含有質數。同樣,有限歐拉乘積包含由不超過 的質數構成的任意大整數,因此不應與截斷相同的調和和等同。
總結
中心二項式係數把階乘賦值轉化為 的線性界。高次質數冪只貢獻較小的誤差,由此得到 的線性界,以及質數計數的 量級。把這些界反過來,得到第 個質數的 量級。有限幾何乘積與唯一分解則獨立地證明了質數倒數之和發散。
練習
快速檢查
(在 處,透過計算 ,驗證 的質數冪解釋。)
解答 · 答案
不超過 的極大質數冪為 ,所以最小公倍數為 。它的對數等於 ,即 。而 對這四個質數的對數各只含一份,剩下的額外權重為 。
快速檢查
(由所述的初等誤差估計證明 。並說明為甚麼僅憑這一點不能證明質數定理。)
解答 · 答案
把誤差估計除以 ,得到以 為界,它趨於零。因此這兩個加權函數相差一個次線性的量。但它們已證明的主要界的常數不同:對其中任何一個,都沒有證明它與 之比為 。兩個未知的線性量級函數之間的微小差距,並不能確定它們共同的極限係數。
快速檢查
(證明有限乘積 趨於零,並解釋它們的倒數在發散證明中的含義。)
解答 · 答案
它們的倒數支配調和和,因而趨於無窮。每個因子都為正,所以取倒數後可見乘積趨於零。這並不斷言任何一個有限乘積為零;每一個都是嚴格為正的有理數。極限表達的是越來越多的質數倒數貢獻。
快速檢查
(為甚麼 給出的是 的下界而不是上界?利用平方根分割修正這個錯誤的上界論證。)
解答 · 答案
將不等式除以正數 ,得 。要給出上界,低於平方根的質數至多有 個,而每個更大的質數都有 。因此它們的個數至多為 ,再加上小質數的餘量,就得到已證明的上界估計。同一個加權和之所以能在兩個相反的方向上給出計數估計,只是因為作了這兩種不同的最大權重與最小權重的比較。