Almost every number comes down

The Collatz problem is famous for being open, and the fame obscures how much is known. It is not the case that nothing can be proved about the rule; it is the case that the last step cannot be, and the steps before it are a good deal more informative than the headline suggests.

The chief result is due to Riho Terras, in 1976, and it says this: almost every whole number is provably driven below its own starting value. Not conjecturally, not for the numbers anybody has checked — for a set of numbers of density one, by an argument that fits on two pages.

The shortcut rule #

Everything below is stated for a slightly modified rule, and the modification is free.

Under the original rule, an odd number $n$ goes to $3n+1$, which is always even, so the next step always halves. Pairing the two gives the shortcut map

$$T(n) = \begin{cases} n/2 & n \text{ even} \\ (3n+1)/2 & n \text{ odd}\end{cases}$$

which has the same orbits with the forced halvings folded in. Nothing is lost, and something important is gained: under $T$ the sequence of parities is unconstrained, while under the original rule an odd step is always followed by an even one and most parity patterns never occur.

The residue decides the parities #

Here is the fact everything rests on.

The first $k$ parities of the orbit of $n$ under $T$ depend only on $n$ modulo $2^k$. And the map from residues to parity strings is a bijection: there are $2^k$ residues and $2^k$ strings of length $k$, and each residue produces a different one.

Both halves are short to prove. If $n$ is even, its first parity is even and $T(n) = n/2$, whose residue modulo $2^{k-1}$ is determined by $n$’s modulo $2^k$; if $n$ is odd, the same holds with $(3n+1)/2$. So induction on $k$ gives the first claim. For the bijection, note that the map is a map between two sets of size $2^k$ and is onto — because given any string one can solve backwards for a residue producing it — so it is one to one.

There is a way of saying it that makes the strength obvious. Reading $n$ in base two, halving deletes the last digit and the tripling step consults only the last digit before doing so. Over $k$ steps the rule can therefore consult at most the last $k$ digits, whatever else it does — so the itinerary is a function of those digits and of nothing else.

That is a surprisingly strong statement. The parity string is the entire itinerary of the first $k$ steps, and it is decided by the last $k$ binary digits of the start. Knowing a number’s last twenty bits is knowing exactly how the first twenty steps of its orbit will go.

It is worth naming what would go wrong without the shortcut. Under the original rule, an odd step is always followed by an even one, so OO never occurs and the number of achievable strings of length $k$ is a Fibonacci number rather than $2^k$. The correspondence with residues would then be onto a proper subset, the counting below would be about that subset, and every estimate would carry an extra factor nobody wants. The pairing is not a convenience; it is what makes the bijection exact.

What a parity string does to the size #

Follow $n$ through a run whose parity string has $j$ odd steps among $k$. Each even step halves; each odd step multiplies by $3/2$ and adds a bounded amount. Chasing the constants gives

$$T^k(n) = \frac{3^j}{2^k}\,n + c,$$

where $c$ depends on the string and not on $n$, and is bounded by a constant times $3^j/2^k$.

So the multiplier is $3^j/2^k$, and whether the number has shrunk is whether that is less than one. For large $n$ the additive part is negligible, and the condition $3^j < 2^k$ decides it.

That is where the counting comes in. Among the $2^k$ parity strings, how many have some prefix with $3^j < 2^i$? Since $\log_2 3 \approx 1.585$, the condition on a prefix of length $i$ with $j$ odd steps is $j < i/1.585$, that is, fewer than about $63\%$ odd steps. And a random string of length $i$ has about half its entries odd, comfortably under that threshold.

So a string fails to drop only if it has an unusually large excess of odd steps for its whole length, and by a straightforward large-deviations estimate the share of strings that manage it goes to zero as $k$ grows.

The estimate is worth doing roughly, since it explains the rate. A string of length $i$ needs more than $0.63 i$ odd steps to keep the multiplier above one, against an expected $0.5 i$ — an excess of $0.13 i$, or about $0.26\sqrt{i}$ standard deviations. For that to hold at every prefix length simultaneously is far more demanding than holding at one, and the share of strings managing it falls geometrically rather than merely tending to zero. That geometric fall is what the hero figure’s curve approaches one at.

Reading the shading across the three tables gives the theorem as an observation before it is an argument. At four steps the majority of classes shrink; at five more of them do; at six more still. The count is a count of binary strings with a bounded excess of ones, which is a question about coin tossing, and the answer is that an excess of the required size becomes exponentially rare.

The theorem #

Putting the two halves together:

• the parity string of the first $k$ steps is decided by the residue modulo $2^k$;
• a string with a prefix satisfying $3^j < 2^i$ forces the orbit below its start;
• the share of strings with no such prefix tends to zero.

Therefore the set of starting values whose orbits drop below their own start has density one. The hero figure is that share, counted exactly at each $k$.

The consequence usually quoted is the corollary. If almost every number drops below itself, then almost every number’s orbit eventually reaches a smaller number, and iterating that argument shows almost every number reaches $1$ — with “almost every” weakening a little at each iteration, which is why the theorem stops short of the conjecture.

What the theorem does not give #

Three gaps, and the third is the one that matters.

It says nothing about any particular number. Density one is compatible with infinitely many exceptions — the squares have density zero and there are infinitely many of them — and the exceptions here are not identified even as a set. If some number’s orbit never drops, the theorem is undisturbed.

It does not rule out a cycle. A number in a non-trivial cycle never falls below its own start in the long run, but a cycle is a measure-zero object and density arguments cannot see it. Ruling out cycles is a separate problem, attacked by different methods — continued fractions and bounds on how well $\log_2 3$ can be approximated by rationals — and the current results rule out cycles below extremely large lengths.

And it cannot be iterated to a proof. Applying the argument again to the numbers that dropped gives a set of density one within that set, and repeating this infinitely many times does not give a set of density one at the end. The losses compound.

The reason they compound is worth stating precisely, because it is the crux. After the first drop the orbit is at some new number $m < n$, and the theorem applies to $m$ only if $m$ is typical — but $m$ was produced by a process that selected it, so there is no reason to expect it to be. Every iteration of the argument needs the images to be as random as the starts, and nothing establishes that, which is exactly the point at which Tao’s much later work makes progress by tracking a distribution forward rather than a set.

That is precisely the gap between the theorem and the conjecture, and closing it has resisted everybody.

The stopping time, and how long a drop takes #

The theorem is about whether a number drops. How long it takes is a second question with a clean answer, and it is worth having because it is the quantity the figures actually measure.

The stopping time of $n$ is the least $k$ with $T^k(n) < n$. The theorem says it is finite for almost every $n$; the counting says more, namely that its distribution is essentially that of the first time a random walk with a slight downward drift goes below its starting level.

That comparison predicts the shape. A walk with drift $\mu < 0$ per step hits any level below with probability one and does so in a time whose distribution has an exponential tail — so the share of numbers with stopping time above $k$ should fall geometrically in $k$, which is exactly the shape of the gap between the hero figure’s curve and the line at one.

The prediction is checkable and it holds. The measured shares at $k = 8, 10, 12$ leave gaps of roughly a tenth, a twentieth and a sixteenth of what remained — a geometric decay with ratio near two thirds, which is what the walk predicts. Nothing about the agreement is surprising and it is the reason the theorem’s proof works: the parity string behaves like a coin toss because the residues make it one, and the walk is not an analogy but the same combinatorial count.

What has been squeezed out of it since #

The line of work is worth knowing because it shows what “progress on an open problem” looks like when the problem stays open.

Terras, 1976: density one drop below the start, by the argument above. Everett proved the same thing independently in the same year, which is a good sign that the argument is the natural one.

Krasikov and Lagarias, 2003: the count of numbers below $x$ that reach $1$ is at least $x^{0.84}$. That is a lower bound on the number of numbers the conjecture is true for, and it is not $x$.

Tao, 2019: almost every orbit reaches a value below any prescribed slowly growing function of the start — below $\log\log\log\log n$, say, which is as close to “reaches one” as a density statement has come. This is by far the strongest result, it uses genuinely different machinery — a logarithmic density argument together with a study of how the map acts on a suitably chosen probability distribution — and it still says almost every.

The pattern across fifty years is that the density statements get stronger and the exceptional set is never eliminated, and there is a structural reason: every method available is statistical, and a statistical method cannot address a single number.

Why the residue trick is the right tool #

The reduction to residues is worth abstracting, because it is the standard move for iterations on the whole numbers.

The rule mixes two operations of different characters: halving, which is a shift in base two, and tripling-and-adding, which is not. What makes the analysis possible is that halving only looks at the last digit, so a fixed number of steps only ever consults a fixed number of digits.

That is the same reason the Chinese remainder theorem is useful: a question about the whole numbers becomes a question about a finite ring, and a finite ring can be searched exhaustively. Here the ring is $\mathbb{Z}/2^k$ and the search is over $2^k$ residues, which the figures do at $k$ up to twelve.

The limitation is the same too. A property that depends on all the digits — such as whether an orbit ever reaches one — is not visible in any $\mathbb{Z}/2^k$, and no amount of increasing $k$ makes it so.

The cycle question, separately #

Ruling out other cycles is worth a section because it uses methods with nothing in common with the above, and it has come much closer to a complete answer.

Suppose $n$ lies on a cycle of $T$ of length $k$ with $j$ odd steps. Then $T^k(n) = n$, and the formula from earlier gives

$$n = \frac{3^j}{2^k}n + c \quad\Longrightarrow\quad n\left(1 - \frac{3^j}{2^k}\right) = c.$$

For $n$ to be a positive whole number, $3^j/2^k$ must be very close to one and just below it — because $c$ is bounded by roughly $3^j/2^k$ times a small constant, so the bracket has to be tiny.

That is a question about how well $\log_2 3$ can be approximated by rationals $k/j$, and it is exactly the subject of continued fractions. The continued fraction of $\log_2 3$ is known, its convergents are known, and each convergent gives one candidate ratio; checking the candidates rules out cycles of every length below an enormous bound.

So the cycle half of the problem is attacked by the theory of best rational approximation and the density half by counting binary strings, and the two halves of one conjecture live in different subjects — one in probability and one in the approximation of an irrational by fractions. Neither half has any purchase on the other, which is a fair description of why the problem is hard: it is two problems, and the proof would have to be one argument.

What the pictures cannot show #

The share is a limit and the figure stops at twelve. The sequence of shares is increasing and bounded by one; that it converges to one rather than to something smaller is the large-deviations estimate, which is prose.

The parity table is exhaustive at thirty-two and the claim is about every $k$. Checking all thirty-two strings is a complete verification of one case, and the induction that makes it general is not drawn.

The tree figure shows eighteen numbers and the tree is infinite. Its branching is irregular — every node doubles, and some nodes additionally have an odd predecessor — so the growth rate is not a simple power, and the question of whether the tree covers the whole numbers is the conjecture. A drawing of nine levels shows the irregularity and settles nothing.

And the drop is about large numbers. The multiplier condition forces a drop for $n$ large enough, and the figures verify the prediction on a large member of each class rather than on the smallest. Small numbers are genuine exceptions to the condition and not to the theorem, which is a distinction a picture cannot carry.

Where the ladder goes next #

The next rung asks not what is proved but what is expected, and why: the heuristic that says the conjecture ought to be true, together with a clear statement of why an argument that convincing cannot be made into a proof.

Named here as a debt: the total stopping time — the number of steps to reach one rather than to fall below the start — whose average is conjectured to be a constant times the logarithm of the start and whose distribution has been measured extensively and proved about hardly at all. The lengths the first rung plots are that quantity, and nothing above says anything about them.

Sideways, the parity string is an orbit written as a word in exactly the sense that field’s essays define, the reduction to a finite ring is the Chinese remainder theorem’s habit, and the original statement of the problem is the first rung.

What is worth carrying away #

An open problem is usually not a wall but a place where a good method runs out, and knowing which method and where is more useful than knowing the problem is open.

Here the method is: reduce a fixed number of steps to a residue class, count residues, and conclude about density. It gives density one, immediately and cleanly. It cannot give every, because the residue only sees finitely many digits and the conjecture is about all of them.

The habit worth taking is to ask what a method’s finite window is. Every technique for an infinite problem looks at some bounded amount of each object, and the statements it can reach are exactly the ones decided within that window.