Discrepancy of cartesian products of arithmetic progressions (Q1422144)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Discrepancy of cartesian products of arithmetic progressions |
scientific article |
Statements
Discrepancy of cartesian products of arithmetic progressions (English)
0 references
5 February 2004
0 references
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\).
0 references
combinatorial discrepancy
0 references
hypergraph
0 references
higher dimensional arithmetic progressions
0 references