Taking an infinite number of logarithms

Question

Let $n$ and $k$ be two integer parameters ($n\geq k$, if that matters). Define the following function:

$\text{LOG }x=\max(\log{x},1)$

What is the limit of the following sequence as a function of $n$ and $k$?

$a_1 = \text{LOG }n$

$a_2 = \text{LOG }k \cdot \text{LOG }\text{LOG }n$

$a_3 = \text{LOG }k \cdot \text{LOG }\text{LOG }k \cdot \text{LOG }\text{LOG }\text{LOG } n$

$a_4 = \text{LOG }k \cdot \text{LOG }\text{LOG } k \cdot \text{LOG }\text{LOG }\text{LOG }k \cdot \text{LOG }\text{LOG }\text{LOG }\text{LOG }n$

...

I looked at Iterated logarithm in Wikipedia, this looks similar but not the same.

A limit in terms of big-Oh notation is fine (e.g. $O(f(n,k)$).

Answer 1

$LOG LOG \dotso LOG(N) \rightarrow 1$ so we can ignore that completely. You can generate the proof by looking at a cobweb plot and noticing that the limit must be in the intersection of $y = x$ and $y = \text{LOG }x$ which is at $x = 1, y = 1$.

As far as $\text{LOG } k \text{ LOG } \text{LOG } k \text{ LOG } \text{ LOG } \text{ LOG } k \dotso$ after finitely many of those the sequence will stay the same. The $n$ at which this happens is the iterated log of $k$. A not very tight big-O is $O(\log(k)^{log^*k})$

Answer 2

Let us agree upon the notation $f^{(n)}(x)=(f\circ f\circ\cdots f)(x)$. Then According to your current definition, note that $\exists N$ such that $LOG^{(N)}n=\log^{(N)}n,\ LOG^{(N+1)}=1$. Similarly, you can find a $K$ such that $LOG^{(K)}k=\log^{(K)}k,\ LOG^{(K+1)}=1$. So, for $m\ge \max(K+1,N+1),\ a_m=\prod_{i=1}^{K}log^{(i)}k$ which is a constant, i.e your sequence converges to a constant number.

I think the problem becomes more interesting if you define $LOG x=1+\log x$, just like the definition of the iterated logarithm function.

Edit: Note that $f(k)=\log^{(K)}k$ is the number such that $\log(f(k))<0$ for the first time. So we need to find this $K$. Let us define the sequence $b_n=\log^{(n)}k,\ n\ge 0$ with $b_0=k$. Then, by the previous analysis, your original sequence is going to converge to $a$ where $\log a=\sum_{n=1}^K \log b_n$ where $K$ is such that $b_{K+1}<0,\ b_i>0,\ 1\le i\le K$. One can easily see that $\{b_n\}$ is a positive monotonic decreasing sequence; so $b_n\ge 1\ \forall 0\le n\le K$. Now, using LMVT we can write $$b_{n+1}-b_{n}=\frac{b_n-b_{n-1}}{c_n},\ \forall 1\le n\le K-1\\ \implies \frac{b_n}{b_{n-1}}<\frac{b_{n-1}}{b_{n-2}},\ 2\le n\le K$$ since $c_n\in (b_n,b_{n+1})$. Now, it can be easily shown that $$\frac{b_1}{b_0}=\frac{\log k}{k}<\frac{1}{e}\approx 0.3679=:\alpha$$ Thus, $b_n<\alpha^{n}k,\ 1\le n\le K\implies K<\log\log k\implies \log a<K\log k-\frac{K(K+1)}{2}<\log k\cdot \log\log k-1\implies a=O((\log k)^{\log k})$