How to prove the sequence $\{a_n\}$ is unbounded, which satisfies the recurrence relation $a_{n+1}=\ln |a_n|$?

When I browsed Zhihu(a Chinese Q&A community), I met this question. That is

Let $\{a_n\}$ be recursive s.t. $$a_1=2,\ a_{n+1}=\ln |a_n|(n\in \Bbb N).$$ Show that $\{a_n\}$ is unbounded.

I want to investigate a subsequence $\{a_{t_n}\}$ of $\{a_n\}$, where $t_n$ is greatest integer satisfying $$a_{t_n}=\min_{1\leqslant k\leqslant n}a_k.$$ Thus $a_{t_n}\to -A(<0),n\to \infty$.

However, it helps little with the origin question. So how can I solve it ?

Solution 1:

Note: This discussion relies heavily on results from my answer to a related question. Any references to numbered theorems below refer to theorems from there.

Showing that this sequence is bounded would require showing that it is not cyclic, which I believe is not solvable with our current knowledge of exponentiation. To see why: If $a_K = 2$ for some $K\in \mathbb{N}$, then we would have $$ \ln|\ln|\cdots \ln 2|| = 2 $$ or equivalently $$ 2 = e^{\pm e^{\pm e^{\cdots^ 2}}} $$ for some appropriate sequence of $+$'s and $-$'s. It would be a miracle if this existed, but given that simple facts like whether $e^{e^{e^{e^e}}}$ is an integer are unknown, my guess would be that proving it's impossible would require some ground-breaking techniques. It's also presumably unknown whether or not there exists a sequence of $+$'s and $-$'s such that $$ 2 = e^{\pm e^{\pm e^{\cdots ^{\pm e}}}} $$ which would imply that the sequence blows up after finitely many iterations. Theorem 2 implies that both $$ \left\{e^{\pm e^{\pm e^{\cdots ^{\pm e}}}}\right\} \mbox{ and } \left\{e^{\pm e^{\pm e^{\cdots ^{2}}}}\right\} $$ are dense in $[0,\infty]$, so there's no computational way to check whether $a_n$ is periodic or terminates in finite time.

I can show that "most" starting values for the sequence are bounded (but I can't quite prove "almost all" - see below). By theorems 1 and 2, for all $x$, there exists a sequence $\epsilon\in\{-1,1\}^\mathbb{N}$ such that the sequence of functions $$ x_n(t) = e^{\epsilon_1 e^{\cdots ^{\epsilon_{n-1} e^{\epsilon_n t}}}} $$ converges uniformly to $x$. Alternatively, we can write $$ x = e^{\epsilon_1 e^{\epsilon_2 e^{\epsilon 3 e^{\cdots}}}} := [\epsilon_1,\epsilon_2,...] $$ Note that if $(\epsilon_1,\dots,\epsilon_n)$ are all $1$, then $x> {^{n-1}e} $, where the left superscript represents tetration. Borrowing my notation from the above referenced answer, $L_n(x)$ is the $n$th term of the sequence formed by iterating $\ln |x|$, and is given by $$ L_n(x) = \epsilon_n \cdot [\epsilon_{n+1},\epsilon_{n+2},\dots] $$ If $\epsilon_n$ are chosen randomly, then for any $M\in\mathbb{N}$, with probability 1 there exists $m\in\mathbb{N}$ such that $\epsilon_{m+1},\cdots,\epsilon_{m+M+2}$ are all $1$. Then$$ |L_m(x)| \ge {{^M}e} $$ Hence with probability 1, the sequence $L_n([\epsilon_1,\epsilon_2,\dots])$ is unbounded.

I also proved the following representation for the distribution function of $[\epsilon_1,\epsilon_2,...]$:$$ F(t) = \sum_{n=0}^\infty \frac{\prod_{k=1}^n\mathrm{sgn}(L_k(t))}{2^{n+1}} $$ which looks a lot like a binary digital representation. Notice that if $t = [\epsilon_1,\epsilon_2,...]$, then $$ \mathrm{sgn}(L_n(t)) = \mathrm{sgn}(\epsilon_n \cdot [\epsilon_{n+1},\epsilon_{n+2},\dots]) = \epsilon_n $$ Let $t = [\epsilon_1,\epsilon_2,...]$ and $$ \beta_n = \frac{1+\prod_{k=1}^n\mathrm{sgn}(L_k(t))}2 $$ Note that $\beta_n$ is always $0$ or $1$, and $\beta_0=1$, so $$ F(t) = \sum_{n=0}^\infty \frac{\prod_{k=1}^n\mathrm{sgn}(L_k(t))}{2^{n+1}} = \frac12+\sum_{n=1}^\infty \frac{2\beta_n - 1}{2^{n+1}} = \sum_{n=1}^\infty \frac{\beta_n}{2^n} $$ Hence $\beta_n$ gives exactly the binary digits of $F(t)$. As we already observed, the event that $L_n(t)$ has probability $0$, where $t=[\epsilon_1,\epsilon_2,\cdots]$ is given the distribution that $\epsilon_n$ are chosen i.i.d. uniform on $\{-1,1\}$. But the above computation shows that if $t$ has this distribution, then $F(t)$ has the uniform distribution on $(0,1)$, since the $\epsilon_n$'s are mapping to the binary digits of $F(t)$. Let $S = \{t : L_n(t) \mbox{ is a bounded sequence}\}$. We then have $$ F(S) = \{y\in(0,1) : y\mbox{'s binary expansion does not have arbitrarily long sequences of 1's}\} $$ Because $F(S)$ has measure $0$, I believe that $S$ also ought to have measure $0$, but I'm not sure how to show $F$ has this property. It would suffice to show $F^{-1}$ is absolutely continuous, which it does appear to be, though it might be tough to prove. This same method does show that the set of points that are eventually periodic is countable and dense (since it corresponds to rational points in the image of $F$, which is continuous and bijective).

Update: I think I do see how to show $F^{-1}(x)$ is actually Lipschitz continuous on any $[\alpha,\beta]\subset[0,1)$. It involves applying the uniform convergence of the $x_n(t)$ functions to their limits. It would be rather tedious to write out the details since it seems necessary to have a large proliferation of cases to check. I don't have time to work through it at the moment, but I will update this answer when/if I do.

Solution 2:

Too long for a comment

1) Some equivalent recurrences:

As in Μάρκος Καραμέρης's comment, one may consider the equivalent recurrence: $$a_1 = 2; \ a_{n+1} = |\ln a_n|, n\ge 1.\tag{1}$$ Thus, we have $$a_1 = 2; \ \mathrm{e}^{a_{n+1}} + \mathrm{e}^{-a_{n+1}} = a_n + a_n^{-1}, \ n\ge 1$$ or $$a_1 = 2; \ \cosh a_{n+1} = \frac{a_n + a_n^{-1}}{2}, \ n \ge 1$$ or $$a_1 = 2;\ a_{n+1} = \operatorname{arccosh} \frac{a_n + a_n^{-1}}{2}, n\ge 1.\tag{2}$$ (note: $\operatorname{arccosh} x = \ln (x + \sqrt{x^2-1})$, $x\ge 1$)

Let $b_n = \frac{a_n + a_n^{-1}}{2}$. We have $$b_1 = \frac{5}{4}; \ b_{n+1} = \frac{1}{2}\left(\operatorname{arccosh} b_n + \frac{1}{\operatorname{arccosh} b_n}\right), n\ge 1. \tag{3}$$

2) In [1], consider the following problem: Is the sequence $\{x_n\}$ unbounded? $$x_{n+1} = x_n - \frac{1}{x_n}, \ x_0 = 2.$$ Is the approach there helpful for this problem?

Reference

[1] Marc Chamberland, and Mario Martelli, "Unbounded orbits and binary digits", 2003. http://www.math.grinnell.edu/~chamberl/papers/mario_digits.pdf

Solution 3:

This is not an answer, but is too long for the usual comment format. Below is a numerical example where the initial value is very close to $1$ but the sequence is bounded. This suggests that showing the sequence is unbounded will use very specific properties of $2$ and will therefore be hard.

As in Μάρκος Καραμέρης's comment, I find it more convenient to use the equivalent recurrence $a_{n+1}=f(a_n)$ where $f(x)=|\ln(x)|$ (rather than $f(x)=\ln(|x|)$).

Since $f^{4}(0.44) \geq 0.48$ and $f^{4}(0.45) \leq 0.40$, it follows that $f^{4}$ has a fixed point $\beta\in [0.44,0.45]$.

Any $x\gt 0$ has two preimages by $f$, namely $E(x)=\exp(x)$ and $G(x)=\exp(-x)$. Also, we have $a_{k}=E(a_{k+1})$ when $\ln(a_k)\gt 0$ and $a_k=G(a_{k+1})$ otherwise. So, there is a well-defined sequence $(F_k)_{k\geq 1}$ with values in $\lbrace E,G \rbrace$ such that $a_k=F_k(a_{k+1})$ for all $k$.

Now, define a sequence $(b_k)_{1\leq k \leq 396}$ backwards (why $396$ ? because $a_{396}$ happens to be close to $\beta$), by putting $b_{396}=\beta$ and $b_k=F_k(b_{k+1})$ for all $k$.

Using PARI-GP with 200 digits precision (see program below), one can see that $b_1$ is very close to $2$ : $|b_1-2|\leq 10^{-100}$. On the other hand, if we start from $b_1$ rather than $a_1$, we get a sequence that is eventually $4$-periodic (and therefore bounded).

\p 200
f(x)=abs(log(x))
large_number=396
an_sequence=vector(large_number,k,[]);
an_sequence[1]=2
for(k=2,large_number,an_sequence[k]=f(an_sequence[k-1]))
/* check a good approximation for beta */
f4(x)=f(f(f(f(x))))
betaa=444651345712468867357552650044449620720822557574794055208951851149593925469515592545042756658149233979242459023501275506326633186564851181962848935531478012975488666361285767551984962547168811/(10^192)
check_betaa=abs(f4(betaa)-betaa) /* is around 4E-192 ; that's good */
/*Construct the (bn) sequence backwards */
bn_sequence=vector(396,k,[]);
bn_sequence[396]=betaa;
for(j=1,395,\
k=396-j;\
bn_sequence[k]=if(log(an_sequence[k])>0,exp(bn_sequence[k+1]),exp(-bn_sequence[k+1]));\
)
see_difference=abs(bn_sequence[1]-an_sequence[1])