An elementary proof of a lower bound for the inverse of the star discrepancy

Abstract: A central problem in discrepancy theory is the challenge of evenly distributing points

l e f t x_{1}, d o t s, x_{n} i g h t

in

[0, 1]^{d}

. Suppose a set is so regular that for some

v a r e p s i l o n > 0

and all

y i n [0, 1]^{d}

the sub-region

[0, y] = [0, y_{1}] i m e s d o t s i m e s [0, y_{d}]

contains a number of points nearly proportional to its volume and

forall~y in [0,1]^d qquad left| frac{1}{n} # left{1 leq i leq n: x_i in [0,y] ight} - mbox{vol}([0,y]) ight| leq varepsilon,

how large does

n

have to be depending on

d

and

v a r e p s i l o n

? We give an elementary proof of the currently best known result, due to Hinrichs, showing that

n g t r s i m d c d o t v a r e p s i l o n^{- 1}

.

This page was built for publication: An elementary proof of a lower bound for the inverse of the star discrepancy