The Inverse of the Star Discrepancy

Problem's Description

Suppose we have a finite set of points $\mathcal{P} \subset [0,1]^d$ with the following nice equidistribution property: for any axis-parallel rectangle $R \subset [0,1]^d$ with one point anchored in the origin, the number of points from $\mathcal{P} $ that are contained in the rectangle $R$ is very nearly proportional to the volume of the rectangle

$$ \forall ~ R \qquad \qquad \left| \frac{\# (\mathcal{P} \cap R)}{\#\mathcal{P} } - \mbox{vol}(R) \right| \leq \varepsilon.$$

Question. How large does $\#\mathcal{P}$ need to be (depending on $\varepsilon, d$)?

The best known bounds are $$ \frac{d}{\varepsilon} \lesssim \# \mathcal{P} \lesssim \frac{d}{\varepsilon^2}.$$ The upper bound comes from random points: if the upper bound were correct, then this would mean that random points are basically the best one can do which would be interesting. If the lower bound was correct, then this would mean that much better point sets than purely random points exist which would be very interesting.

1. Article The inverse of the star-discrepancy depends linearly on the dimension.

   • S. Heinrich,
   • E. Novak,
   • G. Wasilkowski,
   • H. Wozniakowski

   Acta Arithmetica 96, 279-302, 2000

2. Article Covering numbers, Vapnik–Cervonenkis classes and bounds for the star-discrepancy

   • Aicke Hinrichs

   Journal of Complexity, 477-483, 2004

3. Conference Paper Irregularities of distributions and extremal sets in combinatorial complexity theory

   • Christoph Aistleitner,
   • Aicke Hinrichs

   Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, 59-74, 2018

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

   • Stefan Steinerberger

   Journal of Complexity 75 (101713), 2023