篩法的奇偶性問題

在數論中，篩法的奇偶性問題（Parity problem）指的是一類使得篩法在許多質數計數問題中，無法給出好的估計的限制。這問題最早由阿特勒·塞爾伯格在1949年發現並命名；另自大約1996年起，弗里蘭（英语：John Friedlander）與伊萬尼茲發展出了一些對奇偶性敏感的篩法，而得以減少奇偶性問題造成的障礙。

陳述

陶哲軒就這問題給出了以下「粗略的」陳述：^[1]

奇偶性問題：假定${\displaystyle A}$ 是一個全部元素都是奇數個質數相乘的數（或全部元素都是偶數個質數相乘的數）構成的集合，那麼（在沒有外加成分的狀況下）篩法無法提供${\displaystyle A}$ 的非顯著下界；此外，任何的上界都會以2或更大的因次偏移實際值。

這問題是顯著的，因為這可能得以解釋為何篩法難以「測到質數」，也就是為何篩法無法給出有特定性質的質數數量的非顯著下界這點。像例如說由於陳氏定理表示說存在無限多個質數${\displaystyle p}$ ，使得${\displaystyle p+2}$ 是質數或兩個質數的乘積之故，因此已經非常接近孿生質數猜想的解；但奇偶性問題顯示說，由於我們感興趣的問題有奇數個質因數（此例中為1個）之故，因此我們不可能用篩法分離這兩種狀況（此例中分別是質數以及兩個質數的乘積的狀況）。

例子

以下例子由阿特勒·塞爾伯格給出，並在科惹卡露與姆爾帝（Cojocaru & Murty）的教科書中作為帶有提示的習題出現：^{[2]:133–134}

這問題是要估計不大於${\displaystyle x}$ 且沒有小於${\displaystyle x^{\frac {1}{2}}}$ 的質因數的數字中，有偶數個（或奇數個）質因數的數字的個數，而可以證明說，不論如何選擇布朗或塞爾伯格篩法中的權重，其上界都至少會是${\displaystyle (2+o(1)){\frac {x}{\ln {x}}}}$ ；但實際上，不大於${\displaystyle x}$ 且沒有小於${\displaystyle x^{\frac {1}{2}}}$ 的質因數，且有偶數個質因數的數字的所構成的集合是空集合；而另一方面，不大於${\displaystyle x}$ 且沒有小於${\displaystyle x^{\frac {1}{2}}}$ 的質因數，且有奇數個質因數的數字的集合，就是介於${\displaystyle x^{\frac {1}{2}}}$ 跟${\displaystyle x}$ 之間的所有質數的集合，因此根據質數定理，這集合的大小大約是${\displaystyle (1+o(1)){\frac {x}{\ln {x}}}}$ 。因此在這種狀況下，這些篩法無法對第一個集合給出有用的上界，且會以一個2的因次，高估第二個集合的上界。

對奇偶性敏感的篩法

自大約1996年起，弗里蘭（英语：John Friedlander）與伊萬尼茲發展出了一些新的篩法技巧，以圖突破奇偶性問題。^[3][4]而這些新方法的一個結果就是弗里蘭（英语：Friedlander–Iwaniec theorem），這定理表示說，有無限多個質數可表示成${\displaystyle a^{2}+b^{4}}$ 的形式。

歌林·哈爾曼（英语：Glyn Harman）將奇偶性問題給表述成篩法中「第一類」與「第二類」訊息間的區別。^[5]

喀喇祖巴現象

在2007年，阿納托利·阿列克謝耶維奇·喀喇祖巴（英语：Anatolii Alexeevitch Karatsuba）發現說在算術序列中，對給定的質因數的奇偶性，會產生不平衡的現象，他的論文^[6][7]在他死後出版。此現象的描述如下：

設${\displaystyle \mathbb {N} }$ 為自然數的集合，也就是${\displaystyle 1,2,3,\dots }$ 這樣的樹構成的集合；然後再設質數的集合，也就是大於一且只有兩個相異質因數（也就是${\displaystyle n}$ 跟${\displaystyle 1}$ ）的自然數${\displaystyle n\in \mathbb {N} }$ 的集合為${\displaystyle \mathbb {P} }$ ，因此有${\displaystyle \mathbb {P} =\{2,3,5,7,11,\dots \}\subset \mathbb {N} }$ 。所有大於一的自然數${\displaystyle n\in \mathbb {N} }$ 都可表示成（未必彼此相異的）質數的乘積，也就是說${\displaystyle n=p_{1}p_{2}\dots p_{k},}$ ，其中${\displaystyle p_{1}\in \mathbb {P} ,\ p_{2}\in \mathbb {P} ,\ \dots ,\ p_{k}\in \mathbb {P} }$ ；而在質因數的排序法下這種表示是唯一的。

現在假定有兩個集合，其中第一個集合包含了有偶數個質因數的正整數，而第二個集合包含了有奇數個質因數的正整數，那在常規表示法下，這兩個集合的大小約略相等。

然而，若對這兩個集合的元素做出限制，使其常規表示法不包含諸如${\displaystyle 6m+1,m=1,2,\dots }$ 或${\displaystyle km+l,1\leq l<k,(l,k)=1}$ , ${\displaystyle m=0,1,2,\dots }$ 之類的算數數列中的質數（英语：primes in arithmetic progression），那麼在這些正整數中，有偶數個質因數的數，傾向少於有奇數個質因數的數。喀喇祖巴發現了這現象，他也發現了這現象的公式，而這公式表示了在這些因子遵循特定限制的狀況下，有偶數個質因數的數的集合跟有奇數個質因數的數的集合其元素個數的差。不論如何，由於這裡牽涉到的集合都是無窮集，因此所謂的「大小」在此指的是在趨近無限時，這些集合中的質數數量上限的比例的極限。在包含算術序列的的質數的情形下，喀喇祖巴證明了說這極限會趨近於無限大。

以下以數學術語重述喀喇祖巴現象：

設${\displaystyle \mathbb {N} _{0}}$ 及${\displaystyle \mathbb {N} _{1}}$ 為${\displaystyle \mathbb {N} }$ 的子集，其中若${\displaystyle n}$ 有偶數個質因數，則${\displaystyle n\in \mathbb {N} _{0}}$ ；而若${\displaystyle n}$ 有奇數個質因數，則${\displaystyle n\in \mathbb {N} _{1}}$ 。直觀上，${\displaystyle \mathbb {N} _{0}}$ 與${\displaystyle \mathbb {N} _{1}}$ 這兩個集合的大小大致相等；更精確地說，對於任意的${\displaystyle x\geq 1}$ ，可定義${\displaystyle n_{0}(x)}$ 與${\displaystyle n_{1}(x)}$ 如次：${\displaystyle n_{0}(x)}$ 是所有屬於${\displaystyle \mathbb {N} _{0}}$ 且不大於${\displaystyle x}$ 的${\displaystyle n}$ 組成的集合的勢；而${\displaystyle n_{1}(x)}$ 是所有屬於${\displaystyle \mathbb {N} _{1}}$ 且不大於${\displaystyle x}$ 的${\displaystyle n}$ 組成的集合的勢。${\displaystyle n_{0}(x)}$ 與${\displaystyle n_{1}(x)}$ 的非病態行為由愛德蒙·蘭道給出：^[8]

${\displaystyle n_{0}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right),n_{1}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right);c>0.}$ 

這表示說

${\displaystyle n_{0}(x)\sim n_{1}(x)\sim {\frac {1}{2}}x,}$ 

換句話說，${\displaystyle n_{0}(x)}$ 與${\displaystyle n_{1}(x)}$ 大體相等。

此外，

${\displaystyle n_{1}(x)-n_{0}(x)=O\left(xe^{-c{\sqrt {\ln x}}}\right),}$ 

也就是這兩個集合的勢的差很小。

另一方面，設${\displaystyle k\geq 2}$ 是一個自然數，而${\displaystyle l_{1},l_{2},\dots l_{r}}$ 為自然數的序列且${\displaystyle 1\leq r<\varphi (k)}$ 、${\displaystyle (l_{j},k)=1}$ 、所有的${\displaystyle l_{j}}$ 對模${\displaystyle k}$ 、${\displaystyle j=1,2,\dots r.}$ ；再設${\displaystyle \mathbb {A} }$ 為等差序列${\displaystyle kn+l_{j}}$ 中的質數的集合且${\displaystyle j\leq r}$ （${\displaystyle \mathbb {A} }$ 是所有不能除${\displaystyle k}$ 的質數）。

現在設${\displaystyle \mathbb {N} ^{*}}$ 為不包含${\displaystyle \mathbb {A} }$ 中的質因數的自然數集合，並設${\displaystyle \mathbb {N} _{0}^{*}}$ 為${\displaystyle \mathbb {N} ^{*}}$ 當中有偶數個質因數的數組成的集合，而${\displaystyle \mathbb {N} _{1}^{*}}$ 則為${\displaystyle \mathbb {N} ^{*}}$ 當中有奇數個質因數的數組成的集合。接著定義以下的方程：

${\displaystyle n^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} ^{*}\end{array}}1;n_{0}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{0}^{*}\end{array}}1;n_{1}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{1}^{*}\end{array}}1.}$ 

喀喇祖巴證明了說當${\displaystyle x\to +\infty }$ 時，下列非病態公式成立：

${\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim Cn^{*}(x)(\ln x)^{2\left({\frac {r}{\varphi (k)}}-1\right)},}$ 

此處的${\displaystyle C}$ 是一個正數常數。

此外，他也證明了說對其他自然數的集合也可證明類似的定理，像例如說對於表示成兩個平方數的數，所有隸屬於${\displaystyle \mathbb {A} }$ 的因子，都會展現出類似的非病態行為。

喀喇祖巴並將其定理推廣到${\displaystyle \mathbf {A} }$ 是特定種類無限的質數集合的情況之上。

喀喇祖巴現象可由以下範例展現。考慮常規表示法不屬於${\displaystyle 6m+1,m=1,2,\dots }$ 這序列的自然數，那這現象就可以下列公式表示：

${\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim {\frac {\pi }{8{\sqrt {3}}}}{\frac {n^{*}(x)}{\ln x}},\qquad x\to +\infty .}$ 

註解

1. Tao, Terence. Open question: The parity problem in sieve theory. 2007-06-05 [2008-08-11]. （原始内容于2023-08-07）. 
2. Cojocaru, Alina Carmen; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts 66. Cambridge University Press. 2005. ISBN 0-521-61275-6. 
3. Friedlander, John; Henryk Iwaniec. Using a parity-sensitive sieve to count prime values of a polynomial. Proceedings of the National Academy of Sciences. 1997-02-18, 94 (4): 1054–1058. Bibcode:1997PNAS...94.1054F. PMC 19742  . PMID 11038598. doi:10.1073/pnas.94.4.1054  . 1054–1058. 
4. Friedlander, John; Henryk Iwaniec. Asymptotic sieve for primes. Annals of Mathematics. 1998, 148 (3): 1041–1065. Bibcode:1998math.....11186F. JSTOR 121035. S2CID 11574656. arXiv:math/9811186  . doi:10.2307/121035. 
5. Harman, Glyn. Prime-detecting sieves. London Mathematical Society Monographs 33. Princeton University Press. 2007: 45,335. ISBN 978-0-691-12437-7. Zbl 1220.11118. 
6. Karatsuba, A. A. A property of the set of prime numbers. Russian Mathematical Surveys. 2011, 66 (2): 209–220. Bibcode:2011RuMaS..66..209K. doi:10.1070/RM2011v066n02ABEH004739. 
7. Karatsuba, A. A. A property of the Set of Primes as a Multiplicative Basis of Natural Numbers. Doklady Mathematics. 2011, (84:1): 1–4. 
8. Landau, E. Über die Anzahl der Gitter punkte in gewissen Bereichen.. Gött. Nachricht. 1912: 687–771.