Every pattern happens exactly once

The rung about density establishes that whether a number falls below its own start in the first few steps is decided entirely by its remainder on division by a power of two. That is a useful fact and it is a corollary of something sharper, which this rung is about.

The map from a remainder to its parity pattern is a bijection. Every sequence of odds and evens of length $k$ is realised, by exactly one residue class modulo $2^k$, no more and no fewer. Nothing is missing and nothing is repeated.

What the bijection says #

Both halves matter and they say different things.

One-to-one is the statement the rung below uses: two numbers in the same class modulo $2^k$ behave identically for $k$ steps, so the behaviour is a function of the remainder. That is what makes the density argument a finite computation.

Onto is the statement this rung is about, and it is the more surprising one. Pick a pattern at random — odd, odd, even, odd, even, even, odd — and some residue class realises it. Ask for a number whose first hundred steps are all odd and there is one, in a specific class modulo $2^{100}$. Ask for any pattern at all and the answer exists.

That has an immediate consequence worth stating plainly: the Collatz map does not restrict which sequences of odds and evens can occur. Every constraint anybody might hope for — a pattern that cannot happen, a run that must end — is absent. The dynamics permit everything locally, and whatever is true globally comes from somewhere else.

Why it is a bijection #

The proof is short and worth having, because it explains why the powers of two are the right modulus and nothing else would do.

Argue by induction on the length. At length one, a number is odd or even according to its remainder modulo two, and the two classes give the two patterns — one each.

Suppose it holds at length $k$: the $2^k$ classes modulo $2^k$ give the $2^k$ patterns, one each. Take a class modulo $2^{k+1}$; it sits inside a class modulo $2^k$, so its first $k$ steps are already determined. What has to be shown is that the two classes modulo $2^{k+1}$ inside one class modulo $2^k$ give different answers at step $k+1$.

They do, and the reason is that the map is invertible on residues. Each step is either halving or tripling-and-halving, and both are bijections modulo a power of two — halving because the number was even, tripling because three is invertible modulo any power of two. So after $k$ steps the two sub-classes are still distinct modulo two, and distinct modulo two means opposite parities at the next step.

Three being odd is the whole of it. If the rule multiplied by two instead of three the map would not be invertible modulo a power of two, the induction would fail, and patterns would collide. The conjecture’s difficulty and this bijection have the same source: the interaction between a multiplication by an odd number and repeated division by two.

That also says why no larger modulus helps. The pattern of $k$ steps is exactly a function of the remainder modulo $2^k$ — not modulo anything smaller, and modulo anything larger adds nothing. The information in a starting number, as far as $k$ steps are concerned, is precisely its last $k$ binary digits.

From patterns to cycles #

The bijection is about finite patterns. Ask for a pattern that repeats forever and the answer stops being a residue class and becomes a number.

The cycle equation says a periodic pattern of $n$ steps with $k$ odd ones forces

$$x \,(2^n - 3^k) = c,$$

with $c$ determined by the pattern. There is exactly one solution, and it is a fraction. Every periodic pattern names exactly one number that cycles through it, whether or not that number is whole.

The denominator is $2^n - 3^k$, which is even minus odd and therefore odd. That matters more than it looks: a fraction with an odd denominator can be halved when its numerator is even and can be tripled and incremented and halved when its numerator is odd, and the result is again a fraction with an odd denominator. So the map is defined on those fractions and they are genuine cycles of it.

Read that table the right way round and the conjecture changes shape. The map has an enormous number of cycles — one per periodic pattern, so infinitely many — and asking whether Collatz has a non-trivial cycle is asking whether any of them consists of whole numbers rather than fractions.

What the conjecture becomes #

Restated through the bijection, the conjecture is not about dynamics at all.

Every orbit has a parity pattern. An orbit reaching one has a pattern ending in the repeating block odd, even. An orbit in a cycle has a periodic pattern. An orbit escaping to infinity has a pattern with too many odd steps in the long run.

The bijection says every pattern belongs to some number, so all three kinds of pattern are realised by something. The conjecture is the claim that the second and third kinds are realised only by fractions and by nothing whole.

So the question is which patterns belong to integers, and that is a question about a map from the integers into the space of infinite binary sequences. That map is injective, its image is where all the difficulty lives, and nobody has any description of it.

The injectivity is worth pausing on because it is the one thing that is easy. Two different positive integers have different orbits, so different parity sequences — two numbers with the same infinite pattern would have to agree modulo every power of two, and only one number does that. So the integers embed, faithfully, into a space where every point is a legitimate orbit of something.

What the conjecture asks is where that embedding lands. The eventually-periodic sequences form a countable set inside an uncountable one, and the conjecture says the integers land not merely in it but in one specific tail of it. Stated that way it sounds outrageous — a countable set landing inside a measure-zero subset of a measure-zero subset — and every numerical check says it is true. That tension is the whole reason the problem is famous rather than merely open.

Where this sits between the two rungs below #

The three rungs beneath this one attack the problem in three different registers, and the bijection is what connects them.

The density rung uses the injective half: behaviour is a function of a remainder, so a share of the integers can be computed exactly. It gets the strongest unconditional results anybody has.

The heuristic rung replaces the pattern by a coin toss. That is only reasonable because the bijection says the patterns are equidistributed — each occurs in exactly one class of $2^k$, so a uniformly random start has a uniformly random pattern for its first $k$ steps. The heuristic is not a fantasy; it is exactly right for finitely many steps and wrong only in the limit.

The cycle rung uses the surjective half without saying so: every periodic pattern has a solution, so the search for a cycle is a search over patterns rather than over numbers, which is what makes it a divisibility question.

One fact underneath all three, used differently each time. That is worth noticing, because it says where a new idea would have to come from: not from any further consequence of the bijection, all of which are on this ladder already.

The rational cycles, looked at #

Before dismissing the fractions it is worth seeing one, because they are not exotic objects and the arithmetic on them is the same arithmetic.

Take the pattern odd, even, even — three steps, one of them odd. The denominator is $2^3 - 3^1$, which is 5, and solving gives the cycle through $1/5$. Follow it: $1/5$ has an odd numerator so it takes the odd step, giving $(3/5 + 1)/2 = 4/5$; that has an even numerator so it halves to $2/5$; and that halves to $1/5$ again. Three steps, back to the start, and every value a fraction over 5.

Nothing is being extended or completed here. The rule halve when the numerator is even, otherwise triple and add one and halve is defined on every fraction with an odd denominator, it never leaves them, and the notion of odd and even is the numerator’s. The whole numbers are the special case where the denominator is 1.

So the map has cycles everywhere and the integers are one thin slice of its domain. The trivial cycle at 1 is not the only cycle; it is the only cycle whose denominator happens to be one, out of an infinite family in which every period is represented.

Read that way, the conjecture stops sounding like a statement about a peculiar map and starts sounding like a statement about a set: the integers avoid every cycle but one, in a system that has a cycle for every pattern. That is a claim about the integers as much as about the rule.

Why the fractions do not help #

A reader meeting the rational cycles for the first time usually asks whether they can be used, and the honest answer is that nobody has managed it.

There is a second reason the rationals have not helped, and it is the more interesting one. The rational cycles are not a perturbation of the integer question that might be deformed back into it; they are a completely separate set of orbits that the integers never meet. A number with denominator 5 stays at denominator 5 forever, because neither halving nor tripling-and-adding-one changes the denominator of a fraction in lowest terms with an odd denominator. The map preserves the denominator, so the whole system splits into independent copies — one per odd denominator — and the integers are the copy at 1.

That is why knowing everything about the copy at 5 says nothing about the copy at 1. They do not interact, at all, ever.

The obstacle is compounded by the fact that the rational cycles are far too plentiful. There is one for every periodic pattern, so their number grows like $2^n$ with the period, and knowing that a particular pattern’s solution is $37/11$ rather than a whole number says nothing about any other pattern. There is no visible structure in which patterns give integers, beyond the trivial one.

The 2-adic view sharpens the same statement. The parity map extends to the 2-adic integers, where it is a homeomorphism: every infinite binary sequence corresponds to exactly one 2-adic number, and the eventually-periodic sequences correspond to the rationals with odd denominators. The conjecture is that the ordinary positive integers sit inside the sequences that end in the repeating block odd, even.

That is a beautiful reformulation and it has been available since Bernstein and Lagarias in the 1990s. It has not produced a proof, and the reason is instructive: it converts a question about a map into a question about the position of one set inside another, and nobody has any handle on where the integers go.

A number with any beginning at all #

The surjective half has a constructive form that is worth doing once, because it makes the abstraction concrete and it is a small piece of arithmetic anybody can repeat.

Ask for a number whose first four steps are odd, odd, even, odd. The requirement at each step is a congruence modulo a power of two, and solving them in turn narrows the sixteen classes modulo 16 down to exactly one. It is the class of 11, and the orbit confirms it: 11 to 17 to 26 to 13 to 20, with the entered numbers odd, odd, even, odd as demanded.

Try 3 instead and the pattern is different — 3 to 5 to 8 to 4, giving odd, odd, even, even — which is the injective half doing its work: a different class, a different pattern, and no class shares a pattern with another.

Ask for something extreme and the same machinery answers. The smallest number whose first twenty steps are all odd is 1048575, one less than $2^{20}$, and its orbit multiplies by three-halves twenty times in a row: it climbs from about a million to 3486784400, a factor of 3325, before it can begin to fall.

Orbits that climb for as long as one likes therefore exist, and they are not rare in any absolute sense: one class in $2^{20}$ is a million, and there are plenty of numbers. What the density argument says is that they are rare proportionally, and what the conjecture says is that even they come down eventually.

That is the cleanest way to see why no local argument can work. Whatever bad behaviour one asks for over a finite horizon, the bijection supplies a number exhibiting it. The conjecture is a statement about the infinite horizon, and the finite horizons are all completely permissive.

What the pictures cannot show #

The bijection is checked exhaustively to length twelve, which is 4,096 residues. The general statement holds at every length and has a short inductive proof that no figure carries.

The rational cycles are computed at lengths six and eight. Periods of interest are in the millions and the table’s pattern — the count of whole solutions not moving while the count of rationals doubles — is a fact about the short lengths, consistent with the conjecture and evidence for nothing.

And the 2-adic statement is described rather than drawn. The 2-adic integers have a picture — an infinite binary tree — and drawing the position of the ordinary integers inside it would be drawing the answer, which is exactly the thing nobody has.

Where the ladder goes next #

Named here as debts. The divergent orbits, which the pattern language handles no better than anything else: a pattern with a high proportion of odd steps in the long run corresponds to an escaping orbit, and whether any integer has one is as open as the cycle question.

And the 2-adic map’s dynamics in their own right, which are completely understood — it is conjugate to the shift on binary sequences, so it is as chaotic as anything can be — and which say nothing about the integers, in a way worth a rung of its own.

Sideways, the cycle equation solved forwards is the rung below, the density this bijection makes computable is the rung below that, the coin-toss model it justifies is the heuristic, and the problem itself is the first rung.

What is worth carrying away #

When a map turns out to be a bijection, the useful move is to ask what the two halves say separately, because they are usually used by different arguments.

Injectivity makes behaviour a function of a remainder, which is what turns an infinite question into a finite computation. Surjectivity says every pattern occurs, which is what turns a search for a cycle into a search over patterns. The first is what the density results use and the second is what the cycle bounds use, and neither argument mentions the other.

The habit worth taking is to restate a problem in the coordinates the bijection provides. Collatz in the integers is a question about a strange map. Collatz in parity sequences is a question about where one set sits inside another, and the map has become the identity.

The corollary is a caution about what a restatement buys. This one is exact, it is elegant, it has been known for thirty years, and it has not produced a proof — because moving a difficulty into better coordinates does not remove it, and the difficulty here is genuinely that nobody knows which sequences the integers occupy.