Last time we found that when a sequence with and does not become periodic, its upper limit must be at least . This time we’ll see that can be as low as and determine for which it is equal to 1.
The quadratic polynomial maps the interval onto itself. Since the linear function maps onto , it follows that the composition maps onto . This composition is easy to compute: .
We want to know whether the iteration of , starting from , produces numbers arbitrarily close to . Since the goal is equivalent to finding whether the iteration of , starting from , produces numbers arbitrarily close to . To shorten formulas, let’s write for the th iterate of , for example, .
So far we traded one quadratic polynomial for another, . But satisfies a nice identity: , hence for all . It’s convenient to introduce , so that .
The problem becomes to determine whether the numbers come arbitrarily close to , modulo an integer multiple of . Dividing by rephrases this as: does the fractional part of come arbitrarily close to ?
A number that is close to has the binary expansion beginning either with or with . Since the binary expansion of is just the binary expansion of shifted digits to the left, the property is equivalent to the following: for every the binary expansion of 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, 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 s will be preceded by a , and vice versa.
For example, combining the pairs 01 and 10 in some non-periodic way, we get an irrational number such that the fractional part of does not get any closer to 1/2 than or . Hence, , which leads to the upper bound for the sequence with the starting value .
Let us summarize the above observations about .
Theorem: if and only if (A) the number is irrational, and (B) the binary expansion of 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 , except 0, 1/2 and -1/2, the number is irrational. This will imply, in particular, that 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 there exists a monic polynomial with integer coefficients such that for all .
Proof. Induction, the base case being . Assuming the result for integers , we have
which is a monic polynomial of .
Suppose that there exists such that . Then . By the lemma, this implies , that is . Since is a rational root of a monic polynomial with integer coefficients, the Rational Root Theorem implies that it is an integer.