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?

$\endgroup$
3
  • $\begingroup$ Yes, you are making a mistake. $\endgroup$
    – Phira
    Commented Apr 22, 2011 at 13:35
  • $\begingroup$ @user9325 You don't say :). $\endgroup$
    – AVH
    Commented Apr 22, 2011 at 13:48
  • 2
    $\begingroup$ See also terrytao.wordpress.com/2008/09/23/the-divisor-bound $\endgroup$
    – lhf
    Commented Apr 22, 2011 at 21:45

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @user9325 Please see the edit to my question. $\endgroup$
    – AVH
    Commented Apr 22, 2011 at 11:38
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – AVH
    Commented Apr 22, 2011 at 10:34
  • $\begingroup$ This not the sequence with the most divisors, compare $d(30)=8$ and $d(32)=6$. $\endgroup$
    – Phira
    Commented Apr 22, 2011 at 10:55
  • $\begingroup$ Ah, do you mean the growth of $f(n) = \sup_{m\le n} d(m)$? $\endgroup$
    – lhf
    Commented Apr 22, 2011 at 11:03
  • $\begingroup$ @Darhuuk, see en.wikipedia.org/wiki/Divisor_function#Approximate_growth_rate $\endgroup$
    – lhf
    Commented Apr 22, 2011 at 11:11
  • $\begingroup$ 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. $\endgroup$
    – AVH
    Commented Apr 22, 2011 at 11:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .