These are notes from a survey talk given by Jeff Lagarias at the Simons Center for Physics and Geometry on the Collatz problem. If there are errors here, it's probably because I added them myself.
On the Collatz Problem
Let $c(n)$ be the Collatz map, defined on $\mathbb{N}_{> 0}$ via \begin{equation*} c(n) = \begin{cases} 3n + 1 & \text{if } n \text{ odd} \\ n / 2 & \text{else}. \end{cases} \end{equation*}
The Collatz Conjecture states that for any integer $n \geq 1$, there exists some $k$ such that the $k$th composition $C^{(k)}(n) = 1$.
This is attributed to Lothar Collatz. Jeff wrote Collatz a letter when he was asked to write a survey article on the conjecture several years ago. He asked Lothar if he did, in fact, come up with this problem. Collatz equivocated.
But Lothar Collatz did come up with a related problem. His problem was the following. Define the permutation $\Phi$ on $\mathbb{Z}$ by \begin{align*} \Phi(3n) &= 2n, \\ \Phi(3n + 1) &= 4n + 1, \\ \Phi(3n + 2) &= 4n + 3. \end{align*} One can study the inverse permutation $\Phi^{-1}$ too.
It is clear that every number is either a member of a cycle or a bi-infinite orbit. But proving any number is in an infinite orbit seems essentially impossible. Concretely, one might try to prove that $8$ is an an infinite orbit. (This is not known).
Open Problems
- Collatz Conjecture.
This might be harder then the Riemann Hypotheis. Don't work on this problem.
- Are there finitely many periodic orbits, which all integers go to one of them?
This is also too hard. Don't work on this.
- Is there an infinite orbit?
Also too hard.
Each of these problems is completely open, and further they're open in most related statements (unless not for completely trivial reasons).
There is a paper out there called Don't work on these problems. It contains these problems and related. Don't work on them.
Variations on the problem
We now describe a few variants. Even though these are all "equivalent", they all have somewhat different dynamical behavior.
3n+1 Problem
We state a variation. Define $T: \mathbb{N}_{>0} \longrightarrow \mathbb{N}_{>0}$ by \begin{equation*} T(n) = \begin{cases} \frac{3n + 1}{2} & \text{if } n \text{ odd} \\ n / 2 & \text{else}. \end{cases} \end{equation*} This does the obvious step of applying $c$ twice if $n$ is odd.
This is a very nice function when studied dynamically. The map $T$ is measure-preserving in the $2$-adic Haar measure, and one can apply ergodic methods to study it. It is maximally ergodic in a sense that can be made rigorous. But there is still space for exceptional behavior.
One can study the inverse $T$ map: \begin{align*} T^{-1}(n) &= \{ 2n \} \qquad (n \equiv 0, 1 \bmod 3) \\ T^{-1}(n) &= \{ 2n, \frac{2n - 1}{3} \} \qquad (n \equiv 2 \bmod 3). \end{align*} Every number will have an infinite tree of preimages under the $T^{-1}$ map.
If one cuts off the tree at height $K$, then one can reduce this problem to questions mod $2 \cdot 3^{K-1}$, and interpret this dynamically or over $3$-adic integers. One might try to grow random $3$-adic trees to determine some of the underlying behavior.
Accelerated Collatz Map
One can also further accelerate the map, removing extraneous steps. \begin{equation*} \widetilde{C}(n) = \begin{cases} \frac{3n + 1}{2^{\mathrm{ord}_2(3n+1)}} & \text{if } n \text{ odd} \\ n / 2 & \text{else}. \end{cases} \end{equation*} This divides out by as many values of $2$ as possible, immediately.
Terry Tao studied the accelerated Collatz map in his recent work in 2019.
Base Collatz mod $2$
Consider $T(\cdot)$ on $\mathbb{Z}/2\mathbb{Z}$ — or alternately on $\mathbb{Z}_2$ (i.e. $2$-adics).
Take the first $k$ forward iterates mod $2$, \begin{equation*} v_{k+1}(n) := \big(n, T(n), T^{(2)}(n), \ldots, T^{(k)}(n) \big) \bmod 2. \end{equation*} Take some $n$ with $1 \leq n \leq 2^{k+1}$. Then all possible bit patterns will occur exactly once.
Concretely1 1I do different numbers than Jeff gave, but the idea is the same I think. Mistakes are probably my own. , consider $k = 5$, $n = 3$.
\begin{equation*} v_{6}(3) = (3, 5, 8, 4, 2, 1) \equiv (1, 1, 0, 0, 0, 1). \end{equation*}
This indicates that $T(\cdot)$ fills up $2$-adic discs, and one can get lost studying patterns in the binary expansions under Collatz.
Probabilistic thought
Considered $2$-adically, this map is doing perfect coin flips. This is nontrivial.
Assuming the claim, there exists $n$ such that $v_k(n) = (1, \ldots, 1, 1)$. This means that there are arbitrarily long increasing sequences under the Collatz map. Troubling!
Considered $2$-adically, there will be a sequence consisting of all $1$s. This is the number $1 + 2 + 2^2 + \cdots = -1$. And indeed, $T(-1) = -1$ (if we perform the natural extension to negative integers).
Negative Integers
We note that this problem can be extended to the negative integers. Experimental evidence suggests that there are three known additional cycles. These have smallest (in absolute value) elements $(-1, -5, -17)$.
Knowing anything about this is open.
An interesting question is: can one predict which of the (presumed) three cycles that a given number will lead to? This seems hard.
Probabilistic thought
This suggests a probabilistic model. Choose a large number $n$ and iterate it. Suppose $n \approx 2^k$. We might expect that the behavior under $T(\cdot)$ will act like a series of coin flips.
Probabilistically, we might expect the size to behave like \begin{equation*} n \mapsto \left( \frac{3}{2} \right)^j \left( \frac{1}{2} \right)^{k-j} n + (\text{small}), \end{equation*} where $j$ is the number of increasing coin flips. In log terms, this is \begin{equation*} \log n \mapsto j(\log (3/2)) + (k-j) \log(1/2) + \log n + (\text{small}). \end{equation*} This is a biased random variable.
In his survey paper, he carries this line of reasoning to show that for most numbers $n$, after around $k = \log_2 n$ iterations the numbers are smaller. If this were uniform, then this would show that the $3x+1$ map goes downhill — but in practice numbers could land on rare numbers that grow very large under iterates.
A set of density $1$ of integers have some $T^{(k)}(n) < n$.
The set of exceptional integers $1 \leq n < x$ without some $T^{(k)}(n) < n$ is of size $O(n^\alpha)$ for some $\alpha < 1$.
Closely related is Terry Tao's theorem.
Take any function $f(k)$ nondecreasing, $f(k) \to \infty$ (however slowly). Call an integer $n$ good if some iterate $T^{(k)}(n) \leq f(n)$. Then the set of good integers has logarithmic density $1$.
Here, the logarithmic density of a set of integers $A$ is defined as \begin{equation} \lim \frac{1}{\log X} \sum_{\substack{n \leq X \\ n \in A}} \frac{1}{n}. \end{equation} This is a really outstanding result, but it's not enough. What if everything reduces to a particular exceptional rapidly growing core?
But this is the brick wall that we have hit, and the status of affairs.
Undecideability
To end, we consider a generalized form. There will be some modulus $B$ and a partition of the congruence classes mod $B$, and then define a map \begin{equation*} g(n) = \frac{a_j}{B} n + \frac{cj}{B} \qquad (n \equiv j \bmod B). \end{equation*} There will be a separate condition for each $j$ in $0 \leq j \leq B - 1$. Each of these are maps $g : \mathbb{Z} \longrightarrow \mathbb{Z}$.
Conway had an interesting idea in 1971 or 1972.2 2Jeff says this is an extremely sketchy three page paper, with many details that want to be added. Set all $c_j = 0$. Define \begin{equation*} g(n) = \frac{a_j}{B} n \qquad (n \equiv j \bmod B) \end{equation*} such that $j a_j \equiv 0 \bmod B$.3 3This is almost correct, but perhaps possibly off.
We look at a variant of Collatz here: given $n$, does there exist some $j$ such that $g^{(j)} = 2^m$ for some $m$? Note this is easier than the typical Collatz, as $1 = 2^0$.
There exists such a function $g$ defined mod $B = 2 \cdot 3 \cdots 41$ (product of small primes) that encodes a universal Turing machine — it can in fact be written explicitly. Then for Conway's map, one only cares about $n = 2^{e_2} 3^{e_3} \cdots 41^{e_{41}}$.
By being clever, one can treat the exponents $e_j$ as registers for the Turing machine. The halt state will be $2^n$.
Then the halting problem for Turing machines implies that the Collatz question for this map is undecideable.
For fun, Conway implemented this system in a silly programming language called
FRACTRAN (a pun on FORTRAN). There exist implementations of FRACTRAN out
there. (They're not particularly useful).
The idea here is just that there are sort of related questions that are undecideable — but this is missing the $+1$ part of $3n+1$.
Omitted from this talk
Jeff omitted from this talk various aspects on the existence or nonexistence of cycles. There are interesting Diophantine equations here, but that's for another day.
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$or$$(your display equation)$$.Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.