Why classical sequences cut corners

The baseline. Monte Carlo puts N independent random points into the unit square. They leave holes and they clump: the two closest points are typically about 1/N apart, much closer than the spacing 1/√N of a grid with the same number of points. A grid has no clumps, but it exists for one N only, and points cannot be added to it.

Low-discrepancy sequences sit in between. They are one infinite list of points, and every prefix of q^m points (in base q) is a net: if the square is cut into q^m boxes of equal area, of any of the allowed shapes, each box holds exactly one point. So there are never large holes. Clumps are another matter.

Quasi-uniform asks for both at every prefix: no hole and no clump larger, respectively smaller, than a constant times the grid spacing N^−1/2 (in dimension s, N^−1/s). We measure clumps by the separation δ, the smallest distance between two of the first N points, in grid units: sep = δ·√N. The grid has sep = 1. A sequence is quasi-uniform exactly when sep stays above a positive constant for every N (for the sequences here the holes take care of themselves, lem:prefix).

The question. Quasi-uniformity of quasi-Monte Carlo point sets was studied systematically by Dick, Goda, Larcher, Pillichshammer and Suzuki (Part I, Part II). Dick, Goda and Suzuki asked for digital nets and sequences in a fixed base that are both low-discrepancy and quasi-uniform. Their positive example is the two-dimensional Larcher–Pillichshammer net (Larcher and Pillichshammer); for dimension s ≥ 3 they state the construction as open, for nets and for sequences (Dick, Goda and Suzuki). Goda, Hofer and Suzuki proved that the Halton sequences are not quasi-uniform and asked whether any Halton-type sequence is, their Open Problem 2 (Goda, Hofer and Suzuki). The companion paper answers the question of Dick, Goda and Suzuki for nets in every dimension; the paper explained here answers it for sequences and shows that no Halton-type sequence is quasi-uniform.

Move the slider. The closest pair of the first N points is circled; the curve below is sep for every N up to the end of the slider. Random points sink fast. Halton, Sobol' and Faure sink too, more slowly and in steps; the last button previews the sequence of page 2, which has a certified floor.

Why do the classical sequences clump? They are built from polynomial bases: the index of a point is written as a polynomial V over a finite field, and each coordinate reads V in its own base, digit block by digit block, like a radical inverse. The Faure (Faure), Sobol' (Sobol') and Niederreiter (Niederreiter) sequences and Tezuka's generalizations (Tezuka) are of this kind. In the two-dimensional Faure sequence in base p, coordinate 0 reads the ordinary digits of the index (the base z), and coordinate 1 reads the Taylor digits of V around z = 1 (the base z − 1).

Take two indices that differ by a carry in the last digits of coordinate 0: in base 5 the digits 0.04444 of one point become 0.1 for the other. As numbers they differ by one unit of the last digit, so the two points sit on either side of a cell boundary, almost touching. If the same index difference is also divisible by a high power of the other base, it leaves the leading digits of the other coordinate unchanged. Then the two points are close in every coordinate at once. Here the difference is D = (z − 1)^Q−1: its first Q digits in base z are all 1 (the carry), and it is divisible by (z − 1)^Q−1 (coordinate 1 is blind to it).

One close pair does not prove anything about large N. The point of thm:nonqu is that the pair comes back at ever larger sizes, ever closer in grid units. Over a field of characteristic p the map f ↦ f^p (the Frobenius map) is additive: (f + g)^p = f^p + g^p. So raising the index difference to the power p stretches the carry and the shared digits by the factor p, while the gap between the length of the shared digits and the cell side grows each time. The table computes the explicit pairs of rem:faurerate for Q = p, p², p³, … and the pairs of cor:sobol for the Sobol' sequence, exactly, with polynomial arithmetic in your browser (the indices run to about a hundred digits; no prefix is enumerated).

For the Sobol' sequence this goes against an old expectation. Sobol' and Shukhman suggested, from numerical experiments, that its separation is of the optimal order N^−1/s (Sobol' and Shukhman). Goda disproved this in dimension two (Goda), and Suzuki showed that there the mesh ratio grows at least like N^1/4 (Suzuki); Goda, Hofer and Suzuki stated the question for s ≥ 3 as open (Goda, Hofer and Suzuki). cor:sobol disproves the expectation in every dimension s ≥ 2, for any admissible direction numbers.

A standard remedy for bad patterns is a scramble: replace digit n of a coordinate by a fixed combination of its digits 0, …, n (a lower-triangular matrix L; such scrambles of Faure-type sequences are classical, Tezuka, Matoušek). That keeps the net property for free (lem:t0). But it cannot undo the shared leading digits: if two points agree in the first d digits of a coordinate before the scramble, they agree after it. So scrambling the coordinates that do not carry changes nothing about the pair. Try it on the base-5 pair of section 2: each click draws a new random scramble of coordinate 1 and recomputes the whole prefix of 3125 points.

Corollary cor:unscrambled says more: as long as one coordinate is still a radical inverse up to a constant factor, no fixed lower-triangular scramble of the other coordinates makes the sequence quasi-uniform. Scrambling every coordinate is not covered by the theorem, and the second button shows that the pair can then disappear. A random scramble comes with no guarantee, though; page 2 builds one fixed scramble of all coordinates with a proved floor.

At N = q^2K points (a full level) the square splits into q^K × q^K cells, and each cell holds exactly one point. So separation is decided by where each point sits inside its cell compared with its neighbours. To first order that position is the geometric digit: the first digit of each coordinate below the cell. It is a linear function of the cell digits, the offset map, and what matters is how it changes when one steps to the neighbouring cell.

For the Faure sequence the offset map changes with the level. In dimension two one of its coefficients is (−1)^K(K + 1) at level K (ex:faurelaw), which runs through all residues modulo p, the bad ones included:

A net is built for one size and can conjugate this away with a scramble chosen for that size; the nets of the companion paper do exactly that. A sequence cannot: a row of its scramble, once used, stays in use at every finer level. The way out is a self-similar scramble. Going one level finer is multiplication of the index by one fixed polynomial w, and a self-similar scramble makes that a shift of every digit by one place. Then the offset map is the same at every level (prop:law), and one finite check bounds the separation at all levels at once (lem:cert, page 4).

The three panels zoom into a cell twice. Each panel shows 7 × 7 cells with the lattice image of each point (open circle: the position predicted by the geometric digits) joined to the point. The label on an arrow is the change of the geometric digits (r₀, r₁) modulo 7 across that step. Click a cell of the first or second panel to zoom into it.

Being self-similar is not enough: the brick wall still has to choose its infinitely many responses well, one for each carry length, and exact linear rules can fix only a few of them (page 3). What it does fix, it fixes with one identity between the coordinates, and that identity is the subject of page 2.