A gentle introduction to the 5th Polymath project

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 both counting by 1s and counting 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.