How short a cycle could be

The drift argument predicts that every Collatz orbit descends, agrees with every measurement anybody has made, and is not a proof. Its blind spot is named precisely on that rung: the rule $3n - 1$ has the identical drift and has three cycles, so no argument about growth rates can rule a cycle out.

This rung is about the arguments that can, and they are arithmetic rather than probabilistic. They have produced hard theorems where the density side has produced heuristics, and the reason is that a cycle is a finite object satisfying an exact equation.

The equation a cycle satisfies #

Work with the shortcut map: halve an even number, and send an odd $n$ to $(3n+1)/2$. It is the same dynamics with the forced even step folded in, and it makes the arithmetic clean.

Follow an orbit for $n$ steps of which $k$ are odd. Each odd step multiplies by three and adds one; each step divides by two. Composing them gives

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

where $c$ is a positive whole number determined entirely by where in the sequence the odd steps fall. Nothing about $x$ enters $c$.

If the orbit is a cycle, $T^n(x) = x$, and rearranging gives

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

That is the whole subject of this rung. A cycle exists exactly when some pattern’s $c$ is divisible by $2^n - 3^k$, and the quotient is the cycle’s starting value.

Two consequences follow immediately. The quantity $2^n - 3^k$ must be positive, so $2^n > 3^k$ and $n/k > \log_2 3$. And $x$ is large exactly when $2^n - 3^k$ is small, because $c$ is bounded by the pattern’s own size.

Why the logarithm appears #

The Collatz conjecture has been verified for every starting number below $2^{68}$. So a cycle nobody has found consists of numbers all larger than that.

Feed that into the equation. If $x$ exceeds $2^{68}$ and $x(2^n - 3^k) = c$, then $2^n - 3^k$ has to be smaller than $c$ divided by $2^{68}$ — which forces $2^n$ and $3^k$ to be within a whisker of each other, relative to their own size.

Taking logarithms turns that into a statement about a fraction:

$$\frac{n}{k} \text{ must be extremely close to } \log_2 3,$$

with the closeness improving as the verification bound rises. And the fractions that approximate a number extremely well are its continued fraction’s convergents and nothing else — which is the theory of how close a fraction can get, used here for the purpose it was built for.

The continued fraction of $\log_2 3$ begins 1, 1, 1, 2, 2, 3, 1, 5, 2, 23. Its convergents are $2/1$, $3/2$, $8/5$, $19/12$, $65/41$, $84/53$, $485/306$, $1054/665$, and then a jump to $24727/15601$ caused by the 23 in the expansion.

The denominators are the only possible values of $k$, and they are sparse. Every fraction appears exactly once in the Stern–Brocot tree and the convergents are the path down it towards $\log_2 3$; what the argument uses is that the path visits very few fractions and every fraction not on it is a worse approximation than one that is. That is the whole mechanism: a cycle’s number of odd steps is not merely large, it is one of a short list of specific numbers.

Half the candidates fail on sign alone #

The table has a feature that is easy to walk past and cuts the list in half.

The convergents of a continued fraction alternate, approaching their target from above and below in turn. Here $2/1$ is above $\log_2 3$, $3/2$ is below, $8/5$ above, $19/12$ below, and so on. A cycle needs $2^n > 3^k$, which is exactly the condition $n/k > \log_2 3$ — so every other convergent is excluded before any arithmetic is done.

The exact integers make it concrete. For $8/5$: $2^8 = 256$ and $3^5 = 243$, so the gap is 13 and a cycle of that shape would satisfy $13x = c$. For $19/12$: $2^{19} = 524288$ and $3^{12} = 531441$, so the gap is $-7153$ and the equation has no positive solution at all, whatever the pattern.

What is left is the sub-list $2/1$, $8/5$, $65/41$, $485/306$ and so on — every second entry — and those are the only shapes a cycle can have. The gaps along that sub-list are 1, 13, about $4.2 \times 10^{17}$, about $10^{143}$, and each one has to divide a $c$ built from a pattern of the corresponding length.

A divisibility condition by a number of a hundred and forty digits is not a condition anybody satisfies by accident, and that sentence is the informal content of the whole bound.

The offset is what changes the answer #

The three rules in the search differ by one number, and the equation shows exactly where it enters.

Replacing $3n+1$ by $3n+d$ leaves the left side alone — $2^n - 3^k$ has no $d$ in it — and multiplies $c$ by $d$. So the cycle condition becomes: does $2^n - 3^k$ divide $d$ times the pattern sum?

That is why the answers differ so wildly. With $d = 1$ the pattern sums must be divisible outright and essentially none are. With $d = -1$ the sign flips, positive solutions come from patterns where $2^n < 3^k$, and a different and non-empty set of patterns qualifies — giving the cycles at 1, 5 and 17. With $d = 5$ the divisibility condition is five times easier to satisfy and four cycles appear.

The drift is identical in all three cases, because the drift depends on the factor three and the halving and not on $d$ at all. The number of cycles depends on $d$ and nothing else. Two quantities computed from the same rule, one blind to the offset and one determined by it — and the conjecture is about the second.

That is the sharpest way to state the rung below’s warning. A statistic that does not mention $d$ cannot distinguish rules that differ only in $d$, and those rules have different answers.

What Eliahou actually did #

The bound is worth unpacking a little, because “seventeen million” sounds like the output of a computation and is the output of an argument.

The steps are these. Suppose a non-trivial cycle exists with $k$ odd steps and $n$ total. Verification says every element exceeds the checked bound $M$. The cycle equation and a bound on $c$ then give an inequality of the form

$$0 < \frac{n}{k} - \log_2 3 < \frac{\text{something}}{k \, \log M},$$

so $n/k$ approximates $\log_2 3$ to within a quantity that shrinks as $M$ grows. The theory of continued fractions converts that into a statement about $k$: a fraction approximating a number that well must be a convergent, and the convergents’ denominators are known. Reading down the list to the first denominator whose approximation is good enough gives the bound.

Every ingredient is exact except the verification, which is a number that has been improving for fifty years. The 1993 bound used the verified range of the day; the same argument with today’s range gives about $10^{11}$.

The reason the number is not larger is the 23 in the continued fraction. A large term means a convergent that approximates unusually well, and $24727/15601$ is unusually good — good enough that ruling it out takes a verification bound far beyond anything achieved. So the bound sits just below the denominator that the arithmetic cannot yet exclude, and the next big improvement will come from verification rather than from theory.

What the small cases say #

The equation can be solved outright when the cycle is short enough to enumerate. For each parity pattern, compute $c$, divide by $2^n - 3^k$, and see whether the answer is a positive whole number whose orbit really follows that pattern.

The comparison is the point. The three rules have identical drift, identical parity statistics and identical heuristics, and they have one, three and four cycles. Whatever decides the number of cycles is not visible in any statistic the rung below computes, and it is entirely visible in the divisibility of $c$ by $2^n - 3^k$.

The search also shows what the equation costs. Solving every pattern up to eighteen steps is a quarter of a million divisions; up to forty steps it would be a million million, and up to the length a real cycle would need it is beyond anything. So the exhaustive method settles the short cases and the continued fraction settles the rest — the two halves of the argument covering different ranges of the same question.

The bound, and what it comes to #

Putting the verification bound and the continued fraction together gives a lower bound on the length of any cycle nobody has found, and the numbers are large.

Eliahou proved in 1993 that any non-trivial cycle of the Collatz map has at least 17,087,915 steps. The argument is exactly the one above, run carefully: the verification bound of the day forced $n/k$ to be a convergent past a certain point in the list, and the denominators there are already in the millions. Later verification has pushed the bound to around $10^{11}$ steps.

Compare that with what the density side has produced. The best density result says that the numbers reaching one have counting function at least $x^{0.84}$ — a statement about almost all numbers, with the exceptional set unbounded. The cycle side says a cycle would need a hundred billion steps, which is not a proof that none exists and is a far more specific piece of knowledge.

The two halves of the conjecture have completely different mathematics behind them, and the cycle half is the one where the arithmetic bites.

Why the verification bound matters #

A striking feature of the argument is that computation and theory feed each other, which is unusual in a subject where verification is normally decorative.

Checking every number below $2^{68}$ proves nothing about the conjecture directly — the conjecture is about all numbers and the checked range is a vanishing fraction. What it does is raise the floor a cycle’s elements must exceed, which tightens the approximation $n/k$ has to achieve, which pushes the admissible $k$ further along a sparse list.

So every doubling of the verified range lengthens the shortest possible cycle, and the mechanism is entirely explicit. That is a rare relationship: usually a computation either settles a case or contributes nothing, and here it contributes a bound on a case it cannot reach.

The relationship runs the other way too. If somebody proved a good enough upper bound on the elements of a hypothetical cycle — an a priori bound rather than one relying on verification — the argument would close by itself. Nobody has, and finding one is the obvious line of attack that has not worked.

Why the equation is exact and the heuristic is not #

It is worth being explicit about what changed between the two rungs, because both are about the same map and only one produces a theorem.

The drift argument replaces the sequence of parities by a coin toss, and reads the orbit as a random walk with a downward drift. That replacement is excellent for predicting averages and it discards exactly one thing: the parity sequence of a real orbit is determined, and the determination is what an equation can use. A coin toss has no $c$.

The cycle equation never approximates anything. It takes the pattern as given, computes the resulting arithmetic exactly, and asks a divisibility question — and a divisibility question has an answer rather than a probability. That is why the two approaches produce results of such different kinds: one gives a prediction confirmed over enormous ranges and provable for nothing, the other gives a bound that is a theorem and reaches nowhere near the conjecture.

The trade is generic. An argument that replaces structure with randomness gets the typical behaviour and loses the exceptional cases; an argument that keeps the structure gets the exceptional cases and cannot reach the typical ones. The Collatz conjecture needs both halves, and the two halves are attacked by the two methods, and neither method has ever been made to do the other’s job.

There is a third position worth naming, since it is where most of the recent work sits: keep the structure and estimate rather than solve. That is how the density results are proved — the parity sequence is treated as a genuine object with measurable properties rather than as a coin — and it is why those results are theorems where the drift argument is not, even though they prove far less than the drift argument predicts.

What the argument does not reach #

Three limits are worth stating, because the cycle result is easy to overstate.

It bounds cycles, not divergence. An orbit that grows forever is not a cycle and none of this touches it. The conjecture has two ways to fail and the arithmetic addresses one.

The bound depends on verification. Eliahou’s number is not an absolute theorem; it is a theorem given that everything below a certain size has been checked. A proof independent of computation would be a different and better result.

And the argument is about the shortcut map’s cycles in the positive integers. Extended to the negative integers the same rule has three cycles, at $-1$, at $-5$ and at $-17$, and the equation is satisfied there — so the conclusion genuinely uses positivity, in the step where $c$ and $2^n - 3^k$ are required to have the same sign.

What the pictures cannot show #

The exhaustive search runs to eighteen steps. A cycle would have at least seventeen million, so the search covers none of the range where a cycle could hide, and its value is entirely in the comparison between rules.

The continued fraction is computed to a dozen terms in ordinary floating point, which is enough for the convergents shown and not for the ones the real bound uses. Eliahou’s argument works with far more terms and with error estimates this figure does not attempt.

And the verification to $2^{68}$ is quoted. Nothing here checks it, and it is a distributed computation of considerable size rather than something a figure could rerun.

Where the ladder goes next #

Named here as a debt: the cycle equation solved backwards, which is the rung above — every periodic parity pattern has a rational solution, and asking which of those rationals are integers is what the search above does one pattern at a time.

Also unwritten: the divergence side, where nothing of this kind is known and where the only results are the density ones the rungs below describe.

Sideways, the drift that cannot see a cycle is the rung below, the residues that fix a parity pattern are the rung below that, the approximation theory the bound rests on is how close a fraction can get, and the statement of the problem is the first rung.

What is worth carrying away #

When a probabilistic argument reaches a wall, the useful question is what exact statement the object satisfies.

The drift argument gets the growth rate, the step count and the distribution right, and cannot rule out a single cycle. The cycle equation ignores every statistic and produces a bound of seventeen million, because a cycle is a finite object satisfying an identity in whole numbers, and identities in whole numbers are what arithmetic is for.

The habit worth taking is to look for the equation the special case satisfies. A general orbit satisfies nothing; a periodic one satisfies $x(2^n - 3^k) = c$, and everything follows from that single line.

The corollary is about the relationship between computation and proof here, which is worth carrying to other problems. Verifying cases raised a bound rather than settling anything, and it did so through an explicit mechanism — a floor on a cycle’s elements, tightening an approximation, forcing a denominator further along a list. A verification that feeds a theorem is worth far more than one that merely accumulates confidence, and whether one has the first or the second is decided by whether the theorem has a place to put the number.