The Collatz conjecture
I recently came across the book Mathematics: An Illustrated History of Numbers, which appears to be part of a series. One of the fun “ponderables” (as they are called) considered in the book is the Collatz conjecture.
The Collatz conjecture goes something like this. Pick a number n. If n is even, divide it in half. If it’s odd, then multiply it by three and add one. Repeat the process with the new number. Written as a function:
The conjecture is that eventually, regardless of the size of the initial value of n, the sequence will converge to 1.
In 1970 HSM Coxeter offered a $50 reward to anyone who could prove the conjecture. Paul Erdős later upped the ante to $500. More recently, according to a nice overview by Jeffrey Lagarias (who also edited a volume dedicated to the conjecture), B Thwaite offered £1000.
A lot of time and effort has been put into studying the rate of convergence (or, rather, total stopping time) for larger and larger values of n. Interestingly enough, there is a heuristic solution that is based on probabilistic arguments. If you consider only the odd numbers in the sequence, on average, each odd number ends up being 3/4 the previous one. This argument, when extended, can be used to prove that there is no divergence but it can’t rule out other cycles, e.g. numbers other than 1 that the sequence converges to. In addition, though we know it works for every integer up to at least 100 million (thanks to the power of computing), this cannot be seen as proof. Indeed, there are other conjectures that turn out to fail for very large numbers (e.g. the Pólya conjecture was disproven in 1958 by Haselgrove who found a counter example that was roughly equal to ).
Might this be interesting to the physics community or is this a purely number theoretic problem? The study of the iterates of measure-preserving functions on a measure space, i.e. dynamical systems that include an invariant measure, is known as ergodic theory. In quantum mechanics, for instance, trace-preserving operations are essentially invariant measures. So while the Collatz conjecture might or might not have a direct physical corollary, proving (or disproving) it could have implications for ergodicity in general that might prove useful in physical systems.
But even if it had no useful physical corollary, it’s still a neat problem…