Erdős Discrepancy Problem

Paul Erdos
Paul Erdos

Terrence Tao, a mathematician at UCLA, has recently – September 2015 – announced a proof to the Erdos Discrepancy Problem! This 80-year-old problem in number theory was posed by legendary Hungarian mathematician Paul Erdos. Having recently heard about this news, I was thrilled to be present at a time of such an exciting moment in mathematics, and concluded to quickly research about what this problem outlined. Overwhelmed by the complexity of mathematics presented on most websites that discuss this problem, I decided to summarise the problem in a blogpost for any budding mathematicians who are interested in these discoveries but, like me, do not yet have the mathematical capability to understand the nitty gritty details.

The Theorem

Let xn be a sequence and let C be a constant. Must there exist positive integers dk such that:


Looking at this I was perplexed and so I decided to do a little further research. 

This simply states that if we have a sequence of numbers that is made up of 1 and -1, then we consider any finite sequence of length n spaced elements apart and take the sum of these numbers to find the discrepancy.

For example, if we look at this simple sequence with an obvious pattern:

1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1 etc.

Then if we

  • Start on the third number (or ‘element’) – 1
  • Chose a spacing of 2 – d = 2
  • Chose a length of 6

the discrepancy will be

1 – 1 + 1 + 1 – 1 + 1 + 1 = 3

This conjecture states that given a sequence xn, then for any integer C>0, there exists a subsequence xd, x2d, x3d,… xkd for some choice of positive integers k and d such that desequation

(the sum of these numbers -the discrepancy – is greater than C)

If you’re still confused then below I’ve presented a very good analogy that presents a simplified version of this problem, which I got from this article.

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, 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.

Terrance Tao

This problem has shown to be very difficult to prove. However, on September 17 2015, Field’s Medalist Terrance Tao posted a paper on arXiv announcing his proof for this conjecture.

So how did he do it? Tao measured the ‘entropy‘ of mathematical objects called multiplicative functions or sequences, which are deeply connected to the Erdos Discrepancy Problem, as well as problems in number theory, such as the distribution of the prime numbers.

On Tao’s solution, Andrew Granville – British number theorist at the University of Montreal and University College London – said: “it should be an immediate observation, but somehow it had to take vast amounts of deep ideas and cleverness to get there.”


2 thoughts on “Erdős Discrepancy Problem”

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s