Discrepancy of Arithmetic Progressions in Higher Dimensions

AbstractK. 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 cN1/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