一橋大学の今年の問題に$1000$以下の素数が$250$個以下であることを示す問題が出題された（たとえば こちらのツイート 参照）。本記事では、やや強く$1000$以下の素数は$9$個以上$232$個以下であることを $2, 3, 5, 7$ 以外の素数に関する情報を用いずに証明する。証明は包含と除去の原理を用いる。この議論は本質的にはEratosthenesの篩と同じ原理に基づく。
$1000$ 以下の正の整数のうち、$I$ に属するいずれの素数でも割れるもの全体の集合を $A_I$ と書くことにする。$S$ を素数の集合とすると、$1000$ 以下の正の整数のうち、$S$ に属するいずれの素数でも割れないものの個数は包含と除去の原理から、
$$\sum_{I\subset S} (-1)^{\# I} \# A_I$$
に一致する。
さて $n$ が $I$ に属するいずれの素数でも割れるのは、$n$ が $I$ に属する素数すべての積で割れることと同値である。たとえば $n$ が $2, 3, 5$ のいずれでも割れるのは $n$ が $30$ の倍数であることと同値である。
よって $I$ に属する数すべての積を $P(I)$ （ただし $P(\emptyset)=1$ とする）とおくと
$$\# A_I=\floor{\frac{1000}{P(I)}}$$
となる。たとえば $1000$ 以下の正の整数のうち $2, 3, 5$ で割れるものの個数は
$$\# A_{\{2, 3, 5\}}=\floor{\frac{1000}{30}}=33$$
となる。
よって$1000$ 以下の正の整数のうち、$S$ に属するいずれの素数でも割れないものの個数は
$$\sum_{I\subset S} (-1)^{\# I} \floor{\frac{1000}{P(I)}}$$
に一致する。
上の式で $S=\{2, 3, 5, 7\}$ とおくことで $1000$以下の正の整数で $2, 3, 5, 7$ のいずれでも割り切れないものの個数は
$$\begin{split}
\sum_{I\subset \{2, 3, 5, 7\}} (-1)^{\# I} \# A_I
=& \sum_{I\subset \{2, 3, 5, 7\}} (-1)^{\# I} \floor{\frac{1000}{P(I)}} \\
=& \floor{\frac{1000}{1}}-\floor{\frac{1000}{2}}-\floor{\frac{1000}{3}}-\floor{\frac{1000}{5}}-\floor{\frac{1000}{7}} \\
& +\floor{\frac{1000}{6}}+\floor{\frac{1000}{10}}+\floor{\frac{1000}{14}}+\floor{\frac{1000}{15}}+\floor{\frac{1000}{21}}+\floor{\frac{1000}{35}} \\
& -\floor{\frac{1000}{30}}-\floor{\frac{1000}{42}}-\floor{\frac{1000}{70}}-\floor{\frac{1000}{105}}+\floor{\frac{1000}{210}} \\
=& 1000-500-333-200-142 \\
& +166+100+71+66+47+28 \\
& -33-23-14-9+4 \\
=& 228
\end{split}$$
であることがわかる。
$7$ より大きな素数は $2, 3, 5, 7$ のいずれでも割り切れないから、$1000$ 以下の素数の個数は $228+4=232$ 個以下である。
下からの評価には少し工夫が必要となる。まず、次の一般的な因数分解の等式を示す。
有限集合 $S=\{p_1, p_2, \ldots, p_k\}$ に対して
$$\sum_{I\subset S} \frac{(-1)^{\# I}}{P(I)}=\prod_{i=1}^k \left(1-\frac{1}{p_i}\right).$$
$k=0$ つまり $S=\emptyset$ のときは両辺 $1$ なので成り立つ。
$\# S< k$ のとき成り立つと仮定し、 $S=\{p_1, p_2, \ldots, p_k\}$ の場合を考える。
$$\sum_{I\subset \{p_1, p_2, \ldots, p_{k-1}\}} \frac{(-1)^{\# I}}{P(I)}=\prod_{i=1}^{k-1} \left(1-\frac{1}{p_i}\right)$$
および
$$\begin{split}
\sum_{p_k\in I\subset \{p_1, p_2, \ldots, p_k\}} \frac{(-1)^{\# I}}{P(I)}
=& \sum_{J\subset \{p_1, p_2, \ldots, p_{k-1}\}} \frac{(-1)^{\# (J\cup \{p_k\})}}{P(J\cup \{p_k\})} \\
=& \sum_{J\subset \{p_1, p_2, \ldots, p_{k-1}\}} \frac{(-1)^{1+\# J}}{p_k P(J)} \\
=& -\frac{1}{p_k}\prod_{i=1}^{k-1} \left(1-\frac{1}{p_i}\right)
\end{split}$$
より
$$\begin{split}
\sum_{I\subset S} \frac{(-1)^{\# I}}{P(I)}=& \sum_{I\subset \{p_1, p_2, \ldots, p_{k-1}\}} \frac{(-1)^{\# I}}{P(I)}+\sum_{p_k\in I\subset \{p_1, p_2, \ldots, p_k\}} \frac{(-1)^{\# I}}{P(I)} \\
=& \prod_{i=1}^{k-1} \left(1-\frac{1}{p_i}\right)-\frac{1}{p_k}\prod_{i=1}^{k-1} \left(1-\frac{1}{p_i}\right) \\
=& \left(1-\frac{1}{p_k}\right)\prod_{i=1}^{k-1} \left(1-\frac{1}{p_i}\right) \\
=& \prod_{i=1}^k \left(1-\frac{1}{p_i}\right)
\end{split}$$
となって、この場合にも補題は成り立つ。よって数学的帰納法より任意の数の有限集合 $S$ に対して補題は成り立つ。
$1000$ 以下の素数を $p_1=2< p_2=3<\cdots < p_k$ とする。
$p_1, p_2, \ldots, p_k$ のいずれでも割り切れない最小の正の数を $q$ とおくと $q$ 自身が素数でなければならないから $q>1000$ となる。
よって $1000$ 以下の正の整数はすべて $p_1, p_2, \ldots, p_k$ のいずれかで割り切れなければならない。よって
$S=\{p_1, p_2, \ldots, p_k\}$ とおくと
$$\sum_{I\subset S} (-1)^{\# I} \# A_I=0$$
となる。また
$$\frac{1000}{P(I)}-1<\# A_I=\floor{\frac{1000}{P(I)}}\leq \frac{1000}{P(I)}$$
となるから
$$\begin{split}
\sum_{I\subset S} (-1)^{\# I} \# A_I= & \sum_{\substack{I\subset S,\\ \# I\equiv 0\mmod{2}}} \#A_I-\sum_{\substack{I\subset S,\\ \# I\equiv 1\mmod{2}}} \#A_I \\
\geq & \sum_{\substack{I\subset S,\\ \# I\equiv 0\mmod{2}}} \left(\frac{1000}{P(I)}-1\right)-\sum_{\substack{I\subset S,\\ \# I\equiv 1\mmod{2}}} \frac{1000}{P(I)} \\
=& \sum_{\substack{I\subset S,\\ \# I\equiv 0\mmod{2}}} \frac{1000}{P(I)}-\sum_{\substack{I\subset S,\\ \# I\equiv 1\mmod{2}}} \frac{1000}{P(I)}-\sum_{\substack{I\subset S,\\ \# I\equiv 0\mmod{2}}} 1 \\
=& 1000\left(\sum_{I\subset S} \frac{(-1)^{\# I}}{P(I)}\right)-\sum_{\substack{I\subset S,\\ \# I\equiv 0\mmod{2}}} 1
\end{split}$$
となる。先の補題から
$$\sum_{I\subset S} \frac{(-1)^{\# I}}{P(I)}=\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)$$
となる。さらに
$$\begin{split}
\sum_{I\subset S, \# I\equiv 0\mmod{2}} 1=& \sum_{0\leq r\leq k, r\equiv 0\mmod{2}}\binom{k}{r} \\
=& \frac{1}{2}\left(\sum_{0\leq r\leq k}\binom{k}{r}+\sum_{0\leq r\leq k}\binom{k}{r}(-1)^r\right) \\
=& 2^{k-1}
\end{split}$$
であることを用いると、
$$0=\sum_{I\subset S} (-1)^{\# I} \# A_I\geq 1000\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)-2^{k-1}$$
つまり
$$2^{k-1}\geq 1000\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)$$
とならなければならない。$p_4=7< p_5< p_6<\cdots$ より
$$\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)\geq \frac{1}{2}\times \frac{2}{3}\times \frac{4}{5}\times \prod_{i=4}^k \left(1-\frac{1}{i+3}\right)
=\frac{4}{15}\times \frac{6}{k+3}=\frac{8}{5(k+3)}$$
となるから
$$2^{k-1}(k+3)\geq 1600$$
が成り立つ。 $2^7\times 11=1408<1600$ なので $k\geq 9$ が成り立つ。
より一般に、与えられた数 $X$ 以下の正の整数で $k$ 個の素数 $p_1, p_2, \ldots, p_k$ のいずれでも割り切れないものの個数を $M$ とすると
$$ X\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)-2^{k-1}\leq M\leq X\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)+2^{k-1}$$
が成り立つことが分かる。Legendreはこの方法を用いて一般の与えられた数 $X$ 以下の素数の個数に対して同じ方法を用いて、素数の密度は0であることを示した。
この議論の本質は包含と除去の原理を用いて、与えられた数以下の正の整数で、与えられた素数のいずれでも割り切れないものの個数を数えることにある。所与のいずれの素数でも割り切れないものを残すという点では、Eratosthenesの篩を数量化し一般化したといえる。
ただし、このままの形では、$2^{k-1}$ が非常に速く増加するため、与えられた数以下の素数の個数の良い評価を得るには適さない。しかし、20世紀に入ってMerlinがこの議論を拡張することで双子素数の問題が解決できる可能性を示唆し、Brunはその思想を継承して篩の方法を発展させ、双子素数予想やGoldbachの予想に関する部分的成果を得ることに成功した。現在に至る篩の理論の発展の基礎がこうして築かれたのである。篩の理論とその発展の歴史については参考文献を参照されたい。両文献の第1章に、本記事で述べた、Eratosthenesの篩を定式化する方法について記されている。