How high an orbit climbs

The question nobody can answer set out the Collatz map — halve an even number, triple an odd one and add one — and the conjecture that every start eventually reaches 1. It recorded two famous orbits along the way: 27, which climbs to 9,232 before coming down, and 703, which climbs to 250,504, more than three hundred and fifty times its start. The heuristic that cannot be a proof explained why orbits are expected to come down at all: treated as a sequence of fair coin tosses, the map shrinks a number by a quarter every two steps on average.

An average says little about extremes, and the extremes are what the two famous orbits were. This essay asks how high orbits climb before they fall, measures it for every start up to ten million, and finds that the same coin-tossing model that predicts the average descent also predicts the extremes — with an exponent that comes out exactly, for a reason that is one line of arithmetic.

Ten million peaks, cheaply #

Write $M(n)$ for the largest number in the orbit of $n$, the start included. Computing it for every $n$ up to ten million by following each orbit to 1 would take about a billion steps. A shortcut makes it about a tenth of that. An orbit from $n$ eventually falls below $n$ — that has been checked far beyond this range — and the moment it does, it lands on some smaller number $m$ whose whole orbit, and therefore whose peak $M(m)$, is already known. So $M(n)$ is the larger of the highest point before the fall and $M(m)$. Most orbits fall below their start within a handful of steps, and the whole table of ten million peaks takes a few seconds.

A path record is a start $n$ whose peak exceeds the peak of every smaller start. Below ten million there are 37 of them: 1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1,819 and so on up to 6,631,675, whose orbit reaches 60,342,610,919,632. The list agrees with the published tables of path records, which were computed the same way to far larger bounds. In the hero figure the records form a staircase that climbs, on the logarithmic scales, along the line where the peak is the square of the start.

The square law, measured #

The natural measure of a record’s height is the exponent $\log M / \log n$: the power of the start that the peak equals.

For small starts the exponent is erratic — 27 reaches 9,232, which is $27^{2.77}$, an excess that made it famous — because with few starts the luck of a single orbit dominates. From a hundred thousand onward the exponents settle between 1.75 and 2.0, with a slow upward drift: 1.82 around a million, 1.86 for 6,416,623, and 2.02 for the last record, 6,631,675, whose peak is slightly more than the square of its start. Jeffrey Lagarias and Allan Weiss, analysing exactly this question with a stochastic model in 1992, predicted that the exponent of the path records tends to 2. The figure is consistent with that and cannot prove it.

Climbing x-fold has chance one in x #

The square law comes from the distribution of how far a typical orbit climbs, and that distribution can be measured directly.

For each start between one million and ten million the ratio $M(n)/n$ says how many times its start the orbit climbs. Every orbit climbs at least to its start, so the ratio is at least one; about half climb at least twice as high, a fifth at least five times; and the share that climbs at least $x$-fold falls, between $x = 10$ and $x = 10^4$, with slope $-1.01$ on logarithmic scales. In words: an orbit climbs to $x$ times its start with a chance of about $1/x$.

The dashed curve is a walk that knows nothing about arithmetic. It starts at 1 and at each step multiplies by $3/2$ or by $1/2$ with equal chances — the two moves of the map in its shortcut form, where an odd step $n \mapsto (3n+1)/2$ is combined with the halving that must follow, and the $+1$ is ignored. Its highest point is recorded, doubled to account for the unshortened step $3n + 1$, and the curve shows how often it exceeds each $x$. It lies on the Collatz curve to within the sampling noise over four decades. The map’s climbs are, in distribution, the climbs of a fair coin.

Why the exponent is exactly one #

The slope of $-1$ is not an accident of the measurements. It follows from the walk, and the argument is short.

For a walk that multiplies by a random factor $s$ at each step, consider the function $\gamma \mapsto \mathbb{E}[s^\gamma]$. At $\gamma = 0$ it is 1. Its slope there is $\mathbb{E}[\log s]$, the average change in the logarithm, which here is $\tfrac12\log\tfrac32 + \tfrac12\log\tfrac12 = \tfrac12\log\tfrac34 < 0$: the walk drifts down, which is the heuristic’s quarter lost every two steps. Because the function is convex, it dips below 1 and comes back up, crossing 1 again at a second root $\gamma^*$. A classical theorem about such walks — the same one that gives the ruin probability of an insurance company with positive expected profit, due to Filip Lundberg and Harald Cramér — says that the chance that the walk ever climbs to $x$ times its start is about $x^{-\gamma^*}$.

For the Collatz walk the second root is exactly $\gamma^* = 1$, because

$$\tfrac12 \cdot \tfrac32 + \tfrac12 \cdot \tfrac12 = 1.$$

The average of the multiplier itself is one. In the language of two barriers and a fair game, the walk’s value is a fair game: its expected value after any number of steps equals its start, even though its logarithm drifts down. A fair game that is almost certain to sink must, to keep its average, occasionally soar, and the chance of soaring to $x$ times the stake is about $1/x$ — the only tail that keeps the average fixed. The Collatz map’s climbs inherit that from the arithmetic of $3/2$ and $1/2$.

From the tail to the records #

The square law follows from the tail by counting. Among the starts below $N$, the share that climb at least $x$-fold is about $1/x$, so about $N/x$ of them do. The highest climb among them is therefore the $x$ at which $N/x$ falls to about one: $x \approx N$. A start near $N$ that climbs $N$-fold reaches about $N^2$. So the highest peak among all starts below $N$ is roughly $N^2$, and the path records — each the highest peak so far — sit near the square of their start.

The approximations in that argument are all of the kind that lose factors smaller than any power: the tail is $1/x$ only up to a slowly varying correction, the largest of $N$ samples from a $1/x$ tail is $N$ only up to a random factor, and the records are not uniformly spread. That is why the measured exponents approach 2 from below and slowly. The same kind of argument, applied to a tail falling like $e^{-x}$ rather than $1/x$, gives a maximum growing like $\log N$, which is what the longest run has no limit found for runs of heads in coin tosses; the Collatz peaks have a heavy tail, so their maximum grows like a power of $N$ instead.

An average climb that does not exist #

A tail falling like $1/x$ has a consequence that is easy to state and strange to meet. The average of the climb ratio $M(n)/n$ over many starts does not settle. The share of starts climbing between $x$ and $2x$ is about $1/(2x)$, and each of them contributes about $x$ to the sum, so every doubling of $x$ adds roughly the same amount to the average — and there are infinitely many doublings. Over the starts below $N$, the largest ratio is about $N$, and the average ratio grows like $\log N$, without bound. The typical orbit climbs to a small multiple of its start; the average orbit, in the sense of the mean, climbs higher and higher the more orbits are averaged.

That is the behaviour a wait that ends and has no average found for the time a fair random walk takes to return to its start: finite every time, infinite on average. The connection is not superficial. A walk’s highest point before it falls back is the same kind of quantity as its waiting time, and both are governed by how its rare long excursions are distributed. The Collatz walk, with its downward drift, has finite waiting times and a finite median climb; its exponent of exactly one puts its climb ratio precisely on the border where the mean stops existing.

A border case is fragile. If the map multiplied odd numbers by slightly less than $3$ — by $2.9$, say, with the same rule — the second root of the moment equation would move above one, the tail would fall faster than $1/x$, the mean climb would be finite, and the records would grow like a power of the start smaller than two. If it multiplied by slightly more, the root would fall below one, and the records would outgrow the square. The number $3$ in the Collatz map sits exactly where the arithmetic $\tfrac12 \cdot \tfrac32 + \tfrac12 \cdot \tfrac12 = 1$ makes the square law exact, and it was not chosen for that reason.

Peaks and stopping times are different questions #

The highest point of an orbit and the number of steps it takes are related but different, and their records are different lists. A delay record is a start whose orbit takes more steps to reach 1 than any smaller start’s. The two lists share 27, which is both a path record and a delay record, but they quickly part: 703 is a path record whose orbit takes 170 steps, while the delay records near it are numbers whose orbits take longer without climbing so high. A long orbit can wander at moderate heights, and a high one can be short, climbing steeply and falling straight back.

In the coin-tossing model the two are governed by different features of the walk. The height of a climb depends on the longest run of excess upward steps, and its distribution has the $1/x$ tail above. The length of an orbit is the time a drifting walk takes to fall from $\log n$ to nought, which is about $\log n$ divided by the drift, with fluctuations of order $\sqrt{\log n}$ — a quantity with a bell-shaped spread around a mean, of the kind the tail is not a bell warned is accurate in the middle and misleading at the edges. Delay records grow only like a multiple of $\log n$, a much gentler law than the square law of the peaks: lengths are averages of many steps and are tamed by the averaging, heights are extremes and are not.

A steady supply of records #

The number of path records grows in a way that the same picture explains.

The 37 records below ten million arrive at about 5.3 per factor of ten, after the first few. For a sequence of independent random numbers drawn from a fixed distribution, records thin out — the $k$-th is expected around the $e^k$-th term. The peaks are not like that: they grow, in proportion to the start, so a new record can be set either by a lucky climb or simply by a larger start with an ordinary one. On a logarithmic scale every decade looks the same as the last — the starts are ten times larger and the luck is distributed identically — and the records arrive at a constant rate per decade, as the figure shows.

The champion below ten million #

The highest climber below ten million is worth looking at whole.

The orbit takes 576 steps. It climbs in two stages — a first rise of about a thousandfold in its first sixty steps, a pause, then a second long climb — in which odd steps come far more often than half the time, and it peaks at step 163 at about nine million times its start. After the peak it falls, with the usual zigzag, at very nearly the average rate of the heuristic — a factor of $\sqrt{3/4}$ per step on average — taking another four hundred steps to reach 1. Nothing in the descent remembers the climb. That is the coin-tossing picture in miniature: the climb is a rare run of upward steps, as likely to happen anywhere as anywhere else, and once it ends the walk resumes its ordinary downward drift.

Where the model must fail #

The coin-tossing model is not the map. The map is deterministic, every orbit is fixed by its start, and the model’s success is a statistical statement about how the map’s orbits look in aggregate, not a proof about any one of them. Where the Collatz map is a coin showed one precise sense in which the map really is a coin, on the 2-adic integers, and every pattern happens exactly once showed that every finite pattern of odd and even steps is realised by exactly one residue class. Those results explain why the coin is such a good model for the first steps of an orbit. They do not reach the far tail, where an orbit’s climb is a run of hundreds of steps and the question of whether its parities behave like coin tosses is exactly the question nobody can answer.

The model also ignores the $+1$, which matters for small numbers and not for large ones, and treats the parity of each step as independent of the last, which is exact for the first steps of a uniformly random start and only approximately true later. Its agreement with the measured tail across four decades says those approximations do not matter at these sizes; it does not say they never will.

What the table of peaks cannot show #

Ten million starts is a small fraction of what has been checked: the conjecture itself has been verified beyond $2^{68}$, and path records have been tabulated far past ten million. The figures here use ten million because the full table of peaks fits in memory and can be recomputed in seconds, and the slope, the record exponents and the record rate are already stable at that size. What a finite table cannot show is whether the square law holds for ever, or whether some orbit eventually climbs much higher than its start squared — or never comes down, which would be a counterexample to the conjecture and a path record that is infinite.

The model predicts that this does not happen: an orbit climbing to the $k$-th power of its start should become rarer and rarer as $k$ exceeds 2, until, among all starts, it essentially never occurs. The prediction is for a model of the map, and the map is under no obligation to follow it.

Still open: the exponent’s limit #

Lagarias and Weiss’s stochastic models predict that the path records satisfy $\log M(n)/\log n \to 2$. No proof is known, and none is in sight: even the statement that every orbit is bounded is the Collatz conjecture’s weaker cousin, open in its own right. The measured exponents, rising from about 1.8 to 2.0 across the last decade of starts examined here, are consistent with a limit of 2 approached slowly, and also with a limit somewhat different from 2 — the difference between those cannot be resolved by tables of any feasible size, because the corrections to the square law are logarithmic. The cleanest open statement is the simplest: that there is a constant $C$ with $M(n) \le n^C$ for every start. It is not known for any $C$, and it could not be, short of a proof that every orbit is bounded — which is itself an open question, weaker than the conjecture and as far out of reach.