← All problems

Erdős Problem #177 — Uniform discrepancy of arithmetic progressions

Find the smallest h(d)h(d) such that there exists a function f:N→{−1,1}f:\mathbb{N}\to\{-1,1\} for which, for every integer d≥1d\geq 1, every finite arithmetic progression with common difference dd has signed sum of absolute value at most h(d)h(d). Explicitly, write a nonempty progression as a,a+d,…,a+(m−1)da,a+d,\ldots,a+(m-1)d, with integers a,m≥1a,m\geq 1, and define

Df(d)=sup⁡a,m≥1∣∑i=0m−1f(a+id)∣.D_f(d)=\sup_{a,m\geq 1}\left|\sum_{i=0}^{m-1}f(a+id)\right|.

The requirement is Df(d)≤h(d)D_f(d)\leq h(d) for every d≥1d\geq1, using one and the same function ff for all differences. When this supremum is finite, it is a maximum because the sums are integers. The question is to determine the smallest such bound function hh; the statement does not specify a further convention for comparing candidate bound functions. Erdős Problem #177 A Discrepancy Problem: Balancing Infinite Dimensional Vectors

Background

This is a two-coloring discrepancy problem: the signs −1-1 and 11 color the positive integers, and the discrepancy of a progression is the imbalance between its two color classes. The bound must be uniform in both the starting point and the length, while a single coloring must work simultaneously for every common difference. Cantor, Erdős, Schreiber, and Straus established that such a coloring exists with finite discrepancy for each difference, giving the bound Df(d)≤d!D_f(d)\leq d!. Their result answers the basic existence question but leaves the growth rate of the discrepancy as the difference varies to be investigated. Erdős Problem #177 A Discrepancy Problem: Balancing Infinite Dimensional Vectors

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.