Discrepancy of Sums of Three Arithmetic Progressions

Abstract

The set system of all arithmetic progressions on $[n]$ is known to have a discrepancy of order $n^{1/4}$. We investigate the discrepancy for the set system ${\cal S}_n^3$ formed by all sums of three arithmetic progressions on $[n]$ and show that the discrepancy of ${\cal S}_n^3$ is bounded below by $\Omega(n^{1/2})$. Thus ${\cal S}_n^3$ is one of the few explicit examples of systems with polynomially many sets and a discrepancy this high.