On the Discrepancy for Cartesian Products
We prove that the discrepancy for the family of Cartesian products \(B_1\times B_2\subseteq \mathbb{R}^4\), where \(B_1\) and \(B_2\) are circular discs in the plane, is \(O(n^{1/4+\varepsilon})\) for an arbitrarily small constant \(\varepsilon>0\), i.e. essentially the same as that for discs in the plane. The result is established for the combinatorial discrepancy, and consequently it holds for the discrepancy with respect to the Lebesgue measure as well. This answers a question of Beck and Chen. More generally, we prove an upper bound for the discrepancy for a family \(\{\prod_{i=1}^k A_i: A_i\in {\mathcal A}_i\), \(i=1,2,\ldots,k\}\), where each \(\mathcal A\) is a family in \(\mathbb{R}^{d_i}\), each of whose sets is described by a bounded number polynomial of inequalities of bounded degree. The resulting discrepancy bound is determined by the ``worst of the families \({\mathcal A}_i\), and it depends on the existence of certain decompositions into constant-complexity cells for arrangements of surfaces bounding the sets of \({\mathcal A}_i\). The proof uses Beck's partial coloring method and decomposition techniques developed for the range-searching problem in computational geometry.
This page was built for publication: On the Discrepancy for Cartesian Products
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4520420)
