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.


1 Answer 1


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?

  • $\begingroup$ It help yes! But I don't see why we need to reverse the digits $\endgroup$
    – 3m0o
    Jul 31, 2022 at 10:58
  • $\begingroup$ 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. $\endgroup$ Jul 31, 2022 at 12:51
  • $\begingroup$ 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. $\endgroup$ Aug 1, 2022 at 14:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .