Rosser–Iwaniecの篩

同義語:Rosser-Iwaniecの篩Rosserの篩ベータ篩Rosser–Iwaniec sieveRosser's sievebeta sieve

概要

Rosser–Iwaniecの篩(Rosser–Iwaniec sieve)とは、ベータ篩ともよばれる組合せ的な篩で、包除の和 $\sum\mu(d)\lvert\mathcal A_d\rvert$ を、素因数を大きい順に $p_1>\dots>p_r$ と並べた約数のうち、奇数番目(上界)または偶数番目(下界)の各段で $p_1\cdots p_{m-1}p_m^{\beta+1}\le D$ を満たすものに打ち切る。$\beta\ge1$ なら上界で使う約数は $D$ 以下に収まり、打ち切った和は篩った個数の上界・下界になる。$\beta=2$ の線形の篩では主要項が遅延微分方程式の解 $F,f$ で与えられ、Bombieri–Vinogradov の定理と合わせると双子素数の個数の上界 $\pi_2(x)\le(4+o(1))\Pi(x)$ が得られる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 篩法, Möbius関数, Mertensの定理

Rosser–Iwaniecの篩(Rosser–Iwaniec sieve)は、ベータ篩(beta sieve)ともよばれる組合せ的な篩である。篩法 の基本である包除の和 $\sum_{d\mid P(z)}\mu(d)\lvert\mathcal A_d\rvert$ を、約数 $d$ の素因数を大きい順に $p_1>p_2>\dots>p_r$ と並べたとき、奇数番目(上界の場合)または偶数番目(下界の場合)の各段で
$$ p_1\cdots p_{m-1}\,p_m^{\beta+1}\le D $$
が成り立つ $d$ だけに打ち切る。$D$ は重みの水準、$\beta\ge1$ はパラメータである。打ち切った和は篩った個数の上界・下界を与え(thm-ri-basic)、上界で使う約数はすべて $D$ 以下で、下界で使う約数は $D$ 以下か $z$ 未満の素数である(prop-ri-level)。
この篩は Iwaniec(Iwa80、題は「Rosser's sieve」)による。$\beta=2$ の場合が 線形の篩(次元 1 の篩)で、上界と下界の主要項は遅延微分方程式で定まる関数 $F,f$ で与えられる(Lich25 p. 1、thm-ri-linear)。この上界・下界は Jurkat–Richert の定理ともよばれる(JR65、Lich25 p. 15)。
この記事では、重みを定義し、篩の不等式の組合せ的な核心(thm-ri-basic)と水準の性質を完全に証明する。主要項の展開を示したうえで線形の場合の定理を引用し、応用として双子素数の個数の上界 $\pi_2(x)\le(4+o(1))\Pi(x)$ を導く。

篩の設定

$\mathcal A$ を正の整数の有限列(重複を許す)、$\mathcal P$ を素数の集合、$z\ge2$ とし、$P(z):=\prod_{p\in\mathcal P,\ p< z}p$ とおく。$d\mid P(z)$ について $\lvert\mathcal A_d\rvert$ を $\mathcal A$ の項のうち $d$ で割り切れるものの個数とし、
$$ S(\mathcal A,z):=\#\{a\in\mathcal A:\gcd(a,P(z))=1\} $$
とする。乗法的関数 $g$ を $0\le g(p)< 1$($p\in\mathcal P$)となるようにとり、$X>0$ を固定して $r(d):=\lvert\mathcal A_d\rvert-Xg(d)$ とおく。$X g(d)$ は $d$ で割り切れる項の個数の近似で、$r(d)$ はその誤差である。$w>0$ について
$$ V(w):=\prod_{p\in\mathcal P,\ p< w}\bigl(1-g(p)\bigr) $$
とおく。$V(z)$ は「$X$ 個のうち篩に残る割合」の期待値にあたる。

定義

ベータ篩の重み

$D\ge1$、$\beta\ge1$ とする。$1< d\mid P(z)$ を $d=p_1p_2\cdots p_r$($p_1>p_2>\dots>p_r$)と書く。

  • $\mathcal D^+$ は、$1$ と、すべての 奇数 $m\le r$ について $p_1\cdots p_{m-1}p_m^{\beta+1}\le D$ を満たす $d$ の集合である。
  • $\mathcal D^-$ は、$1$ と、すべての 偶数 $m\le r$ について同じ不等式を満たす $d$ の集合である。
    $d\mid P(z)$ について $\lambda^\pm(d):=\mu(d)$($d\in\mathcal D^\pm$)、$\lambda^\pm(d):=0$($d\notin\mathcal D^\pm$)とおき、$\lambda^+$ を上界の重み、$\lambda^-$ を下界の重みという。

$d>1$ の最小の素因数を $p(d)$ と書く($p(d)=p_r$)。$\mathcal D$ を $\mathcal D^+$ か $\mathcal D^-$ とし、$d\notin\mathcal D$ かつ $d/p(d)\in\mathcal D$ となる $d\mid P(z)$ の集合を 境界 $\mathcal B^\pm$ とよぶ。$\beta=2$ のとき $\mathcal D^\pm$ は、Lich25 (3.1)(p. 9)の集合のうち $P(z)$ の約数であるものと一致する($\mathcal D^-$ については $z\le D^{1/2}$ のとき)。

境界の素因数の個数の偶奇

(i) $1< d\in\mathcal D^\pm$ なら $d/p(d)\in\mathcal D^\pm$ である。
(ii) $d=p_1\cdots p_r\in\mathcal B^+$ なら $r$ は奇数、$d\in\mathcal B^-$ なら $r$ は偶数である。

(i) $d/p(d)=p_1\cdots p_{r-1}$ に課される不等式は、$d$ に課される不等式のうち $m\le r-1$ のものだけで、すべて成り立っている。
(ii) $d\in\mathcal B^+$ とする。$r$ が偶数なら、$d$ に課される不等式は奇数 $m\le r-1$ のものだけで、これは $d/p(d)\in\mathcal D^+$ の条件と同じだから $d\in\mathcal D^+$ となり、$d\notin\mathcal D^+$ に反する。よって $r$ は奇数である。$\mathcal B^-$ も同様である。$\square$

篩の不等式

基本不等式

$h$ を $0\le h(p)\le1$($p\in\mathcal P$)を満たす乗法的関数とする。すべての $n\mid P(z)$ について
$$ \sum_{d\mid n}\lambda^\pm(d)h(d)=\prod_{p\mid n}\bigl(1-h(p)\bigr)\pm\sum_{\substack{d\mid n\\ d\in\mathcal B^\pm}}h(d)\prod_{\substack{p\mid n\\ p< p(d)}}\bigl(1-h(p)\bigr) $$
(複号同順)が成り立つ。右辺の第 2 項の和は $0$ 以上なので
$$ \sum_{d\mid n}\lambda^-(d)h(d)\le\prod_{p\mid n}\bigl(1-h(p)\bigr)\le\sum_{d\mid n}\lambda^+(d)h(d) $$
である。

最初に外れる段で分類する

$\mathcal D=\mathcal D^\pm$、$\mathcal B=\mathcal B^\pm$ とする。$n$ の約数全体の和は $\sum_{e\mid n}\mu(e)h(e)=\prod_{p\mid n}(1-h(p))$ なので、$e\notin\mathcal D$ である約数 $e\mid n$ の和
$$ \Sigma:=\sum_{\substack{e\mid n\\ e\notin\mathcal D}}\mu(e)h(e) $$
を求めればよい。$e=q_1\cdots q_k$($q_1>\dots>q_k$)$\notin\mathcal D$ について、$q_1\cdots q_l\notin\mathcal D$ となる最小の $l$ をとる($1\in\mathcal D$ なので $l\ge1$)。$d:=q_1\cdots q_l$ は最小性から $d/p(d)\in\mathcal D$ を満たし、$d\in\mathcal B$ である。$e=de'$ で、$e'$ は $n$ の約数のうち素因数がすべて $p(d)$ より小さいものである。
逆に、$d\in\mathcal B$、$d\mid n$ と、素因数がすべて $p(d)$ より小さい $e'\mid n$ をとると、$e:=de'$ の素因数を大きい順に並べた最初の $l$ 個は $d$ そのものである。$d$ の真の先頭部分は (i) の繰り返しにより $\mathcal D$ に属し、$d\notin\mathcal D$ だから、$e$ から上の手順で得られるのは $d$ である($\mathcal D$ の定義は先頭部分の条件の積み重ねなので、$d\notin\mathcal D$ なら $e\notin\mathcal D$)。よって $e\leftrightarrow(d,e')$ は全単射で、$\mu$ と $h$ の乗法性から
$$ \Sigma=\sum_{\substack{d\mid n\\ d\in\mathcal B}}\mu(d)h(d)\sum_{\substack{e'\mid n\\ p\mid e'\Rightarrow p< p(d)}}\mu(e')h(e')=\sum_{\substack{d\mid n\\ d\in\mathcal B}}\mu(d)h(d)\prod_{\substack{p\mid n\\ p< p(d)}}\bigl(1-h(p)\bigr) $$
である。lem-ri-boundary (ii) から、$\mathcal B^+$ では $\mu(d)=-1$、$\mathcal B^-$ では $\mu(d)=1$ である。$\sum_{d\mid n,\,d\in\mathcal D}\mu(d)h(d)=\prod_{p\mid n}(1-h(p))-\Sigma$ に代入すれば主張の等式を得る。$h(p)\le1$ なので第 2 項の各項は $0$ 以上である。$\square$

この証明は Lich25 Lemma 4.3(p. 15)の議論(最小の添字が奇数になることを使う)と同じ筋である。

篩った個数の上界と下界

$V^\pm:=\sum_{d\mid P(z)}\lambda^\pm(d)g(d)$ とおくと、$V^\pm=V(z)\pm\sum_{d\in\mathcal B^\pm}g(d)V(p(d))$(複号同順)で、
$$ XV^-+\sum_{d\mid P(z)}\lambda^-(d)r(d)\le S(\mathcal A,z)\le XV^++\sum_{d\mid P(z)}\lambda^+(d)r(d),\qquad V^-\le V(z)\le V^+ $$
が成り立つ。

$h\equiv1$(すべての $p$ で $h(p)=1$)として thm-ri-basic を $n=\gcd(a,P(z))$($a\in\mathcal A$)に当てると、$\prod_{p\mid n}(1-1)$ は $n=1$ のとき $1$、それ以外で $0$ なので
$$ \sum_{d\mid\gcd(a,P(z))}\lambda^-(d)\le[\gcd(a,P(z))=1]\le\sum_{d\mid\gcd(a,P(z))}\lambda^+(d) $$
である。$a\in\mathcal A$ について足すと、$d$ の和と $a$ の和を入れ替えて $\sum_{d\mid P(z)}\lambda^\pm(d)\lvert\mathcal A_d\rvert$ が現れ、$\lvert\mathcal A_d\rvert=Xg(d)+r(d)$ を代入すると不等式を得る。$V^\pm$ の式は thm-ri-basic を $h=g$、$n=P(z)$ に当てたもので、$\prod_{p\mid P(z),\,p< p(d)}(1-g(p))=V(p(d))$ である。$\square$

水準

重みの水準

$\beta\ge1$ とする。$d\in\mathcal D^+$ なら $d\le D$ である。$d\in\mathcal D^-$ なら、$d\le D$ であるか、$d$ は $z$ 未満の素数である。

$d=p_1\cdots p_r\in\mathcal D^+$、$r\ge1$ とする。$r$ が奇数なら $m=r$ の不等式から $d\le p_1\cdots p_{r-1}p_r^{\beta+1}\le D$ である。$r$ が偶数なら $m=r-1$ は奇数で、$p_r< p_{r-1}$ と $\beta\ge1$ から
$$ d=p_1\cdots p_{r-1}p_r< p_1\cdots p_{r-2}\,p_{r-1}^2\le p_1\cdots p_{r-2}\,p_{r-1}^{\beta+1}\le D $$
である。$\mathcal D^-$ では、$r$ が偶数なら $m=r$ の不等式、$r\ge3$ が奇数なら $m=r-1$ の不等式から同じく $d\le D$ で、残りは $r=1$、つまり $z$ 未満の素数である。$\square$

したがって cor-ri-sieve の誤差の項は $d\le D$(下界では $d\le\max(D,z)$)の $r(d)$ だけを含み、$\lvert\lambda^\pm(d)\rvert\le1$ である。$D$ を $\mathcal A$ の算術級数での分布が分かる範囲にとれば、誤差の項を小さくできる。

主要項の展開

cor-ri-sieve の $V^+-V(z)=\sum_{d\in\mathcal B^+}g(d)V(p(d))$ は、境界の約数を素因数の個数 $r$(奇数)ごとに分けて評価する。$r=1$ の部分は正確に計算できる。

境界の最初の項

$\beta=2$ とする。$\mathcal B^+$ の素数は $D^{1/3}< p< z$ を満たす $p\in\mathcal P$ で、$D^{1/3}< z$ のとき
$$ \sum_{\substack{p\in\mathcal P\\ D^{1/3}< p< z}}g(p)V(p)=\prod_{\substack{p\in\mathcal P\\ p\le D^{1/3}}}\bigl(1-g(p)\bigr)-V(z) $$
である。

素数 $p$ が $\mathcal D^+$ に属する条件は $m=1$ の $p^3\le D$ だけで、$1\in\mathcal D^+$ だから、$\mathcal B^+$ の素数は $p^3>D$ の $p$ である。$V(p)-g(p)V(p)=V(p)(1-g(p))$ は $p$ 以下の $\mathcal P$ の素数にわたる積なので、$g(p)V(p)$ は $\mathcal P$ の相続く素数での積の差であり、和は望遠鏡のように消えて右辺になる。$\square$

次元 1 の条件

$g$ が 次元 1 の条件 を満たすとは、$2\le w\le z$ について
$$ \frac{V(w)}{V(z)}=\prod_{\substack{p\in\mathcal P\\ w\le p< z}}\bigl(1-g(p)\bigr)^{-1}=\frac{\log z}{\log w}\Bigl(1+O\Bigl(\frac1{\log w}\Bigr)\Bigr) $$
が成り立つことをいう($O$ の定数は $w,z$ によらない)。各素数で割り切れる割合が平均して $1/p$ 程度であることを表す(Lich25 (2.3)、p. 8)。

$g$ が def-ri-dim1 を満たすとき、$s:=\log D/\log z\in[1,3]$ について prop-ri-first の和は $V(z)\bigl(\frac3s-1+O(\frac1{\log D})\bigr)$ である。BJS25 (13)–(15)(p. 6)は $F(s)=1+\sum_{n\text{ 奇数}}f_n(s)$、$sf_1(s)=3-s$($1\le s\le3$)と書いている。ここで計算した $r=1$ の項の係数 $\frac3s-1$ は $f_1(s)$ と一致する。

線形の篩

関数 $F,f:(0,\infty)\to\mathbb R$ を
$$ sF(s)=2e^\gamma\ (0< s\le3),\qquad sf(s)=0\ (0< s\le2),\qquad (sF(s))'=f(s-1)\ (s>3),\qquad (sf(s))'=F(s-1)\ (s>2) $$
で定める(Lich25 (2.5)、p. 8)。$\gamma$ は Eulerの定数 である。

線形の篩の上界(引用)

$g$ が def-ri-dim1 を満たすとし、$\beta=2$ とする。$s\ge1$ を固定し $z=D^{1/s}$ とすると、$D\to\infty$ のとき
$$ S(\mathcal A,z)\le XV(z)\bigl(F(s)+o(1)\bigr)+\sum_{d\mid P(z)}\lambda^+(d)r(d) $$
である(Lich25 (1.1)、p. 1。上界にはこの条件の片側の不等式で足りる:同 Remark 2.9、p. 8)。

下界は、$s\ge2$ について $f(s)$ を使った同じ形で成り立つ。誤差の項を明示した形は Chenの定理 の定理「線形篩(主張)」(BJS25 Theorem 6)にある。この記事ではこの定理を証明しない。$F$ は最良で、ある数列について上界が漸近的に等号になる(Lich25 p. 1)。篩の情報だけでは越えられない限界については パリティ問題(篩法) を参照。

$f$ の最初の区間

$2\le s\le4$ で $f(s)=\dfrac{2e^\gamma\log(s-1)}{s}$ である。とくに $f(s)>0$($2< s\le4$)である。

$2< s\le4$ では $s-1\in(1,3]$ なので $(sf(s))'=F(s-1)=2e^\gamma/(s-1)$ である。$sf(s)$ は $s=2$ で $0$(連続性)なので、積分して $sf(s)=2e^\gamma\log(s-1)$ を得る。$\square$

$f(s)=0$($s\le2$)は、$z\ge D^{1/2}$ では下界が何も与えないことを表す。数値は次のとおりである($F$ の $s=4,5,6$ と $f$ の $s=5,6$ は方程式を数値積分した値で、小数第 4 位に丸めた)。

$s$$1$$2$$3$$4$$5$$6$
$F(s)$$3.5621$$1.7811$$1.1874$$1.0216$$1.0017$$1.0001$
$f(s)$$0$$0$$0.8230$$0.9784$$0.9982$$0.9999$
一般の次元とよく分解できる重み

次元が $1$ 以外の篩への一般化もある(Lich25 p. 1 は線形の篩を $\beta=2$ のベータ篩として扱い、一般の $\beta$ の篩に触れている)。$\lambda^+$ そのものは、Bombieri–Friedlander–Iwaniecの定理 の意味でよく分解できる重みではないが、Iwaniec は主要項を変えずにそうなるように重みを少し変えた(Iwa80b、Lich25 p. 2 と Theorem 2.10、p. 8)。

応用:双子素数の上界

$\pi_2(x)$ を $p+2$ も素数である素数 $p\le x$ の個数とし、
$$ \Pi(x):=\frac{2C_2\,x}{(\log x)^2},\qquad C_2:=\prod_{p>2}\Bigl(1-\frac1{(p-1)^2}\Bigr) $$
とおく(Lich25 (1.5)、p. 3。$1-\frac1{(p-1)^2}=\frac{1-2/p}{(1-1/p)^2}$)。Hardy–Littlewood の予想は $\pi_2(x)\sim\Pi(x)$ である(双子素数予想)。

線形の篩による双子素数の上界

$x\to\infty$ のとき $\pi_2(x)\le\bigl(4+o(1)\bigr)\Pi(x)$ である。

$\mathcal A=(p+2)_{p\le x}$、$\mathcal P$ を奇素数の全体、$X=\pi(x)$、$g(d)=1/\varphi(d)$ とする。奇数 $d\mid P(z)$ について $\lvert\mathcal A_d\rvert=\pi(x;d,-2)$($x$ 以下の素数 $p\equiv-2\pmod d$ の個数)で、$r(d)=\pi(x;d,-2)-\pi(x)/\varphi(d)$ である。
次元 1 の条件の確認. $1-\frac1{p-1}=(1-\frac1p)(1-\frac1{(p-1)^2})$ である。Mertensの定理 の定理「Mertensの第三定理」から $\prod_{w\le p< z}(1-\frac1p)^{-1}=\frac{\log z}{\log w}(1+O(\frac1{\log w}))$ で、$1\le\prod_{p\ge3}(1-\frac1{(p-1)^2})^{-1}< \infty$、$\prod_{p\ge w}(1-\frac1{(p-1)^2})^{-1}=1+O(\frac1w)$ だから def-ri-dim1 が成り立つ。同じ分解と第三定理から
$$ V(z)=\prod_{3\le p< z}\Bigl(1-\frac1{(p-1)^2}\Bigr)\cdot2\prod_{p< z}\Bigl(1-\frac1p\Bigr)=\bigl(1+o(1)\bigr)\frac{2C_2e^{-\gamma}}{\log z} $$
である。
誤差の項. Bombieri–Vinogradovの定理 の $\pi(x)/\varphi(q)$ を主項にした形(May25a (1.2)、p. 2)から、$B$ を十分大きくとり $D:=x^{1/2}(\log x)^{-B}$ とすると
$$ \sum_{q\le D}\max_{\gcd(a,q)=1}\Bigl\lvert\pi(x;q,a)-\frac{\pi(x)}{\varphi(q)}\Bigr\rvert\ll\frac{x}{(\log x)^3} $$
である。$z:=D$($s=1$)とすると、prop-ri-level と $\lvert\lambda^+\rvert\le1$ から $\bigl\lvert\sum_d\lambda^+(d)r(d)\bigr\rvert\le\sum_{d\le D}\lvert r(d)\rvert\ll x(\log x)^{-3}$ である($d$ は奇数なので $\gcd(-2,d)=1$)。
まとめ. thm-ri-linear を $s=1$、$F(1)=2e^\gamma$ で使うと
$$ S(\mathcal A,D)\le\pi(x)\frac{2C_2e^{-\gamma}}{\log D}\bigl(2e^\gamma+o(1)\bigr)+O\Bigl(\frac x{(\log x)^3}\Bigr)=\bigl(1+o(1)\bigr)\frac{8C_2\,x}{(\log x)^2} $$
である。ここで $\log D=(\frac12+o(1))\log x$ と 素数定理 $\pi(x)\sim x/\log x$ を使った。$p+2$ が素数で $p+2\ge D$ なら $p+2$ は $D$ 未満の奇素数で割り切れないので、$\pi_2(x)\le S(\mathcal A,D)+D$ である。$D=o(x/(\log x)^2)$ なので $\pi_2(x)\le(4+o(1))\Pi(x)$ を得る。$\square$

同じ証明で、算術級数での分布を水準 $x^{\theta-\varepsilon}$ まで(重みつきでもよい)示せれば $\pi_2(x)\le(2/\theta+o(1))\Pi(x)$ となる(Lich25 p. 3)。上の $4$ は Bombieri–Davenport の値で、$\theta=4/7$ の $7/2$ は Bombieri–Friedlander–Iwaniecの定理 による(同 p. 3)。

反例

外した仮定例成り立たなくなる結論
$\beta\ge1$(prop-ri-level)$\beta=0$、$D=10$、$z=8$、$d=35$$d\in\mathcal D^+$ なら $d\le D$
打ち切りを def-ri-weights の段ごとの条件にとる(thm-ri-basic)条件を $d\le D$ に替え、$\mathcal P=\{2,3,5\}$、$z=6$、$D=6$、$n=30$、$h\equiv1$上界の不等式 $\sum_{d\mid n}\lambda(d)h(d)\ge\prod_{p\mid n}(1-h(p))$
反例の確かめ

1 行目:$35=7\cdot5$ で、上界の条件は奇数 $m$ の $m=1$ だけ、つまり $7^{\beta+1}=7\le10$ で成り立つ。よって $35\in\mathcal D^+$ だが $35>10$ である。$\beta$ 以外の条件($d\mid P(8)$、素因数の並べ方)は満たしている。
2 行目:$d\mid30$ で $d\le6$ のものは $1,2,3,5,6$ で、$\mu$ の和は $1-1-1-1+1=-1$ である。一方 $\prod_{p\mid30}(1-1)=0$ なので、上界の不等式が成り立たない。$\beta=2$ の $\mathcal D^+$ では $2^3>6$ なので $\mathcal D^+=\{1\}$ で、和は $1\ge0$ である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する