最近,UHAのグミサプリが気に入っていて,お菓子気分でボリボリだべています.
シンプルにうまいです.良い感じに酸っぱい.
錠剤の形をしていると医薬品に見えてしまうので,医薬品との違いを明確にするという意味でもいいかも.
それはそうとして,Shoup『A Computational Introduction to Number Theory』の演習問題をやっていきます.
なお書影を出すためにAmazonの商品ページにリンクを貼っていますが,この本は著者により無料公開されています.興味のある方はぜひどうぞ!
今回やるのは演習問題5.3です.
問題文とその解説
Show that $\sum_{p \leq x} 1/ \log p = \Theta (x / (\log x)^ 2)$.
シンプルな問題です.漸近評価
$$ \sum_{p \leq x} 1/ \log p = \Theta (x / (\log x)^ 2) $$
を示せという問題ですね.
本書では素数定理の弱い形である $\pi(x) = \Theta(x/ \log x)$ は既に証明していますので,それを使っていけということでしょう.
また,既にチェビシェフのシータ関数 $\theta(x) = \sum_{p \leq x} \log p$ が $\theta(x) = \Theta(x)$ という漸近評価を持つことも示しましたので,それを使ってもいいですね.
回答
与えられた関数を $ψ(x)$ としておきましょう.つまり $ψ(x) = \sum_{p \leq x} 1/\log p$ です.
下界
上界と下界を別々に示します.まずは下界から.
まず最初に思いつく不等式評価 $\log p \leq \log x$ を用いることにより
$$ \psi(x) \geq \frac{\pi(x)}{\log x} $$
を得ます.チェビシェフの定理により $\pi(x) = \Omega(x/\log x)$ なので,$ψ(x) = \Omega(x/(\log x)^ 2)$ です.
下界の証明はあっさり終わってしまいました.
上界
この調子で上界の証明もさくさくやっていきましょう!……と言いたいところですが,上界はちょっと難しかったです.
シータ関数 $θ(x)$ の評価をうまく使えないか試行錯誤しましたが,失敗.
数学的帰納法で示すというアイデアも頓挫しました.
最終的に $\sqrt{x}$ より大きいか小さいかで区切るというアイデアを試したところ,これが正解でした.
実際にやると
$$ ψ(x) - ψ(\sqrt{x}) \leq \frac{2}{\log x} \cdot ( \pi(x) - \pi(\sqrt{x}) ) $$
という不等式が得られます.
$\pi(\sqrt{x})/ \pi(x)$ は $x$ が大きいときにはゼロに収束します.したがって
$$ ψ(x) - ψ(\sqrt{x}) = O(x/ (\log x)^ 2) $$
であります.
ここで $\log p \geq \log 2$ という自明な評価を使えば $\psi(\sqrt{x}) = O(\sqrt{x} / \log x)$ が示せるので,特に $\psi(\sqrt{x}) = O(x/ (\log x)^ 2)$ でもあります.
ゆえに $ψ(x) = O(x/(\log x)^ 2)$ が結論できます.
感想
「難しいなぁ」と思って悩んでいたんですが,いろいろいじっているうちにできました.
$ψ(\sqrt{x})$ が結構小さいということに気づくのに時間がかかってしまって,当たり前のことに苦しんでいたのでちょっと反省しています.