That Time Terence Tao Won $500 From Paul Erdős

A 10 year old Terence Tao hard at work with Paul Erdős in 1985. Couresty of Wikimedia Commons.

Suppose you have some arbitrary sequence of 1 and -1, something like this

1, 1, -1, -1, -1, 1, 1, 1, 1, 1, -1, -1, ….

And suppose you start plucking entries from fixed intervals and adding them together. For example, if I just pick every third entry from the sequence, and add them all together, I would get

-1 + 1 + 1 + -1 + …

If I carry on doing that for some finite amount of time, will that sum get as big (positive or negative) as I want? Very simply, this is the idea behind the Erdős Discrepancy Problem, which claims that for any arbitrary sequence {x₁, x₂, x₃, …} where the x_i are either 1 or -1, and for any constant C, it is possible to find positive numbers k and n so that

x_k + x_2k + x_3k + … + x_nk > C.

Sounds easy enough, right?

Not quite. And indeed this problem perplexed the great Paul Erdős to such an extent that he offered a $500 reward for a solution in the 1950s. And let’s hope that the late Erdős left a stack of cash lying around, because as of last week the problem has been solved by Terence Tao and the contributors to Polymath5.

In his blog, Tao gives a series of technical explanations of how he and the people of Polymath5 solved the famous problem. He explains how the key to cracking open the Discrepancy Problem was actually solving a totally different problem called the Elliot conjecture. This is such a common occurrence in math (and all fields, I suppose) that solving a really hard problem turns out the be just solving another really hard (but maybe a wee bit easier) problem.

The Polymath project — whose most well-known result to date is the tightening of the prime gap bounds of Maynard and Zhang — is a crowd-sourcing effort to drive mathematical breakthroughs. Mathematician Timothy Gowers, over on his webblog, gives a great commentary on the collaborative nature of this result. Although Tao was admittedly the one to put bring the whole thing to a culminating result, the terrain of the foundation would have looked much different without the crowd-sourced contributions. Gowers comments,

“My own experience of polymath projects is that they often provoke me to have thoughts I wouldn’t have had otherwise, even if the relationship between those thoughts and what other people have written is very hard to pin down — it can be a bit like those moments where someone says A, and then you think of B, which appears to have nothing to do with A, but then you manage to reconstruct your daydreamy thought processes to see that A made you think of C, which made you think of D, which made you think of B.”

This result is a marked victory for polymath, speaking to the impressive power of collaboration in mathematics, and an exciting success for Tao. And Tao will not be spending his well-deserved $500 on high-priced journal fees, since he will be publishing his paper in the new Arxiv overlay journal Discrete Analysis.