因數個數函數的上界

本文簡述因數個數函數的一個上界：對任意正實數 $k$，均存在一正實數 $c$ 使得對任意正整數 $n \comma$其因數個數不多於 $cn^k \period$

1　正因數的個數

1.1　因數個數函數

對任意正整數 $n$，我們用 $d(n)$ 表示 $n$ 的正因數的個數；函數 $d$ 稱為因數個數函數（number-of-divisors func­tion）。

1.2　上界

定理 1 說明 $d(n) = n^{o(1)} \period$

定理 1　對任意正整數 $n$ 與任意正實數 $k$，有 \[ \begin{split} \rule[-2.8ex]{0pt}{6.8ex}\frac{d(n)}{n^k} \leq \exp\biggl(\frac{2^{1/k}}{k \ln 2}\biggr) \period \end{split} \]

證明　考慮質因數分解 \[\begin{split} n = \prod_{i=0}^{r-1} p_i^{a_i} \comma \end{split}\] 其中 $r$ 為非負整數，$p_0, p_1, \ldots, p_{r-1}$ 為滿足 $p_0 < p_1 < \cdots < p_{r-1}$ 的質數，且 $a_0, a_1, \ldots, a_{r-1}$ 為非負整數。設 \[\begin{split} \ell = \bigl|\bigl\{i \in \{0, 1, \ldots, r-1\}: p_i^k < 2\bigr\}\bigr| \period \end{split}\]

注意到我們有 \[ \begin{split} \rule[-2.8ex]{0pt}{6.8ex}\frac{d(n)}{n^k} = \frac{1}{n^k} \prod_{i=0}^{r-1} (a_i + 1) = \prod_{i=0}^{r-1} \frac{a_i + 1}{p_i^{a_ik}} \period \end{split} \]

對於 $i \in \{0, 1, \ldots, \ell-1\}$，由於 $p_i \geq 2$，故 \[ p_i^{a_ik} \geq 2^{a_ik} = \exp(a_ik \ln 2) > a_ik \ln 2 \comma \] 因而 \[ \begin{split} \rule[-2.8ex]{0pt}{6.8ex} \frac{a_i + 1}{p_i^{a_ik}} \leq \frac{a_i}{p_i^{a_ik}} + 1 < \frac{1}{k \ln 2} + 1 \leq \exp\biggl(\frac{1}{k \ln 2}\biggr) \period \end{split} \]

對於 $i \in \{\ell, \ell+1, \ldots, r-1\}$，由於 $p_i^k \geq 2$，我們有 \[ \begin{split} \rule[-2.8ex]{0pt}{6.8ex} \frac{a_i + 1}{p_i^{a_ik}} \leq \frac{a_i + 1}{2^{a_i}} \leq 1 \period \end{split} \]

因而 \[\begin{split} \rule[-2.8ex]{0pt}{6.8ex} \frac{d(n)}{n^k} \leq \prod_{i=0}^{\ell-1} \exp\biggl(\frac{1}{k \ln 2}\biggr) = \exp\biggl(\frac{\ell}{k \ln 2}\biggr) \leq \exp\biggl(\frac{2^{1/k}}{k \ln 2}\biggr) \comma \end{split}\] 故得$\textrm{證。}\mkern6mu\blacksquare$

範例 1　對 $k = 1/3$ 套用定理 1，可得 $d(n) \leq \exp(24/\ln 2)n^{1/3} < 2^{50}n^{1/3}$。

參考資料