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

  • 0
    Ah, thanks! Th$i$s works! I appreciate the help. Thanks also for helping to formalize what I really wanted to know. :)2012-07-01