TOPICS
Search

Erdős Discrepancy Problem

The Erdős discrepancy problem asks whether every function f:N->{-1,1} has unbounded sums on homogeneous arithmetic progressions d, 2d, ..., md. More precisely, the proposed assertion is

sup_(d,m>=1)|sum_(k=1)^mf(kd)|=infty.

Erdős (1957) recorded the problem, and Tao (2016) proved the assertion.

Controlling the sums beginning at 1 does not suffice. For example, the alternating choice f(n)=(-1)^n has bounded such sums, but its values on the even positive integers are all 1, giving arbitrarily large sums when d=2.

This is problem 67 in the Erdős problems collection (Bloom 2026).

See also

Arithmetic Progression, Erdős Problems

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 67." Accessed Oct. 26, 2026. https://www.erdosproblems.com/67.Erdős, P. "Some Unsolved Problems." Michigan Math. J. 4, 291-300, 1957. https://doi.org/10.1307/mmj/1028997963.Tao, T. "The Erdős Discrepancy Problem." Discrete Anal. 2016, 1, 2016. https://doi.org/10.19086/da.609.

Cite this as:

Weisstein, Eric W. "Erdős Discrepancy Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ErdosDiscrepancyProblem.html

Subject classifications