Discrepancy of Arithmetic Progressions in Higher Dimensions

K. F. Roth (1964, Acta. Arith.9, 257-260) proved that the discrepancy of arithmetic progressions contained in [1, N]={1, 2, …, N} is at least cN^1/4, and later it was proved that this result is sharp. We consider the d-dimensional version of this problem. We give a lower estimate for the discrepancy of arithmetic progressions on [1, N]^d and prove that this result is nearly sharp. We use our results to give an upper estimate for the discrepancy of lines on an N×N lattice, and we also give an estimate for the discrepancy of a related random hypergraph.