オイラーの φ関数の漸近挙動 後編 - Ex5.5

Shoup『A Computational Introduction to Number Theory and Algebra』を読んでいきます．

A Computational Introduction to Number Theory and Algebra

書影を得るためにAmazonのリンクを貼っていますが，この本は著者のＨＰからＰＤＦが無料でＤＬできます．単に安いだけでなくとてもおもしろい本なので，興味のある方はぜひどうぞ．

今回やるのは演習問題5.5です．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]

問題文

原文はこちら．

The previous exercise showed that $φ(n)$ could be as small as (about) $n/\log \log n$ for infinitely many $n$. Show that this is the "worst case," in the sense that $φ(n) = \Omega(n / \log \log n)$.

Exercise 5.5

訳すとしたらこうです．

前回の演習問題で無限に多くの $n$ に対して $φ(n)$ がおおよそ $n/ \log \log n$ まで小さくなることを示した．この下界が最善であること，つまり $φ(n) = \Omega(n / \log \log n)$ であることを示せ．

回答

φ関数の定義から

$$ φ(n) = n \prod_{p \ \mid \ n} (1 - 1/p) $$

が成り立ちます．

ここまではいいですね．この後が問題です．

方針１: Mertensの定理を使う

前回の問題同様，まずMertensの定理を使ってみます．

Mertensの定理

$$ \prod_{p \leq x} (1- 1/p) = \Theta(1/ \log x) $$

$n$ の素因数のうち最大のものを $q$ としましょう．

そうするとMertensの定理から

$$ φ(n) = \Omega(n / \log q) $$

が示せます．

後は $q = O(\log n)$ が示せれば良いわけですが，しかしそれは無理です．

$n$ が素数の平方であるようなときには $q = \Theta(\sqrt{n})$ なので，示せるわけがありません．

$q = O(n)$ は明らかに成り立つので，このアプローチで示せるのは $φ(n) = \Omega(n / \log n)$ までです．

したがって別のアプローチを採る必要があります．

方針2: 前回の演習問題の結果を使う

前回の演習の結果を使うのも鉄板の方針です．

$n$ の素因数の個数を $\omega$ とします．

$p_i$ は小さいほうから $i$ 番目の素数なので，

$$ φ(n) = n \prod_{p \ \mid \ n} (1 - 1/p) \geq n \prod_{1 \leq i \leq ω} (1 - 1/p_i) $$

が成り立ちます．

したがって

$$ \frac{φ(n)}{n} \geq \frac{φ(P_{ω})}{ P_ω} $$

です．ですから前回の演習問題の結果により $φ(n)/n = \Omega(1/ \log \log P_ω)$ です．

明らかに $P_ω = O(n)$ なので，これにより $φ(n) = Ω(n/ \log \log n)$ が言えます．

意外とうまくいきました．

感想

オイラーの φ関数の漸近挙動って示せるんですね．

なんだか意外．もっと難しいというイメージだったので．