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 just wanted some help to prove that

$$\log_2 \log_2 y = \mathcal{o}(\log_2 y) + \mathcal{O}(1),$$ when $y = f(n) \in \mathcal{O}(n)$ and $y > 4$.

Thanks!

share|improve this question
    
Where is $y$ going to? –  Siminore Jul 1 '12 at 13:26
    
I would like to show it for all y. I should have been a bit more clear. . . Let y = f(n) \in O(n), where n tends to infinity. I'd like to prove it's true for any y under those circumstances. So, for instance, y could be a constant with respect to n, and then the O(1) term would be necessary. But I need a formal proof. –  Robert Jul 1 '12 at 13:29
    
By the way, this is false: try $y=1+o(1)$. –  Did Jul 1 '12 at 13:38
1  
Anyway, you can't use the Landau symbols without specifying when they should be used. Could you please write your formula without $\mathcal{o}$ and $\mathcal{O}$? –  Siminore Jul 1 '12 at 13:56
1  
Do you actually want to prove that: for every $\varepsilon>0$ there exists a constant $C_\varepsilon$ such that $\log_2 \log_2 y = \varepsilon \log_2 y + C_\varepsilon$ whenever $y>4$? –  Siminore Jul 1 '12 at 13:58
show 2 more comments

1 Answer 1

up vote 2 down vote accepted

To make things clear, I think that you are trying to show that for all sequences $u_n>4$, there exist a sequence $a_n\to 0$ and a constant $b$ such that for all $n$, $$\lg \lg u_n\le a_n\lg u_n + b$$ (The hypothesis $u_n=O(n)$ is not useful since the difficult cases are when the growth is slow, not when it is fast.)


The result is of course true when $u_n$ is non-decreasing (since it is either bounded or diverging).

But the result is false in the general case. Let $u_n = 5+n-\lfloor \sqrt n\rfloor^2$. We have $$u_n=\ 5,\ \ 5,6,7,\ \ 5,6,7,8,9,\ \ 5,6,7,8,9,10,11,\ \ \dots$$ so that it is possible to extract an arbitrarily slowly growing sequence from $u_n$.

Suppose the result is true and consider the subsequence $u_{\phi(n)}$ of $u_n$ formed by the elements where $$\frac{\lg u_n}{\lg \lg u_n}<\frac{1}{2a_n}$$ Because the right hand side diverges and $u_n$ hits each integer infinitely many times, each integer will eventually be reached by $u_{\phi(n)}$ so that it is not bounded.

We have $$\lg\lg u_{\phi(n)}\le a_n\lg u_{\phi(n)} + b < \tfrac 12 \lg\lg u_{\phi(n)} + b$$ $$\lg\lg u_{\phi(n)} < 2b$$ But this contradicts the fact that $u_{\phi(n)}$ is not bounded. So the result is false in general.


EDIT: I didn't see this, but in the comments Siminore asked a very different question:

For all $\varepsilon>0$, there is a constant $C_\varepsilon$ such that for all $y\ge 2$, $$\lg\lg y \le \varepsilon\lg y + C_\varepsilon$$

This version is true: $\lg\lg y/\lg y\to 0$ as $y\to+\infty$, so that there is an $M_\varepsilon$ such that for $y\ge M_\varepsilon$, we have $\lg\lg y/\lg y<\varepsilon$. But the continuous function $\lg \lg y - \varepsilon\lg y$ is bounded on $[2,M_\varepsilon]$, so calling $C_\varepsilon$ its maximum finishes the proof.

The reason why this works is twofold: $\varepsilon$ does not need to go to 0 as $y\to+\infty$, and $C_\varepsilon$ is allowed to diverge as $\varepsilon\to 0$ (in the first version, $b$ is fixed for obvious reasons).

share|improve this answer
1  
I suggested a different condition since this games with $\varepsilon$ and $C_\varepsilon$ are rather common and many people tend to confuse them with Landau symbols. In particular, somebody writes $O(1)$ to denote a constant. –  Siminore Jul 1 '12 at 15:51
    
Ah, thanks! This works! I appreciate the help. Thanks also for helping to formalize what I really wanted to know. :) –  Robert Jul 1 '12 at 21:02
add comment

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.