Selbergの篩

1：$P$ の約数は平方因子をもたないので、$p\mid[d_1,d_2]$ となる素数は $d_1$ か $d_2$ の素因数で、$(d_1,d_2)$ の素因数はその両方に現れる。乗法性から $g([d_1,d_2])g((d_1,d_2))=g(d_1)g(d_2)$ である。また $p\in\mathcal{P}$ について $\frac1{g(p)}=1+\frac{1-g(p)}{g(p)}=1+\frac1{h(p)}$ なので、平方因子をもたない $m\mid P$ について積を展開して $\frac1{g(m)}=\prod_{p\mid m}\bigl(1+\frac1{h(p)}\bigr)=\sum_{e\mid m}\frac1{h(e)}$ である。よって $$Q(\lambda)=\sum_{d_1,d_2}\lambda_{d_1}g(d_1)\lambda_{d_2}g(d_2)\sum_{e\mid(d_1,d_2)}\frac1{h(e)}=\sum_{e\mid P}\frac1{h(e)}\Bigl(\sum_{e\mid d}\lambda_dg(d)\Bigr)^2$$ である（$e\mid(d_1,d_2)$ は $e\mid d_1$ かつ $e\mid d_2$ と同値）。

2：$e\mid d$ なら $d\ge e$ なので、$e>D$ なら和の項はすべて $\lambda_d=0$ である。また $$\sum_{e\mid P}\mu(e)y_e=\sum_{d\mid P}\lambda_dg(d)\sum_{e\mid d}\mu(e)=\lambda_1g(1)=1$$ である。ここで Möbius関数 の記事の定理「約数にわたる和」により、$\sum_{e\mid d}\mu(e)$ は $d=1$ のとき $1$、それ以外で $0$ である。

3：右辺に $y_e$ の定義を代入すると $\sum_{d\mid c}\lambda_cg(c)\sum_{d\mid e\mid c}\mu(e/d)$ となる（$c$ は $P$ の約数）。$e=dk$ と書くと内側の和は $\sum_{k\mid c/d}\mu(k)$ で、$c=d$ のとき $1$、それ以外で $0$ である。$\square$

1：lem-ss-diagonal の 2 と Cauchy–Schwarzの不等式 により $$1=\Bigl(\sum_{e\mid P,\ e\le D}\mu(e)\sqrt{h(e)}\cdot\frac{y_e}{\sqrt{h(e)}}\Bigr)^2\le\Bigl(\sum_{e\mid P,\ e\le D}h(e)\Bigr)\Bigl(\sum_{e\mid P,\ e\le D}\frac{y_e^2}{h(e)}\Bigr)=G(D)\,Q(\lambda)$$ である（$\mu(e)^2=1$ を使った。最後は lem-ss-diagonal の 1 と、$e>D$ で $y_e=0$ であることによる）。

2：$y'_e:=\mu(e)h(e)/G(D)$（$e\le D$）、$y'_e:=0$（$e>D$）とおく。$\lambda_dg(d):=\sum_{d\mid e}\mu(e/d)y'_e$ で $\lambda$ を定めると、$\mu(e/d)\mu(e)=\mu(d)$（$e$ は平方因子をもたない）と $e=dm$、$h(dm)=h(d)h(m)$ から、$\lambda=\lambda^{\mathrm S}$ である。この $\lambda$ について $\sum_{d\mid P,\ e\mid d}\lambda_dg(d)=\sum_{c\mid P,\ e\mid c}y'_c\sum_{e\mid d\mid c}\mu(c/d)=y'_e$ なので（prf-ss-diagonal の 3 と同じ計算）、lem-ss-diagonal の $y_e$ は $y'_e$ に等しい。$d>D$ で $\lambda_d=0$ であり、$\lambda_1=\frac1{G(D)}\sum_{m\le D}h(m)=1$ なので $\lambda$ は重みである。lem-ss-diagonal の 1 から $Q(\lambda)=\sum_{e\le D}h(e)/G(D)^2=1/G(D)$ である。

$|\lambda^{\mathrm S}_d|\le1$：$d\le D$ とし、$T:=\sum_{m\mid P/d,\ m\le D/d}h(m)$ とおく。$k\mid d$ と $m\mid P/d$（$m\le D/d$）の組ごとに $km$ は $P$ の約数で、$km\le dm\le D$ であり、$(k,m)$ は $km$ から $k=(km,d)$ として復元できるので、異なる組は異なる約数を与える。よって $$G(D)\ge\sum_{k\mid d}\ \sum_{m\mid P/d,\ m\le D/d}h(k)h(m)=T\prod_{p\mid d}(1+h(p))$$ である。$1+h(p)=\frac1{1-g(p)}=\frac{h(p)}{g(p)}$ なので右辺は $T\,h(d)/g(d)$ に等しく、$|\lambda^{\mathrm S}_d|=\frac{h(d)T}{g(d)G(D)}\le1$ である。

3：lem-ss-basic を $\lambda^{\mathrm S}$ に使い、$|\lambda^{\mathrm S}_{d_1}\lambda^{\mathrm S}_{d_2}|\le1$ と $d>D$ で $\lambda^{\mathrm S}_d=0$ を使えば最初の不等式である。$[d_1,d_2]=d$ となる $d_1,d_2\mid P$ の組は、$d$ の各素因数を $d_1$ だけ、$d_2$ だけ、両方のどれに入れるかで決まるので $3^{\nu(d)}$ 個あり、$d_1,d_2\le D$ なら $d\le D^2$ である。$\square$

平方因子をもたない $d$ について $\frac1{\varphi(d)}=\prod_{p\mid d}\frac1{p-1}=\prod_{p\mid d}\sum_{k\ge1}p^{-k}=\sum_{n}\frac1n$ である。最後の和は、素因数の集合が $d$ の素因数の集合に一致する正の整数 $n$ にわたる。そのような $n$ は $d$ 以上なので、$q=1$ の場合は$$\sum_{d\le D}\frac{\mu(d)^2}{\varphi(d)}\ge\sum_{n\le D}\frac1n\ge\int_1^{\lfloor D\rfloor+1}\frac{dt}t\ge\log D$$である。一般の $q$ では、平方因子をもたない $d\le D$ を $d=km$（$k=(d,q)$、$(m,q)=1$）と一意に分けると $\varphi(d)=\varphi(k)\varphi(m)$ で、$m\le D$ なので$$\sum_{d\le D}\frac{\mu(d)^2}{\varphi(d)}\le\Bigl(\sum_{k\mid q}\frac{\mu(k)^2}{\varphi(k)}\Bigr)\sum_{\substack{m\le D,\ (m,q)=1}}\frac{\mu(m)^2}{\varphi(m)}$$である。$\sum_{k\mid q}\mu(k)^2/\varphi(k)=\prod_{p\mid q}\bigl(1+\frac1{p-1}\bigr)=\frac q{\varphi(q)}$ なので主張を得る。$\square$

thm-ss-bt を $\varepsilon=1$ で使い、その $Y_0$（$Y_0>e$ にとる）をとる。$x/q\ge Y_0$ なら $C=3$ でよい。$1< x/q< Y_0$ なら、$n\equiv a\pmod q$ となる $1\le n\le x$ は $x/q+1<2x/q$ 個以下なので$$\pi(x;q,a)<\frac{2x}q=\frac{2\log(x/q)\cdot x}{q\log(x/q)}\le\frac{2\log Y_0\cdot x}{\varphi(q)\log(x/q)}$$である（$\varphi(q)\le q$）。$C:=\max(3,2\log Y_0)$ とすればよい。$\square$

$\tau(n)$ を $n$ の正の約数の個数とする。奇素数 $p$ について、$2(p-1)^2-(2p-1)(p-2)=p\ge0$ なので$$h(p)=\frac2{p-2}\ge\frac{2p-1}{(p-1)^2}=\Bigl(1-\frac1p\Bigr)^{-2}-1=\sum_{k\ge1}\frac{k+1}{p^k}=\sum_{k\ge1}\frac{\tau(p^k)}{p^k}$$である。$d$ を $D$ 以下の奇素数の積（重複なし）とし、積を展開すると、$\tau$ の乗法性から $h(d)\ge\sum_n\tau(n)/n$ である。和は、素因数の集合が $d$ の素因数の集合に一致する $n$ にわたる。奇数 $n\le D$ はちょうど 1 つの $d$（$n$ の相異なる素因数の積。$d\le n\le D$）についてこの和に現れるので$$G(D)\ge\sum_{\substack{n\le D\\ n\text{ は奇数}}}\frac{\tau(n)}n=\sum_{\substack{ab\le D\\ a,b\text{ は奇数}}}\frac1{ab}\ge\Bigl(\sum_{\substack{a\le\sqrt D\\ a\text{ は奇数}}}\frac1a\Bigr)^2$$である。$y\ge1$ について、奇数 $a\le y$ では $\frac1a>\frac1{a+1}$ なので、$\sum_{a\le y,\ a\text{ 奇}}\frac1a$ は偶数 $b\le y$ にわたる $\sum\frac1b$ 以上であり、2 つを足すと $\sum_{n\le y}\frac1n\ge\log y$ になる。よって奇数にわたる和は $\frac12\log y$ 以上で、$y=\sqrt D$ として主張を得る。$\square$