インテジャーズ

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

インテジャーズ

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

1229:素数定理

1229は素数であり、かつ10000以下の素数の個数でもあります。x以下の素数の個数を\pi (x)と表して、\pi (10^n)の値をいくつか見てみましょう*1:

\begin{align} \pi (10) &= 4\\
\pi (10^2) &= 25\\
\pi (10^3) &= 168\\
\pi (10^4) &= 1229\\
\pi (10^5) &= 9592\\
\pi (10^6) &= 78498\\
\pi (10^7) &= 664579\\
\pi (10^8) &= 5761455\\
\pi (10^9) &= 50847534\\
\pi (10^{10})&= 455052511\\
\pi (10^{11})&= 4118054813\\
\pi (10^{12})&= 37607912018\\
\pi (10^{13})&= 346065536839\\
\pi (10^{14})&= 3204941750802\\
\pi (10^{15})&= 29844570422669\\
\pi (10^{16})&= 279238341033925\\
\pi (10^{17})&= 2623557157654233\\
\pi (10^{18})&= 24739954287740860\\
\pi (10^{19})&= 234057667276344607\\
\pi (10^{20})&= 2220819602560918840\\  
\pi (10^{21})&= 21127269486018731928\\
\pi (10^{22})&= 201467286689315906290\\
\pi (10^{23})&= 1925320391606803968923\\
\pi (10^{24})&= 18435599767349200867866\\
\pi (10^{25})&= 176846309399143769411680\\
\pi (10^{26})&= 1699246750872437141327603\end{align}

となっています。ちなみに、1229と664579は素数です。
1000以下の素数の個数は168ですが、かけそば代が168円という理由だけで毎日かけそばを食べていた時代がありました。

さて、これらの数を見て何か法則性を見いだせるでしょうか?
眺めていると、なんとなく\pi (10^n)nを掛けたくなってきたので掛けてみましょう。

\begin{align}\pi (10) &= 4\\
2\pi (10^2) &= 50\\
3\pi (10^3) &= 504\\
4\pi (10^4) &= 4916\\
5\pi (10^5) &= 47960\\
6\pi (10^6) &= 470988\\
7\pi (10^7) &= 4652053\\
8\pi (10^8) &= 46091640\\
9\pi (10^9) &= 457627806\\
10\pi (10^{10})&= 4550525110\\
11\pi (10^{11})&≒ 4.529860294\times 10^{10}\\ 
12\pi (10^{12})&≒ 4.512949442\times 10^{11}\\
13\pi (10^{13})&≒ 4.498851979\times 10^{12}\\
14\pi (10^{14})&≒ 4.486918451\times 10^{13}\\
15\pi (10^{15})&≒ 4.476685563\times 10^{14}\\ 
16\pi (10^{16})&≒ 4.467813457\times 10^{15}\\ 
17\pi (10^{17})&≒ 4.460047168\times 10^{16}\\ 
18\pi (10^{18})&≒ 4.453191772\times 10^{17}\\
19\pi (10^{19})&≒ 4.447095678\times 10^{18}\\ 
20\pi (10^{20})&≒ 4.441639205\times 10^{19}\\  
21\pi (10^{21})&≒ 4.436726592\times 10^{20}\\
22\pi (10^{22})&≒ 4.432280307\times 10^{21}\\
23\pi (10^{23})&≒ 4.428236901\times 10^{22}\\
24\pi (10^{24})&≒ 4.424543944\times 10^{23}\\ 
25\pi (10^{25})&≒ 4.421157735\times 10^{24}\\
26\pi (10^{26})&≒ 4.418041552\times 10^{25}\end{align}

今度は\log 10 = 2.302585093\cdotsを掛けてみたくなったので、掛けてみましょう。

\begin{align}\pi (10) \log 10 &≒ 0.9210340342\times 10 \\
2\pi (10^2)\log 10  &≒ 1.151292546\times 10^2\\
3\pi (10^3)\log 10  &≒ 1.160502887\times 10^3\\
4\pi (10^4)\log 10  &≒ 1.131950832\times 10^4\\
5\pi (10^5)\log 10  &≒ 1.104319811\times 10^5\\
6\pi (10^6)\log 10  &≒ 1.084489948\times 10^6\\ 
7\pi (10^7)\log 10  &≒ 1.071174789\times 10^7\\
8\pi (10^8)\log 10  &≒ 1.061299232\times 10^8\\  
9\pi (10^9)\log 10  &≒ 1.053726964\times 10^9\\ 
10\pi (10^{10})\log 10 &≒ 1.04779128\times 10^{10}\\ 
11\pi (10^{11})\log 10 &≒ 1.043038879\times 10^{11}\\ 
12\pi (10^{12})\log 10 &≒ 1.039145011\times 10^{12}\\ 
13\pi (10^{13})\log 10 &≒ 1.03589895\times 10^{13}\\
14\pi (10^{14})\log 10 &≒ 1.033151154\times 10^{14}\\
15\pi (10^{15})\log 10 &≒ 1.030794944\times 10^{15}\\ 
16\pi (10^{16})\log 10 &≒ 1.028752066\times 10^{16}\\ 
17\pi (10^{17})\log 10 &≒ 1.026963812\times 10^{17}\\ 
18\pi (10^{18})\log 10 &≒ 1.025385299\times 10^{18}\\ 
19\pi (10^{19})\log 10 &≒ 1.023981622\times 10^{19}\\ 
20\pi (10^{20})\log 10 &≒ 1.022725222\times 10^{20}\\  
21\pi (10^{21})\log 10 &≒ 1.021594051\times 10^{21}\\
22\pi (10^{22})\log 10 &≒ 1.020570256\times 10^{22}\\ 
23\pi (10^{23})\log 10 &≒ 1.019639228\times 10^{23}\\ 
24\pi (10^{24})\log 10 &≒ 1.018788893\times 10^{24}\\
25\pi (10^{25})\log 10 &≒ 1.018009189\times 10^{25}\\
26\pi (10^{26})\log 10 &≒ 1.017291662\times 10^{26}\end{align}

ここまでくると、nがどんどん大きくなると\displaystyle n\pi (10^n)\log 10 ≒ 10^{n}が成り立つような気がしてきませんか?(実際は、これはひどい精度の予想ですが、私は答えを知っているのでこのように誘導しています笑。精度をあげる話はまたいつかします。)

なんと、答えはYesなのです!

これを数学的な正しい主張にしたものが、次の素数定理です:

素数定理 \ \ \ \ \ \ \displaystyle \pi (x) \sim \frac{x}{\log x}.
ただし、f(x) \sim g(x)\displaystyle \lim_{x \to \infty}\frac{f(x)}{g(x)} = 1を表す記号とする。

素数は分布が高度に非自明に思えます。てんでんばらばらに出現する素数ですが、実は出現する頻度にしっかりとした数学的法則が存在したのです。素数定理を用いれば、大きいnに対して\displaystyle \pi (10^n) ≒ \frac{10^n}{\log 10^n}が成り立つので、\displaystyle n\pi (10^n)\log 10 ≒ 10^nとなって、先ほどの主張が正しいことが分かりました。\log 10が出てくるのは人間が10進法表記を勝手に使っているからであって、やはり自然対数で書くことで素数定理も美しく正規化されるのです。

この素数定理はGaussが15才のとき(1792)に予想したと言われています。その後、Riemannの研究(1859)を経て、Hadamardとde la Vallée-Poussinが独立に1896年に証明しました。SelbergとErdősが1949年に初等的証明を独立に発表しています*2。今となっては証明は簡単なので、別の記事で紹介しようと思います。

素数定理には多数の同値な言い換えが存在します。ここでは、3つ紹介します。

 \ \ \ \displaystyle \mathrm{Li}(x) := \int_2^x\frac{dt}{\log t}とする。このとき、素数定理は\pi (x) \sim \mathrm{Li}(x)と同値である。

証明. \displaystyle \mathrm{Li}(x) = \frac{x}{\log x} + O\left( \frac{x}{\log^2 x} \right)を示せば十分である*3。これは、部分積分によって

\displaystyle \mathrm{Li}(x) = \frac{x}{\log x}-\frac{2}{\log 2}+\int_2^x\frac{dt}{\log^2 t}

であり、

\displaystyle \int_2^x\frac{dt}{\log^2 t} = \int_2^{\sqrt{x}}\frac{dt}{\log^2 t}+\int_{\sqrt{x}}^x\frac{dt}{\log^2 t} \leq \frac{\sqrt{x}}{\log^2 2}+\frac{x}{\log^2 \sqrt{x}} = O\left( \frac{x}{\log^2 x} \right)

と評価されることからわかる。 Q.E.D.

n番目の素数p_nの近似の言葉にも言い換えられます:

素数定理はp_n \sim n\log nと同値である。

証明. 素数定理が成り立つと仮定する。すると

\displaystyle \lim_{n \to \infty}\frac{n\log p_n}{p_n}=1

が成り立つ。対数をとってから\log p_nで割ることにより、

\displaystyle \lim_{n \to \infty} \left( \frac{\log n}{\log p_n} + \frac{\log \log p_n}{\log p_n} \right) = 1

を得る。第二項は0に収束するので、

\displaystyle \lim_{n \to \infty}\frac{\log n}{\log p_n}=1

となる。従って、

\displaystyle \lim_{n \to \infty}\frac{n\log n}{p_n} = \lim_{n \to \infty} \frac{n\log p_n}{p_n}\frac{\log n}{\log p_n} = 1

が示された。逆に、

\displaystyle \lim_{n \to \infty}\frac{n\log n}{p_n}=1

を仮定する。このとき、

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

なので、

\displaystyle \lim_{n \to \infty} \frac{\log n}{\log p_n} = \lim_{n \to \infty}\frac{\log n}{\log p_n+\log \frac{n\log n}{p_n}} = \lim_{n \to \infty}\frac{\log n}{\log n + \log \log n} = 1

となる。よって、

\displaystyle \lim_{n \to \infty}\frac{n\log p_n}{p_n} = \lim_{n \to \infty}\frac{\log p_n}{\log n}\frac{n \log n}{p_n} = 1

を得る。また、

\displaystyle \lim_{n \to \infty}\frac{p_{n+1}}{p_n} = \lim_{n \to \infty}\frac{p_{n+1}}{(n+1)\log (n+1)} \frac{n\log n}{p_n}\frac{(n+1)\log (n+1)}{n\log n} = 1

である。さて、p_n \leq x < p_{n+1}としよう。このとき、\pi (x) = nに注意すると、

\displaystyle \frac{n \log p_n}{p_{n+1}} < \frac{\pi (x)\log x}{x} < \frac{n\log p_{n+1}}{p_n}

すなわち、

\displaystyle \frac{p_n}{p_{n+1}}\frac{n\log p_n}{p_n} < \frac{\pi (x)\log x}{x} < \frac{(n+1)\log p_{n+1}}{p_{n+1}}\frac{n}{n+1}\frac{p_{n+1}}{p_n}

が成り立つ。よって、n \to \inftyとすることにより素数定理が得られる。 Q.E.D.

この同値性から
integers.hatenablog.com
で述べていた謎が解き明かされます。すなわち、十分大きいnに対してp_{10^n} ≒ 10^{n}\log 10^{n}が成り立つので、\displaystyle \frac{p_{10^n}}{10^n} ≒ n\log 10となって、nのときとn+1のときの差は約\log 10 ≒ 2.3となります。これが整数部分を考えれば2か3で推移していた理由です。


実際に証明する際には、次の式を証明する場合が多いです:

素数定理は\vartheta (x) \sim xと同値である。ただし、\displaystyle \vartheta (x) := \sum_{p \leq x}\log pはChebyshev関数で、和はx以下の素数をわたる。

証明. \displaystyle \vartheta (x) = \sum_{p \leq x}\log p\leq \sum_{p \leq x}\log x = \pi (x) \log xである。一方、任意に0 < \varepsilon < 1をとるとき、

\displaystyle \begin{equation}\begin{split}\vartheta (x) &\geq \sum_{x^{1-\varepsilon} \leq p \leq x}\log p \geq \sum_{x^{1-\varepsilon} \leq p \leq x}(1-\varepsilon )\log x = (1-\varepsilon )\log x(\pi (x) - \pi (x^{1-\varepsilon}) ) \\ &\geq (1-\varepsilon )\log x (\pi (x) - x^{1-\varepsilon})\end{split}\end{equation}

と評価されるので、

\displaystyle \frac{\pi (x)\log x}{x} \geq \frac{\vartheta (x)}{x} \geq (1-\varepsilon ) \frac{\pi (x)\log x}{x} - \frac{(1-\varepsilon )\log x}{x^{\varepsilon}}

を得る。よって、素数定理が成り立つならば

\displaystyle 1 \geq \limsup_{x \to \infty}\frac{\vartheta (x)}{x} \geq \liminf_{x \to \infty}\frac{\vartheta (x)}{x} \geq 1-\varepsilon

となり、0 < \varepsilon <1は任意であったから \vartheta (x) \sim xが成り立つ。同様に、

\displaystyle \frac{\vartheta (x)}{x} \leq \frac{\pi (x)\log x}{x} \leq \frac{1}{1-\varepsilon}\frac{\vartheta (x)}{x} + \frac{\log x}{x^{\varepsilon}}

であるから、\vartheta (x) \sim xが成り立つならば

\displaystyle 1\leq \liminf_{x \to \infty}\frac{\pi (x)\log x}{x} \leq \limsup_{x \to \infty}\frac{\pi (x)\log x}{x} \leq \frac{1}{1- \varepsilon}

を得る。0 < \varepsilon <1は任意であったから素数定理が得られる。 Q.E.D.

素数定理は素数に関する未解決の予想の妥当性をheuristic(発見的)に議論する際に次の形でよく用いられます:

与えられた数xが素数である確率は約1/\log xである。

素数は実際には全く一様には分布していないので、上の主張は厳密には誤りです。しかし、これを用いた確率論的考察によって素数に関する法則を予見することには一定の価値があります。実際に当ブログでも、今後heuristicな議論を行っていく予定です。

素数の確率に関してはtsujimotterさんによる記事を合わせて読むと理解が深まるでしょう:
tsujimotter.hatenablog.com

*1:素数個数関数(prime counting function)\pi(x)\piは円周率ではありません。素数を表す英語、"prime"の頭文字は"p"ですが、対応するギリシャ文字\piが用いられています。

*2:この業績によりSelbergはFields賞を受賞。独立とは言っても2人は密接に議論を交わしている。ただ、Selbergが共著論文を書かない主義の数学者だったのである。なお、「初等的」と「簡単」の言葉の意味は全く異なることに注意。

*3:O(f(x) )はLandauの記号(ビッグオー)で、絶対値がf(x)の定数倍で上から押さえられるような関数のことを表す。また、\log^k x = (\log x)^k