素数計数関数の下からの素朴な評価 (1)

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

$n$ 番目の素数を $p_{n}$ で表す. 例えば, $p_{1}=2$, $p_{2}=3$, $p_{3}=5$, $p_{4}=7$, $p_{5}=11$ である.

実数 $x$ に対して, $\pi(x)$ を $x$ 以下の素数の個数とする. こうして定まる関数 $\pi(x)$ を素数計数関数という.

[補題] 任意の正の整数 $n$ に対して, $$ p_{n}\leq 2^{2^{n-1}-1} + 1 $$ が成り立つ.

[証明] $n$ に関する数学的帰納法により証明する.

$p_{1}=2$ かつ $2^{2^{1-1}-1} + 1 = 2$ であるから, $n=1$ のときは正しい.

$n$ より小さいとき正しいとする. $p_{1}p_{2}\cdots p_{n-1}+1$ は $p_{1}$, $p_{2}$, $\ldots$, $p_{n-1}$ のいずれでも割れないから, ある番号 $m$ が存在して, $m\geq n$ かつ $p_{m}$ は $p_{1}p_{2}\cdots p_{n-1}+1$ を割る. ゆえに, $$ p_{n}\leq p_{m} \leq p_{1}p_{2}\cdots p_{n-1}+1. $$ 一方, 帰納法の仮定より, $$ p_{k} \leq 2^{2^{k-1}-1} + 1 \leq 2\cdot 2^{2^{k-1}-1} = 2^{2^{k-1}} \quad (k=1,\,2,\,\ldots,\,n-1) $$ であるから, $$ p_{1}p_{2}\cdots p_{n-1}+1\leq 2^{2^{0}+2^{1}+\cdots+2^{n-2}} + 1 = 2^{2^{n-1}-1} + 1. $$ ゆえに, $p_{n}\leq 2^{2^{n-1}-1}+1$ となり, $n$ のときも正しい. (証明終)

[定理] 任意の実数 $x\geq 2$ に対して, $$ \log_{2}(\log_{2}x) \leq \pi(x) $$ が成り立つ.

[証明] $k$ を $2^{2^{k-1}}\leq x$ なる最大の正の整数とする. $x\geq 2$ より, $k\geq 1$ である. 補題より, $k$ 番目の素数 $p_{k}$ について, $$ p_{k} \leq 2^{2^{k-1}-1} + 1 \leq 2\cdot 2^{2^{k-1}-1} = 2^{2^{k-1}}\leq x. $$ よって, $x$ 以下の素数は少なくとも $k$ 個ある. すなわち, $k\leq \pi(x)$ である. 一方, $k$ の最大性により $x<2^{2^{k}}$ であるから, $$ \log_{2}x < \log_{2}2^{2^{k}} = 2^{k}\log_{2}2 = 2^{k}. $$ さらに, $$ \log_{2}(\log_{2}x) < \log_{2}2^{k} = k\log_{2}2 = k. $$ したがって, 求める不等式が得られる. (証明終)

関連記事

素数計数関数の下からの素朴な評価 (2)
素数計数関数の上からの素朴な評価
素数計数関数の公式

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示