Discrepancy in modular arithmetic progressions

Abstract

Celebrated theorems of Roth and of Matoušek and Spencer together show that the discrepancy of arithmetic progressions in the first $n$ positive integers is $\Theta (n^{1/4})$. We study the analogous problem in the ${\mathbb{Z}}_n$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in ${\mathbb{Z}}_n$ for all positive integer $n$. We further determine up to a constant factor the discrepancy of arithmetic progressions in ${\mathbb{Z}}_n$ for many $n$. For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in ${\mathbb{Z}}_n$ is $\Theta (n^{1/3+r_k/(6k)})$, where $r_k\in \{0,1,2\}$ is the remainder when $k$ is divided by $3$. This solves a problem of Hebbinghaus and Srivastav.

arXiv comment22 pages + 4 pages appendix