The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\) (Q6084392): Difference between revisions

The paper studies the \(L_p\)-discrepancy, where \(p\in [1,\infty]\), of point sets \(\mathcal{P}\) consisting of \(N\) points \(\boldsymbol{x}_1,\boldsymbol{x}_2,\ldots,\boldsymbol{x}_N\) in the \(d\)-dimensional unit cube \([0,1)^d\). The \(L_p\)-discrepancy is a measure of uniformity for such point sets. The lower the value of the \(L_p\)-discrepancy, the more uniform the distribution of the points in \([0,1)^d\). For \(d\in \mathbb{N}\) and \(\varepsilon \in (0,1)\), the inverse of the \(L_p\)-discrepancy is defined as the minimal cardinality \(N\) of a point set \(\mathcal{P}\) with an \(L_p\)-discrepancy of at most \(\varepsilon\). In the field of information-based complexity, one then considers the question of how the inverse of the \(L_p\)-discrepancy depends on the dimension \(d\). As it turns out, this behavior changes considerably with the value of \(p\). E.g., it is known that the inverse of the \(L_2\)-discrepancy grows exponentially fast with \(d\), i.e., it suffers from the curse of dimensionality. On the other hand the inverse of the \(L_\infty\)-discrepancy only grows linearly with \(d\). While the \(d\)-dependence of the inverse of the \(L_p\)-discrepancy is well known for the important cases when \(p=2\) and \(p=\infty\), the corresponding problem for \(p\not\in \{2,\infty\}\) has remained open for a long time. The paper's main result shows that the inverse of the \(L_p\)-discrepancy also suffers from the curse of dimensionality for any \(p\) of the form \(p=2\ell /(2\ell -1)\) with \(\ell\in\mathbb{N}\). The result is shown via a more general result for the worst case error of numerical integration in anchored Sobolev spaces.