A Magical Answer to an 80-Year-Old Puzzle
The mathematician Terence Tao, of the University of California, Los Angeles, has presented a solution to an 80-year-old number theory problem posed by the legendary Hungarian mathematician Paul Erdős. Erdős was famous for the thousands of puzzles he came up with, many of which have led to surprisingly deep mathematical discoveries. This particular problem, which came to be known as the Erdős discrepancy problem, was one of his favorites, said Ben Green, a mathematician at the University of Oxford. “He mentioned it many times over the years, particularly towards the end of his life.”
A simplified version of the problem goes like this: Imagine that you are imprisoned in a tunnel that opens out onto a precipice two paces to your left, and a pit of vipers two paces to your right. To torment you, your evil captor forces you to take a series of steps to the left and right. You need to devise a series that will allow you to avoid the hazards — if you take a step to the right, for example, you’ll want your second step to be to the left, to avoid falling off the cliff. You might try alternating right and left steps, but here’s the catch: You have to list your planned steps ahead of time, and your captor might have you take every second step on your list (starting at the second step), or every third step (starting at the third), or some other skip-counting sequence. Is there a list of steps that will keep you alive, no matter what sequence your captor chooses?
In this brainteaser, devised by the mathematics popularizer James Grime, you can plan a list of 11 steps that protects you from death. But if you try to add a 12th step, you are doomed: Your captor will inevitably be able to find some skip-counting sequence that will plunge you over the cliff or into the viper pit.
Around 1932, Erdős asked, in essence, what if the precipice and pit of vipers are three paces away instead of two? What if they are N paces away? Can you escape death for an infinite number of steps? The answer, Erdős conjectured, was no — no matter how far away the precipice and viper pit are, you can’t elude them forever.
But for more than 80 years, mathematicians made no progress on proving Erdős’ discrepancy conjecture (so named because the distance from the center of the tunnel is known as the discrepancy). “Everyone in the subject has whetted their teeth on this and failed,” said Andrew Granville, a number theorist at the University of Montreal and University College London. “It’s one of those problems that nobody has really written a sensible paper about, because no one had a clever idea.”
Even the seemingly simple scenario in which the pit and the precipice are just three paces away involves an enormous number of possible choices. This version of the problem was finally solved last year by Boris Konev and Alexei Lisitsa of the University of Liverpool in England, who showed, via a computer calculation whose output is comparable in size with all of Wikipedia, that it is possible to write down 1,160 safe steps, but no more. Their proof, however, did not offer a foothold on the more general problem.
Now, in a preprint posted online on September 17, Tao, a winner of the Fields Medal, mathematics’ highest honor, has shown that no matter how far away the viper pit and precipice are, there is always a maximum number of steps you can safely list.
To solve the problem, Tao measured the “entropy” of mathematical objects called multiplicative functions or sequences, which lie at the heart of not just the Erdős discrepancy problem, but also some of the deepest problems in number theory, such as understanding the distribution of prime numbers. This novel synthesis of number theory and entropy — a concept that originated in coding theory — “will certainly open up new avenues of research,” Green predicted.
Until now, the Erdős discrepancy problem has been an example of “the most ridiculous things we have felt we didn’t understand” about multiplicative functions, Granville said. “It should be an immediate observation, but somehow it had to take vast amounts of deep ideas and cleverness to get there.” Tao’s solution, he said, is “a wonderful breakthrough.”
Handles on the Wrecking Ball
In late 2009, Timothy Gowers, a mathematician at the University of Cambridge who jump-started the massive online mathematical collaborations known as “Polymath” projects, was casting about for a good topic for the next such project. In a series of blog posts, he described several possible projects, including the Erdős discrepancy problem, and asked readers to weigh in. The post on the discrepancy problem quickly attracted nearly 150 comments, and on January 6, 2010, Gowers wrote what he called an “emergency” post saying that this problem was clearly the people’s choice.
Like Erdős himself, the project cast the problem as a question about sequences of +1s and –1s, not rights and lefts. Over the course of the project, Tao figured out that it is essentially sufficient to solve the discrepancy problem for multiplicative sequences: ones in which the (n × m)th entry is equal to the nth entry times the mth entry (so, for example, the sixth entry equals the second entry times the third entry).
It makes sense that multiplicative sequences should offer high prospects for survival. In a multiplicative sequence, each skip-counting sequence of +1s and –1s is either identical to or the mirror image of the original sequence as a whole. For instance, the sequence that consists of every third entry is simply the original sequence times the third entry in the sequence, which is either +1 or –1. So, if you’ve found a survivable list of steps for the main sequence, it will automatically give you a survivable list of steps for every skip-counting sequence your captor might choose.
Multiplicative sequences are related to deep structures in number theory. One example is the famous Liouville function, which, when written as a sequence, has a +1 or –1 in the nth spot depending on whether n has an even or odd number of prime factors, and which gives mathematicians a way to study the number of primes below a given number. Multiplicative sequences have been intensively studied, but many basic questions about them have stubbornly resisted attempts to answer them. One such question, the Polymath project eventually concluded, was the Erdős discrepancy problem. “By 2012, [the Polymath project] petered out,” Tao said.
But the problem somehow seemed more approachable after the Polymath project, he said. Before, the problem had been “like a giant wrecking ball that you had to pick up, but it was completely smooth,” he said, using an analogy he attributes to Gowers. After Polymath, “the problem had handles,” he said. “So you could at least try to pick it up now. If you found a crane, you could hook it up.”
Hoisting the Wrecking Ball
In January, a pair of mathematicians — Kaisa Matomäki of the University of Turku in Finland and Maksym Radziwiłł of Rutgers University — took the first step toward building that crane, although it wasn’t immediately clear that they had done so. They came up with a way to understand the correlations between near neighbors in a multiplicative sequence, an achievement that had long been considered beyond reach.
Tao started working with Matomäki and Radziwiłł on a raft of potential applications of their method to problems in number theory. On September 6, Tao wrote a blog post about some of this work pertaining to the Liouville function, and he mentioned that the problem reminded him of a Sudoku puzzle. A few days later, a Polymath participant named Uwe Stroinski commented that the Erdős discrepancy problem also had a Sudoku-like flavor. Could Matomäki and Radziwiłł’s approach, he asked, be applied to that problem as well?
“I replied saying, ‘No, I don’t think so,’” Tao said. He was convinced — as in fact proved to be the case — that every sequence eventually leads to death in the Erdős puzzle. Matomäki and Radziwiłł’s approach seemed as if it might be useful for constructing sequences that allow you to survive for a while, but not for the reverse problem of showing that the sequence must eventually fail. As Tao gave the question more thought, however, he realized that his knee-jerk response was wrong — he could in fact prove the Erdős conjecture, if he could only control a certain complicated sum.
“I tried seriously to tackle this head-on, now that I knew that it would solve the discrepancy problem,” Tao said. And one afternoon, as he waited for his son to get out of a piano lesson, the answer came to him: He could use an argument “like a magician’s choice, where the magician offers someone in the audience two options, and it seems as if the audience has control, but the magician has a trick planned for whichever option you pick.”
Tao’s trick involves breaking up a candidate sequence into chunks and then examining the sequence, chunk by chunk, to see whether you can survive your captor. When you encounter a new chunk, one of two things must happen, Tao showed: Either the captor can kill you, or the sequence’s entropy — a measure of how random a sequence is — will drop by a definite increment. Entropy can never drop below zero, so if you continue on from chunk to chunk, you must eventually hit a chunk for which the only possibility is that your captor can kill you.
Tao solved the problem in the space of a month, which is “an amazing testament to his strength,” Granville said. “Once he gets his teeth into something, he can’t let go.”
Tao, who was 10 when he first met Erdős at a mathematics event, is excited about the power of the “magician’s trick” approach, he said. “I hope it can be used to prove many other things.”
This article was reprinted on Wired.com.
