Discrepancy of Arithmetic Progressions in Higher Dimensions

✍ Scribed by Benedek Valkó

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 136 KB
• Volume: 92
• Category: Article
• ISSN: 0022-314X
• DOI: 10.1006/jnth.2001.2704

✦ Synopsis

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.