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

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: