Where the Collatz map is a coin

The Collatz map used throughout these essays is the shortcut version: halve an even number, and send an odd number $n$ to $(3n + 1)/2$. The essay on parity patterns found that the first $k$ odd-and-even steps of an orbit are decided exactly by the number’s last $k$ binary digits, and that every pattern of $k$ steps happens exactly once among the numbers below $2^k$. It ended by naming a debt: the map extends to a much larger world, the 2-adic integers, where its behaviour is completely understood — and understanding it there says nothing about whether every whole number comes down to 1.

This essay pays that debt. It is worth paying because the way a complete understanding can coexist with total ignorance is itself the clearest statement of why the Collatz problem is hard.

Numbers that run on for ever to the left #

A whole number in binary is a finite string of digits: $27$ is $11011$. A 2-adic integer is a string that is allowed to continue for ever to the left, $\ldots 0011011$, with no leading end. Addition and multiplication work exactly as in school, digit by digit from the right with carries moving left, and the carries never need to finish because nothing is ever read from the left end.

In that system some familiar numbers have surprising strings. The string of all ones, $\ldots 1111$, is $-1$: add $1$ to it and every digit becomes $0$ with a carry that moves off for ever to the left, leaving $\ldots 0000$. That is the series that converges to minus one, $1 + 2 + 4 + 8 + \cdots$, written as a string of digits. Fractions with odd denominators have strings too, and they are exactly the strings that eventually repeat: $1/3$, for instance, is a string whose digits settle into $01$ repeated, because multiplying that string by three produces the carry pattern of $1$.

The Collatz map makes sense on all of these. Whether a 2-adic integer is odd is decided by its last digit. Halving an even one shifts its string one place to the right. And $(3x + 1)/2$ for an odd $x$ is computed digit by digit from the right, exactly as for a whole number, since $3x + 1$ is even. So $T$ is defined on every string, and whole numbers are the strings that end, on the left, in zeros for ever.

Parity coordinates, in which the map is a shift #

Every 2-adic integer $x$ has a parity string: the sequence of 1s and 0s recording whether $x$, $T(x)$, $T^2(x), \ldots$ are odd or even. Call it $Q(x)$. For whole numbers this is the sequence of odd and even steps of the orbit, which the pattern essay studied in its first $k$ entries.

The key fact, due to Jeffrey Lagarias in 1985, is that $Q$ is a bijection from the 2-adic integers to the set of all infinite binary sequences. Every sequence of odd and even steps is the parity string of exactly one 2-adic integer. The finite statement — every pattern of $k$ steps happens exactly once below $2^k$ — is this fact truncated, and the infinite one follows by letting $k$ grow, since each new step of the pattern decides exactly one new binary digit of $x$.

The finite version is where the infinite one comes from, and the mechanism is worth stating because it is also the reason the bijection is so rigid. Suppose the first $k$ parities of a pattern have fixed the last $k$ binary digits of $x$. The next parity depends on the digit in position $k$. Changing that digit adds $2^k$ to $x$, and after $k$ steps — $a$ of them odd, each multiplying by three, and $k$ halvings in all — that addition has become exactly $3^a$ added to $T^k(x)$. Three to any power is odd, so the change flips the next parity. One of the two choices for the digit gives the pattern’s next entry, and only one. Digit by digit, the pattern builds its number, and no two patterns can build the same one.

Now look at what $T$ does to a parity string. The parity string of $T(x)$ is the parity string of $x$ with its first entry removed. That is immediate — the orbit of $T(x)$ is the orbit of $x$ minus its first term — and it is the whole content of the change of coordinates.

In parity coordinates, then, the Collatz map is the shift: delete the first symbol of a binary sequence. Read a binary sequence as a fraction between 0 and 1, and the shift becomes the doubling map $y \mapsto 2y \bmod 1$ — which is exactly the pair of straight lines in the right-hand panel of the opening figure. The map is conjugate to the shift: after a relabelling of points that is a bijection, it is the same map.

The left-hand panel of that figure is worth a second look. Half of it is already a straight line: an even number is halved, which shifts its binary string one place, and in the backwards-reading coordinates a shift is a doubling. All the scatter comes from the odd branch, where $(3x + 1)/2$ mixes the digits. The change to parity coordinates straightens out that half as well.

Everything the shift does, the Collatz map does #

The shift on binary sequences is the most thoroughly understood chaotic system in mathematics. Symbolic dynamics is largely the study of it and its relatives. Transferred to the 2-adic integers through $Q$, every one of its properties becomes a property of the Collatz map.

It is a coin. Choose a 2-adic integer at random — every binary digit an independent fair coin — and the parity string of its orbit is itself a sequence of independent fair coins, because $Q$ preserves this natural measure. The odd and even steps of a random 2-adic orbit are exactly as random as tossing a coin, not approximately, and forever, not for a while. That is the coin-toss model of the heuristic that cannot be a proof, and on the 2-adic integers it is not a heuristic. It is a theorem.

It is as chaotic as a map can be. It is mixing, in the strongest sense: knowing the first $k$ digits of a 2-adic integer tells nothing about its orbit’s parities after step $k$. Two 2-adic integers that agree in their last $k$ digits have orbits that agree for $k$ steps and are independent afterwards — sensitive dependence in its cleanest form.

Its periodic points are exactly known. Every periodic parity string is the string of exactly one 2-adic integer, and that integer is periodic under the map. Each is a fraction with odd denominator, which is the content of the rational cycles the pattern essay drew. There are $2^k$ of them with period dividing $k$, just as for the doubling map.

Its fixed points are $0$ and $-1$. Zero is even and halves to itself. Minus one is odd, and $(3 \cdot (-1) + 1)/2 = -1$. Their parity strings are all zeros and all ones.

The integers that imitate minus one #

The fixed point $-1$ has parity string all ones: every step odd, each multiplying by about $3/2$. In the ordinary sense it is an orbit that climbs for ever — except that $-1$ is not a positive whole number, and as a 2-adic integer it simply stays where it is.

Whole numbers can imitate it for a while. A whole number that agrees with $-1$ in its last $k$ binary digits is one ending in $k$ ones — the simplest is $2^k - 1$ — and since the first $k$ parities depend only on the last $k$ digits, its orbit takes $k$ odd steps in a row, just as $-1$’s does.

The straight climbs in the figure are exactly $k$ steps long. After them, $2^k - 1$ has been multiplied by about $(3/2)^k$ and has become $3^k - 1$ — even, and with no remaining resemblance to $-1$. From there its orbit is as unpredictable as any other, and in each case it comes down. The number $2^{40} - 1$ climbs from forty binary digits to about sixty-three and takes 343 steps in all to reach 1.

This is the 2-adic picture of a question the pattern essay left open: can a whole number follow a rising pattern for ever? Any rising pattern is followed for ever by some 2-adic integer. A whole number follows it only for as long as its binary digits agree with that 2-adic integer’s, and every whole number has only finitely many digits before the zeros begin. Whether its digits force the orbit to fall eventually is exactly what nobody can prove.

The density that decides up from down #

What makes a parity pattern rising or falling is the fraction of its steps that are odd. An odd step multiplies by about $3/2$, an even one by $1/2$. So a pattern with a fraction $d$ of odd steps multiplies the size by about $3^d/2$ per step, and it grows exactly when $3^d > 2$, that is, when

$$d > \frac{\log 2}{\log 3} \approx 0.631.$$

The arithmetic can be tested on four patterns, and the result matches the prediction to within rounding: after sixty steps of the pattern $110$, with two thirds of its steps odd, the number has grown by about three binary digits, and the prediction from the density is $60 \times (\tfrac{2}{3}\log_2 3 - 1) \approx 3.4$. The pattern $10$ is the one the trivial cycle $1 \to 2 \to 1$ follows forever; any other whole number following it for sixty steps loses about twelve binary digits.

A random 2-adic integer has parity string with density of odd steps exactly $\tfrac12$ — a coin — and $\tfrac12$ is below the critical $0.631$. That is the heuristic for why orbits come down: on average they shrink by a factor of $\sqrt 3/2$ per step. For the random 2-adic integer this is a theorem; for whole numbers it is the unproved step.

The same coin for a map that climbs #

The conjugacy is not special to $3x + 1$. The argument above used two facts: that the parity of $x$ decides the branch, and that changing the next binary digit of $x$ flips the next parity. Both hold for the map that sends even $x$ to $x/2$ and odd $x$ to $(5x + 1)/2$, and for $(7x + 1)/2$, and for any odd multiplier. Every one of these maps is conjugate to the shift on the 2-adic integers, and every one is, in the same exact sense, a fair coin.

And yet they behave completely differently on whole numbers. With multiplier $5$, an odd step multiplies by about $5/2$ and an even step by $1/2$, so a random pattern — half odd — multiplies by $\sqrt 5/2 \approx 1.12$ per step, which is growth. The critical density is $\log 2/\log 5 \approx 0.43$, below one half, and the coin now favours climbing. Experiments agree: under the $5x + 1$ map most starting numbers appear to climb for ever, and small ones fall into a handful of cycles — $13 \to 33 \to 83 \to 208 \to 104 \to 52 \to 26 \to 13$ is one — while the question for $3x + 1$ is whether anything climbs at all.

So the 2-adic picture cannot tell the two maps apart. Both are the shift; both are coins. The difference between a map where everything seems to fall and a map where almost everything seems to rise is the single number $\log 2/\log 3$ against $\log 2/\log 5$, compared with the density one half — a statement about the sizes the steps multiply by, which the 2-adic world, measuring divisibility by two and nothing else, does not see. And proving that any particular whole number under $5x + 1$ climbs for ever is as far out of reach as proving that none does under $3x + 1$.

Why understanding the whole does not reach the part #

Here is the situation laid out plainly. The Collatz map on the 2-adic integers is conjugate to the shift, measure-preserving, mixing, with every periodic point known. Nothing about it is mysterious. The whole numbers sit inside the 2-adic integers — as the strings ending in zeros to the left — and the Collatz conjecture is a statement about what happens to those particular points.

And they are a set of measure zero. A property that holds for a random 2-adic integer with probability one — that its parity string has density $\tfrac12$, say — can fail on every whole number without contradicting anything, because the whole numbers are too few to register. Worse, the conjugacy $Q$ scrambles them: the parity strings of whole numbers are not a set anyone can describe. Which parity strings the whole numbers have is not known in any form: whether they are all eventually periodic is the Collatz problem itself, restated.

So the 2-adic picture converts the Collatz problem into a question about where a small, explicitly described set of points goes under a map that is completely understood — and the answer depends entirely on the fine structure of that set, which the map’s good behaviour on average says nothing about. It is the same gap that the heuristic essay found between a probability model and a proof, now made exact: the model is literally true on a larger space, and the problem lives on a part of it the model cannot see.

What the pictures cannot show #

Every figure truncates. A 2-adic integer is an infinite string, and the figures use its last few dozen digits, which determine the first few dozen steps of its orbit and nothing after. The opening figure’s clean lines are a statement about 2,048 strings of eleven digits, and the conjugacy is a statement about all infinite strings; the figure is the eleventh approximation to it, and each finer approximation looks the same. The bijection figure has the same character: it lists every pattern of a fixed length, and the claim about infinite strings is an argument, the digit-by-digit one above, that the finite lists cannot replace.

The climbing orbits are whole numbers, followed to the end, and they do come down — every one of them. That is evidence of the usual kind, which is to say it is worth nothing as proof: the numbers that would break the conjecture, if any exist, are far beyond anything that can be run. And no figure can show a 2-adic integer climbing for ever, because the only thing that climbs for ever with every step odd is $-1$, and in the 2-adic world it does not climb at all.

Still open: which strings the whole numbers have #

The 2-adic dynamics are closed. What is open is the one question that matters. Lagarias’s periodicity conjecture says that a 2-adic integer has an eventually periodic parity string exactly when it is a rational number. One direction is proved — a periodic parity string belongs to a rational, as the cycle equation shows. The other says every rational number with odd denominator, and in particular every whole number, has an orbit that eventually repeats — so no whole number climbs for ever — and together with the belief that the only cycle among positive whole numbers is $1 \to 2 \to 1$, it would give the Collatz conjecture. Nobody knows how to decide from a number’s binary digits what its parity string does in the long run, and the conjugacy offers no help, since it is defined by the orbit it is supposed to describe.

A second question is the one the climbing figure raises: whether any whole number has an orbit whose parity string has density of odd steps above $\log 2 / \log 3$ forever, which would make the orbit grow without bound. Terence Tao showed in 2019 that almost all orbits, in the sense of logarithmic density, eventually fall below any function that tends to infinity, however slowly. That is the strongest statement known, and it still leaves room for a single divergent orbit.