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 Z_n setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in Z_n for all positive integer n . We further determine up to a constant factor the discrepancy of arithmetic progressions in Z_n for many n . For example, if n=p^k is a prime power, then the discrepancy of arithmetic progressions in Z_n is Θ (n^1/3+r_k/(6k)), where r_k {0, 1, 2} is the remainder when k is divided by 3 . This solves a problem of Hebbinghaus and Srivastav.