Legendreの篩

LegendreはEratosthenesの篩をつぎのように変形し、素数の個数を数えることを試みた。

$X$ までの正の整数
$$1, 2, \ldots, X$$
から $\sqrt{X}$ 以下の素数 $p$ で割り切れるものをすべて取り除く。
$n\leq X$ が合成数ならば、$n$ は $\sqrt{n}\leq \sqrt{X}$ 以下の素因数をもつから、取り除かれる。
一方で、$\sqrt{X}$ 以下の素数 $p$ は自分自身で割れるので取り除かれるが、
$\sqrt{X}< p\leq X$ となる素数は、$p$ より小さい素数で割れないから取り除かれずに残る。
よって、取り除かれずに残る数全体は $\sqrt{X}< p\leq X$ となる素数全体と一致する。

つまり
$$A=A(X)=\{1, 2, \ldots, \floor{X}\}=\Z\cap [1, X]$$
について
$$A_d=\{n\mid n\in A, d\mid n\}$$
を $A$ の要素のうち、$d$ で割り切れるもの全体の集合、
$$S(A, P)=\#\{n\mid n\in A, \gcd(n, P)=1\}$$
を $A$ の要素のうち、$P$ と互いに素なもの、つまり $P$ のどの素因数でも割り切れないもの全体の個数、
$$P(z)=\prod_{p\leq z} p$$
を $z$ 以下の素数の積とすると、$z=\sqrt{X}$ とおけば、 $S(A, P(\sqrt{X}))$ は $A$ の要素のうち、$\sqrt{X}$ 以下の素因数をもたないもの全体の個数となるから、
$$\pi(X)-\pi(\sqrt{X})=S(A, P(\sqrt{X}))$$
となる。

さらに一般に、$z\leq X$ となる実数 $z$ に対して、$p$ が $z$ より大きな素数ならば、$p$ は $z$ より小さな素因数をもたないので
$$\pi(X)-\pi(z)\leq S(A, P(z))$$
となる（$p_0$ が $\sqrt{X}$ 以下の最大の素数で、$z$ が $p_0$ より小さいときは、$p_0^2$ は合成数だが、$S(A, P(z))$ に数えられるため、等号は成り立たない）。

$S(A, P(z))$ は $A$ の要素のうち、$z$ 以下の素因数をもたないもの全体の個数となるから、明らかに
$$S(A, P(z))=A\backslash \bigcup_{p\leq z}A_p$$
となる。よって 包含と除去の原理 より
$$S(A, P(z))=\sum_{d\mid P(z)}(-1)^\mu(d) \#A_d=\sum_{d\mid P(z)}(-1)^\mu(d)\floor{\frac{X}{d}}$$
となる。$\mu(d)$ は Möbius関数 である。

$$0\leq \frac{X}{d}-\floor{\frac{X}{d}}<1$$
となることから
$$S(A, P(z))=\sum_{d\mid P(z)}(-1)^\mu(d)\left(\frac{X}{d}+O^*(1)\right)$$
となる。$P(z)$ の約数の個数は
$$2^{\omega(P(z))}=2^{\pi(z)}<2^z$$
となる。また
$$\sum_{d\mid P(z)}\frac{(-1)^\mu(d)}{d}=\prod_{p\leq z}\left(1-\frac{1}{p}\right)$$
を用いると
$$S(A, P(z))=X\prod_{p\leq z}\left(1-\frac{1}{p}\right)+O^*(2^z)$$
が成り立つ。

$$\prod_{p\leq z}\left(1-\frac{1}{p}\right)^{-1}\geq \sum_{n\leq z}\frac{1}{z}>\log z$$
より
$$S(A, P(z))<\frac{X}{\log z}+2^z$$
となるので、
$z=(\log X-\log\log X)/\log 2$ とおくと、
$$\pi(X)\leq z+S(A, P(z))<\frac{X(1+o(1))}{\log\log X}$$
となることがわかる。
とくに、
$$\frac{\pi(X)}{X}\rightarrow 0\ (X\rightarrow\infty)$$
となることが示される。

これは、素数定理はもちろん、初等的かつ比較的容易に得られる結果、たとえば
「初等整数論」素数の分布（初等的理論）: x 以下の素数の個数:定理1の系 および 「初等整数論」素数の分布（初等的理論）:Chebyshev関数の初等的評価の定理2 から得られる
$$\pi(X)=O\left(\frac{X}{\log X}\right)$$
よりも弱い。和の中の項の個数が $2^z$ 個となって $z$ に比べて大きすぎるためである。

一方で、この考察は $N$ 個の連続する整数 $M+1, M+2, \ldots, M+N$、あるいは
長さ $X$ の区間 $(U, U+X]$ に属する整数にも一般化できる。すなわち
$$A=A(X)=\{n\mid U< n\leq U+X\}=\Z\cap (U, X]$$
について
$$A_d=\{n\mid n\in A, d\mid n\}$$
とおくと、
$$\abs{\#A_d-\frac{X}{d}}=\abs{\floor{\frac{U+X}{d}}-\floor{\frac{U}{d}}-\frac{U+X}{d}+\frac{U}{d}}<1$$
となるので、上と同様に
$$S(A, P(z))=X\prod_{p\leq z}\left(1-\frac{1}{p}\right)+O^*(2^z)$$
が成り立つ。このことから $z=(\log X-\log\log X)/\log 2$ とおくと、区間 $(U, U+X]$ のとり方によらず
$$\pi(U+X)-\pi(U)\leq z+S(A, P(z))<\frac{X}{\log z}+2^z<\frac{X(1+f(X))}{\log\log X}$$
となる関数 $f(X)\rightarrow 0\ (X\rightarrow +\infty)$ が存在することがわかる（Hardy-Littlewood, 1923）。
これは素数定理のみからは従わず、さらにRiemann予想と同値な評価
$$\pi(X)=\mathrm{li} X+O(X^{1/2}\log X)$$
を用いても得られない結果である。