約数個数関数の上からの評価

自然数 $n$ の約数の個数を $d(n)$ で表します。

$d(n)$ は次の公式で求めることができます：

公式 $n=p_1^{a_1}\cdots p_k^{a_k}$ と $n$ が素因数分解されているとき、

$d(n)=(a_1+1)\cdots (a_k+1)$

が成り立つ。

cf.)
mathtrain.jp

以前の記事で $d(n)$ を用いた例としてサブライム数 - INTEGERSがあります。

$d(n)$ の上からの評価として、自明な評価

$d(n) \leq n$

がありますが、この記事では次の便利な評価を与えます:

定理 $n \to \infty$ において、

$\displaystyle d(n) \leq \exp \left( O\left( \frac{\log n}{\log \log n} \right) \right)$

が成り立つ。

証明*1. $\varepsilon = \varepsilon (n)$ は $n \to \infty$ のときに $\varepsilon \to 0$ なる関数であり、後で指定する。 $d(n)$ の公式より、 $n=p_1^{a_1}\cdots p_k^{a_k}$ と素因数分解されていれば

$\displaystyle \frac{d(n)}{n^{\varepsilon}} = \prod_{j=1}^k\frac{a_j+1}{p_j^{\varepsilon a_j}}$ -①

が成立する。素因子の大きさによって場合分けを行う。

$p_j \geq \exp (1/\varepsilon )$ のとき:

$p_j^{\varepsilon a_j} \geq \exp (a_j) \geq 1+a_j$

なので、 $\frac{a_j+1}{p^{\varepsilon a_j}} \leq 1$ である。

$p_j \leq \exp (1/\varepsilon )$ のとき:

$p_j^{\varepsilon a_j} \geq \exp (\varepsilon a_j \log p_j) \geq 1+\varepsilon a_j\log p_j$

より、

$\displaystyle \frac{a_j+1}{p_j^{\varepsilon a_j}} \leq \frac{a_j+1}{1+\varepsilon a_j\log p_j} \leq O\left( \frac{1}{\varepsilon \log p_j} \right)$

が成り立つ(ビッグ $O$ の定数は $a_j$ に依らないことに注意)。従って、①より

$\displaystyle \frac{d(n)}{n^\varepsilon} \leq \prod_{\substack{p < \exp (1/\varepsilon) \\ p:\text{素数}}}O\left( \frac{1}{\varepsilon \log p} \right) \leq \prod_{\substack{p < \exp (1/\varepsilon) \\ p:\text{素数}}}O\left( \frac{1}{\varepsilon} \right) \frac{1}{\log 2} \leq O\left( \frac{1}{\varepsilon} \right)^{\exp (1/\varepsilon )} = \exp \left( \exp (O(1/\varepsilon ) ) \right)$