Home / Opinion / Columns /  Collatz Conjecture on my mind, almost

Some years ago, I wrote here about “hailstone numbers" (Follow that hailstone, 8 April 2016). These are numbers that are generated when you try your hand at the Collatz Conjecture—sometimes described as the “simplest impossible problem" in all of mathematics.

I realize that will either scare you away or grab your attention. If the former, bear with me for a few moments, for what it involves are instructions so simple, they are almost trivial:

1) Think of any positive integer.

2) If it’s odd, multiply by 3 and add 1.

3) If it’s even, divide by 2.

4) Go back to #2 and repeat.

So if you started with 5, you’d have this sequence: 5-16-8-4-2-1-4-2-1 ...

With 9, you get this: 9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1-4-2-1 ...

These sequences are called hailstone numbers because of how they yo-yo up and down, as hailstones do in the clouds where they form. In that previous column, I mentioned the 112-step yo-yo fest that 27 kicks off, the 78th of which is 9,232.

Hailstones apart, in both cases above, you see that the sequence arrives at 1. At that point, we can stop because then it’s just a 1-4-2-1 cycle, which brings us to the Collatz Conjecture. In the 1930s, the German mathematician Lothar Collatz suggested that no matter what number you start with, the sequence always reaches 1.

That simple, at least in how it’s spelt out. Yet this is a diabolically hard question that mathematicians, in all these decades, have been unable to prove. They have started with numbers going up beyond the 20th power of 10—beyond two hundred quintillion—and every single one of them produces a sequence, often hailstone-like, that ends in 1. That’s pretty good evidence, you’d think, to assume that Collatz’s Conjecture holds true. But not to mathematicians. They want not just several quintillion examples without a single counter-example but an ironclad, irrefutable, logical proof. Note that a single counter-example would constitute proof—that the Conjecture is wrong.

Yet proof is what they don’t have. But there’s been recent and intriguing progress towards one.

This story begins with a blog post in 2011 by Terence Tao, who won the Fields Medal in 2006 and is widely regarded as one of the brightest stars in contemporary mathematics. He called that post “The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3" (bit.ly/3qWcGZm). The first few lines spell out the hailstone instructions, and the Collatz Conjecture itself more mathematically than I’ve done above. Then he goes on to explain how mathematicians regard it:

“Open questions with this level of notoriety can lead to what Richard Lipton calls ‘mathematical diseases’ (and what I termed an ‘unhealthy amount of obsession on a single famous problem’). As such, most practising mathematicians tend to spend the majority of their time on more productive research areas that are only just beyond the range of current techniques."

Mathematicians have scoured the Collatz canvas in search of that most fundamental of mathematical ideas: a pattern. There are plenty of pretty pictures that show how the numbers behave as they jump about hailstone-fashion. Discouragingly, no patterns. Still, Tao spent a few days in 2011 working on the Conjecture without solving it. The rest of the (long) post explains his findings then. It attracted over 200 comments. In August 2019, an anonymous reader left this:

“Another possibility is to show that the conjecture is true ‘almost everywhere’ in the sense that the number of integers below N which belong to any periodic loop is o(N) for large N."

In plainer words: perhaps there is progress to be made in trying to prove the Conjecture for almost all numbers, but not all. This notion got Tao’s Collatz juices flowing again because later that year, he again took a few days to dive into the Conjecture. This time, he made enough progress ("Almost all orbits of the Collatz map attain almost bounded values", bit.ly/3cHxUVL, 8 September 2019), if not yet a proof, to make the news outside mathematical circles.

Tao’s Collatz mathematics flies some distance above my head, at one point even involving certain right-angled triangles. These two sentences, for example, are typical:

“Theorem 1.6 then corresponds to an ‘almost sure almost global wellposedness’ result, where one needs to control the solution for times so large that the evolution gets arbitrary close to the bounded state N = O(1). To bootstrap from almost sure local wellposedness to almost sure almost global wellposedness, we were inspired by the work of Bourgain, who demonstrated an almost sure global wellposedness result for a certain non-linear Schrödinger equation by combining local wellposedness theory with a construction of an invariant probability measure for the dynamics."

Still, there’s a good analogy to how he approached the idea of “almost all numbers". Imagine a poll that’s conducted ahead of a major election to gauge the mood of the electorate. Clearly, it cannot reach every single voter —that’s the job of the election itself. So it must choose a sample of voters.

For everyone who conducts polls, this is the challenge: how do you select such a sample? How large should it be? What kinds of people should be in it? For example, samples with only women, or only men over 80, or only car-owners, will produce totally unreliable results. In other words, you need a sample that fairly represents the whole electorate. In the same way, Tao wondered if a sample of the positive integers could give him some insights into solving the Conjecture. For let’s say you are able to put together a reasonable sample, and you find that most of the numbers in it generate sequences that end at 1. Then it might be reasonable to assume that almost all numbers do the same.

But how do you select a sample that nicely represents all numbers? For example, it cannot contain only powers of 2—4, 8, 16, 512, 2048 and so on—because they get divided by 2 again and again and quickly subside to 1. Such a sample trivially, but wrongly, “proves" the Conjecture. Similarly, perhaps multiples of 7 behave differently from those of 37, and so our sample should include some of both. Then there’s what happens once you apply the instructions above—the sample changes its character with each iteration. So maybe you have to construct your sample keeping this in mind too.

In fact, Tao was able to spell out how to select a sample that, through each iteration, would hold on to its essential character. This meant that no matter how long the iterations carried on, he retained a good idea of what was happening to the sample and how it would continue to behave.

His conclusion? An article in Quanta Magazine suggests that it was “along the lines" of stating that 99% of the numbers greater than a quadrillion generate Collatz sequences that eventually subside to below 200, which is good, because we know that all numbers below 200 eventually produce 1.

It’s still not a full proof of the Conjecture, and it’s probably not the way any eventual proof will proceed. But that same Quanta article commented: “It is arguably the strongest result in the long history of the Conjecture."

In mathematics, that’s high praise.

Once a computer scientist, Dilip D’Souza now lives in Mumbai and writes for his dinners. His Twitter handle is @DeathEndsFun