4
$\begingroup$

I've been looking at this the past few days, but can't figure it out. Maybe I don have enough mathematical background, but most probably I'm overlooking something super basic from times long gone. Anyway, my problem:

What is the complexity of:
$\limsup _{n \to \infty} \; d(n)$

With $d(n)$ the divisor function. I know that the average complexity is $O(log n)$ and that the infinum is $2$ (for primes), but I can't figure out the complexity of the limit of the supremum.

Ridicule and actual solutions both much appreciated. Also, feel free to retag, I have no clue under what I should tag this.

[Edit] I should have mentioned that I was aware of the Wikipedia article. Here's what I don't get about it. Wikipedia states:

$\limsup_{n\to\infty}\frac{\log d(n) \log\log n}{\log n} = \log 2$

This, I assume leads to:

$d(n) = O(n^{\frac{\log 2}{\log \log n}})$

But then, as $n \to \infty$, the exponent will go to $0$, since $\lim _{n \to \infty} \log \log n = \infty$. And thus

$\lim _{n \to \infty} d(n) = O(1)$

That seems wrong, am I making a mistake? And if so, where?

  • 2
    See also http://terrytao.wordpress.com/2008/09/23/the-divisor-bound/2011-04-22

3 Answers 3

1

You can find the answer on wikipedia:

http://en.wikipedia.org/wiki/Arithmetic_function#Summation_functions

$\limsup_{n\to\infty}\frac{\log d(n) \log\log n}{\log n} = \log 2$

with a reference to the book of Hardy & Wright, §§ 18.1–18.2.

(To get an approximate idea, you can consider what happens to the product of the first $k$ primes that have sizes of about $k\log k$ each. This product has $2^k$ divisors. Of course, this is not a proof of the above result.)

  • 0
    @user9325 Please see the edit to my question.2011-04-22
2

(answering your edited question): When you have an expression $x^y$ where $y$ tends to $0$ as some parameter (say $n$) tends to infinity, you can't conclude that the expression tends to a constant. Yes, $y$ goes to $0$, but $x$ may tend to $\infty$ (as it does in your case). Who's winning? You should be able to come up with examples where the result is $0$, $\infty$ or anything in between. Give it a try.

Also, from $\limsup \frac{d(n)\log \log n}{\log n} = \log 2$ you can immediately see that there's no way $d(n)$ would be $O(1)$. Had it been, the LHS would go to $0$.

1

Since $d(2^k)=k+1$, the lim sup is $\infty$.

  • 0
    Yes, that's what I meant. I was, however, aware of the Wikipedia article, should have stated that, sorry. I've updated my question a bit more.2011-04-22