🔢 mathematics

Tractability versus curse of dimensionality for geometric $L_p$ -discrepancies

This paper investigates the curse of dimensionality for various geometric $L_p$ -discrepancies by employing a unified discrepancy-integration duality framework to establish exponential information complexity under tensor-product assumptions, while also presenting new results on periodic discrepancies and summarizing the current research landscape with a comprehensive table of open questions.

Original authors: Erich Novak, Friedrich Pillichshammer

Published 2026-06-24

📖 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

Imagine you are trying to paint a giant, multi-dimensional wall with a perfect, even coat of white paint. In a simple 2D room, you can easily figure out where to place your brush strokes to make sure no spots are missed and no areas are too thick. But what if your "room" has 100 dimensions? Or 1,000?

This paper is about the mathematical challenge of evenly spreading points (like your brush strokes) in these high-dimensional spaces. The authors, Erich Novak and Friedrich Pillichshammer, investigate whether it's possible to do this efficiently or if the task becomes impossible as the number of dimensions grows.

Here is a breakdown of their findings using simple analogies:

1. The Goal: The "Perfect Grid"

In math, we often need to pick a set of points inside a cube (a box) to represent a whole space. We want these points to be distributed as uniformly as possible.

The Problem: If the points are clumped together in one corner, they are a bad representation.
The Measure: The authors use a tool called Discrepancy. Think of this as a "clumpiness score." A low score means the points are spread out perfectly; a high score means they are messy.

2. The Enemy: The "Curse of Dimensionality"

The paper asks a terrifying question: As we add more dimensions, does the number of points we need to keep the "clumpiness score" low explode?

The Curse: If you need 10 points for a 2D room, 100 for a 3D room, but 1,000,000 for a 10D room, and the number keeps doubling exponentially with every new dimension, you have hit the "Curse of Dimensionality." It's like trying to fill a room with sand, but every time you add a new dimension, the room suddenly becomes a billion times bigger, and you don't have enough sand.
Tractability: This is the "good news" scenario. It means the number of points needed grows slowly (like a polynomial), so we can actually solve the problem even in high dimensions.

3. The Secret Weapon: The "Mirror" Trick

The authors developed a clever way to prove that the "Curse" is real for many types of problems. They used a concept called Discrepancy–Integration Duality.

The Analogy: Imagine you want to know how unevenly your paint is spread (Discrepancy). Instead of measuring the paint directly, you look at a mirror reflection of the problem: Numerical Integration (calculating the total area under a curve).
The Magic: The paper shows that the "clumpiness" of your points is mathematically identical to the "error" you make when trying to calculate an area using those points.
Why it helps: It is often easier to prove that you cannot calculate an area accurately in high dimensions than it is to prove points are clumped. By proving the integration is impossible, they automatically prove the points are clumped.

4. The Results: Who Wins and Who Loses?

The authors tested several different ways of measuring "clumpiness" (called $L_p$ -discrepancies) and found a split verdict:

The Losers (Suffering from the Curse)

For most standard ways of measuring unevenness (specifically for $p$ values between 1 and infinity, but not including 1 or infinity), the Curse of Dimensionality is real.

The Scenario: If you try to spread points evenly in a high-dimensional space using these rules, you will need an astronomical number of points. It's like trying to find a needle in a haystack, but the haystack is growing exponentially every second.
Specifics: This applies to "Star," "Extreme," and "Periodic" discrepancies for most cases.

The Winners (Tractable)

There are a few special cases where we can win.

The $L_\infty$ Case: If you measure clumpiness by looking only at the worst single spot (the maximum error), you can actually solve it efficiently. The number of points needed grows slowly, even in high dimensions.
The Periodic Case: If you treat the space like a video game world where the edges wrap around (like Pac-Man), you can also solve it efficiently for the "worst spot" measurement.

The Mystery (The Open Question)

The paper highlights a big gap in our knowledge: The $L_1$ case.

The Analogy: We know the "average" clumpiness is bad (Curse), and we know the "worst spot" clumpiness is good (Tractable). But we don't know what happens if we measure the "total sum of all clumps."
The Verdict: The authors admit they don't know the answer yet. It remains a massive open question in mathematics.

Summary

The paper acts as a map for navigating high-dimensional spaces. It tells us:

Don't bother trying to evenly distribute points for most standard rules if you are in a high-dimensional world; the "Curse" makes it impossible.
You can succeed if you change the rules slightly (like looking only at the worst spot or using a "wrapping" space).
We still have a mystery regarding the "total sum" rule ( $L_1$ ), which the authors are challenging the math community to solve.

They didn't just guess these results; they built a unified "mirror" framework to prove them rigorously, turning a geometric problem into an integration problem to get the answers.

Technical Summary: Tractability versus Curse of Dimensionality for Geometric $L_p$ -Discrepancies

1. Problem Statement

The paper investigates the computational complexity of geometric $L_p$ -discrepancies in high dimensions. Specifically, it addresses the "curse of dimensionality" versus "tractability" for various notions of discrepancy, including anchored (star and centered), unanchored (extreme), and periodic discrepancies.

The central metric is the information complexity $N^{\bullet}_{\text{disc}}(\varepsilon, d)$ , defined as the minimal number of points $N$ required to reduce the initial discrepancy by a factor of $\varepsilon$ in dimension $d$ . The problem asks how this complexity grows as $d \to \infty$ and/or $\varepsilon \to 0$ .

Curse of Dimensionality: Occurs if $N^{\bullet}_{\text{disc}}(\varepsilon, d)$ grows at least exponentially in $d$ for a fixed $\varepsilon > 0$ .
Tractability: Occurs if the growth is sub-exponential (e.g., polynomial in $d$ and $\varepsilon^{-1}$ ).

The study considers three types of weights for the point sets: arbitrary real weights, non-negative weights ( $+$ ), and Quasi-Monte Carlo (QMC) weights ($qmc$).

2. Methodology

The authors employ a unified discrepancy–integration duality framework. This approach establishes an equivalence between the geometric discrepancy of a point set and the worst-case integration error of a linear quadrature rule in a specific normed function space.

2.1 Discrepancy–Integration Duality

For a given discrepancy $D_N(P, A)$ , the authors identify a Banach space of functions $F_d$ such that the worst-case error of a linear rule $Q_{P,A}$ in $F_d$ equals the discrepancy:
$e(Q_{P,A}; F_d) = D_N(P, A)$
This duality allows the translation of geometric discrepancy problems into integration problems, where tools from Information-Based Complexity (IBC) can be applied.

2.2 Lower Bound Method (The Curse of Dimensionality)

To prove the curse of dimensionality, the paper utilizes a general lower bound method (Theorem 1) based on tensor-product assumptions. The method requires:

Tensor-product structure: The norm of a product function is bounded by the product of the norms of its components.
Initial error factorization: The initial error in dimension $d$ is the $d$ -th power of the initial error in dimension 1.
Existence of specific functions: A "worst-case" function $h$ and a family of "spline-like" functions $s_y$ that satisfy specific integral and norm inequalities involving constants $A > 1$ and $B > 1$ .

If these conditions are met, the information complexity satisfies $N^+_{\text{int}}(\varepsilon, d) \ge C^d(1-2\varepsilon)$ for some $C > 1$ , proving the curse of dimensionality for non-negative weights.

3. Key Contributions and Results

3.1 Anchored and Quadrant Discrepancies

The paper analyzes $a$ -quadrant and $a$ -anchored discrepancies (which include star and centered discrepancies as special cases).

Duality: Theorem 3 establishes a duality between $a$ -quadrant $L_p$ -discrepancy and integration in the space $W^1_{a,q}$ (functions with vanishing value at anchor $a$ and derivatives in $L_q$ ).
Curse of Dimensionality:
- For $p \in (1, \infty)$ and $a \in \{0, 1\}$ (star discrepancy), the curse holds for non-negative weights.
- For $p \in [1, \infty)$ and $a \in (0, 1)$ , the curse holds.
- For $p = \infty$ and $a = 1/2$ (centered), the curse holds.
Tractability:
- For $p = \infty$ and $a \in \{0, 1\}$ (star $L_\infty$ ), the problem is polynomially tractable ( $N \le C d \varepsilon^{-2}$ ).
- For the "intermediate" case $p = \infty$ and $a \in (0, 1) \setminus \{1/2\}$ , the problem is not polynomially tractable, but it does not suffer from the full curse of dimensionality (complexity is polynomial for fixed $\varepsilon$ ).

3.2 Unanchored Discrepancies

The paper examines extreme and periodic discrepancies.

Extreme Discrepancy:
- Duality: Theorem 4 links extreme $L_p$ -discrepancy to integration in a space defined by a linear operator on $L_q(D_d)$ .
- Results: The curse of dimensionality holds for $p \in (1, \infty)$ . For $p = \infty$ , the problem is polynomially tractable.
Periodic Discrepancy (New Results):
- Duality: Theorem 6 provides a new duality for general $p, q$ linking periodic $L_p$ -discrepancy to integration in a space $F^{per}_{d,q}$ defined via a periodic integral operator.
- Curse of Dimensionality: Theorem 7 proves that for all $p \in (1, \infty)$ , the periodic $L_p$ -discrepancy with non-negative weights suffers from the curse of dimensionality. This extends previous results known only for $p=2$ .
- Tractability: For $p = \infty$ , the periodic discrepancy is polynomially tractable (specifically $N \le C d \log(d+1) \varepsilon^{-2}$ ).

3.3 Summary of Open Questions

The paper explicitly identifies the behavior of $L_1$ -discrepancies as a major gap in current knowledge.

Open Question: It remains unproven whether the star, extreme, or periodic $L_1$ -discrepancy suffers from the curse of dimensionality. The current methods rely on $p > 1$ (specifically the existence of specific worst-case functions and Hölder conjugates $q$ where $1/p + 1/q = 1$ ).

4. Significance and Scope

The paper's primary significance lies in providing a systematic overview and unifying framework for the tractability of geometric discrepancies.

Unification: It consolidates scattered results from various publications into a single coherent structure using the discrepancy–integration duality.
New Proofs: It provides complete proofs for general settings (e.g., general $a$ and $p$ for anchored discrepancies) where literature previously offered only partial or specific cases.
New Insights: It presents new results for the periodic $L_p$ -discrepancy for $p \in (1, \infty)$ and clarifies the tractability status of the "intermediate" anchored $L_\infty$ case.
Limitations: The authors modestly note that their lower bound method (Theorem 1) does not currently apply to the $L_1$ case, leaving the $L_1$ -discrepancy problem as the primary open question in the field.

The paper concludes that while the curse of dimensionality is a prevalent phenomenon for $L_p$ -discrepancies with $p \in (1, \infty)$ , the behavior for $p=1$ and $p=\infty$ varies significantly depending on the specific type of discrepancy and the choice of weights.