🔢 mathematics

Infinite sequences with optimal diaphony, periodic $L_2$ -discrepancy, and beyond

This paper proves that infinite order-2 digital sequences over $\mathbb{F}_2$ achieve optimal periodic $L_2$ -discrepancy and diaphony bounds, thereby confirming their conjectured optimality, reducing the dimensionality of interlacing constructions from $5d$ to $2d$ , and establishing superior worst-case integration errors for periodic Besov spaces with dominating mixed smoothness.

Original authors: Peter Kritzer, Nicolas Nagel, Friedrich Pillichshammer

Published 2026-06-05

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Peter Kritzer, Nicolas Nagel, 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 (a mathematical space called a "unit cube") using a specific number of dots. Your goal is to make sure the dots are spread out as perfectly as possible, with no clumps and no big empty gaps. This is the core problem of Quasi-Monte Carlo (QMC) methods, which are used to solve complex math problems by sampling points instead of guessing randomly.

If your dots are clumped together, your math calculation will be sloppy. If they are perfectly spread out, the calculation is incredibly accurate. The paper by Kritzer, Nagel, and Pillichshammer is about finding the perfect recipe for spreading these dots out.

Here is the breakdown of their discovery using simple analogies:

1. The Problem: The "Perfectly Even" Distribution

In the past, mathematicians knew that for a wall with $d$ dimensions, there is a theoretical "best possible" way to spread $N$ dots. It's like a gold standard. However, actually building a set of dots that hits this gold standard was difficult.

Previous recipes (called "order-5 digital sequences") worked, but they were incredibly heavy and complicated. To build a pattern for a 10-dimensional wall, the old recipe required you to first build a pattern for a 50-dimensional wall and then mash it down. It was like trying to bake a simple cake by first building a massive, 50-story factory just to mix the batter. It was theoretically possible but practically useless for high-dimensional problems.

2. The Solution: The "Order-2" Shortcut

The authors of this paper proved that you don't need that massive 50-dimensional factory. You can achieve the same perfect spread using a much simpler, lighter recipe called an "order-2 digital sequence."

The Old Way: To get a good pattern for a $d$ -dimensional problem, you had to construct a pattern in $5d$ dimensions.
The New Way: You only need to construct a pattern in $2d$ dimensions.

The Analogy:
Imagine you are arranging chairs in a room.

The Old Method was like trying to arrange the chairs by first arranging them in a giant warehouse with five times as many aisles, then squishing them into your room. It worked, but it was a nightmare to manage.
The New Method proves you can get the exact same perfect arrangement by only organizing a warehouse with twice as many aisles. It's much easier to manage, faster to build, and just as perfect.

3. What They Actually Proved

The paper doesn't just say "this is easier." It mathematically proves that these simpler "order-2" sequences are optimal.

The "Diaphony" and "Discrepancy": These are fancy math words for "how unevenly the dots are spread." The paper proves that the new, simpler sequences achieve the lowest possible unevenness allowed by math. You cannot do better than this.
The "Infinite" Advantage: Unlike some methods that only work for a specific number of dots (like exactly 1,024 dots), these sequences are infinite. This means you can start with 10 dots, then add 11, then 12, and the pattern stays perfect. You never have to throw away your previous work to add more points. It's like a puzzle where you can keep adding pieces forever without ever having to restart.

4. Why This Matters (According to the Paper)

The authors show that this new method works not just for simple dot-arranging, but for a wide variety of complex math functions (specifically "periodic functions" and "Besov spaces").

Efficiency: By reducing the underlying complexity from $5d$ to $2d$ , they made high-dimensional problems solvable that were previously too heavy to handle.
Precision: They confirmed a long-held guess (conjecture) that "order-2" is the sweet spot. You don't need "order-5" to get the best results; order-2 is enough and much faster.

Summary

Think of this paper as the engineers who finally figured out how to build a perfectly balanced bridge using half the amount of steel and half the construction time of the previous designs. They proved that the simpler design isn't just "good enough"—it is mathematically the best possible design, and it works for infinite lengths of bridge.

In short: They found a simpler, faster, and perfectly optimal way to spread points out in multi-dimensional space, making complex computer calculations much more practical.

Technical Summary: Infinite Sequences with Optimal Diaphony, Periodic $L_2$ -Discrepancy, and Beyond

Problem Statement
The paper addresses the construction of infinite sequences $S_d$ in the $d$ -dimensional unit cube $[0, 1)^d$ that achieve optimal convergence rates for numerical integration and discrepancy measures. Specifically, the authors focus on the periodic $L_2$ -discrepancy and its analytic counterpart, the diaphony.

It is a known theoretical result that for any dimension $d$ , there exists a lower bound for the periodic $L_2$ -discrepancy of infinite sequences of the order $\Omega((\log N)^{d/2}/N)$ for infinitely many $N$ . While previous constructions achieved this optimal order using order-5 digital sequences over the finite field $\mathbb{F}_2$ , these constructions rely on an "interlacing" procedure that increases the underlying dimension of the generating matrices from $d$ to $5d$ . This high dimensionality renders such constructions impractical for high-dimensional applications. The paper investigates whether order-2 digital sequences can achieve the same optimal asymptotic order, thereby reducing the underlying dimension to $2d$ and significantly improving practicality.

Methodology
The authors employ a framework based on Quasi-Monte Carlo (QMC) integration over Besov spaces with dominating mixed smoothness, denoted as $S^r_{p,q}B(\mathbb{T}^d)$ , where the smoothness parameter $r \in (1/p, 2)$ . The methodology proceeds through the following steps:

Function Space Characterization: The analysis utilizes the Faber basis (hierarchical basis) to characterize functions in $S^r_{p,q}B(\mathbb{T}^d)$ . The worst-case error of a QMC rule in these spaces is bounded by the decay of the coefficients of the local discrepancy function when expanded in this basis.
Connection to Discrepancy: The paper establishes a link between the worst-case error in Besov spaces and the periodic $L_2$ -discrepancy/diaphony. Specifically, for the case $p=q=2$ and $r=1$ , the worst-case error is equivalent to the periodic $L_2$ -discrepancy.
Digital Sequence Construction: The study focuses on order-2 digital sequences over $\mathbb{F}_2$ . These are constructed via an interlacing procedure applied to two order-1 digital sequences (generating matrices $C_1, \dots, C_{2d}$ are interlaced to form $E_1, \dots, E_d$ ). This reduces the required dimension of the underlying generating matrices from $5d$ (required for order-5 sequences) to $2d$ .
Haar Coefficient Analysis: The core technical work involves bounding the Haar coefficients of the local discrepancy function for order-2 digital sequences. The authors utilize properties of digitally shifted order-2 digital nets and sequences to derive specific bounds on these coefficients, distinguishing between cases where the dyadic box size is large or small relative to the number of points $N$ .
Summation and Aggregation: Using the derived bounds on Haar coefficients, the authors sum the errors over the dyadic decomposition to estimate the total worst-case error in the Besov space. This involves careful handling of logarithmic factors and the interplay between the smoothness parameter $r$ , the integrability parameters $p, q$ , and the dimension $d$ .

Key Contributions and Results

Optimality of Order-2 Sequences: The primary result (Theorem 12) proves that infinite order-2 digital sequences attain the optimal order of convergence for the worst-case error in $S^r_{p,q}B(\mathbb{T}^d)$ .
- For $r \neq 1$ , the error is of order $N^{-\min(r,1)} (\log N)^{(d-1)(1-1/q)}$ .
- For $r = 1$ , the error is of order $N^{-1} (\log N)^{d(1-1/q)}$ .
- These bounds hold for all $N \in \mathbb{N} \setminus \{1\}$ , not just for infinitely many $N$ .
Confirmation of Conjecture: By establishing the bound $L_{2,N}^{\text{per}}(S_d) \lesssim_d (\log N)^{d/2}/N$ for order-2 sequences (Corollary 14), the paper confirms the conjecture that order-2 constructions are sufficient to achieve the optimal periodic $L_2$ -discrepancy/diaphony. This matches the known lower bounds for infinite sequences.
Dimensional Reduction: The paper demonstrates that the underlying dimension for the interlacing construction can be reduced from $5d$ (required for order-5 sequences) to $2d$ . This reduction is presented as a significant improvement in practicality for high-dimensional integration.
Extensibility: The results apply to infinite sequences, ensuring that the QMC rules are extensible. This means that increasing the number of integration nodes $N$ does not require discarding previous function evaluations, a property characteristic of "open type" rules.

Significance and Claims
The paper claims that its results confirm the conjectured optimality of order-2 digital sequences for periodic $L_2$ -discrepancy and diaphony. The significance lies in:

Theoretical Confirmation: It resolves the question of whether the higher complexity of order-5 sequences is necessary for optimal periodic discrepancy, showing that order-2 is sufficient.
Practical Improvement: By reducing the underlying dimension of the generating matrices from $5d$ to $2d$ , the construction becomes significantly more feasible for implementation in high-dimensional problems.
Broad Applicability: The bounds are established within the general framework of Besov spaces with dominating mixed smoothness, covering a wide range of function classes, with the periodic $L_2$ -discrepancy appearing as a specific case ( $p=q=2, r=1$ ).

The authors note that these findings align with previous results showing that order-2 sequences exhibit optimal rates for various other discrepancy measures (star discrepancy, extreme discrepancy, and norms in Sobolev, Besov, and Triebel-Lizorkin spaces), further evidencing the "universally excellent distribution properties" of Dick's order-2 digital sequences.