ON THE DISCREPANCY FOR CARTESIAN PRODUCTS

Abstract

Let [Bscr ]₂ denote the family of all circular discs in the plane. It is proved that the discrepancy for the family {B₁ × B₂ [ratio ] B₁, B₂ ∈ [Bscr ]₂} in R⁴ is O(n^1/4+ε) for an arbitrarily small constant ε > 0, that is, it is essentially the same as that for the family [Bscr ]₂ itself. 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 {Π^k_i=1A_i[ratio ] A_i∈A_i, i = 1, 2, …, k}, where each A_i is a family in R^d_i, each of whose sets is described by a bounded number of polynomial inequalities of bounded degree. The resulting discrepancy bound is determined by the ‘worst’ of the families A_i , and it depends on the existence of certain decompositions into constant-complexity cells for arrangements of surfaces bounding the sets of A_i. The proof uses Beck's partial coloring method and decomposition techniques developed for the range-searching problem in computational geometry.