The Discrepancy Function of a set $P_N$ of $N$ points of the unit cube in dimension $d$ is given by

$$D_N (x)=\vert P_N\cap [0,x) \vert -N \vert[0,x)\vert$$

where $[0,x)$ is a $d$-dimensional box with lower corner at the origin and upper corner at $x$.

A Theorem of Roth shows that regardless of how the point set is chosen $D_N$ satisfies a lower bound on its $L^2$ norm,

$$\Vert D_N \Vert _2 > c(\log N) ^{ (d-1)/2 }$$

The $L^\infty$ norm however, is conjectured to be larger, by a suitable power of $\log N$. Definitive information is known only in dimension 2, a theorem of Schmidt.

Recently, new information has been obtained in dimensions 3 and higher. This talk will survey relevant conjectures, and illustrate the connection between this topic and questions in approximation theory and probability theory.