Matpic
mathematics, in pictures
Concept

Collatz

The rule that halves an even number and sends an odd one to three times itself plus one. Whether every starting value reaches one is unproved, though almost every value is known to fall below its own start.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

The Collatz orbit of 27. Halve an even number, triple an odd one and add one; the sequence plotted on a logarithmic scale.

The question nobody can answer

Halve it if it is even, triple it and add one if it is odd. Every number anyone has tried comes down to one. Nobody can prove they all do, and the reason is not that the problem is hard to state.

dynamics · Collatz The share that provably comes down. The proportion of starting values that fall below their own start within k steps, plotted against k up to 12. The proportion rises towards one; at the largest k drawn it is 0.94.

Almost every number comes down

The Collatz conjecture is open and a great deal about it is not. 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, and the share of numbers for which it happens can be counted exactly.

dynamics · Collatz Downhill on average, and never on purpose. The logarithms of 4 Collatz orbits plotted against step number, each wandering upward and downward and each ending at one. A separate sample of four thousand starts gives an average fall of -0.15 per step.

The heuristic that cannot be a proof

There is a two-line argument that the Collatz conjecture is true, it is convincing, and everybody who works on the problem believes it. It also cannot be turned into a proof, and understanding exactly where it fails is more instructive than the argument itself.

dynamics · Collatz The Collatz map on the 2-adic integers, before and after changing to parity coordinates. Two scatter plots of 2048 points: the Collatz map on 2-adic integers in binary-digit coordinates, a scattered cloud, and the same map in parity-vector coordinates, where every point lies on the two lines of the doubling map.

Where the Collatz map is a coin

Extend the Collatz map from the whole numbers to the 2-adic integers — binary strings that run on for ever to the left — and it stops being mysterious. It becomes, after a change of coordinates, the simplest chaotic system there is: shifting a string of coin tosses one place. Everything about it is then known, and none of it says anything about the whole numbers, which is the most instructive failure in the whole story.

dynamics · Collatz PRIMEGAME: fourteen fractions whose powers of two are the primes. The size in binary digits of the numbers produced by Conway's PRIMEGAME from 2 over 40000 steps, with the pure powers of two marked; their exponents are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Fourteen fractions that list the primes

Change the Collatz rule so that the multiplier depends on the remainder modulo some other number than two, and the resulting maps can compute anything a computer can. John Conway proved it in 1972, which means no method can decide, for every such map, whether its orbits come down — and fourteen fractions, applied in order, turn out to be enough to print every prime.

dynamics · Collatz

Named alongside it

The objects these essays reach for when they reach for this one.

IterationParityHeuristicLogarithmUndecidabilityBinaryComputationConjugacyCounting two waysDensityDriftExpectation

All concepts