筛法（8）——组合筛的基本原理

  TravorLZH：筛法（5）——大筛法的解析形式（推广Bessel不等式与Rényi的权重）

  TravorLZH：筛法（6）——大筛法的算术形式（Farey数列与中国剩余定理）

  TravorLZH：筛法（7）——大筛法的积性形式（原特征与柯西不等式）

  今年1月1日，笔者在《哥德巴赫猜想》系列中创作了第一篇文章。为了能够更好的保证哥猜文章的主要内容简洁，从本文开始《筛法》系列将详细推导一些可拿来估下界的筛法。而这种筛法早期都是通过Brun的方法来实现的。因此我们有必要深入探究一些组合筛的结论。为了尽最大可能避免读者在阅读的时候经常性更换页面，我们将接下来可能涉及的所有符号都重新定义一遍。

  筛法的思想本质上是从一个集合中筛去特殊的元素并估计剩余元素的数量。因此我们将用\mathcal A表示这个需要被筛去元素的原始集合。而由于在筛法中，我们都是在筛出特定的倍数，所以我们用\mathcal A_d表示集合\mathcal A中全体能被d整除的元素。我们筛倍数的时候也是在筛一个集合\mathcal P元素的倍数，这个元素为素数的集合被称作筛域（sieving range）。为了更灵活地使用筛法，我们会引入一个动态变量z，使得筛函数（sieving function）S(\mathcal A,\mathcal P,z)真正使用的筛选范围的大小可以动态调整：

  因此我们称z为筛级（sieving level）。由于在很多场景中我们都需要用p来表示\mathcal P中小于z的素数，所以我们用P(z)表示\mathcal P中小于z的元素之积，使得我们大家可以把上面的定义式改写成：

  利用最大公约数的语言，我们大家可以发现筛函数实际上计算的就是\mathcal A中所有与P(z)互素的元素数目：

  其中\delta_0(n)在n=1时为1而n≠1时取零。通过用数论方法构造\delta_0(n)我们就可以把筛函数化成更好操作的形式。

  熟悉初等数论的朋友们可以注意到莫比乌斯反演是一种可行的方案。把\delta_0(n)=\sum_{dn}\mu(d)代入到(1)中便有：

  若用\mathcal A表示全体不超过x的素数减去一的整数集合，则根据等差数列素数定理可知：

  从之前的文章中，我们不难发现由于(4)的误差项增速太快所以往往在使用Eratosthenes-Legendre筛来探究数论问题时我们不能让z取太大的值（z不能超过log X的固定次方），否则误差项会把主项吞噬。而正是因为Brun对筛法进行了一种非常深刻的改进从而让我们避开了直接使用(4)，从而能够在z很大时（X的固定次方）得到有效的上下界，最终得到了一系列与哥德巴赫猜想和孪生素数问题相关的非平凡结论。

  由于Brun的原始工作过于繁琐且难以推广，所以本系列接下来采用的推导思路依赖的实际上是Halberstam和Richert在1972年对Brun筛的研究[1]以及两位作者在1974年出版的教材[2]。

  为了构造新筛法，我们大家可以考虑给(2)中的莫比乌斯函数增添权重\chi(d)，满足\chi(1)=1。在此之上我们定义函数：

  很明显当\chi(d)=1对于所有d都成立时(6)恰好就是\delta_0(n)。所以与其说改进，我们实际上是在对原始的筛法进行推广。把(2)中的莫比乌斯换上权重，便得：

  通过对(7)做进一步展开，我们就可以比较这个带权重的筛函数与S(\mathcal A,\mathcal P,z)的大小了。

  根据本文中对\chi的定义，我们可以把(7)右侧中k=1的情况分离出来，得到：

  根据算术基本定理，任何一个大于一的整数都有素因子，所以我们可以用p表示k的最小素因子，得到：

  为了避免考虑第三种情况，我们要求\mathcal D_v因子封闭（divisor closed）。再将第二个条件考虑进来我们就得到了一个定理1的充分条件：

  做好这些准备工作之后我们就可以将这些结果与(3)结合从而得到比(4)更优化的筛法公式。

  从(12)中我们不难发现只要我们对\chi_v进行巧妙的设计就可以避免余项增长过大。事实上Brun、Rosser以及Iwaniec就是从这个角度出发来得到强力的上界筛和下界筛。但为了得到更普适性的结论，这里我们把注意力放在蓝色部分。由于我们的特征函数只在0、1中取值，所以我们大家可以先把一个V(z)分离出来：

  在本篇文章中，我们以Eratosthenes-Legendre筛的抽象形式为起点，开始改进筛法。通过给莫比乌斯反演附加特征函数，我们得到了能用来构造上界筛和下界筛的定理1与定理2。通过将特征函数与g(p)的性质结合，我们得到了定理3从而能更方便地让我们估计筛函数的上下界。

  虽然本文中得到的公式都是抽象的，但这仅仅是为了后面的精彩内容做铺垫。通过对\chi_v进行特别的设计我们就可以把定理3变成具体的筛法问题从而用来解决数论问题。敬请期待本系列的新文章！