Discrepancy of cartesian products of arithmetic progressions (Q1422144)

The authors determine the combinatorial discrepancy of the hypergraph \(\mathcal{H}\) of Cartesian products of \(d\) arithmetic progressions in the \([N]^{d}\)-lattice \(([N]=\{0,1,\ldots, N -1\}).\) The study of such higher dimensional arithmetic progressions is motivated by a multidimensional version of van der Waerden's theorem, namely the Gallai theorem (1933). In the present paper the discrepancy problem for \(d\)-dimensional arithmetic progressions is solved by proving disc \(\mathcal{H} = \Theta (N \frac{d}{4})\) for every fixed integer \(d \geq 1.\) This extends the famous lower bound of \(\Omega (N^{\frac{1}{4}})\) of Roth (1964) and the matching upper bound \(O (N^{\frac{1}{4}})\) of Matousek and Spencer (1996) from \(d = 1\) to arbitrary, fixed \(d\).