最近就職して，毎日出社してもそもそと仕事をしています．
オオサンショウウオかわいいねって言われたのでよかったです．
それはそうとして『A Computational Introduction to Number Theory and Algebra』の演習問題をやっていきましょう．
今回やるのは演習5.2です．
問題文
For each positive integer $n$, denote the number of distince primes dividing $n$. Show that $\omega(n) = O(\log n / \log \log n)$.
回答
今回はあまり自信がないですが，やっていきましょう．
今回の問題は，異なる素因数の個数 $\omega(n)$ の上界を求めなさいといっています．いい方を変えれば，異なる素因数の積の下界を求めろと言っているともとれますね．
まずは何も考えずに素朴にやってみます．
自明な考察
整数 $n$ に対して，
$$ n = \prod_{1 \leq i \leq r} p_i^ {e_i} $$
という素因数分解が得られていたものとします．このとき各々の素数 $p_i$ は（当たり前だけど！）２以上なので，$n \geq 2^ r$ です．したがって $r \leq \log_2 n$. つまり $\omega(n) = O(\log n)$ です．
なんとも当たり前．いい方を変えれば，これをもう少し工夫してオーダーを $\log \log n$ の分だけよくしなさいという問題であるわけです．
再び自明な考察
第５章ではチェビシェフの定理をやりましたから，それを使って改善せよということなのだと思うのですが，実はまだ自明な考察で改善の余地があるのでそれを先にやります．
再び
$$ n = \prod_{1 \leq i \leq r} p_i^ {e_i} $$
という素因数分解が得られていたものとします．このとき素因数 $p_i$ の添字 $i$ は $p_1 \leq p_2 \leq \cdots \leq p_r$ となるように振られているものとします．
そうすると，$p_i \geq 1 + i$ が常に成立しますので $n \geq (r+1)!$ を得ます．$r+1$ というのはちょっと中途半端なので $n \geq r!$ でいきます．
ここから，どうやら $\omega(n) = O(\log n / \log \log n)$ が示せるようです．
証明: 背理法で証明しましょう．仮に $\omega(n) = O(\log n / \log \log n)$ でなかっとします．つまり，どんな(大きな)数 $M$ に対しても
$$ r > \frac{M \log n}{ \log \log n} $$
を満たすような整数 $n$ が無限に存在します．
この仮定と $r! \geq (r/e)^ r$ というスターリングの公式の弱い形とを用いると，$\log n > M \log n$ を満たす整数 $n$ が無数にあることが示せます．しかしそんなはずはないので，これは矛盾です．□
この証明のまずいポイントは，第５章の内容をなんにも使ってないことです．
自明な考察だけで終わってしまった．
せっかく $n$ 番目の素数の大きさが $\Theta( n \log n)$ であることとか示したのに，使わずに示せてしまった．だから多分何か間違ってるんですが，どこで間違えたかわからないのでこのまま公開することにします．
感想
この「異なる素因数の数」の漸近上界，素数定理を使えば改善できそうな気がするんですけど意外と難しくて途中でやめてしまいました．
