# $3x+1$ Conjecture and link with Ergodic Theory

I read here https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Lagarias3-23.pdf that the Collatz conjecture is equivalent to $$Q_{\infty}(\mathbb{N}) \subseteq \frac{1}{3} \mathbb{Z}$$. Where $$Q_{\infty} : \mathbb{Z}_2 \to \mathbb{Z}_2$$ is a continous and measure preserving transformation defined by $$x \mapsto Q_{\infty}(x) = \sum_{k=0}^{\infty} \left( T^k(x) \mod 2 \right) 2^k$$ and $$T : \mathbb{Z}_2 \to \mathbb{Z}_2$$ is an ergodic map defined by $$x \mapsto T(x) =\left\{\begin{matrix} \frac{x}{2} & \text{if} & x \equiv 0 \mod 2 \\ \frac{3x+1}{2}& \text{if} & x \equiv 1 \mod 2 \end{matrix}\right.$$ I was wondering how to prove that they are equivalent, and I was wondering if there is any reference I can read to further explore the connection between the Collatz conjecture and the Ergodic Theory.

• Jul 15, 2022 at 13:53

There's an idea in play here that isn't completely obvious. First, let's talk about the more straightforward part.

Choose a positive integer, say $$5$$. It has a 2-adic expansion, usually written $$...0000101.$$, which represents (reading from right-to-left) $$1\times2^0 + 0\times2^1 + 1\times2^2 + 0\times2^3 + 0\times 2^4 + \cdots$$.

The same number has another binary sequence associated with it, namely, its parity sequence under the (shortcut version of the) Collatz function. Since the number's trajectory is:

$$5 \to 8 \to 4 \to 2 \to 1 \to 2 \to 1 \to 2 \to 1 \to 2 \to \cdots$$,

we write the parity sequence $$1,0,0,0,1,0,1,0,1,0,\ldots$$

Now here's the interesting part: We can re-interpret that parity sequence as another 2-adic number! Reversing the digits, to see it the usual way around, it looks like:

$$...0101010001.$$, or emphasizing the repeating part: $$\overline{01}0001.$$

This is the 2-adic expansion of the rational number $$-\frac{13}3$$.

This is the map $$Q_\infty$$. We have just seen that $$Q_\infty(5)=-\frac{13}3$$.

Now, the fact that it's a fraction with denominator $$3$$ reflects the fact that it falls into a pattern repeating "$$01$$". (Note that $$\overline{01}.=-\frac13$$) Therefore, the claim that every element of $$\mathbb{N}$$ has a trajectory eventually reaching $$1,2,1,2,\ldots$$ is transformed, with this $$Q_\infty$$ map, into the claim that every element of $$\mathbb{N}$$ is mapped by $$Q_\infty$$ to a 2-adic integer with $$...0101$$ trailing off to the left. Such numbers are precisely the elements of $$\frac13\mathbb{Z}\setminus\mathbb{Z}$$.

Does this help?

• It help yes! But I don't see why we need to reverse the digits
– 3m0o
Jul 31, 2022 at 10:58
• We don't need to reverse the digits. There are different conventions for writing 2-adic numbers. If you're happy to write larger and larger powers of 2 going to the right, then you can do that. I usually write larger powers of 2 going to the left, because then 2-adic representations of integers look just like binary representations. Jul 31, 2022 at 12:51
• The alternative would have been to say that the 2-adic expansion of 5 is written: $.101000\ldots$, letting positions to the right of the dot represent increasing powers of 2. Aug 1, 2022 at 14:48