インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

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

自然数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.hatenablog.com
があります。

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に依らないことに注意)。従って、①より

\begin{equation}\begin{split} \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) \end{split}\end{equation}

を得る。これより、

\log d(n) \leq \exp (O(1/\varepsilon)) +\varepsilon \log n -②

となるが、十分大きいC > 0に対して

\displaystyle \varepsilon = \frac{C}{\log \log n}

とおけば、②の第一項は第二項にn \to \inftyで吸収される(0 < \delta < 1ならば、\log^{\delta}n = O(\log n/\log \log n)であることに注意)。

故に

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

が示された。 Q.E.D.

*1:Terence Taoのブログより