Lower Bounds

In this chapter, we finally begin with the mathematically most fascinating results in geometric discrepancy theory: the lower bounds (we have already seen some lower bounds in Chapter 4 but not in a geometric setting). So far we have not answered the basic question, Problem 1.1, namely whether the discrepancy for axis-parallel rectangles must grow to infinity as n n → ∞. An answer is given in Section 6.1, where we prove that D(n,R₂) is at least of the order $$\sqrt {\log n}$$. Note that, in order to establish a such a result, we have to show that for any n-point set P in the unit square, some axis-parallel rectangle exists with a suitably high discrepancy. So we have to take into account all possible sets P simultaneously, although we have no idea what they can look like. The proof is a two-page gem due to Roth, based on a cleverly constructed system of orthogonal functions on the unit square. In dimension d, the same method gives D(n,R _d ) = 52((log n)(d-1)/2)