オイラー関数についての不等式
以前からオイラー関数 を何回反復させれば初めて
になるのか興味がありました。特に明確な同機があるわけではないのですが、恐らく約一年前に書いた下の記事の内容がそれとやや関係しているからだったかもしれません。（関係ないですが、しばらく前に書いた記事って今とテンションが違くて恥ずかしいですね。）
まあ、動機は何でもいいです。このことに関して何度か調べても、なかなかオイラー関数の反復について書いているサイトが見つからなかったのですが、今回考察して大分進捗があったのでまとめようと思います。
まず、今回使った関数の定義（といっても大層なものではありませんが）から説明します。１つ目は で、これはオイラー関数を
回反復させたものを表します。再帰的に定義するなら
となるでしょう。
２つ目は で、これは
となるような最小の
を表します。
の場合は
となる
とも言い換えられるでしょう。このときは
の場合
と個別で定義することになります。
さて、興味があるのは がどのような範囲にあるのかということで、結論としては
が考察で得られました。
証明は定理１から７に分けて行いました。結論は上からの評価が定理４、下からの評価が定理７で、定理１～３、５～６はそれぞれを証明するための準備です（補題とするべきだったでしょうか）。
さて、さっそく証明していきます。
については下の記事を参考にしてください。飽くまで
の言い換えです。
最後の不等号に がついていないのは
だからです。この不等式は完全に自力で求めたので、あっているか少し心配ではあります。
自体のときは定理１のようにまったく抑え込めないのですが、
以降になると
が正偶数であることから抑え込めるようになるのがポイントです。
さて、ここまでの結果から の上からの評価が可能になります。
次は下からの評価を証明していきます。
これは証明は兎も角、不等式自体はWikipediaに書いていました（オイラーのφ関数 - Wikipedia）。ただ「簡明な下界」と書いてあり、かなり緩い評価ではあるようです。
この結果から の下からの評価が証明できます。
以上から という結果が得られました。ただ、上からの評価はそこそこ良さそうですが、下からの評価がかなり緩いようです。もっときつくて、かつ扱いやすい
の下からの評価があればよいのですが…。唯一この評価の良い点を挙げるとすれば、上下の評価に
が含まれていて見栄えが良いというところでしょうか。
少なくとも約一年前の記事に関わるのは上からの評価だけなので、とりあえずは満足です。もっとよい下からの評価があれば、また書こうと思います。
ではまた。
