Maths Whizz Solves a Master's Riddle

A mathematical puzzle that resisted solution for more than 80 years—including computerized attempts to crack it—seems to have yielded to a single mathematician.

On September 17, Terence Tao, a mathematician at the University of California, Los Angeles, whose body of work earned him the prestigious Fields Medal in 2006, submitted a paper to the arXiv preprint server claiming to prove a number-theory conjecture posed by mathematician Paul Erdős in the 1930s.

“Terry Tao just dropped a bomb,” tweeted Derrick Stolee, a mathematician at Iowa State University in Ames.

Like many puzzles in number theory, the Erdős discrepancy problem is simple to state but devilishly difficult to prove. Erdős, who died in 1996, speculated that any infinite string of the numbers 1 and −1 could add up to an arbitrarily large (positive or negative) value by counting only the numbers at a fixed interval for a finite number of steps.

The task is intuitively easy for some arrangements—tallying digits at any interval in a sequence that is all 1s will add up to a big number. And in an alternating sequence of 1s and −1s, choosing every second digit will do the job. But Erdős conjectured that it was true for any such sequence.

Tao’s proof shows that Erdős was right: these sums can, in fact, grow infinitely large for any arbitrary sequence, although he does not provide a way to calculate their value for a given instance.

The proof has not yet undergone rigorous peer review, but experts have expressed no concern over whether it will survive a critical look. “I'm completely confident,” says Gil Kalai, a mathematician at the Hebrew University of Jerusalem, adding that he expects the review to be quick.

Constructive commentPolyMath Project, an  in which mathematicians work together on a single mathematical puzzle. Tao was one of several dozen participants.

The effort fizzled out in 2012, but participants did manage to show that proving the conjecture for a certain family of sequences was good enough to prove it in general. That family has arbitrary 1s and −1s in the spots indexed by prime numbers, and the spots indexed by other numbers are determined by multiplication of the values at the locations of their prime factors. For instance, the value of the 15th spot is the product of the values at the 3rd and 5th spots.

In February 2014, researchers presented a computer proof for a special case of the conjecture: they showed that it is always possible to find a sum that is bigger than 2. However, they failed to prove that there is always a sum bigger than 3. Tao’s proof demonstrates that there is always a sum bigger than any finite number.

No one else managed to make major progress after the computational attempt. Tao had been working on a different problem early in September, when a timely comment on his blog suggested that the problem might be related to the Erdős conjecture. “At first, I thought the connection was only superficial,” says Tao. But he quickly realized that combining the commenter's fresh insight with previous results could lead to a solution. He submitted his paper less than two weeks later and included an acknowledgement thanking the commenter, Uwe Stroinski, a maths instructor in Reutlingen, Germany, who holds a PhD in mathematics from the University of Tübingen.

Tao has submitted his proof to the open-access journal , run by Gowers. The journal, which was , provides conventional peer review but accepts only papers that have already been posted on arXiv, thereby avoiding major publishing costs. “Tim’s journal is a promising experiment in completely open-access publishing,” says Tao.

Erdős, who wrote a letter recommending Tao for admission to Princeton University in New Jersey, often offered cash prizes for solving the problems he posed. He set the prize for the discrepancy problem at US$500. Since his death, others have taken it upon themselves to award those prizes on his behalf.

When asked whether he would accept the prize were someone to offer it, Tao demurred. “It was traditional to not actually cash the prizes that Erdős did award while he was alive,” he says. “People usually framed the cheque instead.”

see also: