The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914368974749696 |
|---|---|
| author | Dick, Josef Pillichshammer, Friedrich |
| author_facet | Dick, Josef Pillichshammer, Friedrich |
| contents | The star discrepancy is a quantitative measure of the uniformity of a point set in the unit cube. A central quantity of interest is the inverse of the star discrepancy, $N(\varepsilon, s)$, defined as the minimum number of points required to achieve a star discrepancy of at most~$\varepsilon$ in dimension~$s$. It is known that $N(\varepsilon, s)$ depends only linearly on the dimension~$s$. All known proofs of this result are non-constructive. Finding explicit point set constructions that achieve this optimal linear dependence on the dimension remains a major open problem.
In this paper, we make progress on this question by analyzing point sets constructed from a multiset union of digitally shifted Korobov polynomial lattice point sets. Specifically, we show the following two results. A union of randomly generated Korobov polynomial lattice point sets shifted by a random digital shift of depth $m$ can achieve a star discrepancy whose inverse depends only linearly on $s$. The second result shows that a union of all Korobov polynomial lattice point sets, each shifted by a different random digital shift, achieves the same star discrepancy bound. While our proof relies on a concentration result (Bennett's inequality) and is therefore non-constructive, it significantly reduces the search space for such point sets from a continuum of possibilities to a finite set of candidates, marking a step towards a fully explicit construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15877 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension Dick, Josef Pillichshammer, Friedrich Numerical Analysis Number Theory 11K38, 65C05, 65Y20 The star discrepancy is a quantitative measure of the uniformity of a point set in the unit cube. A central quantity of interest is the inverse of the star discrepancy, $N(\varepsilon, s)$, defined as the minimum number of points required to achieve a star discrepancy of at most~$\varepsilon$ in dimension~$s$. It is known that $N(\varepsilon, s)$ depends only linearly on the dimension~$s$. All known proofs of this result are non-constructive. Finding explicit point set constructions that achieve this optimal linear dependence on the dimension remains a major open problem. In this paper, we make progress on this question by analyzing point sets constructed from a multiset union of digitally shifted Korobov polynomial lattice point sets. Specifically, we show the following two results. A union of randomly generated Korobov polynomial lattice point sets shifted by a random digital shift of depth $m$ can achieve a star discrepancy whose inverse depends only linearly on $s$. The second result shows that a union of all Korobov polynomial lattice point sets, each shifted by a different random digital shift, achieves the same star discrepancy bound. While our proof relies on a concentration result (Bennett's inequality) and is therefore non-constructive, it significantly reduces the search space for such point sets from a continuum of possibilities to a finite set of candidates, marking a step towards a fully explicit construction. |
| title | The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension |
| topic | Numerical Analysis Number Theory 11K38, 65C05, 65Y20 |
| url | https://arxiv.org/abs/2509.15877 |