Optimal star-discrepancy lower bound for infinite sequences
Fix an integer $d \ge 2$ and a sequence $x_1, x_2, \ldots$ in $[0,1)^d$. The star discrepancy of its first $N$ points is $$D_N^* = \sup_{t \in [0,1]^d} \left| \frac{1}{N} \#\{ n \le N : x_n \in [0,t) \} - \prod_{j=1}^d t_j \right|, \qquad [0,t) = \prod_{j=1}^d [0, t_j).$$ By Roth's theorem, every such sequence has $\limsup_{N \to \infty} N D_N^* / (\log N)^{d/2} > 0$; from the work of Bilyk, Lacey and Vagharshakyan, the exponent $d/2$ can be raised to $d/2 + \eta_d$ for some $\eta_d > 0$. Schmidt proved the inequality below for sequences in $[0,1)$. Halton's sequences (with pairwise coprime bases) have $D_N^* = O\bigl((\log N)^d / N\bigr)$, and Levin proved that they attain this order: $\limsup_{N \to \infty} N D_N^* / (\log N)^d > 0$.
Problem. Does every such sequence satisfy $$\limsup_{N \to \infty} \frac{N D_N^*}{(\log N)^d} > 0,$$ that is, is there a constant $c > 0$, which may depend on the sequence and on $d$, such that $D_N^* \ge c (\log N)^d / N$ for infinitely many $N$?
Source: A well-known conjecture of the theory of irregularities of distribution; see Beck and Chen (1987), p. 283, as cited by Levin (2016), (3), and Larcher (2014). Stated for d ≥ 2 by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NT — Number Theory
- Secondary
- NA
- Keywords
- AIM Open Applied Problems, discrepancy, low-discrepancy sequences, quasi-Monte Carlo methods
References
@book{beck1987,
author = {Beck, J{\'o}zsef and Chen, William W. L.},
title = {Irregularities of Distribution},
series = {Cambridge Tracts in Mathematics},
volume = {89},
publisher = {Cambridge University Press},
address = {Cambridge},
year = {1987},
doi = {10.1017/CBO9780511565984},
}
@article{levin2016,
author = {Levin, Mordechay B.},
title = {On the lower bound of the discrepancy of {H}alton's sequence {I}},
journal = {C. R. Math. Acad. Sci. Paris},
volume = {354},
number = {5},
year = {2016},
pages = {445--448},
doi = {10.1016/j.crma.2016.02.003},
eprint = {1412.8705},
archivePrefix = {arXiv},
}
@incollection{larcher2014,
author = {Larcher, Gerhard},
title = {Discrepancy estimates for sequences: new results and open problems},
booktitle = {Uniform Distribution and Quasi-{M}onte {C}arlo Methods},
editor = {Kritzer, Peter and Niederreiter, Harald and Pillichshammer, Friedrich and Winterhof, Arne},
series = {Radon Series on Computational and Applied Mathematics},
volume = {15},
publisher = {De Gruyter},
address = {Berlin},
year = {2014},
pages = {171--190},
doi = {10.1515/9783110317930.171},
eprint = {1407.2380},
archivePrefix = {arXiv},
}
@article{roth1954,
author = {Roth, K. F.},
title = {On irregularities of distribution},
journal = {Mathematika},
volume = {1},
number = {2},
year = {1954},
pages = {73--79},
doi = {10.1112/S0025579300000541},
}
@article{bilyk2008,
author = {Bilyk, Dmitriy and Lacey, Michael T. and Vagharshakyan, Armen},
title = {On the small ball inequality in all dimensions},
journal = {J. Funct. Anal.},
volume = {254},
number = {9},
year = {2008},
pages = {2470--2502},
doi = {10.1016/j.jfa.2007.09.010},
}
@article{schmidt1972,
author = {Schmidt, Wolfgang M.},
title = {Irregularities of distribution, {VII}},
journal = {Acta Arith.},
volume = {21},
year = {1972},
pages = {45--50},
doi = {10.4064/aa-21-1-45-50},
}
@article{halton1960,
author = {Halton, J. H.},
title = {On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals},
journal = {Numer. Math.},
volume = {2},
number = {1},
year = {1960},
pages = {84--90},
doi = {10.1007/BF01386213},
}
@misc{aim-star-discrepancy-sequence-lower-bound,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Optimal star-discrepancy lower bound for infinite sequences}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/536-star-discrepancy-sequence-lower-bound.md},
note = {Entry 536 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00389, "Optimal star-discrepancy lower bound for infinite sequences", clopen.solutions.