# Growth rate of a 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?

• The wikipedia article uses o, little o, not O, big O. Both are true. Commented Dec 16, 2018 at 21:41
• @WesleyStrik sorry I eddited it..I would like to know why this is true? Commented Dec 16, 2018 at 21:42
• @RossMillikan I would like to know why this is true? I edited the page sorry. Commented Dec 16, 2018 at 21:43
• Basically to get lots of divisors you either need lots of prime factors and the primes get bigger or you need lots of factors of a small prime, but the number of divisors grows very slowly (logarithmically) with the number of factors. Either way you need an enormous number to have lots of factors. Commented Dec 16, 2018 at 21:44
• The formulas quoted in Will Jagy's answer show that $d(n)\lt n^\epsilon$ for $n$ large enough and any given $\epsilon \gt 0$ Commented Dec 16, 2018 at 21:52

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)}$$

• If I understood you currently the full proof of the original formula that I posted appears at J.-L. Nicolas et G. Robin. Majorations explicites pour le nombre de diviseurs de n, Canad. Math. Bull., 26, 1983, 485--492? Commented Dec 16, 2018 at 21:37
• no, the more specific $$d(n) \leq n^{ \left( \frac{1.0660186782977...}{\log \log n} \right) }.$$ Commented Dec 16, 2018 at 21:46

We'll prove that for every $$\varepsilon>0$$, there exists $$N$$ such that for $$n>N$$, $$d(n). 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.

1. 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$$.

1. 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$$.

1. 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$$.

1. 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$$