筛法的奇偶性问题

在数论中，筛法的奇偶性问题（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 }$之类的算数数列之上的质数的自然数，那么在这些正整数中，有偶数个质因数的数，倾向少于有奇数个质因数的数。喀喇祖巴发现了这现象，他也发现了这现象的公式，而这公式表示了在这些因子遵循特定限制的状况下，有偶数个质因数的数的集合跟有奇数个质因数的数的集合其元素个数的差。不论如何，由于这里牵涉到的集合都是无穷集，因此所谓的“大小”在此指的是在趋近无限时，这些集合中的质数数量上限的比例的极限。在包含算术序列的的质数的情形下，喀喇祖巴证明了说这极限会趋近于无限大。

以下以数学术语重述喀喇祖巴现象：

设${\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 .}$