🔢 mathematics

Extreme $L_p$ discrepancy, numerical integration and the curse of dimensionality

This paper establishes that extreme $L_p$ discrepancy suffers from the curse of dimensionality for all $p \in (1,\infty)$ by identifying a dual integration problem where the worst-case error exactly matches the discrepancy, while noting that the problem remains tractable for $p=\infty$ and open for $p=1$ .

Original authors: Erich Novak, Friedrich Pillichshammer

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Erich Novak, Friedrich Pillichshammer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Trying to Spread Out Points Evenly

Imagine you are a party planner trying to scatter $N$ guests (points) evenly across a square dance floor (a $d$ -dimensional cube). Your goal is to make sure that no matter which shape you draw on the floor—a small circle, a long rectangle, or a weirdly shaped blob—the number of guests inside that shape matches the percentage of the floor the shape covers.

If you have 10% of the floor covered by a shape, you want exactly 10% of your guests inside it. If the distribution is messy, some shapes will have too many guests, and others too few.

In math, this messiness is called discrepancy. The lower the discrepancy, the better your party planning.

The Two Main Rules of the Game

The paper looks at two different ways to measure how "messy" the party is:

The "Star" Rule (The Corner Check): You only check shapes that start at the bottom-left corner of the floor and stretch out to some point $(x, y)$ . It's like checking how well the guests fill up the bottom-left corner.
The "Extreme" Rule (The Anywhere Check): You check every possible rectangle you can draw on the floor, no matter where it is. It could be in the middle, the top-right, or a tiny sliver in the corner. This is a much harder test because there are infinitely more shapes to check.

The Big Discovery: The "Dual" Problem

The authors found a clever trick. They realized that measuring how messy the party is (the Extreme Discrepancy) is mathematically identical to a different problem: Numerical Integration.

Think of numerical integration as trying to calculate the total amount of "stuff" (like the volume of a cloud or the total heat in a room) by taking a few sample measurements.

The Analogy: Imagine you are trying to guess the total weight of a giant, invisible cloud floating over your dance floor. You can't weigh the whole thing at once, so you send $N$ drones (your points) to take samples.
The Connection: The paper proves that the error you make when guessing the cloud's weight using these specific drones is exactly the same number as the "messiness" of how the drones are scattered on the floor.
Why this matters: It means if you want to solve the "cloud weight" problem perfectly, you have to solve the "party scattering" problem perfectly. They are two sides of the same coin.

The "Curse of Dimensionality": The Room Gets Too Big

The most famous part of the paper is about what happens when you add more dimensions.

2D: A dance floor (flat). Easy to scatter guests.
3D: A room (with height). Still okay.
100D: A hyper-room.

The paper asks: As the number of dimensions ( $d$ ) grows, how many guests (points) do you need to keep the messiness low?

The answer is bad news for high dimensions. The authors prove that for most types of "messiness" (specifically for $p$ between 1 and infinity), the number of points you need grows exponentially as the dimensions increase.

The Analogy:
Imagine you are trying to find a specific grain of sand on a beach.

In 1 dimension (a line), you might need 100 grains to be sure you didn't miss a spot.
In 2 dimensions (a square beach), you might need 10,000 grains.
In 10 dimensions, you might need more grains than there are atoms in the universe.

This is the Curse of Dimensionality. The paper proves that for the "Extreme" rule (checking every possible rectangle), this curse is real and unavoidable for almost all cases. You simply cannot scatter points evenly enough in high-dimensional space without using an impossible number of points.

What About the Exceptions?

The paper notes two special cases:

The "Infinity" Case ( $p = \infty$ ): If you only care about the single worst shape (the one with the biggest error), you can solve it efficiently even in high dimensions. It's like saying, "I don't care if 99% of the shapes are messy, as long as the worst one isn't too bad." This is known to be solvable.
The "One" Case ( $p = 1$ ): The authors admit they don't know the answer for this specific type of average messiness yet. It remains a mystery.

Summary of the Conclusion

The Duality: Scattering points evenly (Discrepancy) and guessing the total weight of a cloud (Integration) are the exact same problem mathematically.
The Curse: If you try to scatter points evenly in high-dimensional space using the "Extreme" rule (checking all rectangles), you will hit a wall. The number of points required explodes exponentially as the dimensions grow.
The Implication: For many high-dimensional problems (like complex simulations in physics or finance), simply throwing more random points at the problem won't work if you need that specific type of evenness. You need smarter methods, or you accept that the problem is too hard to solve perfectly with current methods.

In short: The paper proves that in high-dimensional worlds, keeping things perfectly even is mathematically impossible without an astronomical amount of effort, unless you change the rules of the game.

Technical Summary: Extreme $L^p$ Discrepancy, Numerical Integration, and the Curse of Dimensionality

Problem Statement
The paper investigates the extreme $L^p$ discrepancy, a quantitative measure of the irregularity of distribution for finite point sets within the $d$ -dimensional unit cube $[0, 1)^d$ . Unlike the classical "star" discrepancy, which restricts test sets to anchored hypercubes of the form $[0, b)$ , the extreme discrepancy utilizes the class of all hypercubes $[a, b) \subseteq [0, 1)^d$ .

While the behavior of the inverse star discrepancy (the minimal number of points required to achieve a given error) is well-understood—exhibiting tractability for $p=\infty$ and the curse of dimensionality for $p \in (1, \infty)$ —the behavior of the extreme discrepancy for general $p$ remains largely open. Specifically, prior to this work, there was no known dual integration problem establishing a "discrepancy-integration duality" for the extreme case, and the dependence of the inverse extreme discrepancy on the dimension $d$ was unknown for $p \notin \{2, \infty\}$ .

Methodology
The authors employ a functional analytic approach to establish a duality between discrepancy and numerical integration:

Dual Integration Problem: The authors define a specific function space $F_{d,q}$ (where $q$ is the Hölder conjugate of $p$ ) using a representation via box indicators. Functions in this space are generated by an operator $T_d$ acting on $L^q(D_d)$ , where $D_d$ is the domain of hypercubes. The space is equipped with a "box-norm" $\|\cdot\|_{F_{d,q}, \text{box}}$ .
Discrepancy-Integration Duality: They prove that the worst-case error of a linear integration rule (including Quasi-Monte Carlo algorithms) on this space $F_{d,q}$ is exactly equal to the generalized extreme $L^p$ discrepancy of the underlying nodes and weights.
Initial Error Analysis: The authors explicitly construct a "worst-case function" $h_d$ for the zero integration rule (using no sample points). This function allows for the precise calculation of the initial error $e(0; F_{d,q})$ , which serves as the baseline for measuring information complexity.
Spline Interpolation for Lower Bounds: To prove the curse of dimensionality, the authors adapt a method involving spline interpolation. They construct a univariate worst-case function $h_1$ and associated "spline" functions $s_y$ that interpolate the values of $h_1$ at specific nodes. By analyzing the ratio of the integrals and norms of these spline functions relative to the worst-case function, they derive constants $A_p$ and $B_p$ that are strictly less than 1.

Key Contributions and Results

Establishment of Duality: The primary theoretical contribution is Theorem 2, which rigorously proves that for Hölder conjugates $p$ and $q$ , the worst-case error of integrating functions in $F_{d,q}$ using arbitrary linear rules equals the generalized extreme $L^p$ discrepancy. This resolves the open question regarding the existence of a corresponding integration problem for extreme discrepancy.
Curse of Dimensionality for $p \in (1, \infty)$ : The paper proves Theorem 4 and Theorem 5, demonstrating that the inverse extreme $L^p$ $L^{p}$ discrepancy (and equivalently, the information complexity of the dual integration problem) suffers from the curse of dimensionality for all $p \in (1, \infty)$ $p \in (1, \infty)$ .
- Specifically, for non-negative weights (which includes QMC rules), the minimal number of points $N$ required to reduce the initial error by a factor $\varepsilon$ satisfies:
  $N \ge C_p^d (1 - 2\varepsilon)$
  where $C_p > 1$ is a constant depending on $p$ . This implies that the required number of points grows exponentially with the dimension $d$ .
Explicit Constants: The authors provide explicit formulas for the constant $C_p$ for integer values $p \in \{2, \dots, 7\}$ and indicate that suitable values can be determined numerically for other $p$ .
Extension to Mixed Sobolev Norms: The results are shown to hold not only for the box-norm but also for the mixed Sobolev norm, generalizing previous results known only for $p=2$ .

Significance and Claims
The paper claims to resolve the open problem regarding the tractability of the extreme $L^p$ discrepancy for the range $p \in (1, \infty)$ . By identifying the correct dual integration problem and the associated function space, the authors demonstrate that, contrary to the star discrepancy case where $p=\infty$ is tractable, the extreme discrepancy is intractable for all finite $p > 1$ .

The authors explicitly note that the case $p=1$ remains an open problem. Furthermore, they clarify that their proof of the curse of dimensionality currently applies to linear rules with non-negative weights; while this covers QMC algorithms, the behavior for general signed weights in the extreme case is not fully settled by this specific proof method, though the duality holds generally.

The work underscores the fundamental difficulty of high-dimensional integration when the error is measured by the irregularity of distribution over arbitrary hypercubes, distinguishing it sharply from the anchored hypercube case.