Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Yes, you are making a mistake. –  Phira Apr 22 '11 at 13:35
    
@user9325 You don't say :). –  Darhuuk Apr 22 '11 at 13:48
2  
See also terrytao.wordpress.com/2008/09/23/the-divisor-bound –  lhf Apr 22 '11 at 21:45

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
@user9325 Please see the edit to my question. –  Darhuuk Apr 22 '11 at 11:38

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

share|improve this answer

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

share|improve this answer
    
I might be mistaken, but for your example, isn't the complexity $O(log_2 n)$? I understand that the limit, is per definition $\infty$, I want to know the complexity of the supremum. –  Darhuuk Apr 22 '11 at 10:34
    
This not the sequence with the most divisors, compare $d(30)=8$ and $d(32)=6$. –  Phira Apr 22 '11 at 10:55
    
Ah, do you mean the growth of $f(n) = \sup_{m\le n} d(m)$? –  lhf Apr 22 '11 at 11:03
    
    
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. –  Darhuuk Apr 22 '11 at 11:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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