Covering numbers, dyadic chaining and discrepancy

In 2001 Heinrich, Novak, Wasilkowski and Woźniakowski proved that for every s≥1s≥1 and N≥1N≥1 there exists a sequence (z1,…,zN)(z1,…,zN) of elements of the ss-dimensional unit cube such that the star-discrepancy DN∗ of this sequence satisfies DN∗(z1,…,zN)≤csN for some constant cc independent of ss and NN. Their proof uses deep results from probability theory and combinatorics, and does not provide a concrete value for the constant cc.In this paper we give a new simple proof of this result, and show that we can choose c=10c=10. Our proof combines Gnewuch’s upper bound for covering numbers, Bernstein’s inequality and a dyadic partitioning technique.