In the past I have explained a difficult mathematics problem being worked on via blog comments that was eventually solved. Since then there have been four more Polymath projects, and I want to discuss the one that has shown the most promise, the Erdős discrepancy problem.

Like my last post, this is written for non-mathematicians. If you’re a mathematician you may prefer heading directly to the official description.

Consider some apple and orange trees planted in a row:

Imagine starting at tree #1 and walking your way past all the trees, keeping track of how many trees of each type you have passed along the way:

Take the difference (the *absolute value*) between the number of apple and orange trees at any point during the walk:

Our main concern is the *largest* difference in the row of trees. With the six trees above the largest difference is 2.

Puzzle #1: How could you keep planting trees and keep the largest difference at 1 (that is, the difference between apple and orange trees is always 1 or 0)?

*Skip counting* starts at any number and then “skips forward” by that number:

1, 2, 3, 4, 5, …

2, 4, 6, 8, 10, …

3, 6, 9, 12, 15, …

4, 8, 12, 16, 20, …

(In more mathematical terms, it’s listing all the multiples of a given number.)

Instead of walking along every tree, we could use skip counting and only include particular trees in the row. Let’s take our example skip counting by 2s:

Notice this time the largest difference is only 1.

Puzzle #2: How could you plant six apple and orange trees so that for

bothcounting by 1sandcounting by 2s, the largest difference is 1?

If every kind of skip counting is used (1s, 2s, 3s, 4s, … ) then the largest difference possible is called the **discrepancy**.

Puzzle #3: Design a row of 11 apple and orange trees so that the discrepancy is 1. That is, for any kind of skip counting, the difference between the number and apple and orange trees is always 1 or 0.

Puzzle #4: Prove Puzzle #3 can’t be solved with 12 trees.

According to the solution of Puzzle #4, if we want a discrepancy of 1 at some point we have to stop planting trees.

Well, what about a discrepancy of 2? That turns out to break at 1124, **we think**. As of this writing, it hasn’t even been proven that it is impossible to plant 1125 trees such that the discrepancy is less than 2.

How about a discrepancy of 3, 4, or 5? Now the problem is getting to the point where we aren’t sure how many trees we could have, but the evidence suggests that eventually we’ll have to stop planting trees for those too.

Here is what the Polymath project is attempting to prove:

No matter what discrepancy we pick, there will always be a limit to the number of trees in the row.

This is known as the Erdős discrepancy problem, and has been unsolved now for nearly 80 years.

The main project page is a good place to learn more, and to find everything rendered in proper mathematical notation.

Filed under: Mathematics

joshg, on April 21, 2010 at 10:46 am said:Thanks! I really appreciate these Polymath introduction posts. I’ve found the Polymath project worth following just to get a glimpse of professional mathematicians collaborating on a messy project, but I’ve had trouble getting up to speed to follow along with the actual content.

A gentle introduction to the Polymath project « The Number Warrior, on April 21, 2010 at 10:55 am said:[…] A gentle introduction to the 5th Polymath project […]

A gentle introduction to the 5th Polymath project « The Math Less Traveled, on April 21, 2010 at 3:12 pm said:[…] highly recommend reading Jason Dyer’s description of the Erdős discrepancy problem, the subject of the most recent Polymath project (the Polymath […]

Mini-polymath project #2 « The Number Warrior, on July 8, 2010 at 9:10 am said:[…] Mini-polymath project #2 Posted on July 8, 2010 by Jason Dyer The Polymath Projects have been tackling large and difficult problems collaboratively via blog comments. I have written about them here and here. […]

Eric, on February 19, 2014 at 5:33 pm said:Sequence of length 12:

-+–++-++-+-

With equal number of + and -, the whole sequence has a 1-discrepancy of 0.

Looking at the even terms:

+ – + + – –

Zero again.

Every third term:

– + + –

Zero.

Every fourth term gives us 1:

– + –

And every fifth term is +,-;

While every sixth is the same: +,-.

Higher multiples can only give 1.

What am I misunderstanding?

Jason Dyer, on February 19, 2014 at 5:42 pm said:You aren’t adding them all up and checking at the end. You’re checking at every step of the way. So the sequence + + + – – – would add up to be zero, but would have a discrepancy of 3 because after the 3rd point in the sequence you would be at +3.

Erdős’s discrepancy problem now less of a problem | The Aperiodical, on February 25, 2014 at 1:05 am said:[…] a simpler outline of the statement, try Jason Dyer’s blog post, which explains it in terms of fruit (and was written back in 2010, when the suspected length […]

Taberna Espacial » Una demostración matemática que nunca será revisada por un ser humano, on February 25, 2014 at 10:35 am said:[…] http://arxiv.org/abs/1402.2184 http://harveycohen.net/erdos/ http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html#.UwZkr0J5Nzy https://numberwarrior.wordpress.com/2010/04/21/a-gentle-introduction-to-the-5th-polymath-project/ […]

Donna J Blass, on March 22, 2014 at 8:43 pm said:John and I are whizzing along on our comprehensive of the Erdish discrepancy equation. We are also learning to work together without getting overly intense about it or raising our voices. This Erdish stuff is so frustrating to work through that I can’t help wondering how many divorces Paul Erdish is indirectly personally responsible for? Now that would be a really interesting Erdish number.

Anonymous, on August 9, 2015 at 2:34 am said:Sequence of length 1160 with discrepancy=2 has been discovered. You can check in here: http://cgi.csc.liv.ac.uk/~konev/SAT14/

Jason Dyer, on August 9, 2015 at 7:24 am said:Yep, this is an older blog post. That project was the continuation of this one.