パリティ問題(篩法)

同義語:篩法のパリティ問題parity problem (sieve theory)parity problem in sieve theoryparity barrier

概要

パリティ問題(篩法)(parity problem in sieve theory)とは、合同条件の数え上げ $A_d\approx X/d$ と剰余項の平均の評価だけを使う古典的な篩法が、素因数の個数が偶数の整数と奇数の整数を区別できないという限界のことである。Selberg の例では、Liouville関数 $\lambda$ の値で分けた 2 つの数列が水準 $x^{1-\varepsilon}$ まで同じ篩の情報をもつが、$\sqrt x$ まで篩うと一方には $1$ しか残らず、他方にはほぼすべての素数が残る。このため篩の情報だけでは素数の個数の正の下界も漸近式も得られず、双線形形式の評価などの追加の情報が必要になる。

$$\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}} $$

前提知識: 篩法, Liouville関数, Mertensの定理, 素数定理

篩法の パリティ問題(parity problem in sieve theory)とは、古典的な 篩法 が、素因数の個数が偶数の整数と奇数の整数を区別できないという限界のことである。篩法が使う情報は、数列の項のうち $d$ で割り切れるものの個数 $A_d$ が $Xg(d)$ で近似できること、すなわち剰余項 $r_d=A_d-Xg(d)$ が $d\le D$ について平均して小さいことである。Selberg は、素因数の個数が偶数の整数だけからなる数列と奇数の整数だけからなる数列が、ほとんど同じこの情報をもつことを指摘した。前者は素数を 1 つも含まず、後者はほぼすべての素数を含む。したがって、この情報だけからは素数の個数の正の下界も、漸近式も得られない(FI98b p. 1041、p. 1045、Pin09 p. 381)。
パリティ問題は、篩法の一般的な限界を述べる発見的な原理として語られることが多い。この記事では、Selberg の例そのものを正確に述べて証明し、篩の情報からの上下の評価に越えられない限界があることを示す。次に、この限界が 双子素数予想 や Goldbach予想 への篩法の応用でどう現れるか、どのような追加の情報があれば越えられるかを述べる。

篩の情報

$x\ge4$ とし、$z\ge2$ 以下の素数の積を $P(z)$ とおく。$\{1,\dots,\lfloor x\rfloor\}$ の部分集合 $\mathcal A$ について、篩法 の記号に合わせて
$$ A_d:=\#\{n\in\mathcal A:\ d\mid n\},\qquad S(\mathcal A,z):=\#\{n\in\mathcal A:\ (n,P(z))=1\} $$
とおく。この記事では、密度が $g(d)=1/d$ の場合だけを扱う。

篩の情報の族

$x\ge4$、$z\ge2$、$D\ge1$、$X>0$、$R\ge0$ について、$\{1,\dots,\lfloor x\rfloor\}$ の部分集合 $\mathcal A$ で
$$ \sum_{\substack{d\le D\\ d\mid P(z)}}\Bigl\lvert A_d-\frac Xd\Bigr\rvert\le R $$
を満たすもの全体を $\mathfrak F(x,z,D,X,R)$ と書く。この族の上で
$$ S^-:=\min_{\mathcal A\in\mathfrak F}S(\mathcal A,z),\qquad S^+:=\max_{\mathcal A\in\mathfrak F}S(\mathcal A,z) $$
とおく(族が空でないとき)。

族 $\mathfrak F$ は「水準 $D$ までの合同条件の数え上げが、全体で誤差 $R$ の範囲で $X/d$ に合う」ことだけを知っている状況を表す。篩法がこの情報だけから導く $S(\mathcal A,z)$ の下界は $S^-$ 以下であり、上界は $S^+$ 以上である。篩法 の Legendre の恒等式は $S(\mathcal A,z)=\sum_{d\mid P(z)}\mu(d)A_d$ を与えるが、$d>D$ の $A_d$ はこの情報に含まれないので、そのまま使うことはできない。
$A_d$ が正確に $X/d$ なら、$S(\mathcal A,z)$ の期待値は
$$ XV(z),\qquad V(z):=\prod_{p\le z}\Bigl(1-\frac1p\Bigr) $$
である。Mertensの定理 の第三定理により $V(z)\sim e^{-\gamma}/\log z$($\gamma$ は Euler の定数)である。

Selberg の例

Liouville関数 を $\lambda(n)=(-1)^{\Omega(n)}$($\Omega(n)$ は重複を込めた素因数の個数)とし、$L(y):=\sum_{m\le y}\lambda(m)$ とおく。

Selberg の数列

$$ \mathcal A^+:=\{n\le x:\ \lambda(n)=1\},\qquad\mathcal A^-:=\{n\le x:\ \lambda(n)=-1\} $$
とおく。$\mathcal A^+$ は素因数の個数が偶数の整数、$\mathcal A^-$ は奇数の整数からなる。

合同条件の数え上げ

$d\ge1$ について
$$ A^\pm_d=\frac x{2d}+r^\pm_d,\qquad r^\pm_d=\frac12\Bigl(\Bigl\lfloor\frac xd\Bigr\rfloor-\frac xd\Bigr)\pm\frac12\lambda(d)L\Bigl(\frac xd\Bigr) $$
である。ここで $A^\pm_d$ は $\mathcal A^\pm$ の $A_d$ である。

完全乗法性

$d\mid n$、$n\le x$ となる $n$ は $n=dm$($m\le x/d$)と一意に書ける。$\lambda$ は完全乗法的なので $\lambda(dm)=\lambda(d)\lambda(m)$ である。$\lambda$ の値は $\pm1$ なので、$n\in\mathcal A^\pm$ であることの指示関数は $\frac12(1\pm\lambda(n))$ である。よって
$$ A^\pm_d=\sum_{m\le x/d}\frac{1\pm\lambda(d)\lambda(m)}2=\frac12\Bigl\lfloor\frac xd\Bigr\rfloor\pm\frac12\lambda(d)L\Bigl(\frac xd\Bigr) $$
であり、$\frac12\lfloor x/d\rfloor=\frac x{2d}+\frac12(\lfloor x/d\rfloor-x/d)$ と書けば主張を得る。$\square$

2 つの数列は同じ「大きさ」$X=x/2$ と同じ密度 $g(d)=1/d$ をもち、剰余項は $\lambda(d)L(x/d)$ の符号だけが異なる。

篩った後の個数

$z=\sqrt x$ とする。このとき
$$ S(\mathcal A^+,\sqrt x)=1,\qquad S(\mathcal A^-,\sqrt x)=\pi(x)-\pi(\sqrt x) $$
である($\pi$ は 素数計数関数)。

素因数の大きさ

$n\le x$ が $\sqrt x$ 以下の素数で割り切れないとする。$n$ の素因数はすべて $\sqrt x$ より大きいので、重複を込めて 2 個以上あれば $n>\sqrt x\cdot\sqrt x=x$ となって矛盾する。よって $n=1$ であるか、$n$ は $\sqrt x< n\le x$ の素数である。$\lambda(1)=1$、$\lambda(p)=-1$ なので、前者は $\mathcal A^+$ に、後者は $\mathcal A^-$ に属する。$\square$

期待値 $XV(\sqrt x)$ は $\frac x2\cdot e^{-\gamma}\frac2{\log x}(1+o(1))=e^{-\gamma}\frac x{\log x}(1+o(1))$ である。素数定理 から $\pi(x)-\pi(\sqrt x)\sim x/\log x$ なので
$$ \frac{S(\mathcal A^+,\sqrt x)}{XV(\sqrt x)}\to0,\qquad\frac{S(\mathcal A^-,\sqrt x)}{XV(\sqrt x)}\to e^\gamma=1.781\ldots $$
となる。

剰余項の大きさ

剰余項の平均が小さいことは、$L(y)$ の評価に帰着する。

剰余項の和(引用)

$0<\varepsilon< 1$ と $A>0$ を固定する。$x\to\infty$ のとき
$$ \sum_{d\le x^{1-\varepsilon}}\mu(d)^2\bigl\lvert r^\pm_d\bigr\rvert\ll_{\varepsilon,A}x(\log x)^{-A} $$
である。

剰余項の評価の出典と仕組み

FI98b p. 1045 は、$\mathcal A^+$ の指示関数 $a_n=\frac12(1+\lambda(n))$ が水準 $D=x^{1-\varepsilon}$ で剰余項の仮定 (R)(p. 1043。右辺は $x(\log x)^{-222}$ の定数倍)を満たすと述べている。任意の $A$ についての形は古典的な評価から出る。prop-pp-congruence から仕組みは次のとおりである。
$\frac12\lvert\lfloor x/d\rfloor-x/d\rvert\le\frac12$ なので、第 1 項の和は $D/2=x^{1-\varepsilon}/2$ 以下である。第 2 項は $y=x/d\ge x^\varepsilon$ での $\lvert L(y)\rvert$ の和である。素数定理 と同等な評価 $L(y)=o(y)$(Liouville関数)だけでは $\sum_{d\le D}\lvert L(x/d)\rvert$ は $o(x\log x)$ としか言えず足りない。素数定理の誤差項と同じ形の古典的な評価 $L(y)\ll_A y(\log y)^{-A}$ を使えば、$\sum_{d\le D}\lvert L(x/d)\rvert\ll\sum_{d\le D}\frac xd(\varepsilon\log x)^{-A-1}\ll_\varepsilon x(\log x)^{-A}$ となる。$L(y)\ll_A y(\log y)^{-A}$ は、Riemann ゼータ関数の零点のない領域(Riemannゼータ関数の零点のない領域)から素数定理の誤差項と同じ方法で導かれる古典的な評価であり、この記事では証明しない。

篩の情報から得られる評価の限界

Selberg の例による限界

$0<\varepsilon< 1$、$A>0$ を固定し、$z=\sqrt x$、$D=x^{1-\varepsilon}$、$X=x/2$ とする。定数 $C=C(\varepsilon,A)$ があって、$R=Cx(\log x)^{-A}$ とおくと、$x$ が十分大きいとき $\mathfrak F=\mathfrak F(x,\sqrt x,D,X,R)$ は $\mathcal A^+$ と $\mathcal A^-$ をともに含み、
$$ S^-\le1,\qquad S^+\ge\pi(x)-\pi(\sqrt x) $$
である。特に
$$ \frac{S^-}{XV(\sqrt x)}\to0,\qquad\liminf_{x\to\infty}\frac{S^+}{XV(\sqrt x)}\ge e^\gamma $$
である。

2 つの数列が同じ族に入る

$P(\sqrt x)$ の約数 $d$ は平方因子をもたないので、def-pp-family の和は $\sum_{d\le D,\ d\mid P(\sqrt x)}\lvert r^\pm_d\rvert\le\sum_{d\le D}\mu(d)^2\lvert r^\pm_d\rvert$ 以下である(prop-pp-congruence)。lem-pp-remainder から、適当な $C$ についてこれは $x$ が大きいとき $Cx(\log x)^{-A}$ 以下なので、$\mathcal A^\pm\in\mathfrak F$ である。よって $S^-\le S(\mathcal A^+,\sqrt x)$、$S^+\ge S(\mathcal A^-,\sqrt x)$ であり、prop-pp-sifted から最初の主張を得る。極限についての主張は、prop-pp-sifted の後に計算した比から従う。$\square$

$R=Cx(\log x)^{-A}$ は、$A>1$ なら期待値 $XV(\sqrt x)\asymp x/\log x$ より小さい。つまり剰余項が主項に比べて十分小さいという、篩法にとって最も良い状況でも、

  • 下界:$S(\mathcal A,\sqrt x)\ge c\,XV(\sqrt x)$($c>0$)を、族 $\mathfrak F$ のすべての $\mathcal A$ について示すことはできない。
  • 上界:$S(\mathcal A,\sqrt x)\le c'\,XV(\sqrt x)$ を族のすべての $\mathcal A$ について示すには、$c'\ge e^\gamma+o(1)$ が必要である。
    となる。素数を数えるには $z=\sqrt x$ まで篩う必要があるので、篩の情報だけでは素数の個数の正の下界が得られない。これが パリティ問題 である。上界は正しい程度($x/\log x$)までは得られうるが、下界は $0$ を超えられない。
篩の情報だけでは素数の漸近式は得られない

thm-pp-main の状況で、族 $\mathfrak F$ のすべての $\mathcal A$ について $S(\mathcal A,\sqrt x)\sim\kappa\,XV(\sqrt x)$ が成り立つような定数 $\kappa$ は存在しない。

$\mathcal A^+$ と $\mathcal A^-$ で比の極限がそれぞれ $0$ と $e^\gamma$ になり、一致しないからである。$\square$

例

数値で見る Selberg の例

$x=10^5$ と $x=10^6$ で、prop-pp-congruence の式を $d\le2000$ のすべてで直接の数え上げと照合し、篩った後の個数を数えると次のようになる。

$x$$S(\mathcal A^+,\sqrt x)$$S(\mathcal A^-,\sqrt x)$$XV(\sqrt x)$$S(\mathcal A^-,\sqrt x)/XV(\sqrt x)$
$10^5$$1$$9527$$4826.0$$1.974$
$10^6$$1$$78330$$40482.6$$1.935$

比は $e^\gamma=1.781$ に向かってゆっくり減る($\pi(x)/(x/\log x)$ が $1$ に近づくのが遅いため)。剰余項の和 $\sum_{d\le D}\mu(d)^2\lvert r^\pm_d\rvert$ は、$x=10^6$、$D=x^{0.75}$ で $0.065x$ 程度である。この大きさの $x$ では、第 1 項 $\frac12\lvert\lfloor x/d\rfloor-x/d\rvert$ の和が主に効いていて、lem-pp-remainder の漸近的な評価はまだ数値には表れない。

双子素数と Chen の定理

Chen は 1966 年と 1973 年の仕事で、$p+2$ が素数であるか 2 つの素数の積であるような素数 $p$ が無限に多いことを示した(Pin09 p. 381)。$p+2=p'$(素数)と $p+2=p_1p_2$ のどちらが無限に多く起こるかを特定できないことは、パリティ問題の最も重要な場合とされている(同所)。$p+2$ の素因数の個数が奇数になる素数 $p$ が無限に多いことすら未解決であると、Pin09 p. 381(2009 年)は述べている。

有界な素数間隔の上限 6

素数の有界間隔定理 の Polymath の計画では、一般化された Elliott–Halberstam予想 のもとで、差が $6$ 以下の素数の組が無限に多いことが示された。Pol14 §8(pp. 68–71)は、篩の方法ではこの仮定のもとでも $6$ より小さい上界は得られないことを、次の重みを使って発見的に論じている。
$$ \omega(n)=\bigl(1-\lambda(n)\lambda(n+2)\bigr)\bigl(1-\lambda(n+2)\lambda(n+6)\bigr) $$
$n,n+2$ がともに素数なら $\lambda(n)\lambda(n+2)=1$ で、$n+2,n+6$ がともに素数でも同様なので、このような $n$ で $\omega(n)=0$ となる。一方、$\lambda$ の符号の打ち消しのために、$\omega$ を掛けても篩の入力となる合同条件の和はほとんど変わらないと予想される。こうして、素数の組を含まない重み付きの数列が同じ篩の情報をもつことになり、Selberg の例と同じ構造が現れる。

反例

thm-pp-main は、篩の情報を「水準 $D< x$ までの合同条件の数え上げ」に限ったときの限界である。条件を変えると、結論は成り立たなくなる。

変える条件例起こること
水準 $D=x^{1-\varepsilon}$$D=x$$\mathcal A^+$ と $\mathcal A^-$ の少なくとも一方は剰余項の和が $x/(20(\log x)^2)$ 以上になり、$A>2$ なら同じ族に入らない(下の注意)
合同条件の和だけを使う双線形形式の評価を加える(FI98b の仮定 (B))素数の漸近式が得られる。$a^2+b^4$ の形の素数(FI98a)
下界を求める上界を求める上界は $x/\log x$ の程度までは妨げられない。$S^+$ は $e^\gamma XV$ 程度で有限倍
$\lambda$ による分割偶数と奇数への分割密度が $d$ の偶奇で変わり、$A_d\approx X/d$ が成り立たない。同じ情報をもつ 2 つの数列にならない

1 行目の注意. $x/2< d\le x$ なら $\lfloor x/d\rfloor=1$、$L(x/d)=L(1)=1$ なので、prop-pp-congruence から $\lvert r^+_d\rvert+\lvert r^-_d\rvert\ge\lvert r^+_d-r^-_d\rvert=\lvert\lambda(d)\rvert=1$ である。族の和は $d\mid P(\sqrt x)$ を満たす $d$ にわたる。$\sqrt{x/2}< p< p'\le\sqrt x$ を満たす素数の組について $d=pp'$ とおくと、$x/2< d\le x$ であり、$d$ は $\sqrt x$ 以下の相異なる素数の積なので $d\mid P(\sqrt x)$ である。区間 $(\sqrt{x/2},\sqrt x]$ の素数の個数 $N_x$ は 素数定理 により $(2-\sqrt2)\sqrt x/\log x$ に漸近するので、組の個数 $N_x(N_x-1)/2$ は $x$ が大きいとき $x/(10(\log x)^2)$ 以上である。よって $\sum_{d\le x,\ d\mid P(\sqrt x)}(\lvert r^+_d\rvert+\lvert r^-_d\rvert)\ge x/(10(\log x)^2)$ であり、一方は $x/(20(\log x)^2)$ 以上で、$A>2$ なら $x$ が大きいとき $R=Cx(\log x)^{-A}$ を超える。水準 $D=x$ を要求する情報は、実際の数列についてはまず得られない(FI98b p. 1044)。
2 行目の注意. Friedlander と Iwaniec は、篩の公理に双線形形式の評価 (B) を加えると素数の漸近式が得られることを示し(FI98b p. 1044 の Theorem 1)、Selberg の数列はこの (B) を満たさないことを注意している(p. 1045)。この方法で、正の整数 $a,b$ にわたる和について
$$ \sum_{a^2+b^4\le x}\Lambda(a^2+b^4)=\frac{4\kappa}{\pi}x^{3/4}\Bigl(1+O\Bigl(\frac{\log\log x}{\log x}\Bigr)\Bigr),\qquad\kappa=\frac{\Gamma(1/4)^2}{6\sqrt{2\pi}} $$
が証明された(FI98a p. 946 の Theorem 1)。ここで $\Lambda$ は von Mangoldt関数 である。双線形形式 $\sum_\ell\lvert\sum_m\beta(m)a_{\ell m}\rvert$($\beta$ は Möbius 関数に似た係数)の評価が、パリティ問題を破る追加の情報になっている(FI98a p. 948 の (1.6))。

篩法の上界と Selberg の篩

パリティ問題は上界を妨げない。篩法 の Brun の評価や Selbergの篩 は、双子素数の個数などを正しい程度で上から押さえる。thm-pp-main が述べるのは、上界の定数を $e^\gamma$ 倍より小さくできないこと、下界を正にできないことである。Chen の定理のように、篩法の結論が「素数または 2 つの素数の積」で止まるのも、素因数の個数の偶奇を区別できないことの現れと理解されている(Pin09 p. 381)。

関連項目

参考文献

[1]
John Friedlander, Henryk Iwaniec, Asymptotic sieve for primes, Annals of Mathematics (2), 1998, pp. 1041–1065(§1、pp. 1041–1045:仮定 (R)・(B) p. 1043、Theorem 1 p. 1044、Selberg の例 p. 1045)
[2]
John Friedlander, Henryk Iwaniec, The polynomial X^2+Y^4 captures its primes, Annals of Mathematics (2), 1998, pp. 945–1040(Theorem 1 p. 946、パリティ問題 p. 947、(1.6) p. 948)
[3]
János Pintz, Landau's problems on primes, Journal de Théorie des Nombres de Bordeaux, 2009, pp. 357–404(§§9–10、p. 381)
[4]
D. H. J. Polymath, Variants of the Selberg sieve, and bounded intervals containing many primes, Research in the Mathematical Sciences, 2014, Article 12(本文の頁は arXiv:1407.4897v4 による。§8 The parity problem、pp. 68–71)

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