98-42   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Benjamin Doerr, Anand Srivastav, P. Wehr:

Discrepancy of cartesian products of arithmetic progressions

In this article the combinatorial discrepancy of the hypergraph Hof cartesian products of d arithmetic progressions in the [N]d-lattice is studied ([N] = {0,1, ... ,N-1}). For simplicity, we call such a hyperedge a d-dimensional arithmetic progression. Such higher dimensional arithmetic progressions are motivated by a high-dimensional version of van der Waerden's theorem, namely the Gallai-Witt-theorem (1990). We resolve the discrepancy problem for d-dimensional arithmetic progressions by proving disc(H) = Theta (Nd/4) for every fixed integer d >= 1.

This extends the famous lower bound of Omega(N1/4) of Roth (1964) and the optimal upper bound O(N1/4) of Matousek and Spencer (1994) 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 Matousek and Spencer is sufficient. Finally, some special cases, e.g. symmetric arithmetic progressions and infinite arithmetic progressions, are investigated.

Mathematics Subject Classification (1991): 11B25, 11K38, 22B05, 05C15

Bibliographical note: Electron. J. Combin. 11 (2004), Research Paper 5.

Keywords: arithmetic progressions, discrepancy, harmonic analysis, locally compact abelian groups


Mail an Jens Burmeister
[Thu Feb 19 18:56:34 2009]
Impressum