1
$\begingroup$

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)=\mathcal{O}(n^\epsilon)$ where $d(n)$ stands for number divisors $n$ has.

I would like to know why this is true?

$\endgroup$
  • 1
    $\begingroup$ The wikipedia article uses o, little o, not O, big O. Both are true. $\endgroup$ – Ross Millikan Dec 16 '18 at 21:41
  • 1
    $\begingroup$ @WesleyStrik sorry I eddited it..I would like to know why this is true? $\endgroup$ – נירייב שמואל Dec 16 '18 at 21:42
  • 1
    $\begingroup$ @RossMillikan I would like to know why this is true? I edited the page sorry. $\endgroup$ – נירייב שמואל Dec 16 '18 at 21:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Dec 16 '18 at 21:44
  • 1
    $\begingroup$ 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$ $\endgroup$ – Ross Millikan Dec 16 '18 at 21:52
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – נירייב שמואל Dec 16 '18 at 21:37
  • $\begingroup$ no, the more specific $$ d(n) \leq n^{ \left( \frac{1.0660186782977...}{\log \log n} \right) }. $$ $\endgroup$ – Will Jagy Dec 16 '18 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.