素数全書練習問題1.14 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

正整数nの因子の数をd(n)とするとき、任意の $\epsilon>0$ について、 $d(n)=O(n^{\epsilon})$ を証明せよ、という問題であるがなかなか不思議な結果である。ヒントに沿って考えてみる。

pを素数として、 $q=p^k$ とする。このとき $d(q)=k+1$ である。 $d(q)=k+1>q^{\epsilon}=p^{\epsilon k}$ を満たすpとkを考えると、kを動かすと右辺が指数関数であるのでpを固定するとkに上限があり、また、pに関して右辺は単調増加(して発散）するので、pが大きくなるとその上限は小さくなる。よって有限個のp,kの組み合わせでしか、この不等式を満たせない。□

次に一般のnを考える。nを素因数分解して、 $n=p_1^{k_1}p_2^{k_2}\cdots p_N^{k_N}$ とする。 $q_i=p_i^{k_i}$ と置くと、 $d(n)=\prod_{i=1}^N d(q_i)$ である。
与えられた $\epsilon$ に対して、ヒントの例外的なqを除くと、 $d(q_i)\le q_i^{\epsilon}$ となり、これの辺々をiについて積を取ると $d(n)\le n^{\epsilon}$ が導ける。qが大きくなると、 $d(q)<< q^{\epsilon}$ となっていくため、これはどうやら $d(n)=o(n^{\epsilon})$ である。