🔢 mathematics

Perfectly equidistributed Quasi-Monte Carlo sequences from Artin-Schreier polynomials

This paper establishes conditions for achieving optimal uniformity ( $t=0$ ) in Quasi-Monte Carlo sequences by utilizing Artin-Schreier polynomials and a fast greedy procedure to construct high-dimensional, perfectly equidistributed sampling sequences.

Original authors: Nicolas Bonneel, David Coeurjolly, Victor Ostromoukhov

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicolas Bonneel, David Coeurjolly, Victor Ostromoukhov

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 perfect picture of a complex landscape, but you can only see the world through a tiny, flickering window. To get the whole picture, you have to take many snapshots from different spots and average them together. If you pick your spots randomly, you might accidentally cluster them all in the sky, missing the trees entirely, or leave huge gaps in the grass. This is the problem of "numerical integration": trying to calculate the total area under a curve or the volume of a shape by sampling points.

To solve this, mathematicians use a trick called Quasi-Monte Carlo. Instead of throwing darts blindly at a board, they carefully place their "darts" (or sample points) so they spread out as evenly as possible, like seeds scattered by a master gardener. The goal is to cover every corner of the space without any clumps or empty holes. The quality of this spread is measured by a number called $t$ . Think of $t$ as a "clumpiness score." A score of $t=0$ is the holy grail: it means the points are perfectly balanced, like a checkerboard where every square has exactly one piece. The lower the score, the better the average, and the faster you get a correct answer.

For decades, the gold standard for creating these perfect grids has been a method called Sobol' sequences. These use a special kind of math involving polynomials (equations with variables like $x$ ) to generate the coordinates. Usually, these polynomials are simple, like $x$ plus a number. But what if we could use more complex, "higher-degree" polynomials to create even better, more flexible grids? That is the question this paper tackles. The authors, Nicolas Bonneel, David Coeurjolly, and Victor Ostromoukhov, explore a specific, tricky type of polynomial called Artin-Schreier polynomials. They want to know: Can we use these complex shapes to build perfect grids, and if so, how do we arrange them so they don't mess up the balance?

The Discovery: Finding the Perfect Pattern

The authors discovered that while using complex polynomials usually makes it very hard to guarantee a perfect $t=0$ score, there is a special "sweet spot" where it works beautifully. They found that if you take a specific type of polynomial and create a whole family of them that are identical except for a tiny constant shift (like $x^5 - x + 1$ , $x^5 - x + 2$ , etc.), they form a pattern that is mathematically equivalent to a famous structure called Pascal matrices.

You can think of Pascal matrices as a digital version of Pascal's Triangle, the pyramid of numbers where each number is the sum of the two above it. In this paper, the authors show that when you use these "shifted" polynomials, the complex math behind the Sobol' method simplifies into these beautiful, repeating Pascal patterns. However, there's a catch: just having the pattern isn't enough. You also need to "initialize" the system correctly—like tuning a radio to the right frequency. The authors proved that if you start with a specific kind of tuning (using diagonal matrices based on Pascal powers), you are guaranteed to get a perfect $t=0$ score.

But there is one more hurdle: for the math to work in the real world, these polynomials must be "irreducible," meaning they can't be broken down into simpler pieces. The authors turned to a classic theory called Artin-Schreier theory to solve this. They showed that for any prime number base (like 5, 7, or 11), there is a guaranteed set of these special polynomials that are both complex enough to be interesting and "irreducible" enough to be valid. Specifically, they found that for a base $b$ , you can always find $b-1$ of these perfect polynomials.

Putting It All Together

The paper doesn't just stop at finding these perfect grids; it also figures out how to combine them. Imagine you have a set of simple, linear grids (the old-school way) and a new set of complex, Artin-Schreier grids. The authors created a fast, greedy algorithm to mix them together. They tested different ways to "tune" the complex grids (by changing the diagonal numbers in their initialization) to see which combination gave the best overall spread when you added the dimensions together.

In their experiments, they tested bases like 5, 7, and 11. They found that while the simple grids worked well on their own, the way you tuned the complex grids mattered a lot when you combined them. Some tuning settings created terrible clumps in the combined 9-dimensional space, while their optimized settings kept the points perfectly spread out. They showed that their new sequences are competitive with, and sometimes better than, the best existing methods used by experts today.

Why This Matters

The beauty of this work is that it turns a difficult, trial-and-error problem into a predictable recipe. Before this, trying to use high-degree polynomials for these grids was a gamble; you might get a perfect grid, or you might get a mess. The authors have now provided a clear set of rules: use Artin-Schreier polynomials, initialize them with Pascal-based matrices, and you are mathematically guaranteed a perfect spread. This gives scientists and computer graphics artists a new, powerful tool to calculate complex integrals faster and more accurately, whether they are simulating light in a video game or modeling the behavior of particles in physics. The paper proves that with the right mathematical "recipe," we can achieve perfect uniformity even in the most complex, high-dimensional spaces.

Technical Summary: Artin-Schreier Quasi-Monte Carlo Sequences

Problem Statement
Numerical integration of high-dimensional functions relies on Quasi-Monte Carlo (QMC) estimators, which average integrand values at pseudo-random, well-distributed uniform sampling locations. The quality of these estimators is governed by the uniformity of the point set, typically measured by an integer parameter $t$ . A lower $t$ value indicates better uniformity, with $t=0$ representing the optimal case. While standard constructions like Sobol' sequences can produce $(t, s)$ -sequences, finding conditions that guarantee $t=0$ for general prime bases $b$ and higher-degree polynomials remains a challenge. Specifically, while $t=0$ is achievable for $b$ -dimensional sequences using degree-1 polynomials over the Galois Field $GF(b)$, extending this guarantee to higher-degree polynomials has been an open problem.

Methodology
The authors investigate the construction of Sobol' sequences in $GF(b)$ using sets of irreducible polynomials that differ only by a constant term (consecutive polynomials). The methodology proceeds through several theoretical and algorithmic steps:

Tensorized Pascal Matrices: The authors demonstrate that when using consecutive polynomials $p_i(x) = p(x) + c_i$ of degree $e$ , the resulting Sobol' matrices relate to powers of Pascal matrices. Specifically, the characteristic matrix $K$ (defined as $M(c_2)M(c_1)^{-1}$ ) takes the form of a tensorized power of a Pascal matrix, $P_\alpha \otimes K_{[e \times e]}$ , where $\alpha$ is the difference between the constant terms.
Finite Testing for Infinite Guarantees: Building on the observation that Pascal powers act as polynomial shifts, the authors prove that for consecutive polynomials of degree $e$ , verifying the $(0, m, s)$ -net condition for a finite number of sample sizes ( $m \le s(e-1)$ ) is sufficient to guarantee the $(0, s)$ -sequence property for all $m$ .
Artin-Schreier Construction: To ensure the polynomials are irreducible (a requirement for compatibility with standard Sobol' constructions), the authors utilize Artin-Schreier theory. They select polynomials of the form $p_i(x) = x^b - x + c_i$ over $GF(b)$ where $b$ is prime. This theory guarantees that $b-1$ such polynomials are irreducible.
Initialization Strategy: The paper proposes a specific initialization for the Sobol' recurrence. By initializing the $e \times e$ blocks of the Sobol' matrices with $M(c_i)_{[e \times e]} = D P_{c_i} D^{-1}$ , where $D$ is an invertible diagonal matrix and $P$ is the Pascal matrix, the authors prove that the resulting sequence is a $(0, s)$ -sequence.
Greedy Optimization: For combined sequences of dimension $2b-1$ (concatenating $b$ linear polynomials and $b-1$ Artin-Schreier polynomials), the authors employ a greedy algorithm to select the diagonal matrix $D$ . This approach optimizes the combined $t$ -value by testing diagonal elements sequentially, avoiding the intractable exhaustive search required for larger bases.

Key Contributions

Theoretical Link: The paper establishes a direct link between Sobol' sequences generated by consecutive polynomials and tensorized powers of Pascal matrices, generalizing Faure's construction (which corresponds to the $e=1$ case).
Sufficient Conditions for $t=0$ : The authors provide explicit conditions under which Sobol' sequences using higher-degree polynomials ( $e=b$ ) guarantee $t=0$ . This is achieved by initializing the recurrence with diagonal-conjugated Pascal matrices.
Artin-Schreier Sequences: The work introduces a new class of QMC sequences based on Artin-Schreier polynomials ( $x^b - x + c_i$ ) that guarantee $t=0$ in $b-1$ dimensions for any prime base $b$ .
Combined Sequence Optimization: A fast, greedy procedure is provided to optimize the initialization of combined $(2b-1)$ -dimensional sequences, ensuring $t=0$ projections in subspaces while minimizing the global discrepancy.

Results
Numerical experiments were conducted using the generalized $\ell_2$ discrepancy as a measure of uniformity.

Discrepancy Evaluation: For bases $b=5, 7, 11$ , the proposed Artin-Schreier sequences were compared against existing methods, including Faure and Lemieux's irreducible polynomial sequences, Bonneel et al.'s $t=1$ sequences, and Ostromoukhov et al.'s optimized sequences.
Initialization Sensitivity: The study found that while the choice of initialization matrix $D$ has minimal impact on the uniformity of the standalone $(b-1)$ -dimensional Artin-Schreier sequences, it significantly affects the uniformity of the combined $(2b-1)$ -dimensional sequences.
Performance: The optimized combined sequences demonstrated competitive discrepancy values compared to other state-of-the-art Sobol' samplers, particularly in the context of progressive estimation where sample counts $n$ are not perfect powers of $b$ .

Significance
The paper claims to provide a constructive method for generating high-quality $(0, s)$ -sequences in arbitrary prime bases using higher-degree polynomials. By leveraging Artin-Schreier theory, the authors ensure the existence of the necessary irreducible polynomials, a condition that is not always trivial to satisfy for consecutive polynomials. The work extends the applicability of $t=0$ sequences beyond the linear case, offering a robust framework for high-dimensional numerical integration where strict uniformity bounds are required. The authors emphasize that their approach guarantees $t=0$ projections in subspaces, a critical property for maintaining low integration error in high-dimensional settings.

The Discovery: Finding the Perfect Pattern

Putting It All Together

Why This Matters

Technical Summary: Artin-Schreier Quasi-Monte Carlo Sequences

More like this