## Polymath5 – The Erdős discrepancy problem – is on its way.

Update (September 2015): Terry Tao have now solved Erdos discrepancy problem and proved that indeed the discrepancy tends to infinity. See also this blog post on Tao’s blog.

Update: Gowers’s theoretical post marking the official start of Polymath 5 appeared.

**Update (February 2014)**: Boris Konev and Alexei Lisitsa found a sequence of length 1160 of discrepancy 2 and proved that no such sequence of length 1161 exists.

A SAT Attack on the Erdos Discrepancy Conjecture

The abstract reads: “We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solvers, one can obtain a sequence of length 1160 with discrepancy 2 and a proof of the Erdos discrepancy conjecture for C=2, claiming that no sequence of length 1161 and discrepancy 2 exists. We also present our partial results for the case of C=3. See also this post. So the title of this post could be revised to: Is 2 logarithmic in 1160? (My conjecture is that 2 represents the square root of log 1160.) **Followups**: See also this post Practically P=NP? on GLL, and Jacob Aron’s New Scientist’s article Wikipedia-size maths proof too big for humans to check. On GLL, Dick and Ken devoted the third Hebrew letter ‘Gimel’ for C.

**Original post**

After several discussion threads, polymath5 devoted to Erdos’s discrepency problem is on its way on Gowers’s blog. While a theoretical post with several possible attacks on the problem is planned, there is intensive experimental activity. The picture above shows a sequence of +/- signs length 1124 with discrepency 2: namely on every arithmetic progression of the form d, 2d, 3d, … where all terms are between 1 and 1124 the gap between the number of ‘+’s and the number of ‘-‘s is at most two. The present hopes from these experiments are described in this paragraph:

” I now think it likely that we will come up with a formula that gives something very close to the 1124 sequence. If so, then I am keeping my fingers very firmly crossed that it will give an infinite sequence with sublogarithmic discrepancy. But we shall see: some computation is still needed before we will know what the formula is. There is also a chance that we will obtain a formula but with parameters that have to be chosen for each prime, and that we will not be able to see how to choose them in general. In that case, we may at least obtain a very efficient algorithm for finding extremely long sequences of low discrepancy.”

This is very nice.

Pingback: polymath5 « Euclidean Ramsey Theory

A tiny remark: the update is February 2014 rather than 2013 …

GK: corrected. How time flies!!The Erdos discrepancy problem was just been settled by Terry Tao!