Discrepancy of cartesian products of arithmetic progressions

We determine the combinatorial discrepancy of the hypergraph H of cartesian products of d arithmetic progressions in the [N]^d-lattice ([N] = {0, 1, . . . ,N - 1}). The study of such higher dimensional arithmetic progressions is motivated by a multi-dimensional version of van derWaerden's theorem, namely the Gallai-theorem (1933). We solve the discrepancy problem for d-dimensional arithmetic progressions by proving disc(H) = Θ(N ^d/4 ) for every fixed integer d ≥ 1. This extends the famous lower bound of Ω(N^1/4) of Roth (1964) and the matching upper bound O(N ^1/4) of Matoušek and Spencer (1996) from d = 1 to arbitrary, fixed d. To establish the lower bound we use harmonic analysis on locally compact abelian groups. For the upper bound a product coloring arising from the theorem of Matoušek and Spencer is sufficient. We also regard some special cases, e.g., symmetric arithmetic progressions and infinite arithmetic progressions.