main-content

Discrepancy theory is also called the theory of irregularities of distribution. Here are some typical questions: What is the "most uniform" way of dis­ tributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? For a precise formulation of these questions, we must quantify the irregularity of a given distribution, and discrepancy is a numerical parameter of a point set serving this purpose. Such questions were first tackled in the thirties, with a motivation com­ ing from number theory. A more or less satisfactory solution of the basic discrepancy problem in the plane was completed in the late sixties, and the analogous higher-dimensional problem is far from solved even today. In the meantime, discrepancy theory blossomed into a field of remarkable breadth and diversity. There are subfields closely connected to the original number­ theoretic roots of discrepancy theory, areas related to Ramsey theory and to hypergraphs, and also results supporting eminently practical methods and algorithms for numerical integration and similar tasks. The applications in­ clude financial calculations, computer graphics, and computational physics, just to name a few. This book is an introductory textbook on discrepancy theory. It should be accessible to early graduate students of mathematics or theoretical computer science. At the same time, about half of the book consists of material that up until now was only available in original research papers or in various surveys.

### 1. Introduction

Abstract
In this chapter, we introduce the concept of discrepancy. We formulate a basic problem concerning discrepancy for rectangles, we show its connections to the discrepancy of infinite sequences in the unit interval, and we briefly comment on the historical roots of discrepancy in the theory of uniform distribution (Section 1.1). In Section 1.2, we introduce discrepancy in a general geometric setting, as well as some variations of the basic definition. Section 1.3 defines discrepancy in a seemingly different situation, namely for set systems on finite sets, and shows a close relationship to the previously discussed “Lebesguemeasure” discrepancy. Finally, Section 1.4 is a mosaic of notions, results, and comments illustrating the numerous and diverse connections and applications of discrepancy theory. Most of the space in that section is devoted to applications in numerical integration and similar problems, which by now constitute an extensive branch of applied mathematics, with conventions and methods quite different from “pure” discrepancy theory.
Jiří Matoušek

### 2. Low-Discrepancy Sets for Axis-Parallel Boxes

Abstract
What should a planar set with small discrepancy for axis-parallel rectangles look like? Maybe the first thing coming to mind would be the regular $$\sqrt n \times \sqrt n$$ grid, placed in the unit square in an appropriate scale, as in Fig. 2.1(a). It is easy to see that this gives discrepancy of the order $$\sqrt n$$. Another attempt might be n independent random points in the unit square as in Fig. 2.1(b), but these typically have discrepancy about $$\sqrt n$$ as well. (In fact, with high probability, the discrepancy is of the order $$\sqrt {n\;\log \;\log \;n}$$; a result well-known to probabilists under the name law of the iterated logarithm comes into play.) It turns out that a far better discrepancy can be achieved, of the order log n. This chapter is devoted to various constructions of such sets and to their higher-dimensional generalizations. In dimension d, for d arbitrary but fixed, the best known sets have discrepancy for axis-parallel boxes of the order log d−1 n.
Jiří Matoušek

### 3. Upper Bounds in the Lebesgue-Measure Setting

Abstract
In this chapter we start proving upper bounds for the discrepancy for objects other than the axis-parallel boxes. We will encounter a substantially different behavior of the discrepancy function, already mentioned in Section 1.2. For axis-parallel boxes, the discrepancy is at most of a power of log n, and similar results can be shown, for example, for homothets of a fixed convex polygon. The common feature is that the directions of the edges are fixed. It turns out that if we allow arbitrary rotation of the objects, or if we consider objects with a curved boundary, discrepancy grows as some fractional power of n. The simplest such class of objects is the set H 2 of all (closed) halfplanes, for which the discrepancy function D(n,H 2) is of the order n 1/4. For halfspaces in higher dimensions, the discrepancy is of the order n 1/2−1/2d ; so the exponent approaches 1/2 as the dimension grows. Other classes of “reasonable” geometric objects, such as all balls in R d , all cubes (with rotation allowed), all ellipsoids, etc., exhibit a similar behavior. The discrepancy is again roughly n 1/2−4/2d although there are certain subtle differences.
Jiří Matoušek

### 4. Combinatorial Discrepancy

Abstract
In this chapter, we are going to investigate the combinatorial discrepancy, an exciting and significant subject in its own right. From Section 1.3, we recall the basic definition: If X is a finite set and S ⊑ 2 X is a family of sets on X,a coloring is any mapping $$x:X \to \left\{ { - 1, + 1} \right\}$$, and we have disc $$\left( S \right) = {\min _x}{\max _{s \in s}}|x\left( S \right)|,$$, where $$\sum {_{x \in S}x\left( x \right)} .$$
Jiří Matoušek

### 5. VC-Dimension and Discrepancy

Abstract
In this chapter, we introduce combinatorial parameters measuring the complexity of a set system: the shatter functions and the Vapnik—Chervonenkis dimension. These concepts have recently become quite important in several branches of pure and applied mathematics and of theoretical computer science, such as statistics, computational learning theory, combinatorial geometry, and computational geometry.
Jiří Matoušek

### 6. Lower Bounds

Abstract
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 2) 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)
Jiří Matoušek

### 7. More Lower Bounds and the Fourier Transform

Abstract
In the previous chapters, we have seen several approaches to lower bounds in combinatorial and geometric discrepancy. Here we are going to discuss another, very powerful method developed by Beck, based on the Fourier transform. Although one can argue that, deep down, this method is actually related to eigenvalues and proofs using orthogonal or near-orthogonal functions, proofs via the Fourier transform certainly look different, being less geometric and more akin to classical harmonic analysis. For many results obtained by this method, such as the tight lower bound for the discrepancy for discs of a single fixed radius, no other proofs are known.
Jiří Matoušek