The heuristic that cannot be a proof

Ask anybody who has worked on the Collatz problem whether it is true and the answer is yes. Ask why and the answer is a calculation that takes two lines, uses nothing beyond logarithms, and is wrong in a way that has resisted repair for eighty years.

The calculation is worth doing carefully, because the interesting part is not that it suggests the right answer — plenty of heuristics do — but that the place where it stops being a proof is unusually clean.

The calculation #

Work with the shortcut rule: halve an even number, and send an odd $n$ to $(3n+1)/2$.

Take a number and ask what one step does to it, in the logarithm. If it is even, the logarithm falls by $\log 2$. If it is odd, it rises by about $\log(3/2)$.

Now suppose — and this is the whole of the assumption — that a number in the middle of an orbit is as likely to be even as odd, independently of everything before. Then the expected change in the logarithm per step is

$$\frac{1}{2}\log\frac{1}{2} + \frac{1}{2}\log\frac{3}{2} = \frac{1}{2}\log\frac{3}{4} \approx -0.1438.$$

Negative. So the logarithm of the orbit is a random walk with a downward drift, and a random walk with downward drift goes to minus infinity. In the original terms, the orbit shrinks by a factor of about $3/4$ every two steps, and any number is driven down to the bottom.

Since the only place at the bottom is the cycle $1 \to 2 \to 1$, every orbit ends there. That is the conjecture.

Notice how little the calculation uses. It does not use that the multiplier is three; any multiplier below four would give a negative drift and the same conclusion. It does not use that the added constant is one; the constant vanishes from the logarithm entirely for large numbers. The two lines are about the ratio $\log 3$ against $\log 4$ and nothing else, which is a warning about how much of the problem they can possibly be seeing.

It agrees with the measurements #

The heuristic makes several checkable predictions and they are all correct.

Half the steps should be odd. Over a large sample the figure measures the share and finds it at a half to within a per cent.

The drift should be about $-0.144$ per step. Measured over the same sample, it is.

The number of steps to reach one should be about $\log n / 0.1438$, which is $6.95 \log n$, or about $2.9 \log_{10} n$ steps per decimal digit. That prediction is the one the data confirms most strikingly, over ranges of many orders of magnitude.

The maximum a walk reaches before descending should have a known distribution. A walk with drift $\mu$ starting at height $h$ reaches a height $h + a$ before descending with probability falling like $e^{-2|\mu| a}$, so the largest value an orbit attains should be a bounded multiple of the start with exponentially small probability of exceeding it. That is why orbits like twenty-seven’s, which climbs by a factor of three hundred and fifty, are rare and are not absent.

And the record-holders should be rare and roughly predictable. A start whose orbit is unusually long is a walk that drifted upward for an unusually long time, and the frequency of such walks is what a large-deviations estimate gives. The measured distribution of long orbits matches it.

Four independent predictions, all confirmed over enormous ranges. In any empirical subject that would settle the matter.

Where it stops being a proof #

The assumption is that the parity of a number in the middle of an orbit is a fair coin, independent of the rest. Every part of that is false, and it is worth separating the ways.

The numbers are not random. There is no probability space. Each orbit is a completely determined sequence, and the statement “the next value is odd with probability a half” is not a statement about it. What the heuristic really computes is the behaviour of a different object — an actual random walk — chosen because it resembles the orbit.

The steps are not independent. They are not even nearly independent in the way the calculation needs. If $n$ is odd then $(3n+1)/2$ has a parity determined by $n$ modulo $4$; the previous rung shows the first $k$ parities are a function of $n$ modulo $2^k$. So the parity string is completely determined by the start, and its resemblance to a coin sequence is a fact about the distribution over starts rather than about any orbit.

And a statement about almost every start is not a statement about every start. Even granting a probabilistic model that is right on average, an exceptional set of density zero survives every argument of this kind — and the conjecture is precisely the claim that the exceptional set is empty.

That last point is the fatal one, and it is fatal in a specific way. Any argument built out of averages can be pushed to “density one” and no further, and the previous rung shows that is exactly how far the best rigorous results have got.

That figure is the whole objection in one table. Every string of four parities occurs, once each, so choosing a start uniformly at random from a range gives a parity string that is uniform on the sixteen possibilities — which is why the averages come out right. But choosing a particular start fixes the string entirely, and the conjecture is about particular starts.

The heuristic is exactly right about the distribution and says nothing about any member of it. That is a sharper statement than “it is only a heuristic”, and it is what makes the failure interesting rather than merely regrettable.

The same heuristic on a rule that is false #

The clearest evidence that the argument is not a proof is that the same argument, applied to a very slightly different rule, gives the wrong answer.

Replace $3n+1$ by $5n+1$. The expected change per step becomes

$$\frac{1}{2}\log\frac{1}{2} + \frac{1}{2}\log\frac{5}{2} = \frac{1}{2}\log\frac{5}{4} > 0,$$

so the heuristic predicts orbits grow, and most of them do. That is the heuristic getting a correct answer for a different rule, which is reassuring.

Now replace it by $3n - 1$. The drift is identical to Collatz’s, so the heuristic makes the same prediction: every orbit falls to the bottom. It is false. The rule $3n-1$ has at least three distinct cycles, at $1$, at $5 \to 7 \to 10 \to 5$, and at $17$, and orbits fall into whichever of them they meet.

So a drift argument cannot distinguish a rule with one cycle from a rule with three, because the drift is the same and the cycles are invisible to it. Any proof of the Collatz conjecture has to rule out other cycles, and the drift says nothing whatever about them.

There is a second false relative worth knowing, because it fails the other way round. Consider the rule that sends $n$ to $3n+1$ when odd and $n/2$ when even, but applied to the negative integers. The drift is identical again, and the negative numbers have at least three cycles of their own — at $-1$, at $-5$, and at $-17$. The Collatz conjecture is a statement about which side of zero one is on, and no argument about growth rates can be.

Three rules, one drift, three different truths. The drift is a real quantity, correctly computed, and it is simply not the quantity that decides the question.

What would be needed instead #

The gap has a shape, and knowing it is useful.

Something that sees individual numbers. Every existing method averages, and averaging loses the exceptional set. What is wanted is an argument that, given a specific $n$, produces a bound — and no such argument is known even for the numbers where it is easiest.

Something that rules out cycles. This half is separate, is attacked by continued fractions and bounds on the rational approximation of $\log_2 3$, and has produced strong results — no other cycle below a length of billions — without producing a proof.

And something that connects them. Even granted both halves, a proof would need to combine “every orbit is eventually driven down” with “there is nowhere to stop except one”, and each of the two is currently a different subject with its own vocabulary. A single argument reaching both is what nobody has, and the same shape of gap is what makes several other elementary-looking problems hard.

How far a heuristic of this shape can be pushed #

It is worth knowing that the drift argument is not the end of the probabilistic line — it is the crudest member of a family, and the family has been developed a long way.

The first refinement is to model the whole orbit rather than one step. Instead of asking what a step does on average, one can ask what the distribution of $T^k(n)$ looks like as $n$ ranges over a large interval, and how that distribution evolves. That is a much stronger object than an expected value, and it is what Tao’s 2019 argument tracks — through a carefully chosen logarithmic weighting that makes the evolution controllable.

The second refinement is to keep the dependence rather than assume it away. The parities are not independent and their dependence is completely explicit: it is the residue structure of the previous rung. A model that carries that structure is a Markov chain on residues rather than a coin, and its drift is the same while its fluctuations are not.

Neither refinement crosses the gap, and the reason is unchanged. A distribution’s behaviour is a statement about almost every start, and the exceptional set survives. What the refinements buy is a much stronger “almost every” — below any slowly growing function rather than below the start — which is progress measured in exactly the units the crude argument sets.

Why a heuristic like this is worth having #

It would be a mistake to conclude that the argument is worthless because it is not a proof. It does three things.

It predicts numbers. The constant $6.95$ for steps per logarithm is a real prediction, it is confirmed to several digits over ranges of $10^{20}$, and no proof produces it — the rigorous results give inequalities and this gives an equality. A heuristic that gets the constants right is a model of the phenomenon even when it is not an argument about it.

It says what a proof cannot look like. Any purported proof that would work equally for $3n-1$ is wrong, because $3n-1$ is false. That is a genuine filter and it has disposed of a great many attempts.

And it says where to look. The heuristic’s failure is entirely in the independence assumption, so the useful work is on how far the parities are independent, and over how long a stretch — which is what the residue analysis of the previous rung measures and what Tao’s much stronger result exploits by tracking a whole distribution rather than a set. A heuristic that fails in one identifiable place is a research programme; one that fails everywhere is only an opinion.

Twenty-seven is worth dwelling on because it is the only reason most people distrust the conjecture. It is small, its orbit is enormous, and there is no visible reason for either. Under the heuristic it is a walk that happened to drift upward for forty steps, which has a probability, and among the first hundred starts one should expect roughly one such — so it is not evidence against anything. The unsettling thing about it is that no property of twenty-seven explains it, and that is the same complaint the heuristic itself is subject to.

What the pictures cannot show #

Four orbits are four orbits. The claims are about averages over infinitely many starts, and the sample the figure measures over is four thousand — enough to pin a share to a per cent, and no evidence at all about the exceptional set the whole difficulty concerns.

The drift is invisible in any single orbit. Each drawn orbit wanders, and the downward trend is a fitted quantity rather than something a reader can see. Twenty-seven in particular rises for a long stretch, and it is a perfectly ordinary member of the distribution.

A logarithmic axis flattens the excursions. The orbits are drawn with the logarithm on the vertical axis, which is the right choice for showing a multiplicative drift and makes a climb by a factor of three hundred look like a modest bump. The unlogged picture of twenty-seven is mostly empty space with a spike in it, and neither drawing shows both the trend and the excursion honestly.

And nothing here can show a counterexample not existing. Every figure shows orbits that reached one, because those are the ones that can be drawn. A picture of the conjecture’s content — that there is no orbit doing anything else — is a picture of an absence.

Where the ladder goes next #

Named here as debts, both raised above and not settled: the cycle problem, which is a question about continued fractions and has produced far stronger results than the density side; and the total stopping time distribution, whose measured shape matches the random-walk prediction closely and has never been derived.

Also left standing: the observation that the conjecture is equivalent to a statement about a two-symbol dynamical system, which several people have used to argue that it is undecidable in a suitable generalisation — a claim about a family of rules rather than about this one, and a rung on a different ladder.

Sideways, the walk with drift is the recurrent-or-not question a random walk asks with the answer decided by a sign, the parity string’s determinism is the previous rung’s residue theorem, and the original problem is the first rung.

The same shape elsewhere #

Heuristics of exactly this kind are standard across number theory, and knowing the pattern makes their status easier to read.

Cramér’s model for the primes treats the number $n$ as prime with probability $1/\log n$, independently. It predicts the prime number theorem, the twin prime constant, the distribution of gaps — and it is known to be wrong in detail, because it ignores that no number above two is both prime and even. The refined version fixes the divisibility and gets closer, and neither version proves anything.

The circle method’s main term is a heuristic count made rigorous, and the difference between a heuristic and a proof there is a bound on an error term that took decades to establish in each case where it has been.

And the density of primes in an arithmetic progression was a heuristic for a century before Dirichlet proved it, using machinery from a different subject entirely.

The pattern is that a heuristic gets the main term and a proof needs the error term, and the error term is usually where a new idea has to be found. What distinguishes Collatz is that nobody knows what the error term would even be an error in: there is no candidate exact statement whose approximation the drift is.

What is worth carrying away #

A heuristic that predicts the constants and cannot prove the theorem is a model, and models are worth having as long as their status is stated.

The Collatz drift argument gets the growth rate, the step count, the distribution of long orbits and the answer right. It fails because it replaces a determined sequence by a random one, and the replacement is exactly the step that loses the exceptional set — which is the whole content of the conjecture.

The habit worth taking is to test a heuristic on a rule where the answer is known to be different. The drift for $3n-1$ is identical and the conclusion is false, which locates the argument’s blind spot precisely: it cannot see cycles. That test costs one line and is worth more than any amount of confidence.