{
  "id": "2303.01787",
  "version": "v2",
  "published": "2023-03-03T08:53:29.000Z",
  "updated": "2023-06-12T08:03:33.000Z",
  "title": "The curse of dimensionality for the $L_p$-discrepancy with finite $p$",
  "authors": [
    "Erich Novak",
    "Friedrich Pillichshammer"
  ],
  "doi": "10.1016/j.jco.2023.101769",
  "categories": [
    "math.NA",
    "cs.NA",
    "math.NT"
  ],
  "abstract": "The $L_p$-discrepancy is a quantitative measure for the irregularity of distribution of an $N$-element point set in the $d$-dimensional unit cube, which is closely related to the worst-case error of quasi-Monte Carlo algorithms for numerical integration. Its inverse for dimension $d$ and error threshold $\\varepsilon \\in (0,1)$ is the minimal number of points in $[0,1)^d$ such that the minimal normalized $L_p$-discrepancy is less or equal $\\varepsilon$. It is well known, that the inverse of $L_2$-discrepancy grows exponentially fast with the dimension $d$, i.e., we have the curse of dimensionality, whereas the inverse of $L_{\\infty}$-discrepancy depends exactly linearly on $d$. The behavior of inverse of $L_p$-discrepancy for general $p \\not\\in \\{2,\\infty\\}$ has been an open problem for many years. In this paper we show that the $L_p$-discrepancy suffers from the curse of dimensionality for all $p$ in $(1,2]$ which are of the form $p=2 \\ell/(2 \\ell -1)$ with $\\ell \\in \\mathbb{N}$. This result follows from a more general result that we show for the worst-case error of numerical integration in an anchored Sobolev space with anchor 0 of once differentiable functions in each variable whose first derivative has finite $L_q$-norm, where $q$ is an even positive integer satisfying $1/p+1/q=1$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2023-06-12T08:03:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11K38",
      "65C05",
      "65Y20"
    ],
    "keywords": [
      "dimensionality",
      "worst-case error",
      "element point set",
      "numerical integration",
      "dimensional unit cube"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Elsevier"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}