Sharp Multidimensional Star-Discrepancy Asymptotics

Sharp Multidimensional Star-Discrepancy Asymptotics

Definitions and mathematical statement

For an $N$-point set $P\subset[0,1)^d$, its unnormalized star discrepancy is \[ D^*(P)=\sup_{x\in[0,1]^d} \left|\#\left(P\cap\prod_{j=1}^d[0,x_j)\right)-N\prod_{j=1}^dx_j\right|. \] Let $\Delta_d(N)=\inf_{|P|=N}D^*(P)$. For every fixed $d\ge3$, determine a function $f_d(N)$ for which $c_df_d(N)\le\Delta_d(N)\le C_df_d(N)$ for all sufficiently large $N$, with positive constants depending only on $d$. The boxes are anchored at the origin and half-open. This convention omits the factor $1/N$ used in normalized discrepancy, so any proposed asymptotic must match this normalization. The dimension is fixed while the number of points grows.

Formulation and concept references: [S1].

Short English statement

How small can the worst counting error in origin-anchored boxes be for an optimally placed $N$-point set in each fixed dimension at least three?

Research attempt

Normalization and the unresolved comparison.

The discrepancy here is the counting error itself. We write \[ D_P(x)=\sum_{p\in P}\mathbf1_{\{p_j<x_j\ \forall j\}} -N\prod_{j=1}^dx_j. \] The primary source [S1, Section 1.1] uses this normalization and explains the gap between known supremum-norm estimates in dimension at least three. Results on inverse discrepancy when dimension varies ask a different asymptotic question. A normalized discrepancy bound must be multiplied by $N$ before comparison with this entry.

We give an orthogonal-function lower bound with explicit constants, an elementary existence upper bound, exact finite evaluation rules, and a product-grid stress test. The bounds proved here do not match; their remaining gap is stated quantitatively rather than hidden in the phrase that the points are uniformly distributed.

An elementary one-dimensional obstruction.

In dimension one, order the points $p_1<\cdots<p_N$. At $x=p_j$ the half-open counting function has value $j-1$, while its limit from the right is $j$. Thus the discrepancy has two one-sided values whose difference is one. At least one has absolute value at least $1/2$, giving $D^*(P)\geq1/2$. The midpoint set $p_j=(j-1/2)/N$ attains this value, including both one-sided limits. Hence $\Delta_1(N)=1/2$ in the unnormalized convention.

Projection onto any coordinate gives the same lower bound in higher dimensions, since the remaining box coordinates can be set equal to one. Much stronger growth is forced by multiscale geometry, as the following complete argument shows.

Dyadic Haar functions and empty rectangles.

For a dyadic interval $I=[a,a+\ell)$, let $h_I$ be minus one on its left half, plus one on its right half, and zero outside $I$. Then \[ \int h_I=0,\qquad \|h_I\|_2^2=\ell,\qquad \int_0^1 xh_I(x)\,dx=\ell^2/4. \tag{368.1} \] For a dyadic rectangle $R=I_1\times\cdots\times I_d$, set $h_R(x)=\prod_jh_{I_j}(x_j)$. Its squared norm is $|R|$.

Suppose the interior of $R$ contains no point of $P$. For one point $p$, its contribution to $\langle D_P,h_R\rangle$ factors into $d$ integrals of the form $\int_{I_j}\mathbf1_{p_j<x_j}h_{I_j}(x_j)\,dx_j$. Unless every $p_j$ is strictly inside $I_j$, one factor vanishes: the indicator is either zero or constant one almost everywhere on that interval. Points on its endpoints cause no exception. Thus all point contributions vanish for an empty-interior rectangle. The volume term and $368.1$ give exactly \[ \langle D_P,h_R\rangle=-\frac{N|R|^2}{4^d}. \tag{368.2} \] The sign is irrelevant for the norm estimate but fixes the convention for checking the calculation.

Choose an integer $m$ with $2N\leq2^m<4N$. For each vector of nonnegative integers $r=(r_1,\ldots,r_d)$ with $\sum_jr_j=m$, the rectangles with side lengths $2^{-r_j}$ partition the unit cube into $2^m$ pieces. At most $N$ have an interior point. Hence at least $2^m-N\geq2^{m-1}$ are empty in the required sense.

All Haar functions selected this way, across all shapes $r$, are orthogonal. In one dimension, two distinct dyadic Haar functions have disjoint supports or the smaller support lies in a half on which the larger is constant, and the smaller has mean zero. Taking tensor products proves orthogonality in $d$ dimensions as soon as the rectangles differ in some coordinate interval.

A complete logarithmic lower bound.

Bessel's inequality applied to the normalized empty-rectangle Haar functions gives \[ \|D_P\|_2^2 \geq\sum_{r_1+\cdots+r_d=m}\ \sum_{R\text{ empty of shape }r} \frac{|\langle D_P,h_R\rangle|^2}{|R|}. \] Every summand is $N^2 2^{-3m}/16^d$, and there are at least $2^{m-1}$ per shape. The number of shapes is $\binom{m+d-1}{d-1}$, by the elementary stars-and-bars count. Using $2^m<4N$ yields \[ \|D_P\|_2^2\geq \frac1{32\,16^d}\binom{m+d-1}{d-1}. \tag{368.3} \] Since the cube has volume one, $\|D_P\|_\infty\geq\|D_P\|_2$. Consequently, for fixed $d$ and $N\geq2$, \[ D^*(P)\geq c_d(\log N)^{(d-1)/2}. \tag{368.4} \] The use of an essential supremum in the norm does not weaken this conclusion for the stated supremum over boxes. The latter is at least the former. No assumption that the points avoid dyadic boundaries was made; the empty-interior argument handles them.

This is the classical orthogonal-function mechanism, reproduced here rather than merely quoted. It does not give the conjecturally sharp supremum exponent. The square root in Bessel's inequality combines the contributions of the different rectangle shapes in an $\ell^2$ fashion. Replacing that square root by an ordinary sum would require a new estimate and is not an algebraic simplification.

A direct existence upper bound for every number of points.

Let $X_1,\ldots,X_N$ be independent uniform points in the cube. Take the grid $G=\{0,1/N,\ldots,1\}^d$. For each $x\in G$, the box count is a sum of independent Bernoulli variables with mean $N\prod_jx_j$. The elementary exponential-moment estimate for a Bernoulli variable gives Hoeffding's bound \[ \mathbb P(|D_P(x)|>t)\leq2e^{-2t^2/N}. \tag{368.5} \] One derivation centers each summand, bounds its moment generating function by $e^{\lambda^2/8}$, multiplies by independence and optimizes Markov's inequality at $\lambda=4t/N$; the lower tail uses $-\lambda$.

The union bound over $(N+1)^d$ corners shows that with positive probability all grid discrepancies have absolute value at most \[ t_N=\sqrt{\frac N2\left(d\log(N+1)+\log4\right)}. \tag{368.6} \] For an arbitrary $x$, let $x^-$ and $x^+$ be its coordinatewise lower and upper grid neighbors. Box counts are monotone, and \[ 0\leq\prod_jx_j^+-\prod_jx_j^-\leq\sum_j(x_j^+-x_j^-)\leq d/N. \] Sandwiching the count and subtracting the true volume therefore gives $|D_P(x)|\leq t_N+d$. Random points are distinct and lie in $[0,1)^d$ almost surely. We have proved, for every $N$, \[ \Delta_d(N)\leq \sqrt{\frac N2\left(d\log(N+1)+\log4\right)}+d. \tag{368.7} \] This bound is deliberately elementary and is weaker than the specialized low-discrepancy constructions discussed in [S1]. It is not presented as the best known upper bound. Its role here is to supply a complete existence argument with the same normalization as the lower bound.

Why a regular product grid is not automatically near-optimal.

For $N=q^d$, take the product of one-dimensional midpoint grids. Let $a_j(x_j)$ be the number of coordinate midpoints below $x_j$. Then $|a_j-qx_j|\leq1/2$, interpreted by the appropriate one-sided limit at a midpoint, and both $a_j$ and $qx_j$ lie in $[0,q]$. A product telescoping identity gives \[ \left|\prod_ja_j-q^d\prod_jx_j\right| \leq\frac d2 q^{d-1}. \tag{368.8} \] There is also a matching obstruction in order: choose $x_1$ just above the first midpoint and set the other coordinates to one. The discrepancy tends to $q^{d-1}/2$. Thus these attractive geometric grids have discrepancy of order $N^{1-1/d}$ for fixed $d$, far above logarithmic scales. Small nearest-neighbor spacing and visual regularity do not certify the anchored-box objective.

An exact finite formula respecting half-open boxes.

For computation, let $\Gamma_j=\{0,1\}\cup\{p_j:p\in P\}$ and $\Gamma=\prod_j\Gamma_j$. At each corner define \[ A(x)=\#\{p:p_j<x_j\ \forall j\},\qquad \overline A(x)=\#\{p:p_j\leq x_j\ \forall j\}. \] Then the exact value is \[ D^*(P)=\max_{x\in\Gamma} \max\left\{N\prod_jx_j-A(x),\ \overline A(x)-N\prod_jx_j\right\}. \tag{368.9} \] To prove it, inside any open cell cut out by the coordinate grids the point count is constant, while the volume product is monotone in every coordinate. The most positive and most negative errors are therefore attained as one-sided limits at its corners. At an upper limiting corner, the unchanged half-open count is $A$; at a lower limiting corner, approaching from above includes equality points and gives $\overline A$. Corners at zero are obtained by positive limiting coordinates, and no data point has coordinate one, so the boundary at one causes no exception. Conversely each term in $368.9$ is an actual value or such a one-sided limiting value of the discrepancy, and hence is bounded by its supremum.

Ties among point coordinates are handled by counting all equality points together. Evaluating only the half-open counts at data corners misses the second family of limits and can underestimate the discrepancy. Formula $368.9$ provides a finite certificate for one supplied point set, not a proof that it minimizes discrepancy among all real configurations.

What would strengthen the lower-bound route.

The Haar coefficients in $368.2$ live on many different rectangle shapes of the same volume. They are orthogonal, but their pointwise signs overlap in complicated ways. One may attempt a nonlinear test function built from products of shape sums, paired against $D_P$. To obtain a sharper $L^\infty$ lower bound, its $L^1$ norm must be controlled while its correlation with the discrepancy accumulates more efficiently than $368.3$. Cross terms from rectangles sharing coordinates are then essential. Ignoring those terms is not justified by orthogonality, which controls pairwise integrals rather than all products arising in such a construction.

The source discusses stronger specialized lower bounds and the small-ball approach; this attempt does not reproduce those results or turn them into a sharp all-dimensional order. The elementary proof isolates why simple square-function information alone stops at the exponent in $368.4$.

Diagnostics and outcome.

The script evaluates $368.9$ exactly for rational test point sets, checks the midpoint-grid one-dimensional value and the product-grid obstruction, and verifies the empty-rectangle Haar integral by piecewise polynomial integration. These tests audit endpoint conventions and constants. Sampling random boxes alone would not be an exact supremum computation, so it is not used as a certificate.

The proved lower and upper bounds, $368.4$ and $368.7$, do not match. The first unresolved step in the proposed harmonic route is a uniform nonlinear combination of shape contributions strong enough to reach a matching supremum estimate without uncontrolled cross terms. Determining $f_d(N)$ in the printed two-sided sense remains unresolved by this attempt.

Sources

• S1 Dmitriy Bilyk, Research Statement, Section 1.1. https://www-users.cse.umn.edu/~dbilyk/bilyk-research.pdf. Formulation source.