How quickly does $y_{n+1}=y_n(1-1/\lg y_n)$ decrease?

Question

The iterated logarithm $\log^*(x)$ is defined to be the smallest $n$ such that $\log^{(n)}(x)\le 1$. Similarly, let's define $f^*(x)$ to be the smallest $n$ such that $f^{(n)}(x)\le 10$, where $f(x)=x\cdot(1-1/\lg x)$. We can show that $f^*(x)=O((\lg x)^2)$ as follows:

Fix $x_0$. Let $g(x)=x\cdot(1-1/\lg x_0)$. Clearly, if $x\le x_0$ then $g(x)\ge f(x)$. So, $g^*(x_0)\ge f^*(x_0)$, where $g^*$ is defined similarly to $f^*$ and $\log^*$. But $g^{(n)}(x_0)$ is $x_0\cdot (1-1/\lg x_0)^n$. To bound $g^*(x_0)$ and hence $f^*(x_0)$, we want to find a small $n$ such that

$$x_0 \cdot \Bigl(1 - \frac{1}{\lg x_0}\Bigr)^n \le 10$$

Take logarithms on both sides:

$$\lg x_0 + n \lg (1-1/\lg x_0) \le \lg 10$$

If $x_0$ is large enough, then $\lg (1-1/\lg x_0) \approx -1/\lg x_0$. (This is a bit hand-wavy.) So:

$$\lg x_0 - \frac{n}{\lg x_0} \le \lg 10$$

And since we're looking for the smallest such $n$ we get $n=\Theta((\lg x_0)^2)$. Thus, squared-log is an upper bound for $g^*$ and hence for $f^*$. $\Box$

Question: Is a bound better than $O((\lg x)^2)$ possible for $f^*(x)$?

Answer 1

It takes fewer than $\lg x_0$ steps to reduce $\lg x_n$ by $1$, so the total steps is less than $\lg x_0+(\lg x_0)-1+(\lg x_0)-2+...=O(\lg x_0)^2/2$

Answer 2

By induction we'll show that $f^{(k)}(e^n)\ge e^n(1-k/n)$. Then after $n/2$ steps we have $e^n(1-1/2)\ge e^{n-1}$ "value" left. Thus we need $\Omega(n^2)$ steps to get from $e^n$ to a constant value as in your upper bound.

For the induction step, $$f(e^n(1-k/n)) = e^n(1-k/n)(1-1/(n+\log(1-k/n))).$$ Now use the inequality $\log(1+x)\ge \frac{x}{1+x}$. That gives us $$f^{(k+1)}(e^n) \ge e^n \left(1-\frac{(k+1)-(k+2) k/n}{n-k-k/n}\right) \ge e^n\left(1-\frac{k+1}{n}\right).$$ Where the second inequality comes from Here $(k+2) k/n \le k+k/n$ whenever $k+2\ge n+1$ and $n>0$.