Discrepancy in modular arithmetic progressions. Issue 11 (1st November 2022) - Fox, Jacob; Xu, Max Wenqiang; Zhou, Yunkun
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 $Θ (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 $Θ (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.