Growth rate of a divisor function

Question

Hi I read an very interesting article about divisor function:

https://en.wikipedia.org/wiki/Divisor_function#CITEREFHardyWright2008

I was wondering about a formula which appear under the Growth rate section :

for all $ \varepsilon>0$, $d(n)=o(n^\epsilon)$ and $d(n)=O(n^\epsilon)$ where $d(n)$ stands for number divisors $n$ has.

I would like to know why this is true?

Answer 1

It's true. There are many interesting inequalities involving $d(n)$

I will start off with the simplest type, $$ d(n) \leq \sqrt{3 n} $$ and $$ d(n) \leq 48 \left(\frac{n}{2520}\right)^{1/3} $$ and $$ d(n) \leq 576 \left(\frac{n}{21621600}\right)^{1/4}. $$ The first one has equality only at $n = 12,$ second only at $n =2520,$ third only at $n= 21621600.$ Instead of continuing with fractional powers $1/k$ the better results switch to logarithms. Reference is a 1988 paper by J. L. Nicolas in a book called Ramanujan Revisited.

With equality at $n = 6983776800 = 2^5 \cdot 3^3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$ and $d(n) = 2304,$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1.5379398606751... \right)} = n^{ \left( \frac{1.0660186782977...}{\log \log n} \right) }. $$ Full details of the proof appear in J.-L. Nicolas et G. Robin. Majorations explicites pour le nombre de diviseurs de n, Canad. Math. Bull., 26, 1983, 485--492. The next two appear in the dissertation of Robin, are repeated in the 1988 Nicolas survey article indicated.

With equality at a number $n$ near $6.929 \cdot 10^{40},$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1 + \frac{1.934850967971...}{\log \log n} \right)}. $$ Compare this one with Theorem 317 in Hardy and Wright, attributed to Wigert (1907), $$ \limsup \frac{\log d(n) \log \log n}{\log n} = \log 2. $$

With equality at a number $n$ near $3.309 \cdot 10^{135},$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1 + \frac{1}{\log \log n} + \frac{4.762350121177...}{\left(\log \log n \right)^2} \right)} $$

Answer 2

We'll prove that for every $\varepsilon>0$, there exists $N$ such that for $n>N$, $d(n)<n^\varepsilon$. For each $k\in\mathbb Z_0^+$, let $p_k$ be the $k$-th prime, and let $f_k:\mathbb R_0^+\to\mathbb R$ be the function such that for $x\in\mathbb R_0^+$, $$f_k(x)=\frac{x+1}{p_k^{\varepsilon x}}.$$ We'll make five key observations, which will together imply our main theorem.

---

1. For every $k\in\mathbb Z^+$, $f_k(x)$ is increasing for $x<\frac{1}{\varepsilon\log\left(p_k\right)}-1$, and decreasing otherwise.

We can verify that $$\frac{\mathrm d}{\mathrm dx}\,f_k(x)=\frac{1-\varepsilon\log(p_k)(x+1)}{p_k^{\varepsilon x}}.$$ The result follows easily.

2. For every $k\in\mathbb Z^+$, there exists $m\in\mathbb Z_0^+$ such that for every $n\in\mathbb Z_0^+$, $f_k(m)\ge f_k(n)$.

Because of 1, $f_k(x)$ attains a maximum value at $x=\frac{1}{\varepsilon\log(p_k)}-1$, is increasing to the left of it, and decreasing to the right of it. Clearly, either the floor or the ceiling of this number will satisfy the required condition. Let the maximum value of $f_k$ over the non-negative integers be $M_k$.

3. For sufficiently large $k$, $M_k=1$.

If $p_k\ge e^{1/\varepsilon}$, because of $1$, $f_k(x)$ will be decreasing, and its maximum value will be $f_k(0)=1$. We can therefore define $$M=\prod_{i=1}^\infty M_i,$$ as the product will only have finitely many terms different from $1$.

4. For all $k\in\mathbb Z^+$, there exists $\beta_k'\in\mathbb Z_0^+$ such that for $x\geq\beta_k'$, $f_k(x)<\frac{1}{M}$.

By L'Hopital, $$\lim_{x\to\infty}\frac{x+1}{p_k^{\varepsilon x}}=\lim_{x\to\infty}\frac{1}{\varepsilon\log(p_k)p_k^{\varepsilon x}}=0.$$ The result follows easily. Let the least possible value of $\beta_k'$ be $\beta_k$.

5. For sufficiently large $k$, $\beta_k\le 1$.

If $p_k>\max(e^{1/\varepsilon},(2M)^{1/\varepsilon})$, for all $x\ge 1$, $$f_k(x)\le f_k(1)<\frac{1}{M},$$ so that $\beta_k\le 1$. We can therefore define $$B=\prod_{i=1}^\infty\beta_i,$$ as the product will have only finitely many terms different from either $0$ or $1$.

---

Now, consider $n$ such that $d(n)\ge n^\varepsilon$, and let $n=\prod_{i=1}^\infty p_i^{\alpha_i}$ be its prime factorization. Since $d(n)=\prod_{i=1}^\infty(\alpha_i+1)$, this implies $$\prod_{i=1}^\infty f_i(\alpha_i)\ge1.$$ By 5, it's clear that for any $i$, $\alpha_i$ can only take integer values from $0$ to $\beta_i-1$, since otherwise, the product would be less than $M\cdot\frac{1}{M}=1$. There are therefore at most $B$ possible choices for the exponents $\alpha_i$ – taking $N$ greater than all the values of $n$ they generate is enough to finish the problem. $\blacksquare$