Complexity of divisor function

Question

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?

Answer 1

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

Answer 2

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.)

Answer 3

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