Random-Order Discrepancy Bounds for Lattice Point Sets

Definitions and mathematical statement

Requested bound, in the curated statement. Prove for shifted lattice point sets $M_n\subset[0,1)^d$ a star-discrepancy bound $\operatorname{disc}_\infty(M_n)\le C\sqrt{d/n}$, or a comparably sharp bound of the same order as the probabilistic bound for unrestricted $n$-point sets. For an $n$-point set $M$, define its normalized anchored discrepancy by\[D_M(t)=\frac1n\#(M\cap[0,t_1)\times\cdots\times[0,t_d))-\prod_{j=1}^dt_j,\qquad \operatorname{disc}_\infty(M)=\sup_{t\in[0,1]^d}|D_M(t)|.\] The substantive existence interpretation of the displayed target is: there is an absolute constant $C>0$ such that, for every positive integer $d$ and $n$, an admissible shifted lattice point set $M_n$ of size $n$ can be selected with this bound. It is not a bound for every lattice and every shift; independence of $C$ from $d,n$ is essential to the proposed dimension dependence.

One conventional lattice model is $M_n=(H+\Delta)\bmod{\mathbb{Z}}^d$, represented in $[0,1)^d$, where $H\le{\mathbb{R}}^d/{\mathbb{Z}}^d$ is a finite subgroup of order $n$ and $\Delta\in{\mathbb{R}}^d/{\mathbb{Z}}^d$. Rank-one rules are the special case $M_n=\{\{kz/n+\Delta\}:0\le k<n\}$, with $z\in{\mathbb{Z}}^d$ of order $n$ modulo $n$; braces denote componentwise fractional parts. The source does not state whether all lattice rules, only rank-one rules, or a narrower class such as Korobov rules is intended, nor the quantifier or distribution on shifts. These are conditional models, not silently selected hypotheses.

Formulation discrepancy. The original prose instead asks for an upper bound for $n$-point lattice sets of the same order as the known expected $L^p$ discrepancy bound for random point sets. For finite $p$, $\|D_M\|_{L^p([0,1]^d)}$ differs from the star discrepancy $\|D_M\|_\infty$. The record does not give $p$, its parameter range, the random model, or whether expectation means expected norm or a moment of that norm. Consequently the original $L^p$-benchmark request and the curated star-discrepancy request are both preserved and are not asserted equivalent. The phrase comparably sharp also needs a specified dependence on $d,n,p$.

The supplied triage dated 2026-08-21 labels the lattice question open, reporting that unrestricted point sets attain the square-root dimension bound while located lattice constructions have weaker dimension dependence. This is a dated curation assessment; it neither removes the formulation discrepancy nor independently verifies a current optimal bound.

Short English statement

Seek lattice-based point sets with discrepancy matching the random-point benchmark, in particular the curated target $C\sqrt{d/n}$ for star discrepancy. The original text refers instead to expected $L^p$ discrepancy, and the permitted lattice rules and shift quantifiers remain unspecified.

Sources

• Local UnsolvedMath registry, permanent ID 30000053, code catalogue entry; Random-Order Discrepancy Bounds for Lattice Point Sets, Oberwolfach Reports Open Problems.
• Discrepancy Theory and Its Applications (2004), Oberwolfach Reports, DOI 10.4171/owr/2004/13, pp. 673--722. https://doi.org/10.4171/owr/2004/13. Proposed year 2004; no proposer named.
• Supplied literature label Korobov lattice discrepancy: https://arxiv.org/abs/2601.16571.
• Supplied literature label OWR 13/2004: https://doi.org/10.4171/OWR/2004/13.
• Literature triage checked 2026-08-21, status open; record updated 2026-09-16. The registry labels the statement corrected_verified and reports checking the official report, but that check is not independently verified here.