Later On

A blog written for those whose interests more or less match mine.

Mathematician Proves Huge Result on “Dangerous” Problem

leave a comment »

Kevin Hartnett writes in Quanta:

Experienced mathematicians warn up-and-comers to stay away from the Collatz conjecture. It’s a siren song, they say: Fall under its trance and you may never do meaningful work again.

The Collatz conjecture is quite possibly the simplest unsolved problem in mathematics — which is exactly what makes it so treacherously alluring.

“This is a really dangerous problem. People become obsessed with it and it really is impossible,” said Jeffrey Lagarias, a mathematician at the University of Michigan and an expert on the Collatz conjecture.

Earlier this year one of the top mathematicians in the world dared to confront the problem — and came away with one of the most significant results on the Collatz conjecture in decades.

On September 8, Terence Tao posted a proof showing that — at the very least — the Collatz conjecture is “almost” true for “almost” all numbers. While Tao’s result is not a full proof of the conjecture, it is a major advance on a problem that doesn’t give up its secrets easily.

“I wasn’t expecting to solve this problem completely,” said Tao, a mathematician at the University of California, Los Angeles. “But what I did was more than I expected.”

The Collatz Conundrum

Lothar Collatz likely posed the eponymous conjecture in the 1930s. The problem sounds like a party trick. Pick a number, any number. If it’s odd, multiply it by 3 and add 1. If it’s even, divide it by 2. Now you have a new number. Apply the same rules to the new number. The conjecture is about what happens as you keep repeating the process.

Intuition might suggest that the number you start with affects the number you end up with. Maybe some numbers eventually spiral all the way down to 1. Maybe others go marching off to infinity.

But Collatz predicted that’s not the case. He conjectured that if you start with a positive whole number and run this process long enough, all starting values will lead to 1. And once you hit 1, the rules of the Collatz conjecture confine you to a loop: 1, 4, 2, 1, 4, 2, 1, on and on forever.

Over the years, many problem solvers have been drawn to the beguiling simplicity of the Collatz conjecture, or the “3+ 1 problem,” as it’s also known. Mathematicians have tested quintillions of examples (that’s 18 zeros) without finding a single exception to Collatz’s prediction. You can even try a few examples yourself with any of the many “Collatz calculators” online. The internet is awash in unfounded amateur proofs that claim to have resolved the problem one way or the other.

Try it for yourself here.

“You just need to know multiplying by 3 and dividing by 2 and you can start playing around with it right away. It’s very tempting to try,” said Marc Chamberland, a mathematician at Grinnell College who produced a popular YouTube video on the problem called “The Simplest Impossible Problem.”

But legitimate proofs are rare.

In the 1970s, mathematicians showed that almost all Collatz sequences — the list of numbers you get as you repeat the process — eventually reach a number that’s smaller than where you started — weak evidence, but evidence nonetheless, that almost all Collatz sequences incline toward 1. From 1994 until Tao’s result this year, Ivan Korec held the record for showing just how much smaller these numbers get. Other results have similarly picked at the problem without coming close to addressing the core concern.

“We really don’t understand the Collatz question well at all, so there hasn’t been much significant work on it,” said Kannan Soundararajan, a mathematician at Stanford University who has worked on the conjecture.

The futility of these efforts has led many mathematicians to conclude that the conjecture is simply beyond the reach of current understanding — and that they’re better off spending their research time elsewhere.

“Collatz is a notoriously difficult problem — so much so that mathematicians tend to preface every discussion of it with a warning not to waste time working on it,” said Joshua Cooper of the University of South Carolina in an email.

An Unexpected Tip

Lagarias first became intrigued by the conjecture as a student at least 40 years ago. For decades he has served as the unofficial curator of all things Collatz. He’s amassed a library of papers related to the problem, and in 2010 he published some of them as a book titled The Ultimate Challenge: The 3x + 1 Problem.

“Now I know lots more about the problem, and I’d say it’s still impossible,” Lagarias said.

Tao doesn’t normally spend time on impossible problems. In 2006 he won the Fields Medal, math’s highest honor, and he is widely regarded as one of the top mathematicians of his generation. He’s used to solving problems, not chasing pipe dreams.

“It’s actually an occupational hazard when you’re a mathematician,” he said. “You could get obsessed with these big famous problems that are way beyond anyone’s ability to touch, and you can waste a lot of time.”

But Tao doesn’t entirely resist the great temptations of his field. Every year, he tries his luck for a day or two on one of math’s famous unsolved problems. Over the years, he’s made a few attempts at solving the Collatz conjecture, to no avail.

Then this past August an anonymous reader left a comment on Tao’s blog. The commenter suggested trying to solve the Collatz conjecture for “almost all” numbers, rather than trying to solve it completely.

“I didn’t reply, but it did get me thinking about the problem again,” Tao said.

And what he realized was that the Collatz conjecture was similar, in a way, to the types of equations — called partial differential equations — that have featured in some of the most significant results of his career.

Inputs and Outputs

Partial differential equations, or PDEs, can be used to model many of the most fundamental physical processes in the universe, like the evolution of a fluid or the ripple of gravity through space-time. They arise in situations where the future position of a system — like the state of a pond five seconds after you’ve thrown a rock into it — depends on contributions from two or more factors, like the water’s viscosity and velocity.

Complicated PDEs wouldn’t seem to have much to do with a simple question about arithmetic like the Collatz conjecture.

But Tao realized there was something similar about them. With a PDE, you plug in some values, get other values out, and repeat the process — all to understand that future state of the system. For any given PDE, mathematicians want to know if some starting values eventually lead to infinite values as an output or whether an equation always yields finite values, regardless of the values you start with.

For Tao, this goal had the same flavor as investigating whether you always eventually get the same number (1) from the Collatz process no matter what number you feed in. As a result, he recognized that techniques for studying PDEs could apply to the Collatz conjecture.

One particularly useful technique involves a statistical way of studying the long-term behavior of a small number of starting values (like a small number of initial configurations of the water in a pond) and extrapolating from there to the long-term behavior of all possible starting configurations of the pond.

In the context of the Collatz conjecture, imagine starting with a large sample of numbers. Your goal is to study how these numbers behave when you apply the Collatz process. If close to 100% of the numbers in the sample end up either exactly at 1 or very close to 1, you might conclude that almost all numbers behave the same way.

But for the conclusion to be valid, you’d have to construct your sample very carefully. The challenge is akin to generating a sample of voters in a presidential poll. To extrapolate accurately from the poll to the population as a whole, you’d need to weight the sample with the correct proportion of Republicans and Democrats, women and men, and so on.

Numbers have their own “demographic” characteristics. There are odd and even numbers, of course, and numbers that are multiples of 3, and numbers that differ from each other in even subtler ways. When you construct a sample of numbers, you can weight it toward containing certain kinds of numbers and not others — and the better you choose your weights, the more accurately you’ll be able to draw conclusions about numbers as a whole.

Weighty Choices

Tao’s challenge was much harder than just figuring out how to create an initial sample of numbers with the proper weights. At each step in the Collatz process, the numbers you’re working with change. One obvious change is that almost all numbers in the sample get smaller.

Another, maybe less obvious change is that  . . .

Continue reading.

Written by LeisureGuy

11 December 2019 at 1:58 pm

Posted in Math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.