The Erdős discrepancy problem

Unsolved Research level Archive

archive posted 17 Jul 2026

Let $x_{1}, x_{2}, x_{3}, \dots$ be any infinite sequence with every $x_{i}$ equal to $+ 1$ or $- 1$ . Prove that for every $C$ there are positive integers $k$ and $d$ with

i = 1 \sum k x_{i d} > C .

Posed by Paul Erdős, 1932

Like0

History and references

Solved in 2015 by Terence Tao.

Erdős raised the question around 1932. The sums run along the progressions $d, 2 d, 3 d, \dots$ , so the conjecture says no $\pm 1$ sequence can stay balanced along all of them at once. In 2014 Boris Konev and Alexei Lisitsa used a SAT solver to show that every sequence of length 1161 or more has a sum exceeding 2 in absolute value, a proof whose computer output ran to about 13 gigabytes. In September 2015 Terence Tao proved the full conjecture, building on the online Polymath5 project of 2010 and a suggestion by Uwe Stroinski on Tao's blog. The proof was published in Discrete Analysis in 2016.

References

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0