The inverse of the star-discrepancy depends linearly on the dimension (Q4522902)

Let \(\text{disc}_\infty^* (\underline{t}_1,\dots, \underline{t}_n)\) denote the star-discrepancy of an \(n\)-element point set \(\omega\equiv \{\underline{t}_1,\dots, \underline{t}_n\} \subseteq [0,1]^d\) and let \(\text{disc}_\infty^* (n,d)= \inf_\omega \text{disc}_\infty^* (\underline{t}_1,\dots, \underline{t}_n)\). In the classical theory of irregularities of distribution various upper bounds for \(\text{disc}_\infty^* (n,d)\) are known for fixed \(d\). For instance, Roth's bound \(\text{disc}_\infty^* (n,d)= O(N^{-1} (\log)^{\frac{d-1}{2}})\) [with an implied \(O\)-constant depending on \(d\)] or R. Baker's refinement of Roth's bound. In the present paper the authors consider \(n\) and \(d\) as variables and prove the remarkable and very interesting upper bound \[ \text{disc}_\infty^* (n,d)\leq cd^{1/2} n^{-1/2} \quad\text{for all }n,d= 1,2,\dots, \] with an unknown multiplicative factor \(c\). Furthermore it is shown that the dependence on \(d\) cannot be improved. The proof follows from deep results of the theory of empirical processes. In particular, a result of Talagrand (1994) is used in combination with a result of \textit{D. Haussler} [J. Comb. Theory, Ser. A 69, 217-232 (1995; Zbl 0818.60005)] and some facts on the Vapnik-Cervonenkis dimension. Of course, the proof is non-constructive since it is probabilistic. Furthermore, the authors establish an explicit value for the constant \(c\) and obtain extensions to the \(L^p\)-discrepancy.