1

I am confused, so please help me out.

Background

Consider the dynamical system for $0 \leq x \leq 1$ given by the function

$$f(x) = \begin{cases} \frac 12 (3x+1), & x \in [0, 1/3) \\ \frac 14 (3x-1), & x \in [1/3, 1] \end{cases}$$

Lets call the pieces of $f$ by the names $\sigma(x) = (3x+1)/2$ and $\tau(x) = (3x-1)/4$. Now, by happy coincidence, $\sigma \tau = \tau \sigma$ (function composition), and, by solving simple recurrence relations, we have

$$\sigma^m \tau^n (x) = (1 + x)(3/2)^m(3/4)^n - 1$$

(Note that a simple change of variables elucidates why $\sigma$ and $\tau$ commute: they are just multiplication by a constant!)

OK, so, I want to know how often we use a $\sigma$ on average when we calculate $f^n(x)$ as $n \to \infty$.

Now, I look at the intervals $[0, 1/2]$ and $(1/2, 1]$. We know that $f^n(x) \in (1/2, 1]$ if and only if $f^{n-1}(x) \in [0, 1/3)$, i.e., if and only if the last operation was a $\sigma$ instead of a $\tau$. If we draw $x$ from a uniform distribution on $[0, 1]$, we have that $p_n$, the probability that $f^n(x) \in (1/2, 1]$ is given by the recurrence relation $p_n = 2/3(1 - p_{n-1})$, $p_0 = 1/2$.

This recurrence relation is solved by $p_n = (-2/3)^n/10 + 2/5$, and we clearly have $\lim_{n \to \infty} p_n = 2/5$. Fine so far, right?

Now is the part where I get confused. So, if asymptotically $2/5$ of the operations are $\sigma$, and the other $3/5$ of the operations are $\tau$, then I should expect something like the following for big $n$:

$f^n(x) \approx (1 + x)(3/2)^{2n/5}(3/4)^{3n/5} - 1$

(for almost every $x$).

But, $\lim_{n \to \infty} (3/2)^{2n/5}(3/4)^{3n/5} = 0$, which doesn't make any sense because $f^n(x) \in [0, 1]$, and this is saying that $f^n(x) \to -1$ almost surely.

Question

What is my misunderstanding here?

Motivation

For $x$ a positive integer, let $n$ be such that $2^n \leq x < 2^{n+1}$. Then, we associate with $x$ the dyadic rational $\varphi(x) = (x - 2^n)/2^n$. For odd $x$, this transformation sends $x$ and $2^k x$ to the same point, for any $k \in \mathbb{N}$.

Now, consider the transformation $T(x) = (3x + 1)/2^n, x \equiv a_n \pmod{2^{n+1}}$, where $a_n = 2^n + ((-2)^{n+1}-1)/3$. This is the odd-only version of the transformation from the $3x+1$ problem.

Restricting our attention to odd $x$, for $0 \leq \varphi(x) < 1/3$, we have

$\varphi T(x) = \dfrac{3 \left( \dfrac{x - 2^n}{2^n} \right) + 1}{2} + \dfrac{1}{2^{n+1}} = \dfrac{3 \varphi(x) + 1}{2} + \dfrac{1}{2^{n+1}}$

and for $1/3 \leq \varphi(x) < 1$, we have

$\varphi T(x) = \dfrac{3 \left( \dfrac{x - 2^n}{2^n} \right) - 1}{4} + \dfrac{1}{2^{n+2}} = \dfrac{3 \varphi(x) - 1}{4} + \dfrac{1}{2^{n+2}}$

Thus, if $x, Tx, T^2x, \ldots$ is a divergent trajectory in the $3x+1$ problem, then $n \to \infty$, and the behavior of $\varphi x, \varphi Tx, \varphi T^2x, \ldots$ approaches that of the dynamical system in this question.

Rodrigo de Azevedo
  • 1
  • I posted an answer stating the nature of my mistake, but I deleted it because I felt that a real answer should say more about the problem. The recurrence relation $p_n = 2/3(1-p_{n-1})$ is not correct. –  Jun 21 '19 at 18:45
  • 1
    A possible way: show that $f$ preserves the measure with the density $\mu(x) = 1/((x + 1) \ln 2)$. Then show that $f$ is ergodic wrt $\mu$. Then the fraction of time spent in $[0, 1/3)$ tends to $\int_0^{1/3} \mu(x) , dx$ for almost all starting points. – Maxim Jun 23 '19 at 15:12
  • @Rodrigo, I changed the title because you made affine suggestion. –  Jun 23 '19 at 18:52
  • @Maxim, since $1/((x+1)\ln{2})$ is strictly decreasing, and since $2^n + 1 \equiv 1 \pmod{8}$ for $n \geq 3$, meaning $T(x) = (3x+1)/4 < x$, and since every other odd satisfies $T(x) < x$, did you just sketch a proof that there are no divergent trajectories in the $3x+1$ problem? –  Jun 25 '19 at 14:03
  • (Keep in mind that the assumption of a divergent trajectory precisely means that no future point is the same as any previous point, so the behavior should tend to that of a "typical" point.) –  Jun 25 '19 at 14:44
  • @Maxim, I'm still not exactly sure how you got the measure $1/((x+1)\ln{2})$ because I don't know what "ergodic" means. However, I just transformed the dynamical system to an ergodic circle rotation in log space and applied Weyl's Theorem, which also has the added benefit of proving the behavior of the system on the null set of dyadic rationals. That's why all you need is infinitely many distinct points in your divergent trajectory to show it will behave like a "typical" point. –  Jun 26 '19 at 17:48
  • Once you have the formula for $\mu$, it's not difficult to verify that this measure is preserved. I thought there might be some connection with the Gauss map, but you're right, my reformulation doesn't make the problem easier. In fact, proving the ergodicity of $f$ may be harder than answering your original question. – Maxim Jun 26 '19 at 20:58
  • I feel like you should be more excited. This dynamical system is really an ergodic circle rotation under a change of variables. That means its behavior applies to all starting points, not just almost all. This gives a rigorous justification to heuristic probabilistic arguments regarding the Collatz conjecture for large numbers of iterations, meaning we have a proof that there is no divergent trajectory, a major step toward a long-open famous problem. –  Jun 26 '19 at 21:04
  • Unless there's a mistake, that is :P –  Jun 26 '19 at 21:04

0 Answers0