Polymath5 – Is 2 logarithmic in 1124?

 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.

gimel

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:

Continue reading