篩法（3.1）——Brun篩法與孿生素數對的倒數和

作者：由 TravorLZH 發表于體育時間：2021-08-09

在前篇文章中由於出現了一些不可挽回的錯誤，我們沒能用Eratosthenes-Legendre-Rankin篩法來證明孿生素數倒數和收斂。因此在本篇文章中我們將展現Viggo Brun最初提供的證法。

往期文章：

TravorLZH：篩法（1）——抽象形式與常用形式

TravorLZH：篩法（2）——容斥原理和埃氏篩法

TravorLZH：篩法（3）——孿生素數對的倒數和收斂【本文含錯誤】

Brun篩法的核心

在前兩篇文章裡，我們將透過莫比烏斯反演引入我們具體的篩法，從而得到了埃氏篩的解析形式：

$\sum_{d|n}\mu(d)=\begin{cases} 1 & n=1 \\ 0 & n>1 \end{cases}$

而由於這種方法產生的誤差項過大，所以很多時候我們僅僅能得到過於寬鬆的上界。為此，數學家們提出了各種方法來估計上面的

篩選函式（sifting function）

。其中Viggo Brun本人的方案是對莫比烏斯反演的Dirichlet卷積進行不完全求和：

$s(n,\ell)=\sum_{\substack{d|n\\\omega(d)\le\ell}}\mu(d)=\sum_{0\le r\le\ell}(-1)^r\color{blue}{\sum_{\substack{d|n,\mu(d)\ne0\\\omega(d)=r}}1}$

利用排列組合的知識，我們可以發現藍色部分剛好等同於從

$\omega(d)$

選r的組合數，所以有：

$s(n,\ell)=\sum_{0\le r\le\ell}(-1)^r\binom{\omega(n)}r$

為了求解右側表示式的具體值，我們可以考慮定義冪級數：

$F(x)=\sum_{\ell\ge0}s(n,\ell)x^\ell$

利用交換求和次序，可得：

$\begin{aligned} F(x) &=\sum_{r\ge0}(-1)^r\binom{\omega(n)}r\sum_{\ell\ge r}x^\ell \\ &=\sum_{r\ge0}(-x)^r\binom{\omega(n)}r\sum_{\ell-r\ge0}x^{\ell-r} \\ &={1\over1-x}\sum_{0\le r\le\omega(n)}(-x)^r\binom{\omega(n)}r \\ &=(1-x)^{\omega(n)-1}=\sum_{0\le m\le\omega(n)-1}(-x)^r\binom{\omega(n)-1}r \end{aligned}$

對比係數我們就能得到結論：

$s(n,\ell)=(-1)^\ell\binom{\omega(n)-1}\ell$

這意味著當

$\ell$

為偶數時總有：

$\sum_{d|n}\mu(d)\le s(n,\ell)\tag1$

同樣的當

$\ell$

為奇數時我們可以得到一個下界。

抽象篩法

$S(\mathcal A,\mathcal P,z)$

在本系列第一篇文章裡，我們引入了符號

$S(\mathcal A,\mathcal P)$

。而透過我們對Eratosthenes篩法的探索，我們往往會在最終的放縮中引入引數z。因此數論中更多的篩法問題都會在S中引入引數z：

$S(\mathcal A,\mathcal P,z)=\#\{n\in\mathcal A:\forall p\in\mathcal P\cap[2,z],n\notin\mathcal A_p\}$

為了簡化上面的表示式，我們設

$P_z=\prod_{\substack{p\in\mathcal P\\p\le z}}p$

和

$a_n=\prod_{\substack{p|P_z\\n\in\mathcal A_p}}p$

，則有：

$S(\mathcal A,\mathcal P,z)=\#\{n\in\mathcal A:(a_n,P_z)=1\}$

把篩法轉變成互素的形式後我們就可以開始結合（1）進行放縮了：

$\begin{aligned} S(\mathcal A,\mathcal P,z) &\le\sum_{n\in\mathcal A}s((n,P_z),\ell)=\sum_{n\in\mathcal A}\sum_{\substack{d|(a_n,P_z)\\\omega(d)\le\ell}}\mu(d) \\ &=\sum_{\substack{d|P_z\\\omega(d)\le\ell}}\mu(d)\color{red}{\sum_{\substack{n\in\mathcal A\\d|a_n}}1} \end{aligned}$

很明顯紅色求和描述的是某個集合的元素個數。結合

的定義，我們發現：

$\{n\in\mathcal A:\forall p|d,n\in\mathcal A_p\}=\bigcap_{p|d}\mathcal A_p:=\mathcal A_d\tag2$

由於d的定義，我們在後續章節中討論

$\mathcal A_d$

時都會預設d無平方因子

因此倘若我們將右側的集合定義為

$\mathcal A_d$

，則有：

$S(\mathcal A,\mathcal P,z)\le\sum_{\substack{d|P_z\\\omega(d)\le\ell}}\mu(d)|\mathcal A_d|\tag3$

為了繼續展開，我們需要對

$\mathcal A_d$

的元素個數進行假設。

同餘類的計數

從前兩篇文章的實踐中我們可以發現其實篩法就是在刪除同餘類，所以我們在推導抽象篩法的時候也會假設

$\mathcal A_p$

中儲存的恰好就是要被刪除的模p同餘類。倘若

$\mathcal A_p$

中恰好有g（p）個模p同餘類，則根據

中國剩餘定理

［1］

，

$\mathcal A_d$

中就會剛剛好有g（d）個模d同餘類。因此我們也得到了初步計算

$\mathcal A_d$

大小的方法：

$|\mathcal A_d|=g(d)\times\mathcal A_d中長度為d的區間個數$

倘若

$\mathcal A=\{n\in\mathbb Z^+:n\le x\}$

則

$|\mathcal A_d|={g(d)\over d}x+\mathcal O\{g(d)\}$

。所以我們有理由假設被篩選的集合滿足：

$|\mathcal A_d|={g(d)\over d}|\mathcal A|+\mathcal O\{g(d)\}\tag4$

Brun篩法的主項

現在把（4）代入到（3）中，得：

$\begin{aligned} S(\mathcal A,\mathcal P,z) &\le|\mathcal A|\sum_{\substack{d|P_z\\\omega(d)\le\ell}}{\mu(d)g(d)\over d}+R_1 \\ &=|\mathcal A|\sum_{d|P_z}{\mu(d)g(d)\over d}+|\mathcal A|R_2+R_1 \end{aligned}\tag5$

其中利用積性，主項可以轉化為：

$\sum_{d|P_z}{\mu(d)g(d)\over d}=\prod_{p|P_z}\left(1-{g(p)\over p}\right)\tag6$

接下來我們就可以處理誤差項了：

的處理

而結合定義，我們知道：

$R_1\ll\sum_{\substack{d|P_z\\\omega(d)\le\ell}}g(d)$

結合

的定義，我們發現

$g(p)\le z$

所以

$g(d)\le z^{\omega(d)}\le z^\ell$

，向上回代，便有：

$R_1\ll z^\ell\sum_{\substack{d|P_z\\\omega(d)\le\ell}}1=z^\ell\sum_{0\le r\le\ell}\sum_{\substack{d|P_z\\\omega(d)=r}}1=z^\ell\sum_{0\le r\le\ell}\binom{\omega(P_z)}r$

其中最後一個等號的由來可以參考本文推導

$s(n,\ell)$

的過程。現在，根據組合數的定義，我們得到：

$\binom{\omega(P_z)}r\le{\omega(P_z)^r\over r!}\le{\pi(z)^r\over r!}\le{z^r\over r!}\le{z^\ell\over r!}$

把這個放縮代入，我們就能得到：

$R_1\ll z^{2\ell}\sum_{0\le r\le\ell}{1\over r!}\le z^{2\ell}\underbrace{\sum_{r\ge0}{1\over r!}}_{=\exp(1)=e}\ll z^{2\ell}\tag7$

處理完

，我們就來看看剩餘的誤差項：

用Rankin‘s trick估計

這部分推導源自Dr。 Paul Pollack在今年Ross夏校教授的解析數論課

根據（5），我們知道

$R_2\ll\sum_{\substack{d|P_z\\\omega(d)>\ell}}{g(d)\over d}$

由於g（d）/d是積性函式，所以我們希望能把條件

$\omega(d)>\ell$

化成一個積性函式。換言之，我們希望定義

$h_\ell(\omega(d))$

使得：

$h_\ell(\omega(d)) \begin{cases} \le1 & \omega(d)\le\ell \\ >1 & \omega(d)>\ell \end{cases}$

透過一些嘗試，我們可以發現對於任何固定的u>1我們都可以設

$h_\ell(\omega(d))=u^{\omega(d)-\ell}$

。把這個結果代入，我們就能得到：

$R_2\ll u^{-\ell}\sum_{d|P_z}{u^{\omega(d)}g(d)\over d}=u^{-\ell}\prod_{p|P_z}\left(1+{ug(p)\over p}\right)$

利用初等不等式

$1+t\le e^t$

，上面的乘積就可以化為求和，即對於任意固定的u>1均有：

$\log R_2\le-\ell\log u+u\sum_{p|P_z}{g(p)\over p}+\mathcal O(1)$

為了進一步推導，我們可以根據之前的經驗來對這個求和進行一些假設。根據Mertens定理我們知道

$\sum_{p\le z}\frac1p\le\log\log z+\mathcal O(1)\ll\log\log z$

所以我們有理由相信存在常數K>k>0使得：

$k\log\log z\le\sum_{p|P_z}{g(p)\over p}\le K\log\log z\tag8$

代入到上面，我們就得到了一個更簡潔的不等式了：

$R_2\ll u^{-\ell}(\log z)^{uK}\tag9$

估計好誤差項後，我們就可以開始考慮Brun篩法的整體了：

最後的調參

將（7）和（9）代入到（5），可得：

$S(\mathcal A,\mathcal P,z)\le|\mathcal A|\prod_{\substack{p\in\mathcal P\\p\le z}}\left(1-{g(p)\over p}\right)+\mathcal O\left\{|\mathcal A|u^{-\ell}(\log z)^{uK}+z^{2\ell}\right\}\tag{10}$

由於我們對

$\ell$

唯一的限制就是必須為偶數，所以我們也會透過對其進行限制來儘可能地弱化誤差項。根據之前（8），我們知道：

$\prod_{\substack{p\in\mathcal P\\p\le z}}\left(1-{g(p)\over p}\right)\le\exp\left(-\sum_{p|P_z}{g(p)\over p}\right)\le(\log z)^{-k}$

所以我們也希望

$u^{-\ell}(\log z)^{uQ}$

最終也能夠被log z的負冪次控制住。不妨假設存在T>0使得：

$\begin{aligned} -\ell\log u+uK\log\log z&\le -T\log\log z \\ \Rightarrow\ell&\ge{uK+T\over\log u}\cdot\log\log z \end{aligned}$

由於u、K、T均為固定常數，所以

$\ell=\ell(z)$

的增長速度必然快於z的二重對數。然而根據（10）中的誤差項

$z^{2\ell}$

我們也希望

$\ell=\ell(z)$

不要增長的太快。因此我們可以設

$\frac\alpha2>{uK+T\over\log u}$

然後設

$\ell=\ell(z)$

為不超過

$\frac\alpha2\log\log z$

的最大偶數。把這樣的設定代入回（10），我們就能得到最後的形式：

$S(\mathcal A,\mathcal P,z)\le|\mathcal A|\prod_{\substack{p\in\mathcal P\\p\le z}}\left(1-{g(p)\over p}\right)+\mathcal O\left\{|\mathcal A|(\log z)^{-T}+z^{\alpha\log\log z}\right\}\tag{11}$

由於（11）看起來還是太臃腫了，我們可以考慮提取公因數把第一個誤差項從大O裡拿出來。最後再結合（4）與（8）我們就得到了Brun篩法的最終形式：

定理（Brun's pure sieve

［2］

）：

沿用之前的符號，倘若

$\mathcal A_d$

和g（d）滿足：

1、

$|\mathcal A_d|={g(d)\over d}|\mathcal A|+\mathcal O\{g(d)\}$

2、

$\sum_{\substack{p\in\mathcal P\\p\le z}}{g(p)\over p}\ll\log\log z$

則對於一切M>0均存在

$\alpha>0$

使得：

$S(\mathcal A,\mathcal P,z)=|\mathcal A|\prod_{\substack{p\in\mathcal P\\p\le z}}\left(1-{g(p)\over p}\right)\left\{1+\mathcal O\left(1\over(\log z)^M\right)\right\}+\mathcal O(z^{\alpha\log\log z})\tag{12}$

這裡使用等於號是因為

$\ell$

為奇數的情況下會產生相同的誤差項。

推導完廣義的Brun篩法後，我們就來看看它的應用吧！

區間上的素數個數

設

$\mathcal A=\{n\in\mathbb Z^+:x<n\le x+y\}$

、

$\mathcal A_p=\{n\in\mathcal A:p|n\}$

、

$\mathcal P$

為全體素數，則有：

$\#\{x<p\le x+y\}\le z+S(\mathcal A,\mathcal P,z)$

其中很明顯z≤y。根據上面的設定，我們知道g（p）=1且結合Mertens定理我們知道：

$|\mathcal A_d|=\frac yd+\mathcal O(1)$

$\sum_{p\le z}{g(p)\over p}=\sum_{p\le z}\frac1p\ll\log\log z$

有了這兩個條件，我們就可以代入（12），得：

$\pi(x+y)-\pi(x)\ll y\prod_{p\le z}\left(1-\frac1p\right)+z^{\alpha\log\log z}\ll{y\over\log z}+z^{\alpha\log\log z}\tag{13}$

為了讓誤差項的增速慢於主項，希望

$z^{\alpha\log\log x}\le y^\beta$

其中

$\beta<1$

。結合z≤y我們就能發現設定

$\log z=\frac\beta\alpha\cdot{\log y\over\log\log y}$

即可滿足要求，將其代入（13），得：

$\pi(x+y)-\pi(x)\ll{y\log\log y\over\log y}\tag{14}$

這個上界遠遠優於我們之前用Eratosthenes-Legendre篩得到的界。接下來我們就來看看Brun篩法在孿生素數上的用途吧！

區間上的孿生素數分佈

我們知道n為孿生素數當且僅當對於所有的素數p均有：

$n\not\equiv0,-2\pmod p$

這意味著我們可以設

$\mathcal A_p=\#\{n\in\mathcal A:n\equiv0,-2\pmod p\}$

，則有：

$\pi_2(x+y)-\pi_2(x)\le z+S(\mathcal A,\mathcal P,z)$

結合剛才的設定，我們發現：

$g(p)= \begin{cases} 1 & p=2 \\ 2 & p>2 \end{cases}$

再沿用上一節對

$\mathcal A$

的定義我們還能發現：

$|\mathcal A_d|={g(d)\over d}y+\mathcal O\{g(d)\}$

最後根據Mertens定理，我們知道：

$\sum_{p\le z}{g(p)\over p}\le2\sum_{p\le z}\frac1p\ll\log\log z$

所以根據（12），我們就能得到適用於孿生素數的Brun篩法：

$S(\mathcal A,\mathcal P,z)\ll y\prod_{2<p\le z}\left(1-\frac2p\right)+z^{\alpha\log\log z}\ll{y\over(\log z)^2}+z^{\alpha\log\log z}\tag{15}$

如同上面對素數個數的研究，我們可以依樣畫葫蘆設定

$\beta<1$

然後再代入：

$z=\frac\beta\alpha\cdot{\log y\over\log\log y}$

就能得到最終的結論：

$\#\{x<p\le x+y:p+2\text{ prime}\}\ll{y(\log\log y)^2\over(\log y)^2}\tag{16}$

雖然前一篇文章

［3］

中我們用錯誤的方法進行了孿生素數個數上界的推導，但當時的結論仍然正確。因此利用那篇文章的推導，我們可以自然得到孿生素數的倒數和必然收斂。

總結

從本系列開篇以來我們發現當z關於x的增速越快，主項的增速就會變慢。因此為了估計出緊密的上界，我們總會希望能將大的z代入到

$S(\mathcal A,\mathcal P,z)$

中。然而當z的增速加快時誤差項的增長也會變快。因此在使用篩法的時候我們希望z在儘可能大的同時能保證誤差項的增速不超過主項。

在本篇文章中，我們透過對Eratosthenes-Legendre篩法的篩函式進行修改得到了一個新引數

$\ell$

，接著利用這個可調整的引數，我們成功地將誤差增幅從關於z的指數函式下降為

$z^{\alpha\log\log z}$

。這意味著我們可以將z的增速從之前的

$\log z\asymp\log\log x$

提高到

$\log z\asymp{\log x\over\log\log x}$

。正是因為這個改進，Brun篩法才能成功地給出足以說明倒數和收斂的孿生素數個數上界（16）。

然而這個增速仍然不夠，我們希望能夠繼續改進篩法的誤差項從而能夠代入更大的z來得到更緊密的界。敬請期待本系列的更新！

時代的一粒灰，落到個人頭上就是一座山

參考

尤拉定理、中國剩餘定理以及一道有趣的數論題 - 知乎

https：//zhuanlan。zhihu。com/p/358731224

Cojocaru， A。， & Murty， M。 R。（2005）。 An introduction to sieve methods and their applications。 Cambridge University Press。

篩法（3）——孿生素數對的倒數和收斂【本文含錯誤】 - 知乎

https：//zhuanlan。zhihu。com/p/387914596

標簽：篩法我們素數 Brun 代入

上一篇:《天道》弱勢文化的核心邏輯是什麼？怎麼才能遇到更好的“自己”

下一篇：什麼是等離子激元？

篩法（3.1）——Brun篩法與孿生素數對的倒數和

猜你喜歡

第一章數和整除第2節分解素因數

為什麼在費馬大定理這本書中（不是費馬大定理本身)，最大因數不在這兩個親和數計算範圍之內？

“山無稜，天地合，乃敢與君絕”的數學表示（附C++程式碼）

呆哥數學數列合集——通項公式的6種求法型別2【7】

素數表為平方和問題

篩法（3.1）——Brun篩法與孿生素數對的倒數和

猜你喜歡

第一章 數和整除 第2節 分解素因數

為什麼在費馬大定理這本書中（不是費馬大定理本身)，最大因數不在這兩個親和數計算範圍之內？

“山無稜，天地合，乃敢與君絕”的數學表示（附C++程式碼）

呆哥數學數列合集——通項公式的6種求法型別2【7】

素數表為平方和問題

第一章數和整除第2節分解素因數