インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

41:良素数の無限性

41は良素数*1

良素数のうち、まだ当ブログで他の話題で一度も取り扱っていないものの中で最小の素数ということで41を表題に取り上げました。25個ある100以下の素数の丁度真ん中*2の素数と思うこともできます。

定義 n番目の素数をp_nと表すことにする。このとき、p_n良素数(good prime)であるとは、 p_n^2 > p_{n-i}p_{n+i}が任意の 0 < i < nに対して成り立つときにいう。

41が良素数であることは次の計算から分かります:

41^2=1591
31\cdot 47=1457
29\cdot 53=1537
23\cdot 59=1357
19\cdot 61=1159
17\cdot 67=1139
13\cdot 71=923
11\cdot 73=803
7\cdot 79=553
5\cdot 83=415
3\cdot 89=267
2\cdot 97=194

良素数、最初の100個

5, 11, 17, 29, 37, 41, 53, 59, 67, 71, 97, 101, 127, 149, 179, 191, 223, 227, 251, 257,
269, 307, 311, 331, 347, 419, 431, 541, 557, 563, 569, 587, 593, 599, 641, 727, 733,
739, 809, 821, 853, 929, 937, 967, 1009, 1031, 1087, 1151, 1213, 1277, 1367, 1399,
1423, 1427, 1543, 1597, 1847, 1861, 1867, 1871, 1973, 1987, 1993, 1997, 2063,
2203, 2237, 2267, 2333, 2339, 2521, 2531, 2539, 2609, 2647, 2657, 2677, 2683,
2687, 2999, 3163, 3167, 3251, 3299, 3433, 3449, 3457, 3461, 3511, 3527, 3821,
3847, 3907, 3989, 4001, 4201, 4211, 4217, 4229, 4441

良素数の無限性

良素数はTwitterのフォロワーさんの呟きで知りました:

twitter.com
定義からは良素数が無数に存在するかは分からないというか、むしろ有限個しかなくてもおかしくないと思うのですが、実際には無数に存在することがSelfridgeによって予想され、Pomeranceによって証明されました。

C. Pomerance, The prime number graph, Mathematics of Computation 33:145 (1979), pp. 399-408.

に基づいて、その証明を以下で解説します。

凸包のテクニック

先に一般的な定理を証明します。その際、凸包の考え方が重要となりますので、以下の記事で復習することをお勧めします:
integers.hatenablog.com

定理
0 < a_1 < a_2 < a_3 < \cdots および \displaystyle \lim_{n \to \infty}\frac{a_n}{n} = 0 を満たすような実数列\{ a_n \}を考える。このとき、2a_n > a_{n-i}+a_{n+i}が任意の0 < i < nに対して成立するようなa_nが無数に存在する。

この定理の証明のキーとなるのは次の主張です:

主張 定理の条件を満たすような数列\{ a_n \}を考える。V:=(0, 0) \cup \{ (n, a_n) \mid n \in \mathbb{N} \} \subset \mathbb{R}^2とし、S:=\mathrm{CONV}(V)とする(Vの凸包)。このとき、Sの境界は閉じていない折れ線で表され、折れ線の頂点が無数に存在する。

主張の証明. \{ a_n \}が条件を満たすような数列であるとき、凸包Sは次の図のようになる:
f:id:integers:20160205191719p:plain
(図ではa_1, a_3, a_6, a_8, a_9が凸包の頂点となるような例を考えている。点(n, a_n)のことを便宜的に点a_nと呼ぶことにするとき、点a_8a_9を結ぶ直線と点a_9a_{10}(図には書いていないが、仮にa_{10}も凸包の頂点になったと仮定する)を結ぶ直線の傾きは同じように見えるが、図の精度が悪いだけで傾きは異なる。)
仮定より、原点と点a_nを結んで出来る直線(例えば図の青い直線)の傾きが0に収束するため、a_6a_8a_8a_9のような凸包の辺の傾きはどんどん水平になっていく。一方、数列\{ a_n \}は狭義単調増加数列なので、実際に水平になることはあり得ない。すなわち、凸包の折れ線の頂点は無数に存在しなければならないことがわかる。 Q.E.D.
定理の証明. 凸包Sの原点を除いた頂点は凸性から所望の不等式を満たすことがわかる(図の赤線参照)。主張より頂点が無数に存在するので、不等式を満たすa_nも無数に存在することがわかる。 Q.E.D.

Chebyshevの定理と証明の完結

補題 \displaystyle \lim_{n \to \infty}\frac{\log p_n}{n} = 0.

証明. 素数定理p_n \sim n \log n (n \to \infty)から従う:
integers.hatenablog.com
なお、この補題を示すだけならばp_n = O(n \log n) (n \to \infty)で十分なので、それは初等的に導くことができる。実際、Chebyshevの定理の記事において既に示している:
integers.hatenablog.com
Q.E.D.

良素数が無数に存在することの証明. a_n=\log p_nとして定理を適用すればよい。 Q.E.D.

*1:楕円曲線のgood primeとは全く別概念です。

*2:個数に関して中央という意味。41は13番目の素数。