# Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

In one dimension d=1 an equally-spaced set of N points in [0,1) has the lowest possible (star) discrepancy D=0.5/N. Unfortunately, I found only asymptotic bounds for other dimensions (e.g. acc. to Schmidt and Roth). These best-known lower bounds are so bad (also they are known to be "tight"), that for moderate N and d (like N=10..1000 and d=2) they can be off by a factor of 10 or more.

I would like to have a table D vs N and d (or formulas) for comparing D for the best-known low-discrepancy sets, e.g. against regular grids (for which an exact formula exists) or random sets (here I also found no formula, and simply creating a rnd set and calculating D is also extremely time-consuming.

Actually, I am very suprised because at least for d=2 a Fibonacci set delivers a very low, almost perfect discrepancy, so very low errors for Monte-Carlo integration.

• If you are also interested in low star-discrepancy sets, I can provide some information. But perhaps this is not your focus... – Joseph O'Rourke Sep 1 '17 at 1:29

As I understand it, you might be interested in a quantity called the inverse of the star-discrepancy. Given dimension $d$ and some $\varepsilon > 0$, the inverse of the star-discrepancy $n(d,\varepsilon)$ is the smallest possible cardinality of a point set in $[0,1]^d$ which has discrepancy at most $\varepsilon$. It is know that (somewhat surprisingly) the inverse of the star-discrepancy depends linearly on the dimension (and not exponentially, as some suspected). More precisely, one has $$c_{abs} d \varepsilon^{-1} \leq n(d,\varepsilon) \leq c_{abs} d \varepsilon^{-2}.$$ The optimal dependence on $\varepsilon$ is an open problem. An admissible value for the constant on the right-hand side is 10.

See for example

Heinrich, S., Novak, E., Wasilkowski, G. and Woźniakowski, H. The inverse of the star-discrepancy depends linearly on the dimension. Acta Arith. 96 (2001), no. 3, 279–302.

and

Aistleitner, Christoph, Covering numbers, dyadic chaining and discrepancy. J. Complexity 27 (2011), no. 6, 531–540.

The sort of question you ask (considering the influence of dimensionality on computational complexity) is called tractability theory. In the context of discrepancy, see volume II of the book of Novak and Woźniakowski: Tractability of multivariate problems.

This may not be what the OP seeks, but the paper below contains quite a bit of detailed numberical tables for low star-discrepancy sets. Star discrepancy $d^*$ takes the supremum over rectangles that include the $(0,0)$ corner. The discrepancy $d$ is bounded between $d^*$ and (alas!) $4 d^*$ (in the plane). Doerr, Carola, and De Rainville. "Constructing low star discrepancy point sets with genetic algorithms." Proceedings 15th Conference on Genetic and Evolutionary Computation. ACM, 2013. (arXiv abs.)

• Thank you for these hints. I inspected these very good papers already. – user32038 Dec 12 '18 at 11:41