[Math] $x_1 = 2$, $x_{n + 1} = {{x_n(x_n + 1)}\over2}$, what can we say about $x_n \text{ mod }2$

Question

This question was asked on MathStackexchange here, but there was no answer, so I am asking it here.

Let$$x_1 = 2, \quad x_{n + 1} = {{x_n(x_n + 1)}\over2}.$$What can we say about the behavior of $x_n \text{ mod }2$? Is there an exact formula for $x_n \text{ mod }2$?

Answer 1

As remarked by Joe Silverman, a natural way to look at this question is by phrasing it in terms of the map $f(x):=\frac{1}{2}x(x+1)$ on the $2$-adic integers $\mathbb{Z}_2$. We are then asking about the behaviour of the orbit $f^n(2)$ with respect to the partition of $\mathbb{Z}_2$ into two clopen sets $U_1:=2\mathbb{Z}_2$ and $U_2:=1+2\mathbb{Z}_2$. Most questions of this form are very hard, for reasons which I will attempt to explain. Short answer: dynamically, there is no obvious reason why this should be easier than the Collatz problem or the normality of $\sqrt{2}$.

Suppose that we are given a continuous transformation $f$ of a compact metric space $X$ and a partition of $X$ into finitely many sets $U_1,\ldots,U_N$ of reasonable regularity (e.g. such that the boundary of each $U_i$ has empty interior). We are given a special point $x_0$ and we want to know how often, and in what manner, the sequence $(f^n(x_0))_{n=1}^\infty$ visits each of the sets $U_i$. We might believe the following result to be useful: if $\mu$ is a Borel probability measure on $X$ such that $\mu(f^{-1}A)=\mu(A)$ for every Borel measurable set $A\subset X$, and if additionally every $f$-invariant measurable set $A\subseteq X$ satisfies $\mu(A)\in \{0,1\}$, then $$\lim_{n\to\infty}\frac{1}{n}\sum_{i=0}^{n-1}\phi(f^i(x)) =\int \phi\,d\mu$$ for $\mu$-almost-every initial point $x$ and every $\mu$-integrable function $\phi \colon X \to \mathbb{R}$. This is the Birkhoff ergodic theorem or pointwise ergodic theorem. In particular we could take $\phi$ to be the characteristic function of a partition element $U_i$, so the above measures the average time spent in $U_i$ by the sequence $f^n(x)$. Or we could take $\phi$ to be the characteristic function of a set such as $U_1\cap f^{-1}U_2 \cap f^{-2}U_1$, which would tell us how often the orbit of $x$ follows the path $U_1 \to U_2 \to U_1$, and so on.

The Birkhoff theorem is great if we are content to study points $x$ which are generic with respect to a particular invariant measure. If we want to study a specific $x$ then we have no way to apply the theorem. If multiple different invariant measures $\mu$ exist then the integrals which they assign to the characterstic functions $\chi_{U_i}$ will in general be different and we will get different answers, and the Birkhoff averages along orbits will have fundamentally different behaviours depending on which measure the starting point is generic with respect to (if any). In a broad sense this is an aspect of the phenomenon called "chaos". Here is a nice example: let $X=\mathbb{R}/\mathbb{Z}$, $f(x):=2x$, let $U_1=[0,\frac{1}{2})+\mathbb{Z}$ and $U_2=X\setminus U_1$. What can we say about the manner in which the trajectory $f^n(\sqrt{2})$ visits $U_1$ and $U_2$? For example, does the trajectory spend an equal amount of time in both sets? Put another way, is $\sqrt{2}$ normal to base $2$? Dynamical methods can tell us that Lebesgue a.e. number is normal to base $2$, but they struggle badly for specific numbers. The difficulty of this problem is tied quite closely to the existence of many invariant measures for this map: Lebesgue measure is invariant, but so is the Dirac measure at $0$; there are many invariant measures supported on closed $f$-invariant proper subsets corresponding to restricted digit sets (e.g. numbers where "11" is not allowed in the binary expansion) and also many fully supported invariant measures which are singular with respect to Lebesgue measure (and indeed with respect to one another). Each invariant measure contributes a set of points with its own particular, distinct dynamical behaviour, and given an arbitrary point we have no obvious way of knowing which of these different dynamical behaviours prevails.

There is only one situation in which this dynamical problem becomes easy: when a unique $f$-invariant Borel probability measure exists. In this case the convergence in the Birkhoff theorem is uniform[*] over all $x$, and the problem of distinguishing which invariant measure (if any) characterises the behaviour of the trajectory $f^n(x)$ vanishes completely. An example would be the leading digit of $2^n$: take $X=\mathbb{R}/\mathbb{Z}$, $U_k=[\log_{10}k,\log_{10}(k+1))+\mathbb{Z}$ for $k=1,\ldots,9$, $f(x):=x+\log_{10}2$, then the leading digit of $2^n$ is $k$ if and only if $f^n(0) \in U_k$. The irrationality of $\log_{10} 2$ may be applied to show that Lebesgue measure is the only $f$-invariant Borel probability measure, and using the uniform ergodic theorem we can simply read off the average time spent in each $U_k$ as the Lebesgue measure of that interval.

So how does this affect $f(x):=x(x+1)/2$ on $\mathbb{Z}_2$? Well, $x=1$ and $x=0$ are both fixed points and carry invariant Borel probability measures $\delta_1$ and $\delta_0$. So the dynamical system is not uniquely ergodic, and the problem of determining which of the (presumably many) invariant measures characterises the trajectory of the initial point $2$ has no obvious solution.

[*] to obtain uniform convergence in this case $\phi$ must be a continuous function. By upper/lower approximation we can deduce pointwise convergence to $\int \phi\,d\mu$ for all $x\in X$ in the case where $\phi$ is upper or lower semi-continuous, for example where $\phi$ is the characteristic function of a closed or open set.