# Is my proof that $\ln^{\ln(x)}(x)\in O(x^2)$ correct?

I found this problem in some notes linked on the course page of a particular online class that I am taking. I am not sure if I am allowed to provide them here, so hopefully context does not matter too much. In this post, I use the phrase $f(x)\asymp g(x)$ to mean that $$\lim_{x\to\infty}\frac{f(x)}{g(x)}=M\in\Bbb R \setminus \{0\},$$ i.e. $f$ and $g$ have the same growth rate.

Determine if $\ln^{\ln(x)}(x)\in O(x^2)$.

My Attempt: I believe the answer is yes. The simplest way to prove such a claim, as far as I am aware, is to apply L'Hôpital's rule to the limit $\lim_{x\to\infty}\ln^{\ln(x)}(x)/x^2$. But, first of all, let $f=\ln^{\ln(x)}(x)$. Then, by rules of logarithms it is clear that $\ln(f)=\ln(x)\cdot\ln(\ln(x))$, and moreover \require{cancel}\begin{align}f'\cdot\frac{1}{f} &= \frac{d}{dx}[\ln(x)\cdot\ln(\ln(x))] \\ &=\frac{1}{x}\cdot\ln(\ln(x))+\cancel{\ln(x)}\cdot\frac{1}{\cancel{\ln(x)}}\cdot\frac{1}{x} \\ &=\frac{\ln(\ln(x))+1}{x}\end{align}. Thus, $$f'=\frac{\ln^{\ln(x)}(x)(\ln(\ln(x))+1)}{x}.$$ From here, an application of L'Hôpital's rule yields \begin{align}\lim_{x\to\infty}\frac{\ln^{\ln(x)}(x)}{x^2} &=\lim_{x\to\infty}\frac{\ln^{\ln(x)}(x)(\ln(\ln(x))+1)}{x^2} \\ &=\lim_{x\to\infty}\ln^{\ln(x)}(x) \ \cdot \ \underbrace{\lim_{x\to\infty}\frac{\ln(\ln(x))+1}{x^2}}_{(\star)},\end{align} and it suffices to prove that the limit $(\star)$ is zero; namely that $O(x^2)\ni \ln(\ln(x))+1\asymp\ln(\ln(x))$. Accordingly, we have $$\require{cancel}\lim_{x\to\infty}\frac{\ln(\ln(x))}{\ln(x)}=\lim_{x\to\infty}\frac{\cancel{x}}{\cancel{x}\ln(x)}=0.$$ which implies that $\ln(\ln(x))\in O(\ln(x))$ (as one could pick $M=1$ and some sufficiently large value of $x_0$ in the definition). But, since $$\lim_{x\to\infty}\frac{\ln(x)}{x^2}=\lim_{x\to\infty}\frac{1}{x^2}=0,$$ we have that $$O(\ln(x))\subsetneq O(x^2)\implies\ln(\ln(x))\in O(x^2).$$ Therefore, the limit $(\star)$ is zero and $\ln^{\ln(x)}\in O(x^2)$.

Is this proof correct? Can it be improved upon? Usually, to prove something like this given two functions $f$ and $g$, one would choose a value $x_0$ and then construct a constant $M$ so that $|f(x)|\le Mg(x)$, but in this case, I was not sure how to do that. Also, if you prefer, the notation $f(x)\in O(g(x))$ could be swapped with $f(x)=O(g(x))$.

Edit: Now that I realize my claim is false, is it possible to prove that $x^2\in O(\ln^{\ln(x)}(x))$?

• Are you sure that $(\ln x)^{\ln x} \in O(x^2)$? Jun 23, 2018 at 12:51
• Note that $(\ln x)^{\ln x} = x^{\ln \ln x}$. What can you say for $x\to \infty$. Jun 23, 2018 at 12:52
• @Crosby: that is an illusion. Try to compare them at $x\approx 10^4$ Jun 23, 2018 at 12:54
• Your proof falls apart when you introduce the *, can you see why? Jun 23, 2018 at 12:56
• @cansomeonehelpmeout Oh, I see. Both limits have to be finite. Jun 23, 2018 at 13:17

As the comments suggest, the entire claim fails.

To orient yourself, use the "commutative" law for exponentiation:

$u^{\ln (v)}=\exp(\ln (u) \ln (v))=\exp(\ln (v) \ln (u))=v^{\ln (u)}$

Here $u=\ln (x), v=x$ and you have

$(\ln (x))^{\ln (x)}=x^{\ln(\ln (x))}$

The exponent on $x$ goes only slowly to infinity, but it does go to infinity as $x$ itself does so. So $(\ln (x))^{\ln (x)} \notin O(x^n)$ for any finite $n$.

• Okay, thank you. Is it possible to prove that $x^2\in O(\ln^{\ln(x)}(x))$, then? Jun 23, 2018 at 13:22
• That works, for $x^n$ given any finite $n$ in place of $x^2$. Jun 23, 2018 at 13:25
• (+1) Okay, got it. Thanks for you answer! Jun 23, 2018 at 13:25