Discrepancy of cartesian products of arithmetic progressions
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\).
- Discrepancy in generalized arithmetic progressions
- A survey on hypergraph products
- The higher dimensional analogue of certain estimates of Roth and Sárközy
- Discrepancy of Sums of Arithmetic Progressions
- Discrepancy of Sums of two Arithmetic Progressions
- On the Discrepancy for Cartesian Products
- Discrepancy of arithmetic progressions in higher dimensions
- Discrepancy of arithmetic progressions in grids
This page was built for publication: Discrepancy of cartesian products of arithmetic progressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422144)
