約数個数関数のラマヌジャンによる評価

この記事は日曜数学 Advent Calendar 2017 - Adventarの14日目の記事です。9日目はasangi_a4acさんによる

itonayuta60.hateblo.jp

でした。

クリスマスが待ち遠しいですね。Advent Calendarの日程も半分を超えていますが、クリスマスまでもう少しの辛抱です。

今日はRamanujanの論文を一つ読んでみようと思います。選んだ論文は

S. Ramanujan, On the number of divisors of a number, Journal of the Indian Mathematical Society, VII, 1915, 131-133.

です。

論文は5つのセクションからなり、正整数 $N$ の正の約数の個数 $d(N)$ の上からの評価を与える公式を幾つか示すことが目的の論文となっています。約数は正の約数のみを考えることにしましょう。

1. 自明な評価

$d$ が $N$ の約数であれば、必ずその共役な約数 $d'$ であって $dd'=N$ なるものが存在する。これは $1$ から $\sqrt{N}$ までの $N$ の約数の個数は $\sqrt{N}$ から $N$ までの $N$ の約数の個数に等しいことを示している。 $N \geq 3$ であれば $1$ から $N$ の中に $N$ の約数でない整数があることに注意すると、

$d(N) < 2\sqrt{N}$

がわかる。

2. $N$ の素因数分解が完全に判明している場合

$N$ の素因数分解が $N=\prod_{i=1}^nq_i^{a_i}$ であったとする。このとき、 $d(N)=\prod_{i=1}^n(1+a_i)$ である。相加相乗平均の不等式より

$\displaystyle \frac{1}{n}\sum_{i=1}^n(1+a_i)\log q_i > \sqrt[n]{\prod_{i=1}^n(1+a_i)\prod_{i=1}^n\log q_i}$

なので

$\displaystyle \frac{1}{n}\left(\sum_{i=1}^n\log q_i+\log N\right) > \sqrt[n]{d(N)\prod_{i=1}^n\log q_i}$

であり

$\displaystyle d(N) < \frac{\left(\frac{1}{n}\log(N\prod_{i=1}^nq_i)\right)^n}{\prod_{i=1}^n\log q_i}$

が成り立つ。

3. $N$ の素因数の個数のみが判明している場合

$N$ の素因数の個数が $n$ 個であるとする。 $p_i$ を $i$ 番目の素数とする。 $N$ の素因数分解が $N=\prod_{i=1}^nq_i^{a_i}$ であれば、 $N':=\prod_{i=1}^np_i^{a_i}$ とすると $d(N')=d(N)$ が成り立つ。§2の結果より

$\displaystyle d(N') < \frac{\left(\frac{1}{n}\log(N\prod_{i=1}^np_i)\right)^n}{\prod_{i=1}^n\log p_i}$

が成り立つので、結局

$\displaystyle d(N) < \frac{\left(\frac{1}{n}\log(N\prod_{i=1}^np_i)\right)^n}{\prod_{i=1}^n\log p_i}$

と評価できる。

4. $N$ について何も知らない場合

$a_i$ を非負整数として $N= \prod_{i=1}^{\infty}p_i^{a_i}$ と表す。また、 $h > 0$ を任意にとって、 $x > 0$ を $x^h=2$ で定める。このとき、

$\displaystyle \frac{d(N)}{N^h} = \prod_{i=1}^{\infty}\frac{1+a_i}{p_i^{ha_i}}.$

$p > x$ であれば

$\displaystyle \frac{1+a_p}{p^{ha_p}} \leq \frac{1+a_p}{x^{ha_p}}=\frac{1+a_p}{2^{a_p}} \leq 1$

なので、 $\pi(x)$ を $x$ 以下の素数の個数とすれば

$\displaystyle \frac{d(N)}{N^h} \leq \prod_{i=1}^{\pi(x)}\frac{1+a_i}{p_i^{ha_i}} \leq \prod_{i=1}^{\pi(x)}\frac{1+a_i}{2^{ha_i}}$

が得られる。ここで、 $a$ の関数として増減表でも書いてみると

$\displaystyle \frac{1+a}{2^{ha}} \leq \frac{2^h}{he\log 2}$

がわかるので( $a=(h\log 2)^{-1}-1$ で最大値をとる)、

$\displaystyle \frac{d(N)}{N^h} \leq \left(\frac{2^h}{he\log 2}\right)^{\pi(x)}$

を得る。 $h=\log 2/\log x$ なので、

$\displaystyle d(N) \leq N^{\frac{\log 2}{\log x}}\left(\frac{2^{\frac{\log 2}{\log x}}\log x}{e(\log 2)^2}\right)^{\pi(x)}.$

$e^{\frac{1+2\log \log 2}{(\log 2)^2}} = 6.04737\cdots$ なので、 $x \geq 6.05$ であれば $2^h < e(\log 2)^2$ が成り立ち*1、

$\displaystyle d(N) < 2^{\frac{\log N}{\log x}}(\log x)^{\pi(x)}$

なる評価が得られる。

5. $N$ について何も知らない場合( $N \to \infty$ における漸近不等式)

$x=\frac{\log N}{(\log \log N)^2}$ とおき、 $N \to \infty$ における漸近挙動を考える。自明に $\pi(x) = O(x)$ であることに注意する。

$\begin{align} \log x &= \log \log N+O(\log \log \log N) \\ \frac{\log N}{\log x}&=\frac{\log N}{\log \log N} + O\left(\frac{\log N \log \log \log N}{(\log \log N)^2}\right) \\ \pi(x)\log \log x &= O(x \log \log x) = O\left(\frac{\log N \log \log \log N}{(\log \log N)^2}\right) \end{align}$

が成り立つので、§4の不等式より

$\begin{align} \log d(N) &< \frac{\log 2\log N}{\log x} + \pi(x)\log \log x \\ &= \frac{\log 2\log N}{\log \log N}+O\left(\frac{\log N\log \log \log N}{(\log \log N)^2}\right)\end{align}$