The Erdős Discrepancy Problem

Computational combinatorics made a big splash last spring when Konev and Lisista announced their SAT-solver-based proof of the Erdős Discrepancy Problem for constant . Recently, Le Bras, Gomes, and Selman announced another SAT-based solution for , but when restricting the sequences to have a special property.

I was working on a draft blog post to talk about these results, but then Terry Tao went and solved the full conjecture. I tweeted about it and got many responses, my favorite being simply the following image:

To help those who have difficulty with Tao’s paper (and I am not qualified to read any part of his solution), I made a short video describing the problem, or read below.