2. Brun 筛法

2.1符号定义

沿用前一节中定义的符号, 可知:

$$S(\mathcal{A},\mathcal{P},z)=\#\{a\in \mathcal{A}:p\nmid a,\forall p\in \mathcal{P}\cap [2,z)\},$$(2.1)

很明显当 $P(z)$ 表示全体 $\mathcal{P}\cap [2,z)$ 元素的乘积时 (2.1) 就可以化成:

$$S(\mathcal{A},\mathcal{P},z)=\sum _{\begin{array}{c}a\in \mathcal{A}\\ (a,P(z))=1\end{array}}1.$$

利用 Möbius 反演可知:

$$S(\mathcal{A},\mathcal{P},z)=\sum _{d|P(z)}\mu (d)|{\mathcal{A}}_d|,$$(2.2)

因此在估计 $S(\mathcal{A},\mathcal{P},z)$ 时我们需要对 $|{\mathcal{A}}_d|$ 的大小有一定的了解. 一般来讲我们会要求其满足如下性质:

命题 2.1.1. 存在 $X>0$ 和积性函数 $g(d)$ 使得: $$|{\mathcal{A}}_d|=g(d)X+r(d)$$其中当 $p$ 为素数时 $0<g(p)<1$.

注 2.1.2. 在本讲义的后续章节中我们都会默认 $\mathcal{A}$ 满足这条性质.

将这个渐近公式回代至 (2.2) 中, 便有:

$$S(\mathcal{A},\mathcal{P},z)=XV(z)+\sum _{d|P(z)}\mu (d)r(d),$$

其中 $V(z)$ 表示下列乘积:

$$V(z)=\sum _{d|P(z)}\mu (d)g(d)=\prod _{p|P(z)}(1-g(p)).$$

利用这一点, 我们就得到了著名的 Eratosthenes 筛法:

定理 2.1.3 (Eratosthenes–Legendre). 当 ${\mathcal{A}}_d$ 满足命题 2.1.1 时, 总存在 $-1\le \theta \le 1$ 使得: $$S(\mathcal{A},\mathcal{P},z)=XV(z)+\theta \sum _{d|P(z)}|r(d)|.$$

然而 $z$ 较大时 Eratosthenes 筛法中产生的误差项通常以指数形式增长, 所以这个时候我们就需要引入一些高级工具来处理这个问题.

2.2上下界的构造

我们连续使用两次 Buchstab 迭代式, 可知:

$$S(\mathcal{A},\mathcal{P},z)=|\mathcal{A}|-\sum _{p_1<z}|{\mathcal{A}}_{p_1}|+\underset{p_1>p_2}{\sum _{p_1<z}\sum _{p_2<z}}S({\mathcal{A}}_{p_1{p}_2},\mathcal{P},p_2).$$(2.3)

通过在 (2.3) 上动手脚, 我们就可以构造出上下界.

下界筛

如果我们设 $z_1\le z$ 并要求 (2.3) 中的 $p_2<z_1$, 则有:

$$S(\mathcal{A},\mathcal{P},z)\ge |\mathcal{A}|-\sum _{p_1<z}|{\mathcal{A}}_{p_1}|+\underset{p_1>p_2}{\sum _{p_1<z}\sum _{p_2<z_1}}S({\mathcal{A}}_{p_1{p}_2},\mathcal{P},p_2),$$

反复使用该公式就能发现当 $z\ge z_1\ge z_2\ge \cdots \ge z_n$ 时总有:

$$\begin{array}{rl}& S(\mathcal{A},\mathcal{P},z)\ge |\mathcal{A}|-\sum _{p_1<z}|{\mathcal{A}}_{p_1}|+\underset{p_1>p_2}{\sum _{p_1<z}\sum _{p_2<z_1}}|{\mathcal{A}}_{p_1{p}_2}|\\ & -\underset{p_1>p_2>p_3}{\sum _{p_1<z}\sum _{p_2<z_1}\sum _{p_3<z_1}}|{\mathcal{A}}_{p_1{p}_2{p}_3}|+\cdots +\underset{p_1>p_2>\cdots >p_{2n}}{\sum _{p_1<z}\sum _{p_2<z_1}\cdots \sum _{p_{2n}<z_n}}|{\mathcal{A}}_{p_1{p}_2\cdots p_{2n}}|\\ & -\underset{p_1>p_2>\cdots >p_{2n}>p_{2n+1}}{\sum _{p_1<z}\sum _{p_2<z_1}\cdots \sum _{p_{2n}<z_n}\sum _{p_{2n+1}<z_n}}|{\mathcal{A}}_{p_1{p}_2\cdots p_{2n}{p}_{2n+1}}|=\sum _{\begin{array}{c}d|P(z)\\ d\in {\mathcal{D}}^{-}\end{array}}\mu (d)|{\mathcal{A}}_d|,\end{array}$$

其中 ${\mathcal{D}}^{-}$ 表示满足下列条件的 $d$:

$$d=p_1{p}_2\cdots p_m,p_1>p_2>\cdots >p_m,p_{2k}<z_k,1\le k\le \frac{m}{2}.$$(2.4)

上界筛

对 (2.3) 再做一次迭代, 就可以发现当 $z_1\le z$ 时总有:

$$\begin{array}{rl}S(\mathcal{A},\mathcal{P},z)& \le |\mathcal{A}|-\sum _{p_1<z}|{\mathcal{A}}_{p_1}|+\underset{p_1>p_2}{\sum _{p_1<z}\sum _{p_2<z}}|{\mathcal{A}}_{p_1{p}_2}|\\ & -\underset{p_1>p_2>p_3}{\sum _{p_1<z}\sum _{p_2<z}\sum _{p_3<z_1}}S({\mathcal{A}}_{p_1{p}_2{p}_3},\mathcal{P},p_3).\end{array}$$

迭代使用这个不等式, 便得:

$$\begin{array}{rl}& S(\mathcal{A},\mathcal{P},z)\le |\mathcal{A}|-\sum _{p_1<z}|{\mathcal{A}}_{p_1}|+\underset{p_1>p_2}{\sum _{p_1<z}\sum _{p_2<z}}|{\mathcal{A}}_{p_1{p}_2}|\\ & -\underset{p_1>p_2>p_3}{\sum _{p_1<z}\sum _{p_2<z}\sum _{p_3<z_1}}|{\mathcal{A}}_{p_1{p}_2{p}_3}|+\cdots -\underset{p_1>p_2>\cdots >p_{2n-1}}{\sum _{p_1<z}\sum _{p_2<z}\cdots \sum _{p_{2n+1}<z_n}}|{\mathcal{A}}_{p_1{p}_2\cdots p_{2n+1}}|\\ & +\underset{p_1>p_2>\cdots >p_{2n}>p_{2n+2}}{\sum _{p_1<z}\sum _{p_2<z}\cdots \sum _{p_{2n+1}<z_n}\sum _{p_{2n+2}<z_n}}|{\mathcal{A}}_{p_1{p}_2\cdots p_{2n}{p}_{2n+1}}|=\sum _{\begin{array}{c}d|P(z)\\ d\in {\mathcal{D}}^{+}\end{array}}\mu (d)|{\mathcal{A}}_d|,\end{array}$$

其中 $d\in {\mathcal{D}}^{+}$ 当且仅当:

$$d=p_1{p}_2\cdots p_m,p_1>p_2>\cdots >p_m,p_{2k+1}<z_k,1\le k\le \frac{m-1}{2}.$$(2.5)

上下界的统一

为了方便起见, 我们定义 ${\chi }_0$ 为集合 ${\mathcal{D}}^{-}$ 的特征函数并让 ${\chi }_1$ 为 ${\mathcal{D}}^{+}$ 的特征函数, 则根据 (2.4) 和 (2.5) 可知当 $v=0,1$ 时 ${\chi }_v(d)=1$ 当且仅当:

$$d=p_1\cdots p_m,p_1>\cdots >p_m,p_{2k+v}<z_k,1\le k\le \min \left(n,\frac{m-v}{2}\right),$$(2.6)

因此当我们定义:

$$S_v(\mathcal{A},\mathcal{P},z)=\sum _{d|P(z)}\mu (d){\chi }_v(d)|{\mathcal{A}}_d|$$(2.7)

时总有:

$$S_0(\mathcal{A},\mathcal{P},z)\le S(\mathcal{A},\mathcal{P},z)\le S_1(\mathcal{A},\mathcal{P},z).$$(2.8)

至此我们的任务就变成了估计 $S_v(\mathcal{A},\mathcal{P},z)$ 的大小了.

注 2.2.1. 事实上将 (2.8) 的左侧下标更换成任意非负偶数、右侧下标更换成任意正奇数时依然成立.

2.3$S_v(\mathcal{A},\mathcal{P},z)$ 的估计

当 $|{\mathcal{A}}_d|$ 满足命题 2.1.1 时, 可知存在 $-1\le \theta \le 1$ 使:

$$S_v(\mathcal{A},\mathcal{P},z)=X\underset{Q_v(z)}{\underbrace{\sum _{d|P(z)}\mu (d){\chi }_v(d)g(d)}}+\theta \underset{R_v(z)}{\underbrace{\sum _{d|P(z)}{\chi }_v(d)|r(d)|}},$$(2.9)

其中通过精确地处理, $Q_v(z)$ 将成为 $S_v(\mathcal{A},\mathcal{P},z)$ 的主项而通过放缩 $R_v(z)$ 会成为 $S_v(\mathcal{A},\mathcal{P},z)$ 的余项.

$Q_v(z)$ 的初步处理

从 $Q_v(z)$ 的构造来看, 我们期待它最终能近似 $V(z)$, 所以我们不妨先做一次分离, 得:

$$Q_v(z)=V(z)-\sum _{d|P(z)}\mu (d)[1-{\chi }_v(d)]g(d).$$

结合 (2.8), 可知:

$$\begin{array}{rl}\sum _{d|P(z)}\mu (d)[1-{\chi }_v(d)]g(d)& =\sum _{1\le k\le n}\sum _{\begin{array}{c}{p}_1>\cdots >p_{2k+v}\ge z_k\\ z_k>p_{2k+v+1}>\cdots >p_m\\ p_{2\ell +v}<z_{\ell },1\le \ell \le k\end{array}}\mu (p_1\cdots p_m)g(p_1\cdots p_m)\\ & =\sum _{1\le k\le n}\sum _{\begin{array}{c}{p}_1>\cdots >p_{2k+v}\ge z_k\\ p_{2\ell +v}<z_{\ell },1\le \ell \le k\end{array}}\mu (p_1\cdots p_{2k+v})g(p_1\cdots p_{2k+v})\sum _{\delta |P(z_k)}\mu (\delta )g(\delta )\\ & =(-1{)}^v\sum _{1\le k\le n}V(z_k)\sum _{\begin{array}{c}{p}_1>\cdots >p_{2k+v}\ge z_k\\ p_{2\ell +v}<z_{\ell },1\le \ell \le k\end{array}}g(p_1\cdots p_{2k+v})\\ & =(-1{)}^{v}V(z){\Delta }_v(z),\end{array}$$

其中 ${\Delta }_v(z)$ 满足:

$${\Delta }_v(z)\le \sum _{1\le k\le n}\frac{V(z_k)}{V(z)}\frac{1}{(2k+v)!}{\left(\sum _{z_k\le p<z}g(p)\right)}^{2k+v}.$$

由于当 $0\le y<1$ 时:

$$y\le y+\frac{y^2}{2}+\frac{y^3}{3}+\cdots =\log (1-y{)}^{-1},$$

所以当 $L_k=\log [V(z_k)/V(z)]$ 时总有:

$${\Delta }_v(z)\le \sum _{1\le m\le n}\frac{e^{L_m}{L}_m^{2m+v}}{(2m+v)!}.$$(2.10)

条件 $\Omega (\kappa )$ 与 $z_m$ 的设置

为了继续估计 ${\Delta }_v(z)$, 我们有必要对 $g(d)$ 做更多的要求.

定义 2.3.1 ($\Omega (\kappa )$). 存在常数 $A>0$ 使得 $2\le w<z$ 时总有: $$\prod _{w\le p<z}(1-g(p){)}^{-1}\le {\left(\frac{\log z}{\log w}\right)}^{\kappa }\left(1+\frac{A}{\log z}\right).$$

因此有:

$$L_m\le \kappa \log \frac{\log z}{\log z_m}+\frac{A}{\log z_m}.$$(2.11)

为了让 $L_m$ 最终能够有一个不受制于 $z$ 的上界, Brun 构造了这种形式的 $z_m$:

$$\log z_m=e^{-m\Lambda }\log z,1\le m\le n,$$(2.12)

其中 $\Lambda$ 是一个固定的正实数. 另一方面我们要求 $n$ 足够大使得 $z_n\le 2<z_{n-1}$, 换言之:

$$e^{(n-1)\Lambda }<\frac{\log z}{\log 2}\le e^{n\Lambda }.$$(2.13)

$Q_v(z)$ 的展开式

将 (2.12) 代入到 (2.11) 中, 便有:

$$\begin{array}{rl}{L}_m& \le m\Lambda \kappa +\frac{A{e}^{m\Lambda }}{\log z}\\ & =m\Lambda \kappa \left(1+\frac{e^{m\Lambda }-1}{m\Lambda }\frac{A}{\kappa \log z}\right)+\frac{A}{\log z},\end{array}$$

由于

$$\frac{e^y-1}{y}=\sum _{m\ge 1}\frac{y^{m-1}}{m!}$$

是单调递增函数, 所以根据 (2.13), 可知:

$$\begin{array}{rl}{L}_m& \le m\Lambda \kappa \left(1+\frac{e^{n\Lambda }-1}{n\Lambda }\frac{A}{\kappa \log z}\right)+\frac{A}{\log z}\\ & <m\Lambda \kappa \left(1+\frac{e^{(n-1)\Lambda }}{n\Lambda }\frac{A{e}^{\Lambda }}{\kappa \log z}\right)+\frac{A}{\log z}\\ & <m\Lambda \kappa \left(1+\frac{A_1}{\log \log z}\right)+\frac{A}{\log z}.\end{array}$$

这意味着对于所有的 $\epsilon >0$, 均存在 $Z>0$ 使得当 $z>Z$ 时总有:

$$L_m<m\underset{\tau }{\underbrace{\Lambda \kappa (1+\epsilon )}}+\frac{A}{\log z}.$$(2.14)

现在将 (2.14) 代入到 (2.10), 即得:

$$\begin{array}{rl}{\Delta }_v(z)& <\sum _{1\le m\le n}\frac{e^{m\tau }}{(2m+v)!}{\left(m\tau +\frac{A}{\log z}\right)}^{2m+v}{e}^{A/\log z}\\ & =\sum _{1\le m\le n}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!}{\left(1+\frac{A}{m\tau \log z}\right)}^{2m+v}{e}^{A/\log z}\\ & <\sum _{1\le m\le n}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!}\exp \left\{\frac{2m+v}{m}\frac{A}{\tau \log z}+\frac{A}{\log z}\right\}\\ & \le \sum _{1\le m\le n}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!}\left\{1+O\left(\frac{1}{\log z}\right)\right\}.\end{array}$$

我们不难看出当 $r_m$ 表示上述和式的第 $m+1$ 项除以第 $m$ 项的商时, 有:

$$r_m\sim \frac{e^{\tau }}{4m^2}{\left\{\frac{(m+1)\tau }{m\tau }\right\}}^{2m}[(m+1)\tau {]}^2\sim \frac{{\tau }^2}{4}{e}^{2+\tau },$$

因此当 $\frac{1}{4}{\tau }^2{e}^{2+\tau }<1$ 时可知当 $z$ 充分大时便有:

$$\begin{array}{rl}{\Delta }_v(z)& <\sum _{1\le m\le n}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!}+O\left(\frac{1}{\log z}\right)\\ & <\sum _{m\ge 1}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!}.\end{array}$$

综上所述我们就得到了结论:

引理 2.3.2. 对于每个充分大的 $z$, 总存在 $-1\le \theta \le 1$ 使得: $$\frac{Q_v(z)}{V(z)}=1+\theta \sum _{m\ge 1}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!},$$其中 $v$ 为非负整数, 正实数 $\tau$ 满足: $$0<\frac{{\tau }^2}{4}{e}^{2+\tau }<1.$$

接下来就只需要估计 $R_v(z)$ 的上界了.

$R_v(z)$ 的上界估计

为了灵活性, 我们并不打算像 $g(d)$ 一样给 $r(d)$ 增添限制条件. 所以在本节中我们只会估计这个和式:

$$M_v(z;f)=\sum _{d|P(z)}{\chi }_v(d)f(d),$$(2.15)

其中 $f(d)$ 为一个积性函数. 因此根据 (2.6), 可知 $v\ge 0$ 时总有:

$$M_v(z;f)\le {\left(1+\sum _{p<z}f(p)\right)}^{1+v}\prod _{1\le m<n}{\left(1+\sum _{p<z_m}f(p)\right)}^2.$$(2.16)

在很多应用场景中 $f(p)$ 通常是有界的, 所以此时我们可以追加条件, 即存在 $B>0$ 使 $y\ge 2$ 时总有:

$$1+\sum _{p<y}f(p)\le \frac{By}{\log y}.$$

将这个条件代入到 (2.16) 中, 便可发现 $z$ 充分大时:

$$\begin{array}{rl}{M}_v(z;f)& <z^{1+v}\prod _{1\le m<n}{\left(\frac{B{z}_m}{\log z_m}\right)}^2\\ & <z^{1+v+2(e^{-\Lambda }+e^{-2\Lambda }+\cdots )}\prod _{1\le m<n}{\left(\frac{B{e}^{m\Lambda }}{\log z}\right)}^2\\ & =z^{1+v+\frac{2}{e^{\Lambda }-1}}{e}^{n(n-1)\Lambda }\prod _{1\le m<n}{\left(\frac{B}{\log z}\right)}^2\\ & =z^{1+v+\frac{2}{e^{\Lambda }-1}}{\left(\frac{B{e}^{n\Lambda /2}}{\log z}\right)}^{2(n-1)}.\end{array}$$

现在根据 (2.13), 可知:

$$\frac{e^{n\Lambda /2}}{\log z}<\frac{e^{\Lambda /2}}{\sqrt{\log z\log 2}},$$

另一方面根据 (2.14) 我们知道存在 ${\epsilon }^{\prime }>0$ 使得:

$$\frac{2}{e^{\Lambda }-1}=\frac{2}{e^{\tau /\kappa }-1}+{\epsilon }^{\prime }.$$

将这些结论结合起来, 我们就得到了用于估计 $R_v(z)$ 的辅助工具:

引理 2.3.3. 倘若积性函数 $f(d)$ 满足: $$\sum _{p<z}f(p)=O\left(\frac{z}{\log z}\right),$$则对于所有的 $\epsilon >0$, 当 $z$ 充分大时总有: $$\sum _{d|P(z)}{\chi }_v(d)f(d)<z^{1+v+\frac{2}{e^{\tau /\kappa }-1}+\epsilon }.$$

2.4结论

现将引理 2.3.2 和 (2.9) 相结合, 就有:

定理 2.4.1 (Brun). 若特征函数 ${\chi }_v(d)=1$ 当且仅当 $d$ 满足 (2.6), 且$$R_v(z)=\sum _{d|P(z)}{\chi }_v(d)|r(d)|,$$$${\eta }_v(\tau )=\sum _{m\ge 1}\frac{e^{m\tau }(m\tau {)}^{2m+v}}{(2m+v)!},$$则当 $\mathcal{A}$ 满足命题 2.1.1 和 $\Omega (\kappa )$, 正数 $\tau$ 满足 $0<{\tau }^2{e}^{2+\tau }<4$, $v_1$ 为正奇数, $v_2$ 为非负偶数时$$S(\mathcal{A},\mathcal{P},z)<XV(z)[1+{\eta }_{v_1}(\tau )]+R_{v_2}(z),$$$$S(\mathcal{A},\mathcal{P},z)>XV(z)[1-{\eta }_{v_2}(\tau )]-R_{v_2}(z)$$对所有充分大的 $z$ 均成立.