3
$\begingroup$

I have been searching for a bound of the divisor function $d(n)$, meaning the number of divisors of n. So far I have found that it can be bounded by $ d(n) \le e^{O(\frac{\log n}{\log \log n})}$ Wigert has proven the constant is $\log 2$ so $ d(n) \le e^{(\log 2+ o(1)) \frac{\log n}{\log \log n}} $ However, when I tried to check that bound on a computer, it did not seem right. I have drawn $d(n)$ (in blue), $e^{\frac{\log n}{\log \log n}}$ (in red) and $e^{\log 2 \frac{\log n}{\log \log n}}$ (in green) on the following graph:

enter image description here

Furthermore, when I plot $\frac{\log d(n)}{\log n / \log \log n}$, it does not seem to have $\log 2$ as a limit either. See this other graph:

enter image description here

It appears the constant 1 is a much better fit !

So my question is: is Wigert's bound only true for large $n$ (i.e larger than $10^6$) ?

My confusion comes from the second equation, which is clearly a bound (see this post on Tao's blog) and the result of Wikipedia, which is a limit.

  • 3
    E. R. Canfield, P. Erdos, C. Pomerance, On a problem of Oppenheim concerning Factorisato Numerorum, J. Number Theory 17 (1983) 1-28, Table 1, column "n". [R. J. Mathar, mathar(AT)strw.leidenuniv.nl), Mar 06 2009] has an additional factor of log log log n in the numerator of the exponential. And 10^6 is quite small.2011-09-11

2 Answers 2

3

If you want to see how the bound is approached for bigger values of $n$ you might want take a look to the last graph in this page about highly composite numbers and the tables linked there. There you see how the ratio $\log(d(n))/\mathrm{Li}(\log(n))$ approaches $\log 2$ as $n$ goes through the highly composite numbers, (ie numbers such that $d(n)>d(m)$ for all $m=1,2,\dots, n-1$).

As $\mathrm{Li}(x) \sim x/\log x$ as $x \to \infty$ the asymptotic is equivalent to the one you state but it seems to work much better, as an example the last entry $n$ in the tables (an integer with 17000 decimal digits) gives $ \frac{\log d(n)}{\mathrm{Li}(\log n)} = 0.6946\ldots \quad \text{but} \quad \frac{\log d(n)}{\log n/\log\log n}=0.7793\ldots$

  • 0
    $\mathrm{Li} x$ is the logarithmic integral $=\int_2^x \frac{ dt}{\log t}$ see [here](http://en.wikipedia.org/wiki/Logarithmic_integral_function).2011-09-12
3

Are you confusing the notions of bound and limit? Consider a function $f(n)$ which is 1 unless $n$ is a power of 2, in which case $f(n)=n$. This function is bounded by $n$; $f(n)\le n$. But it doesn't have $n$ as a limit (or to put it another way, $f(n)/n$ doesn't have 1 as a limit). The function isn't bounded by 1, but the constant 1 looks like a much better fit for the graph than the bound $n$.

$d(n)$, like $f(n)$, is generally quite small, but occasionally very large. The occasional large value pushes the bound up.

  • 0
    Thank you for clearing that up. But I understood that the second bound should be true for all n, and it does not look like it. I have edited my question.2011-09-12