Irregularities of distributions and extremal sets in combinatorial complexity theory

Abstract

In 2004 the second author of the present paper proved that a point set in $[0,1{]}^d$ which has star-discrepancy at most $\epsilon$ must necessarily consist of at least $c_{abs}d{\epsilon }^{-1}$ points. Equivalently, every set of $n$ points in $[0,1{]}^d$ must have star-discrepancy at least $c_{abs}d{n}^{-1}$. The original proof of this result uses methods from Vapnik--Chervonenkis theory and from metric entropy theory. In the present paper we give an elementary combinatorial proof for the same result, which is based on identifying a sub-box of $[0,1{]}^d$ which has approximately $d$ elements of the point set on its boundary. Furthermore, we show that a point set for which no such box exists is rather irregular, and must necessarily have a large star-discrepancy.

13 pages. Version 2: several corrections, including values of numerical constants