まずお知らせ．
無料で読める数学書として，符号理論の本を発見したので追加しておきました．
興味のある方はこの機会にぜひどうぞ．
引き続き初等整数論を勉強していきますが，今回は『はじめての数論』はやめて『A Computational Introduction to Number Theory and Algebra』を読んでいきます．
計算的な側面を強調する本ですが，素数分布の話についてもおもしろいことが結構書かれています．
今回やるのは演習問題 5.1 です．
問題文
For each positive integer $n$, let $p_n$ denote the $n$th prime. Show that $p_n = \Theta(n \log n)$.
Exercise 5.1
回答
ではやっていきましょう．
本書では直前に次のチェビシェフの定理が証明されています．
これは素数定理の弱い形ですが，素数定理ほど証明は難しくありませんし，初等的かつ比較的容易に示せる割に示唆的な定理です．これを使って解けということだと思われます．
関数 $\pi(n)$ を使って直接 $p_n$ を表現するのは難しそうです．
その代わりにどうしたらいいでしょうか．
任意の $n$ の関数 $M$ に対して $p_n \leq M$ であることと，$\pi(M) \geq n$ は同値になります．これを使いましょう．
$\pi(x) = \Omega(x/ \log x)$ により，ある正の数 $C$ が存在して，十分大きな整数 $n$ に対して
$$ \pi(x) \geq \frac{C x}{\log x} $$
が成り立ちます．ここで $x = m \log m$ を代入してごちゃごちゃすると，$\pi(m \log m ) \geq C m$ を得ます．あとは細かく書くほどのことはなくて，この式を $p_n$ を使って書き直せば良いです．逆も同じです．
感想とまとめ
素数定理の証明を私が最初に読んだのは，スタインシャカルチの『複素解析』だった気がします．そのときには，発想の経緯が全くわからなくて「いったい何食ったらこんな変数変換とか思いつくんだろうか」と感じた記憶があります．
でも，チェビシェフの定理の証明を読んでいると，素数定理の証明で登場するあまりにも賢い変形の原型のようなものが見られて，どのように発想されたのかが部分的に納得できました．
チェビシェフの定理の証明も大変かしこい（そして理解が追いつかない）ことに変わりはないのですが，短いのでまだ徹底的にいじくり回して理解しようという気になれます．
初等的な手法でどこまでできるかを知っておくのは大事だなあと思いました．
