1
$\begingroup$

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!

  • 0
    Where is $y$ going to?2012-07-01
  • 0
    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.2012-07-01
  • 0
    By the way, this is false: try $y=1+o(1)$.2012-07-01
  • 0
    Let's choose y > 4, to avoid these issues. (I should have also said that. . . .) And, when I say log, I mean log_2. I've updated the original post to reflect the clarifications I should have included.2012-07-01
  • 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}$?2012-07-01
  • 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$?2012-07-01
  • 0
    Yes I think so, though the equality probably should be $\le$, since it's probably not true with the equal sign.2012-07-01

1 Answers 1

2

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

  • 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.2012-07-01
  • 0
    Ah, thanks! This works! I appreciate the help. Thanks also for helping to formalize what I really wanted to know. :)2012-07-01