The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension

This paper demonstrates that the union of randomly digitally shifted Korobov polynomial lattice point sets achieves a star discrepancy with an inverse that depends linearly on the dimension, thereby narrowing the search for explicit constructions from a continuum to a finite set of candidates.

The Gist

Imagine you are throwing a party in a giant, multi-dimensional room. Your goal is to invite exactly $N$ guests and have them stand in the room so that they are perfectly spread out.

If you look at any corner of the room (or any shape you draw inside it), you want the number of people standing there to be exactly proportional to the size of that shape. If a corner takes up 10% of the room, you want roughly 10% of your guests there.

This "perfect spreading" is what mathematicians call low discrepancy. The "Star Discrepancy" is simply a scorecard that measures how messy the party is. A high score means people are clumped together in some corners and missing from others. A low score means the party is perfectly balanced.

The Big Problem: The "Dimension" Curse

In a simple 2D room (like a square), it's easy to spread people out. But what if your room has 100 dimensions? Or 1,000?

Mathematicians have known for a long time that it is theoretically possible to find a perfect arrangement of guests even in these massive, high-dimensional rooms. In fact, the number of people you need to get a "good enough" spread grows only linearly with the number of dimensions. (If you double the dimensions, you only need to double the number of guests to keep the same quality).

However, there's a catch: While we know these perfect arrangements exist, we have never been able to write down a recipe to build them. It's like knowing a perfect treasure map exists somewhere in the world, but having no idea where to start digging. Finding the actual coordinates for these points is a massive, unsolved puzzle.

The Paper's Solution: The "Digital Shuffle" and the "Group Hug"

This paper by Josef Dick and Friedrich Pillichshammer takes a huge step toward solving this puzzle. They don't find the one perfect arrangement, but they show you how to build a "super-arrangement" that is almost as good, using a clever trick involving Korobov polynomial lattice point sets.

Here is the analogy for their method:

1. The "Structured Dancers" (Korobov Lattices)

Imagine you have a group of dancers. Instead of standing randomly, they follow a strict, mathematical dance routine (a lattice). This routine is very orderly, but if you look at it from a certain angle, it might have gaps or clumps. It's too rigid.

2. The "Digital Shuffle" (Random Shifts)

To fix the gaps, the authors take each group of dancers and give them a "digital shuffle." Imagine the floor is made of tiny tiles. They randomly slide the whole group of dancers over by a few tiles.

• If you do this once, it's better.
• But the paper shows that if you take many different groups of dancers, give each group a different random shuffle, and then merge them all together, something magical happens.

3. The "Union" (The Big Mix)

The authors propose taking a union (a big mix) of these shuffled groups.

• The Random Approach: They show that if you randomly pick a bunch of these shuffled groups and mix them, you are almost guaranteed to get a near-perfect spread of people, even in 1,000 dimensions.
• The "All of Them" Approach: Even cooler, they show that you don't even need to pick randomly. If you take every possible variation of these shuffled groups and mix them all together, you get the same perfect result.

Why This Matters

1. Narrowing the Search:
Before this paper, the search for a perfect point set was like looking for a needle in a haystack the size of the universe. The search space was infinite.
This paper says: "Hey, you don't need to look everywhere. You only need to look at a specific, finite list of 'shuffled lattice' combinations." It shrinks the haystack down to a manageable pile of hay.

2. The "Non-Constructive" Twist:
The authors admit their proof is "non-constructive." This means they used a mathematical tool (Bernstein's inequality) to prove that a good mix must exist within their finite list, but they didn't write down the exact recipe for which specific mix is the winner.

• Analogy: It's like proving that if you buy 100 lottery tickets with specific numbers, at least one of them is a winner. They haven't told you which ticket wins yet, but they've proven you only need to check those 100 tickets instead of buying every ticket in the world.

3. The Result:
They proved that the "messiness score" (discrepancy) of their mixed groups depends on the dimension in the best possible way (linearly). This is the "Holy Grail" of Quasi-Monte Carlo methods, which are used for everything from simulating financial markets to rendering 3D graphics in movies.

Summary in Plain English

• The Goal: Spread points perfectly in high-dimensional space.
• The Problem: We know it's possible, but we can't find the specific points.
• The Trick: Take structured patterns, shuffle them randomly, and mix many of them together.
• The Breakthrough: The authors proved that mixing these specific "shuffled patterns" creates a near-perfect spread.
• The Impact: They reduced the infinite search for the perfect points to a finite, manageable list. While they haven't found the exact "winning" combination yet, they've handed us a much smaller list to check, bringing us one step closer to a fully explicit, perfect recipe for high-dimensional uniformity.

It's a bit like saying, "We can't tell you exactly which key opens the treasure chest, but we've proven that the key is definitely in this specific box of 1,000 keys, not in the entire ocean."

Technical Summary

Here is a detailed technical summary of the paper "The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension" by Josef Dick and Friedrich Pillichshammer.

1. Problem Statement

The paper addresses a fundamental open problem in discrepancy theory and Quasi-Monte Carlo (QMC) integration: constructing explicit point sets in the $s$-dimensional unit cube $[0,1)^s$ that achieve a star discrepancy $D^*_N(P)$ of order $O(\sqrt{s/N})$.

• Context: The star discrepancy measures the uniformity of a point set. The inverse star discrepancy, $N(\varepsilon, s)$, is the minimum number of points $N$ required to achieve a discrepancy $\le \varepsilon$.
• Theoretical Baseline: It is known (Heinrich et al., 2001) that $N(\varepsilon, s) = O(s/\varepsilon^2)$, meaning the inverse discrepancy depends linearly on the dimension $s$. This implies the existence of point sets with $D^*_N(P) \lesssim \sqrt{s/N}$.
• The Gap: While probabilistic proofs (random sampling) guarantee the existence of such sets, explicit constructions achieving this optimal linear dependence on $s$ have remained elusive. Classical deterministic constructions (digital nets, rank-1 lattices) typically suffer from a dependence of $(\log N)^{s-1}$, which deteriorates rapidly as $s$ grows.
• Goal: The authors aim to bridge the gap between existential probabilistic bounds and explicit constructions by analyzing unions of Korobov polynomial lattice point sets subjected to random digital shifts.

2. Methodology

The authors employ a probabilistic approach restricted to a finite, structured candidate family rather than the continuous unit cube. The methodology involves three main components:

A. Construction of Point Sets

The proposed point sets are multiset unions of digitally shifted Korobov polynomial lattice rules.

• Korobov Polynomial Lattices: Defined over the finite field $\mathbb{Z}_2$. A lattice is generated by a polynomial vector $\mathbf{q} = (1, q, q^2, \dots, q^{s-1}) \pmod p$, where $p$ is an irreducible polynomial of degree $m$. The number of points in one lattice is $2^m$.
• Digital Shifts: Each lattice is shifted by a random vector $\sigma \in \mathbb{Q}_{2^m}^s$ (dyadic rationals) using component-wise addition modulo 2 (XOR operation).
• The Union:
  • Theorem 1.2: A union of $2^m$independently generated lattices, each with a random generating vector$\mathbf{q}_r$and a random shift$\sigma_r$. Total points$N = 2^{2m}$.
  • Theorem 1.3: A union of all possible Korobov lattices (generated by polynomials $0, \dots, 2^m-1$), where each is shifted by an independent random$\sigma_r$. Total points$N = 2^{2m}$.

B. Analytical Tools

• Walsh Functions: The indicator function of the test boxes $[0, \mathbf{b})$ is expanded into a Walsh series. This allows the discrepancy to be analyzed via Fourier coefficients in the dyadic group.
• Bernstein's Inequality: Instead of Hoeffding's inequality, the authors use Bernstein's inequality. This is crucial because it exploits the variance of the discrepancy contributions. The structured nature of the lattice points ensures that the variance is significantly smaller than that of purely random points, allowing for tighter concentration bounds.
• Union Bound: The proof controls the maximum discrepancy over a finite grid of test points (dyadic boxes) using a union bound, leveraging the fact that the search space is finite.

C. Variance Reduction Mechanism

A key technical insight is that for a single randomly shifted lattice, the expected discrepancy is zero (Lemma 2.2). More importantly, the variance of the discrepancy contribution from a lattice is bounded by $O(s/2^m)$. When summing $2^m$ such independent lattices, the variance of the sum scales favorably, allowing the application of Bernstein's inequality to show that the sum concentrates tightly around zero.

3. Key Contributions

1. Existence within a Finite Candidate Set: The paper proves that a point set achieving the optimal order $D^*_N(P) \lesssim \frac{s \log N}{\sqrt{N}}$ exists within a finite family of structured point sets.
   • This reduces the search space from the continuum of $[0,1)^s$ to a discrete set of size roughly $N^{s\sqrt{N}}$, which is exponentially smaller than the search space of general discretized grids ($(sN)^{sN/2}$).
2. Two Specific Constructions:
   • Randomized Selection (Thm 1.2): Selecting $2^m$ random lattices and shifts.
   • Deterministic Lattice Union (Thm 1.3): Taking the union of all Korobov lattices (parameterized by $r=0 \dots 2^m-1$) with random shifts. This eliminates the randomness in the choice of the generating polynomials, leaving only the shifts as random.
3. Optimal Dimensional Dependence: Both constructions achieve a discrepancy bound where the inverse depends linearly on the dimension $s$ (specifically $D^*_N \approx C \cdot s \cdot \frac{\log N}{\sqrt{N}}$). This matches the existential lower bound up to logarithmic factors.
4. Step Towards Explicit Construction: While the proof is non-constructive (it shows existence with high probability), it significantly narrows the search space. This paves the way for future derandomization (finding a specific good instance via deterministic search) or certification using discrepancy approximation algorithms.

4. Main Results

Theorem 1.2:
Let $P$ be the union of $2^m$independently chosen randomly shifted Korobov polynomial lattice point sets (with random generating vectors and random shifts). With probability at least$\delta$, the star discrepancy satisfies:
$$D^*_N(P) \leq (1.723\dots) \times \frac{s(\log(2N) + 1) + \log 2 - \log(1-\delta)}{\sqrt{N}}$$
where $N = 2^{2m}$.

Theorem 1.3:
Let $Q$ be the union of all $2^m$Korobov polynomial lattice point sets (generated by$q=0, \dots, 2^m-1$), each shifted by an independent random digital shift. With probability at least$\delta$, the star discrepancy satisfies the same bound as Theorem 1.2.

Significance of the Bound:
The bound is of the order $O(s \sqrt{\log N / N})$. Since $N = 2^{2m}$, $\sqrt{N} = 2^m$. The term $s/\sqrt{N}$ confirms the linear dependence on $s$ required for the inverse discrepancy to be linear in $s$.

5. Significance and Impact

• Bridging Theory and Practice: The paper moves the field closer to the "holy grail" of QMC: an explicit construction with linear dimension dependence. By restricting the search to a finite, structured family, it transforms an intractable continuous problem into a potentially solvable combinatorial one.
• Efficiency of Search: Remark 1.1 highlights that the search space for these constructions is vastly smaller than the space of all possible discretized point sets. This suggests that finding a "good" set via derandomization (e.g., using the method of conditional probabilities or greedy algorithms) is computationally more feasible than previously thought.
• Methodological Advancement: The successful application of Bernstein's inequality to structured lattice unions demonstrates a powerful technique for analyzing the discrepancy of composite point sets. It leverages the algebraic structure of the lattices to control variance, a technique that could be applied to other high-dimensional approximation problems.
• Foundation for Future Work: The result provides a concrete target for algorithmic research. Future work can focus on:
  1. Derandomizing the shifts $\sigma_r$ to make the construction fully explicit.
  2. Extending the union concept to other types of lattice rules.
  3. Applying these bounds to specific numerical integration problems in high dimensions.

In summary, Dick and Pillichshammer have provided a rigorous probabilistic proof that structured unions of lattice rules can achieve the theoretically optimal linear dependence on dimension for star discrepancy, significantly reducing the complexity of the search space for such point sets.