筛法

维基百科，自由的百科全书
跳转到导航 跳转到搜索

筛法（Sieve Theory）是数论中的一类基本方法，其研究对象是筛函数，也就是某个被“筛选”过的有限整数子集的元素个数[1]: 5 [2]: 10, 148–149 。

埃拉托斯特尼筛法是一种古典筛法，但由于没有理论价值，在很长时期内都没有发展[2]: 10 ；20世纪以来，筛法得到了改进。常见的筛法有布朗筛法、塞尔伯格筛法、图兰筛法和大筛法等等。另外作为现代筛法始祖的勒让德筛法是埃拉托斯特尼筛法的简单推广，且是理解筛法的基础，但很少有实际应用。

直接对质数集合进行研究的效果不佳，因此研究者常常会改成估计与特定目标集合（如质数的集合）类似但较简单的集合（如殆质数的集合）的元素个数，而通常这样的集合其大小会稍微大于目标集合，但也较好分析。更加细致的筛法也不直接研究集合本身，而是透过精心挑选的、对各集合的权重（也就是给部分集合较高的权重等作法）来计算集合元素个数；此外，在部分当代的研究中，研究者以筛法构造一个在集合中很大、但在集合外很小、且比集合本身的特征函数还容易分析的函数，而非直接估计“被筛选”集合的元素个数。

基本筛法[编辑]

首先我们从非负数的有限序列<math>\mathcal{A}=(a_n)</math>开始。在最基本的状况中，这序列就只是我们要筛选的集合<math>A=\{s:s\leq x\}</math>的指示函数<math>a_n=1_{A}(n)</math>；然而，这样的抽象化可套用在更一般的情境中。

接着我们引入一个称为“筛选范围”（sifting range）的质数集合<math>\mathcal{P}\subseteq \mathbb{P}</math>，及这“筛选范围”中不大于<math>z</math>的质数的乘积<math>P(z)=\prod\limits_{p\in\mathcal{P}, p<z}p</math>，此处<math>P(z)</math>可视为一个对<math>z</math>的函数。

筛法的目标是估计“筛函数”（sifting function）的值，而“筛函数”表记如下：

<math>S(\mathcal{A},\mathcal{P},z)=\sum\limits_{n\leq x, (n,P(z))=1}a_n.</math>

在<math>a_n=1_{A}(n)</math>的状况下，这就单纯是计算整数子集<math>A_{\operatorname{sift}}\subseteq A</math>中与<math>P(z)</math>的质因数互质的元素个数。

相关表记[编辑]

下为此文表记的注意事项：

在文献中，人们常将序列集合<math>\mathcal{A}</math>与<math>A</math>本身等同，也就是说，可以将<math>\mathcal{A}</math>表示成<math>\mathcal{A}=\{s:s\leq x\}</math>以定义序列<math>\mathcal{A}=(a_n)</math>；

此外，在文献中<math>A_d(x)</math>这和有时以集合<math>A_d(x)</math>的元素个数<math>|A_d(x)|</math>表示；然而此处我们因为已经将<math>A_d(x)</math>定义为元素个数之故，因此此处我们以 <math>\mathbb{P}</math>表示质数的集合，并以<math>(a,b)</math>表示<math>a</math>与<math>b</math>的最大公因数。

勒让德等式[编辑]

我们可透过默比乌斯函数及一组由<math>\mathcal{P}</math>中的元素生成的函数<math>A_d(x)</math>，将筛选函数表述为一个称为“勒让德等式”（Legendre's identity）的函数：

<math>S(\mathcal{A},\mathcal{P},z)=\sum\limits_{d\mid P(z)}\mu(d)A_d(x)</math>

其中<math>A_d(x)</math>的形式如下：

<math>A_d(x)=\sum\limits_{n\leq x, n\equiv 0\pmod{d}}a_n.</math>

范例[编辑]

设<math>z=7</math>及<math>\mathcal{P}=\mathbb{P}</math>，由于默比乌斯函数对所有的质数都呈负值之故，因此有下式：

<math>\begin{align}

S(\mathcal{A},\mathbb{P},7)&=A_1(x)-A_2(x)-A_3(x)-A_5(x)+A_6+A_{10}+A_{15}-A_{30}. \end{align}</math>

同余和估计[编辑]

我们可以假定说<math>A_d(x)</math>可以下式表达：

<math>A_d(x)=g(d)X+r_d(x)</math>

其中<math>g(d)</math>是一个“密度”（density），也就是有如下形式的积性函数：

<math>g(1)=1,\qquad 0\leq g(p)<1 \qquad p\in \mathbb{P}</math>

此外，此处的<math>X</math>是<math>A_1(x)</math>的估计，而<math>r_d(x)</math>则是余项，因此筛函数可变为以下的形式：

<math>S(\mathcal{A},\mathcal{P},z)=X\sum\limits_{d\mid P(z)}\mu(d)g(d)+\sum\limits_{d\mid P(z)}\mu(d)r_d(x)</math>

或简单地说，

<math>S(\mathcal{A},\mathcal{P},z)=XG(x,z)+R(x,z).</math>

我们可透过找出<math>S</math>、<math>G</math>及<math>R</math>的上下界来估计筛函数。

筛函数的部分和会交替性地大于跟小于集合大小本身，而其余项最终会变得非常大。玮哥·布朗解决这问题的方法，是将筛函数中的<math>\mu(d)</math>以一个包含受限默比乌斯函数的权重序列<math>(\lambda_d)</math>取代。透过选取两个适当的序列<math>(\lambda_d^{-})</math>及<math>(\lambda_d^{+})</math>并将筛函数以<math>S^{-}</math>及<math>S^{+}</math>表示，可得到原始筛函数的下界与上界：

<math>S^{-}\leq S\leq S^{+}.</math>[3]

另由于<math>g</math>是积性函数之故，因此也可研究下式：

<math>\sum\limits_{d\mid n}\mu(d)g(d)=\prod\limits_{\begin{array}{c} p|n ;\; p\in\mathbb{P}\end{array}}(1-g(p)),\quad\forall\; n\in\mathbb{N}.</math>

筛法种类[编辑]

当代的筛法包括了布朗筛法、塞尔伯格筛法、图兰筛法、大筛法、更大筛法以及GPY筛法等；而筛法的一个原始目的，就是尝试证明孪生质数猜想等数论的问题。尽管筛法原始的目标依旧未达成，透过筛法学界依旧达成了部分目标，尤其在将此筛法与其他数论工具混合时更是如此。一些筛法取得的重要成果如下：

  1. 布朗定理，这定理指出所有的孪生质数的倒数之和收敛（但所有质数的倒数之和发散）
  2. 陈氏定理, 这定理指出，存在无限多的质数<math>p</math>，使得<math>p+2</math>要不就是质数，要不就是殆质数；而一个紧密相关的定理指出，任何一个充分大的偶数都可以表示成两个质数的和或者一个质数及一个半质数（2次殆质数）的和。这两个定理可分别视为与孪生质数猜想和哥德巴赫猜想最接近的定理。
  3. 筛法基本引理，这引理指出如果要对一个有N个元素的整数集合进行筛选，那在<math>\varepsilon</math>（像是1/10之类的分数常用于此情况）足够小的状况下，经过<math>N^\varepsilon</math>个步骤后就能得到精确的估计；然而，尽管这引理在筛出质数方面太弱（一般而言，这需要大约<math>N^{1/2}</math>个步骤），但依旧足以证明殆质数方面的结果。
  4. 弗里兰-伊万尼兹定理（英语：Friedlander–Iwaniec theorem），这定理指出有无限多的质数可表成<math>a^2 + b^4</math>的形式。
  5. 张益唐定理，(Zhang 2014)这定理指出有无限多对的质数，其彼此的间隔是有限的；而梅那–陶定理（Maynard–Tao theorem）(Maynard 2015)将之推广为存在任意长度的质数序列。

筛法技巧[编辑]

筛法是一个相当强力的技巧，但这技巧受限于奇偶性问题（parity problem）；而粗略地说，奇偶性问题指的是筛法在辨别有奇数个质因数的数及有偶数个质因数的数方面极为困难。截至目前为止，学界对奇偶性问题尚未有充分的了解。

跟其他数论方法相比，筛法是一个相对“初等”的技巧，而之所以会说筛法“初等”，是因为筛法不需要用到诸如解析数论或代数数论等其他更为进阶的理论的观念；然而，更加进阶的筛法也可变得非常复杂且细致，尤其在与其他数论技巧混合时更是如此；此外，目前也有专门介绍筛法的教科书，其中一个经典著作是(Halberstam & Richert 1974)；而一个更为现代的著作则是(Iwaniec & Friedlander 2010)。

另外，本文中介绍的筛法与二次筛选法和普通数域筛选法等等作为整数质因数分解方法的筛选法并不密切相关，而这些质因数分解方法大多是利用埃拉托斯特尼筛法来有效率地决定一个数是否可以完全分解成小质数的算法。

参考文献[编辑]

  1. ^ Halberstam, Heini and Richert, Hans-Egon. Sieve Methods. London Mathematical Society Monographs 4. London-New York: Academic Press. 1974. ISBN 0-12-318250-6. 
  2. ^ 2.0 2.1 潘承洞、潘承彪. 哥德巴赫猜想. 纯粹数学与应用数学专著 7. 北京: 科学出版社. 1981. 
  3. ^ (Iwaniec & Friedlander 2010)

扩展阅读[编辑]

检索自“https://arolstar52-zhtest.hf.space/index.php?title=筛法&oldid=2097596”