查看“︁篩法的奇偶性問題”︁的源代码

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

==陳述==
[[陶哲軒]]就這問題給出了以下「粗略的」陳述：<ref>{{cite web |url=http://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/ |title=Open question: The parity problem in sieve theory |access-date=2008-08-11 |last=Tao |first=Terence |author-link=Terence Tao |date=2007-06-05 |archive-date=2023-08-07 |archive-url=https://web.archive.org/web/20230807211237/https://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/ |dead-url=no }}</ref>
{{Quote|'''奇偶性問題'''：假定<math>A</math>是一個全部元素都是奇數個質數相乘的數（或全部元素都是偶數個質數相乘的數）構成的集合，那麼（在沒有外加成分的狀況下）篩法無法提供<math>A</math>的非顯著下界；此外，任何的上界都會以2或更大的因次偏移實際值。}}

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

==例子==
以下例子由[[阿特勒·塞爾伯格]]給出，並在科惹卡露與姆爾帝（Cojocaru & Murty）的教科書中作為帶有提示的習題出現：<ref>
{{cite book | last = Cojocaru | first= Alina Carmen |author1-link= Alina Carmen Cojocaru |author2=M. Ram Murty  | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=Cambridge University Press | isbn=0-521-61275-6 | year = 2005 | author2-link= M. Ram Murty }}
</ref>{{Rp|133–134}}

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

==對奇偶性敏感的篩法==
自大約1996年起，{{le|约翰·弗里德兰德|John Friedlander|弗里蘭}}與[[亨里克·伊萬尼克|伊萬尼茲]]發展出了一些新的篩法技巧，以圖突破奇偶性問題。<ref>{{cite journal |last=Friedlander |first=John |author-link=John Friedlander |author2=Henryk Iwaniec  | date=1997-02-18 |title=Using a parity-sensitive sieve to count prime values of a polynomial |journal=Proceedings of the National Academy of Sciences |volume=94 |issue=4 |pages= 1054–1058|id=1054–1058 |pmid=11038598 |doi=10.1073/pnas.94.4.1054 |pmc=19742|bibcode=1997PNAS...94.1054F |author2-link=Henryk Iwaniec |doi-access=free }}
</ref><ref>
{{cite journal |last=Friedlander |first=John |author-link=John Friedlander |author2=Henryk Iwaniec  | year = 1998 |title=Asymptotic sieve for primes |url=https://archive.org/details/sim_annals-of-mathematics_1998-11_148_3/page/n310 |journal=Annals of Mathematics |volume= 148 |pages=1041–1065 |arxiv=math/9811186 |doi=10.2307/121035 |jstor=121035 |issue=3 |bibcode=1998math.....11186F |s2cid=11574656 |author2-link=Henryk Iwaniec }}
</ref>而這些新方法的一個結果就是{{le|弗里蘭—伊萬尼茲定理|Friedlander–Iwaniec theorem|弗里蘭}}，這定理表示說，有無限多個質數可表示成<math>a^2+b^4</math>的形式。

{{link-en|歌林·哈爾曼|Glyn Harman}}將奇偶性問題給表述成篩法中「第一類」與「第二類」訊息間的區別。<ref>{{cite book | last=Harman | first=Glyn | author-link=Glyn Harman | title=Prime-detecting sieves | series=London Mathematical Society Monographs | volume=33 | publisher=Princeton University Press | year=2007 | isbn=978-0-691-12437-7 | zbl=1220.11118 | pages=45,335 }}</ref>

==喀喇祖巴現象==
在2007年，{{link-en|阿納托利·阿列克謝耶維奇·喀喇祖巴|Anatolii Alexeevitch Karatsuba}}發現說在算術序列中，對給定的質因數的奇偶性，會產生不平衡的現象，他的論文<ref>{{cite journal| last=Karatsuba| first=A. A.| title= A property of the set of prime numbers| pages=209–220| journal=Russian Mathematical Surveys| issue=2| year=2011| volume=66| doi=10.1070/RM2011v066n02ABEH004739| bibcode=2011RuMaS..66..209K}}</ref><ref>{{cite journal| last=Karatsuba| first=A. A.| title= A property of the Set of Primes as a Multiplicative Basis of Natural Numbers| pages=1–4| journal=Doklady Mathematics| issue=84:1| year=2011}}</ref>在他死後出版。此現象的描述如下：

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

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

然而，若將這兩個集合的適用範圍給限制在常規表示法不包含位於<math>6m + 1, m = 1, 2, \dots</math>或<math>km + l, 1 \leq l < k, (l,k) = 1</math>, <math>m = 0, 1, 2, \dots</math>之類的[[算數數列中的質數|算數數列之上的質數]]的自然數，那麼在這些正整數中，有偶數個質因數的數，傾向少於有奇數個質因數的數。喀喇祖巴發現了這現象，他也發現了這現象的公式，而這公式表示了在這些因子遵循特定限制的狀況下，有偶數個質因數的數的集合跟有奇數個質因數的數的集合其[[勢 (數學)|元素個數]]的差。不論如何，由於這裡牽涉到的集合都是無窮集，因此所謂的「大小」在此指的是在趨近無限時，這些集合中的質數數量上限的比例的極限。在包含算術序列的的質數的情形下，喀喇祖巴證明了說這極限會趨近於無限大。

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

設<math>\mathbb{N}_0</math>及<math>\mathbb{N}_1</math>為<math>\mathbb{N}</math>的子集，其中若<math>n</math>有偶數個質因數，則<math>n \in \mathbb{N}_0</math>；而若<math>n</math>有奇數個質因數，則<math>n \in \mathbb{N}_1</math>。直觀上，<math>\mathbb{N}_0</math>與<math>\mathbb{N}_1</math>這兩個集合的大小大致相等；更精確地說，對於任意的<math>x\geq 1</math>，可定義<math>n_0(x)</math>與<math>n_1(x)</math>如次：<math>n_0(x)</math>是所有屬於<math>\mathbb{N}_0</math>且不大於<math>x</math>的<math>n</math>組成的集合的勢；而<math>n_1(x)</math>是所有屬於<math>\mathbb{N}_1</math>且不大於<math>x</math>的<math>n</math>組成的集合的勢。<math>n_0(x)</math>與<math>n_1(x)</math>的非病態行為由[[愛德蒙·蘭道]]給出：<ref>{{cite journal| last=Landau |first=E.| title= Über die Anzahl der Gitter punkte in gewissen Bereichen.| pages= 687–771|journal =Gött. Nachricht.|year=1912}}</ref>

:<math>
n_0(x) = \frac{1}{2}x + O\left(x e^{-c\sqrt{\ln x}}\right), n_1(x) = \frac{1}{2}x + O\left(x e^{-c\sqrt{\ln x}}\right);
c > 0. 
</math>

這表示說

:<math>
n_0(x) \sim n_1(x)\sim\frac12x,
</math>

換句話說，<math>n_0(x)</math>與<math>n_1(x)</math>大體相等。

此外，

:<math>
n_1(x)-n_0(x)=O\left(xe^{-c\sqrt{\ln x}}\right),
</math>

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

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

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

:<math> 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  .</math>

喀喇祖巴證明了說當<math>x\to+\infty</math>時，下列非病態公式成立：

:<math>
n^*_1(x)-n^*_0(x)\sim C n^*(x)(\ln x)^{2\left(\frac{r}{\varphi(k)}-1\right)},
</math>

此處的<math>C</math>是一個正數常數。

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

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

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

:<math>
n^*_1(x) - n^*_0(x) \sim \frac{\pi}{8\sqrt3}\frac{n^*(x)}{\ln x},\qquad
x \to +\infty .
</math>

==註解==
{{Reflist}}

[[Category:篩法]]
[[Category:數學問題]]