Disproving the quasi-uniformity of the Halton sequences and of some Halton-type sequences

This paper proves that the Halton sequence is not quasi-uniform in any dimension $d \ge 2$ with pairwise relatively prime bases, and extends this result to disprove the quasi-uniformity of certain Halton-type sequences, including the Faure sequence.

The Gist

Imagine you are hosting a massive party in a giant, multi-dimensional dance floor (the unit cube). You want to invite guests (points) to stand on the floor so that they are spread out as perfectly as possible. You don't want anyone clumped together in a corner, and you don't want huge empty spaces where no one is dancing.

In the world of mathematics and computer science, this "perfect spreading" is crucial for simulating complex systems, like predicting weather patterns or pricing financial stocks. The Halton sequence is one of the most famous "guest lists" mathematicians have created to achieve this. For decades, it was believed to be a near-perfect way to fill the dance floor.

However, a new study by Goda, Hofer, and Suzuki reveals a surprising flaw in this plan. They prove that while the Halton sequence is great at covering the whole floor, it fails a specific test of "evenness" when the dance floor has two or more dimensions.

Here is the breakdown of their discovery using simple analogies:

1. The Two Rules of a Good Party

To judge if a group of guests is well-distributed, mathematicians look at two specific measurements:

• The "Covering" Radius (The Empty Spot Test): Imagine you are standing anywhere on the dance floor. How far do you have to walk to find the nearest guest? If this distance is small everywhere, the "covering" is good. The Halton sequence passes this test perfectly. It ensures there are no huge empty zones.
• The "Separation" Radius (The Personal Space Test): Now, imagine you are a guest. How close is your nearest neighbor? If two guests are standing practically on top of each other, the "separation" is bad. For a sequence to be truly "quasi-uniform" (perfectly even), the distance between neighbors should shrink at a very specific, predictable rate as you add more guests.

2. The Halton Sequence's Secret Flaw

The authors discovered that the Halton sequence is a master at Covering but a failure at Separation in dimensions higher than one.

The Analogy of the "Crowded Corner":
Imagine you are arranging chairs in a room. The Halton sequence is like a smart robot that places chairs so that no one is left standing in the middle of the room (great covering). However, the robot has a glitch: as the room gets bigger, it accidentally places some pairs of chairs extremely close together, almost touching, while leaving other areas slightly more open.

In a 1-dimensional line (a single row of chairs), the Halton sequence works perfectly. But as soon as you add a second dimension (a 2D dance floor), the robot starts making mistakes. It creates "clumps" where points are dangerously close to each other, much closer than they should be for a perfect distribution.

3. The "Magic Number" Problem

The paper proves that for the Halton sequence, the distance between the closest pair of points shrinks too fast as you add more points.

Think of it like this:

• Ideal Scenario: If you double the number of guests, the distance between neighbors should shrink by a predictable, gentle amount (like $1/\sqrt{N}$).
• Halton Reality: The distance shrinks much faster than expected (like $1/(N \times \text{something huge})$).

This means that if you use the Halton sequence for high-dimensional simulations, you might get lucky with the overall coverage, but you risk having "clumps" of data points that are too close together. In applications like scattered data approximation (where you try to guess the shape of a curve based on a few points), these clumps can cause the math to become unstable or inaccurate, like a bridge collapsing because two support beams are too close together.

4. The "Halton-Type" Sequences

The authors didn't stop there. They looked at a family of related sequences (like the Faure sequence and Sobol' sequence), which are variations of the Halton sequence used for different types of math problems.

They found that these "cousins" of the Halton sequence suffer from the same problem. Specifically, they proved that the famous Faure sequence (used in high-dimensional finance and physics) is also not perfectly even. They provided a new, simpler way to prove this using "polynomial arithmetic" (a fancy way of doing math with algebraic shapes instead of just numbers).

Why Does This Matter?

For a long time, scientists assumed that if a sequence was good at covering a space (low discrepancy), it was automatically good at spacing points evenly (quasi-uniform).

This paper says: Nope.

• Low Discrepancy = No big empty holes.
• Quasi-Uniformity = No clumps and no holes.

The Halton sequence has no holes, but it does have clumps.

The Takeaway

If you are using the Halton sequence (or its cousins like Faure or Sobol) for a computer simulation in 2D, 3D, or higher dimensions, you need to be careful. While they are excellent for general integration (calculating areas/volumes), they might be risky for applications that require strict geometric spacing, such as:

• Radial Basis Function Interpolation: Trying to draw a smooth surface through scattered data points.
• Stability Analysis: Ensuring a mathematical model doesn't crash due to points being too close.

The authors haven't found a "perfect" sequence that fixes this yet (that's an open problem), but they have successfully debunked the myth that the Halton sequence is the golden standard for all geometric distribution tasks. They've shown us that even the most famous "low-discrepancy" sequences have their blind spots.

Technical Summary

Here is a detailed technical summary of the paper "Disproving the Quasi-Uniformity of the Halton Sequences and of Some Halton-Type Sequences" by Goda, Hofer, and Suzuki.

1. Problem Statement

The paper addresses a fundamental question regarding the geometric properties of low-discrepancy sequences, specifically the Halton sequence and its generalizations (Halton-type sequences).

• Context: While the Halton sequence is renowned for its low discrepancy (optimal for numerical integration via the Koksma–Hlawka inequality), its utility in scattered data approximation (e.g., radial basis function interpolation) depends on different geometric properties: covering radius ($h$) and separation radius ($q$).
• Quasi-Uniformity: A sequence is defined as quasi-uniform if the ratio of the covering radius to the separation radius is bounded by a constant ($h(P_N)/q(P_N) \le C$) for all $N$. This requires both radii to decay at the optimal rate of $O(N^{-1/d})$.
• The Gap: It is well-established that Halton sequences achieve the optimal decay rate for the covering radius ($h(P_N) \sim N^{-1/d}$). However, it was an open question whether the separation radius ($q(P_N)$) also decays at this optimal rate. Numerical evidence suggested that $q(P_N)$ might decay faster than $N^{-1/d}$ (implying points become too close), which would disprove quasi-uniformity, but no theoretical proof existed for dimensions $d \ge 2$.

2. Methodology

The authors employ a rigorous number-theoretic approach to construct specific pairs of indices $(n, m)$ such that the corresponding points in the sequence are exceptionally close to each other.

A. For Classical Halton Sequences (Section 2)

• Construction: The authors construct two integers $n$ and $m$ based on the bases $b_1, \dots, b_d$.
  • They utilize Euler's Totient Theorem ($b_j^{\phi(b_1)} \equiv 1 \pmod{b_1}$) to align the expansions of $n$ and $m$ in the first base $b_1$.
  • They use Dirichlet's Simultaneous Approximation Theorem to find integers $c_j$ that balance the decay rates of the radical inverse functions $\phi_{b_j}$ across all dimensions.
• Key Lemma: A lemma is proven showing that if $p \equiv 1 \pmod q$, then $pq^k - 1$ is divisible by $q^{k+1}$. This allows the authors to control the digit expansions of $n$ and $m$ in base $b_1$ to ensure they share a long prefix, making $\phi_{b_1}(n)$ and $\phi_{b_1}(m)$ very close.
• Bounding: By carefully choosing $n$ and $m$, the authors derive an upper bound for the Euclidean distance $\|x_n - x_m\|$ that is strictly smaller than $O(N^{-1/d})$.

B. For Halton-Type Sequences (Section 3)

• Framework: The authors extend the analysis to Halton-type sequences defined over the ring of polynomials $\mathbb{F}_p[X]$ (finite fields), which includes the Faure sequence and specific Sobol' sequences.
• Polynomial Analogue: They define a polynomial radical inverse function $\phi_{b(X)}$ where the base is a polynomial $b(X)$ rather than an integer.
• Key Lemma: They prove that if a polynomial $b(X)^\ell$ divides the difference of the polynomial representations of $n$ and $m$, then the distance between the points is bounded by $p^{-e\ell}$.
• Case Studies: They explicitly construct pairs $(n, m)$ for three specific cases:
  1. 2D projections of Faure sequences ($b_1(X)=X+a, b_2(X)=X+a+1$).
  2. 3D Sobol' sequence ($p=2$, bases $X, X+1, X^2+X+1$).
  3. $p$-dimensional Faure sequence ($b_j(X) = X - (j-1)$).

3. Key Contributions and Results

Main Result 1: Halton Sequences are Not Quasi-Uniform

Theorem 1: For any dimension $d \ge 2$ and pairwise relatively prime bases, the Halton sequence is not quasi-uniform.

• Proof: The authors prove that there exist infinitely many $N$ such that the separation radius satisfies:
  $$q(P_N) \le \frac{c}{N^{1/d} (\log N)^{1/(d(d-1))}}$$
• Implication: Since the separation radius decays strictly faster than the optimal rate $N^{-1/d}$ (due to the extra logarithmic factor in the denominator), the ratio $h(P_N)/q(P_N)$ grows unbounded. Thus, the sequence is not quasi-uniform.

Main Result 2: Disproving Quasi-Uniformity for Halton-Type Sequences

Theorem 2: Several Halton-type sequences are not quasi-uniform. Specifically, for the cases listed (2D Faure projections, 3D Sobol', and $p$-dimensional Faure), the separation radius decays as:
$$q(P_N) \le \frac{c}{N^{1/(d-1)}}$$

• Significance: Since $1/(d-1) > 1/d$for$d \ge 2$, the decay is significantly faster than optimal.
• Alternative Proof: This provides a new proof for the known result that the $p$-dimensional Faure sequence is not quasi-uniform (previously proven using Pascal matrices and Lucas's theorem), utilizing the algebraic structure of polynomial bases instead.

4. Significance and Impact

1. Theoretical Resolution: The paper definitively settles the open problem regarding the quasi-uniformity of the Halton sequence in dimensions $d \ge 2$. It confirms that while these sequences are excellent for integration (low discrepancy), they are geometrically unsuitable for scattered data approximation in higher dimensions because points cluster too closely.
2. Methodological Innovation: The use of Dirichlet's simultaneous approximation to balance the decay rates across different bases in the Halton sequence is a novel technique. Similarly, the application of polynomial arithmetic in finite fields to analyze Halton-type sequences offers a fresh perspective on the properties of digital sequences.
3. Practical Implications: For practitioners using quasi-Monte Carlo methods in applications like radial basis function (RBF) interpolation, this result serves as a warning. Using Halton sequences in high dimensions may lead to ill-conditioned interpolation matrices due to the lack of separation between points, potentially causing numerical instability.
4. Open Problems: The authors identify that the exact order of the separation radius for the general Halton sequence remains unknown (Open Problem 1) and pose the question of whether all Halton-type sequences for $d \ge 2$ are non-quasi-uniform (Open Problem 2).

Conclusion

The paper demonstrates that the geometric quality of the Halton sequence degrades in higher dimensions due to the rapid clustering of points (separation radius decaying faster than $N^{-1/d}$). This finding challenges the assumption that low-discrepancy sequences are universally optimal for all numerical tasks, highlighting a distinct trade-off between discrepancy (integration error) and quasi-uniformity (geometric stability).