インテジャーズ

インテジャーズ

数、特に整数に関する記事。

6より大きい任意の整数は相異なる素数の和として表すことができる

6は相異なる素数の和としては表すことができません。一方、次の定理が成り立ちます:

定理 (Richert 1949) 6より大きい任意の整数は相異なる素数の有限個の和として表すことができる。

証明. 素数は無数に存在するので、次の主張を示せば十分。p_kで小さい方から数えてk番目の素数を表す:

主張 任意の5以上の整数kに対して在る自然数s_kが存在し、区間[7, s_k+6]にある連続するs_k個の整数は全てp_1, p_2, \dots, p_kを用いた相異なる素数の和として表され、s_k \geq p_{k+1}を満たす。

この主張をkに関する数学的帰納法で証明する。

k=5のとき
s_5=13とできる。実際、p_1=2, p_2=3, p_3=5, p_4=7, p_5=11, p_6=13であり、

\begin{align}7&=7 \\ 8&=3+5 \\ 9&= 2+7 \\ 10&= 3+7 \\ 11 &=11 \\ 12 &= 5+7 \\ 13&=2+11 \\ 14 &= 3+11 \\ 15 &= 3+5+7 \\ 16 &= 5+11 \\ 17 &= 2+3+5+7 \\ 18&=7+11 \\ 19 &=3+5+11\end{align}

s_5 = 13 \geq 13=p_6

であることから確認できる。

k \geq 6として、k-1のときに成立すると仮定する。

このとき、題意を満たすようなs_{k-1}が存在する。そうして、

s_k := s_{k-1} + p_k

によって、s_kを定める。[7, s_k+6]の元xを任意にとる。

x \in [7, s_{k-1}+6]ならば帰納法の仮定によって、xp_1, \dots, p_{k-1}を用いた相異なる有限個の素数の和として表される。

x\in [s_{k-1}+7, s_k+6]ならばy \in [7, s_{k-1}+6]が存在して、x=y+p_kと書けるので、再びyに対する帰納法の仮定からxp_1, \dots, p_kを用いた相異なる有限個の素数の和として表されることがわかる。

最後に、帰納法の仮定より、

s_k = s_{k-1}+p_k \geq 2p_k

であるが、Bertrandの仮説
integers.hatenablog.com

より2p_k \geq p_{k+1}が成り立つので、

s_k\geq p_{k+1}

を得る。すなわち、kのときも成立することが示された。

こうして、数学的帰納法によって主張が証明されたので、Richertの定理も示された。
Q.E.D.

Grahamの定理の証明において「数列の半完全性」が重要になりますが、Richertの定理は「素数のなす数列は半完全である」と表現することができます。