# The Inverse of the Star Discrepancy

Open

Posted online: 2024-03-22 15:58:04Z by Stefan Steinerberger15

Cite as: P-240322.1

• Combinatorics

### 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.

Acta Arithmetica 96, 279-302, 2000

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

Journal of Complexity, 477-483, 2004

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

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.

Journal of Complexity 75 (101713), 2023