Upper bound and lower bound of a logarithmic function

Question

Assume a function $T(n)$: $$T(n)=\log{\log^{*}{n}}$$ Let's define: $$\log^{*}{n}=\min\{i\ge{0}:\log^{(i)}{n}\le1\}$$ and: $$\log^{(i)}{n}=\log{(\log^{(i-1)}{n})}$$ Is the following $f(n)$ function an upper bound or a lower bound of $T(n)$? $$f(n)=\log^{*}{\log{n}}$$

---

To see if $f(n)$ could possibly be an upper bound, I feel like the following limit needs to be gone through: $$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{\log^{*}{n}}}=?$$ Now I wonder if the above limit might boil down to this: $$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{(\min{\{\log\log\log\cdots\log^{(0)}{n}\}})}}$$ I'm not quite sure how to solve the above limit to get an idea of the upper bound of $T(n)$. Also, the lower bound is another story which I have little idea about.

Answer 1

For $a\in[1,e]$ we have that $\ln(a)\in [0,1]$ thus $x_n(a)=\exp^{(n)}(a)$ is a subsequence going to infinity such that $T(x_n(a))$ can be any number in $[0,1]$ depending of the initial value of $a$.

Now you asked this for integers, but $y_n(a)=\lfloor x_n(a)\rfloor$ is an integer subsequence such that $x_n(a)\le y_n(a)<x_n(a)+1$

And since $\ln$ and its iterates are striclty increasing functions we have ($n\gg 1$)

$T(x_n(a))\le T(y_n(a))\lt T(x_n(a)+1)$

edit: this is true if it is the same $i$ in $\log^*$ but the following shows it is.

But $\ln(x_n(a)+1)=\ln(x_n(a))+\ln(1+1/x_n(a))=\ln(x_n(a))+x_n(a)^{-1}+o(x_n(a)^{-1})$

And when we iterate $\ln(\ln(x_na(a)+1)=\ln(\ln(x_n(a))+(x_n(a)\ln(x_n(a))^{-1}+o((x_n(a)\ln(x_n(a))^{-1})$

But according to the process $\ln(x_n(a))\ge 1$ so we can majorate roughly

$\ln(\ln(x_na(a)+1)\le\ln(\ln(x_n(a))+O(x_n(a)^{-1})$ and this goes on as we iterate again.

All that to say that $T(x_n(a)+1)\sim T(x_n(a))$.

Thus $\lim\limits_{n\to\infty} T(y_n(a))=\lim\limits_{n\to\infty} T(x_n(a))=\ln(a)$.

We have an integer subsequence $(y_n(a))_n$ going to infinity such that $T(y_n(a))$ can take any pre-decided value in $[0,1]$ so $\lim\limits_{n\to\infty} T(n)$ doesn't exists.

Edit: I realize that I have worked with a different definition of $log^*$.

In my mind it was $\log^*(x)=\max\{i\in\mathbb N\mid \ln^{(i)}(x)\ge 1\}$, the demo can be adapted to your definition I think.

By your definition $T(n)<0$ while $f(n)\ge 0$ so $f$ can only be an upper bound for $T$.