Iterating the logistic map: limsup of nonperiodic orbits

Last time we found that when a sequence with {x_1\in (0,1)} and {x_{n+1} = 4x_n(1-x_n)} does not become periodic, its upper limit {\limsup x_n} must be at least {\approx 0.925}. This time we’ll see that {\limsup x_n} can be as low as {(2+\sqrt{3})/4\approx 0.933} and determine for which {x_1} it is equal to 1.

The quadratic polynomial {f(x)=4x(1-x)} maps the interval {[0,1]} onto itself. Since the linear function {g(x) = 1-2x} maps {[0,1]} onto {[-1,1]}, it follows that the composition {h=g\circ f\circ g^{-1}} maps {[-1,1]} onto {[-1,1]}. This composition is easy to compute: {h(x) = 2x^2-1 }.

We want to know whether the iteration of {f}, starting from {x_1}, produces numbers arbitrarily close to {1}. Since {f\circ f \circ \cdots \circ f = g^{-1}\circ h \circ h \circ \cdots \circ h\circ g} the goal is equivalent to finding whether the iteration of {h}, starting from {g(x_1)}, produces numbers arbitrarily close to {g(1) = -1}. To shorten formulas, let’s write {h_n} for the {n}th iterate of {h}, for example, {h_3 = h\circ h\circ h}.

So far we traded one quadratic polynomial {f} for another, {h}. But {h} satisfies a nice identity: {h(\cos t)=2\cos^2 t-1 = \cos(2t)}, hence {h_n(\cos t) = \cos (2^n t)} for all {n\in\mathbb N}. It’s convenient to introduce {\alpha = \frac{1}{\pi}\cos^{-1}(1-2x_1)}, so that { h_n(g(x_1)) = h_n(\cos 2\pi \alpha ) = \cos(2^n\cdot 2\pi \alpha) }.

The problem becomes to determine whether the numbers {2^n\cdot 2\pi \alpha} come arbitrarily close to {\pi}, modulo an integer multiple of {2\pi}. Dividing by {2\pi} rephrases this as: does the fractional part of {2^n \alpha} come arbitrarily close to {1/2}?

A number that is close to {1/2} has the binary expansion beginning either with {0.01111111\dots} or with {0.10000000\dots}. Since the binary expansion of {2^n\alpha} is just the binary expansion of {\alpha} shifted {n} digits to the left, the property {\limsup x_n=1} is equivalent to the following: for every {k\in\mathbb N} the binary expansion of {\alpha} has infinitely many groups of the form “1 followed by k zeros” or “0 followed by k ones”.

A periodic expansion cannot have the above property; this, {\alpha} must be irrational. The property described above can then be simplified to “irrational and has arbitrarily long runs of the same digit”, since a long run of {0}s will be preceded by a {1}, and vice versa.

For example, combining the pairs 01 and 10 in some non-periodic way, we get an irrational number {\alpha} such that the fractional part of {2^n\alpha} does not get any closer to 1/2 than {0.01\overline{10}_2 = 5/12} or {0.10\overline{01}_2 = 7/12}. Hence, {\cos 2^n 2\pi \alpha \ge -\sqrt{3}/2}, which leads to the upper bound {x_n\le (2+\sqrt{3})/4\approx 0.933} for the sequence with the starting value {x_1=(1-\cos\pi\alpha)/2}.

Let us summarize the above observations about {\limsup x_n}.

Theorem: {\limsup x_n=1} if and only if (A) the number {\alpha = \frac{1}{\pi}\cos^{-1}(1-2x_1)} is irrational, and (B) the binary expansion of {\alpha} has arbitrarily long runs of the same digit.

Intuitively, one expects that a number that satisfies (A) will also satisfy (B) unless it was constructed specifically to fail (B). But to verify that (B) holds for a given number is not an easy task.

As a bonus, let’s prove that for every rational number {y\in (-1,1)}, except 0, 1/2 and -1/2, the number {\alpha = \frac{1}{\pi}\cos^{-1}y} is irrational. This will imply, in particular, that {x_1=1/3} yields a non-periodic sequence. The proof follows a post by Robert Israel and requires a lemma (which could be replaced with an appeal to Chebyshev polynomials, but the lemma keeps things self-contained).

Lemma. For every {n\in \mathbb N} there exists a monic polynomial {P_n} with integer coefficients such that {P_n(2 \cos t) = 2\cos nt } for all {t}.

Proof. Induction, the base case {n=1} being {P_1(x)=x}. Assuming the result for integers {\le n}, we have {2 \cos (n+1)t = e^{i(n+1)t} + e^{-i(n+1)t} } {  = (e^{int} + e^{-int})(e^{it} + e^{-it}) - (e^{i(n-1)t} + e^{-i(n-1)t}) } { = P_n(2 \cos t) (2\cos t) - P_{n-1}(2\cos t) }
which is a monic polynomial of {2\cos t}. {\Box}

Suppose that there exists {n} such that {n\alpha \in\mathbb Z}. Then {2\cos(\pi n\alpha)=\pm 2}. By the lemma, this implies {P_n(2\cos(\pi \alpha)) =\pm 2}, that is {P_n(2y)=\pm 2}. Since {2y} is a rational root of a monic polynomial with integer coefficients, the Rational Root Theorem implies that it is an integer. {\Box}

Wild power pie

Many people are aware of {\pi} being a number between 3 and 4, and some also know that {e} is between 2 and 3. Although the difference {\pi-e} is less than 1/2, it’s enough to place the two constants in separate buckets on the number line, separated by an integer.

When dealing with powers of {e}, using {e>2} is frequently wasteful, so it helps to know that {e^2>7}. Similarly, {\pi^2<10} is way more precise than {\pi<4}. To summarize: {e^2} is between 7 and 8, while {\pi^2} is between 9 and 10.

Do any two powers of {\pi} and {e} have the same integer part? That is, does the equation {\lfloor \pi^n \rfloor = \lfloor e^m \rfloor} have a solution in positive integers {m,n}?

Probably not. Chances are that the only pairs {(m,n)} for which {|\pi^n - e^m|<10} are {m,n\in \{1,2\}}, the smallest difference attained by {m=n=1}.

Indeed, having {|\pi^n - e^m|<1} implies that {|n\log \pi - m|<e^{-m}}, or put differently, {\left|\log \pi - \dfrac{m}{n}\right| < \dfrac{1}{n \,\pi^n}}. This would be an extraordinary rational approximation… for example, with {n=100} it would mean that {\log \pi = 1.14\ldots} with the following {50} digits all being {0}. This isn’t happening.

Looking at the continued fraction expansion of {\log \pi} shows the denominators of modest size {[1; 6, 1, 10, 24, \dots]}, indicating the lack of extraordinarily nice rational approximations. Of course, can use them to get good approximations, {\left|\log \pi - \dfrac{m}{n}\right| < \dfrac{1}{n^2}}, which leads to {\pi^n\approx e^m} with small relative error. For example, dropping {24} and subsequent terms yields the convergent {87/76}, and one can check that {\pi^{76} = 6.0728... \cdot 10^{37}} while {e^{87} = 6.0760...\cdot 10^{37}}.

Trying a few not-too-obscure constants with the help of mpmath library, the best coincidence of integer parts that I found is the following: the 13th power of the golden ratio {\varphi = (\sqrt{5}+1)/2} and the 34th power of Apèry’s constant {\zeta(3) = 1^{-3}+2^{-3}+3^{-3}+4^{-4}+\dots} both have integer part 521.