Pair Correlations of Niederreiter and Halton Sequences are not Poissonian

Lisa Kaltenb\"ock; Roswitha Hofer

REVIEW 1 major objections 4 minor 24 references

Pair Correlations of Niederreiter and Halton Sequences are not Poissonian

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Niederreiter digital sequences and Halton sequences, though uniformly distributed, fail Poissonian pair correlations in every dimension.

desk verdict A credible negative result that closes an open problem; the Halton proof is solid, and the digital proof has a terse but likely true step a referee should ask to be expanded. read the letter →

arxiv 1908.11147 v3 pith:OWSPUWOZ submitted 2019-08-29 math.NT

Roswitha Hofer , Lisa Kaltenböck This is my paper · ORCID

classification math.NT MSC 11K3811K31

keywords PoissonianpaircorrelationsNiederreitersequencesHaltondigital(0ed)-sequenceslow-discrepancyuniformdistributionquasi-MonteCarlo

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that two standard families of uniformly distributed multi-dimensional point sequences—Niederreiter digital sequences and Halton sequences—fail the stronger property of Poissonian pair correlations. In the d-dimensional sup-norm sense, Poissonian pair correlations would require the normalized count of pairs closer than $s/N^{1/d}$ to approach $(2s)^d$, as it does for independent random points. Instead, along infinitely many block lengths, an excess of pairs lie in a narrow annulus of distances, and the paper's general criterion (Proposition 1) shows this annulus excess is incompatible with the Poissonian limit. This confirms a conjecture posed in earlier work and extends known one-dimensional negative results. The main tool is a self-contained criterion that turns a local regularity of a sequence into a proof of non-Poissonian behavior.

What carries the argument

The load-bearing object is Proposition 1, the annulus criterion: a sequence that, for infinitely many $N$, has at least $cN$ pairs at sup-norm distances in $(a/N^{1/d}, b/N^{1/d}]$ with $c>(2b)^d-(2a)^d$ cannot have Poissonian pair correlations. For digital sequences, the supporting machinery is a change-of-basis matrix $S$ (Lemma 2) that makes the difference vector between paired points explicit and sparse, so that the annulus count can be computed; this uses invariance of digital $(t,e,d)$-sequences under right multiplication by non-singular upper triangular (NUT) matrices. For Halton sequences, the supporting machinery is a Diophantine approximation lemma (Lemma 3) that finds simultaneous approximants of the numbers $\log_{\beta_j}(\beta_1)$ accumulating at cube-corner values, which selects block lengths where the first coordinate dominates all others in the distance calculation.

What would settle it

For a small explicit instance of the column-by-column construction (for example, $d=2$ over $\mathbb{F}_2$ with $q_1(x)=x$ and $q_2(x)=x+1$), compute the transformed matrices $C^{(j)}S$ from Lemma 2 and test the row-length bound $L_f \le d f$ for every $f$ that is a multiple of $v=\operatorname{lcm}(e_1,e_2)$; if any such $f$ violates the bound, the sparse difference vector used in the proof of Theorem 1 is not available. A direct count of pairs in the annulus $(a/N^{1/d}, b/N^{1/d}]$ for $N=2q^m$ on the same instance should also reproduce the claimed excess of at least $cN$ pairs.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorems 1 and 2, is that digital $(0,e,d)$-sequences generated by the Niederreiter construction or by the alternative column-by-column construction, and Halton sequences in pairwise coprime integer bases, do not have Poissonian pair correlations under the sup-norm definition (1). These sequences are uniformly distributed, so the theorems separate uniform distribution from the stronger random-like local statistics measured by pair correlations. For each family the proof produces infinitely many block lengths $N$ for which at least $cN$ pairs have sup-norm distance in $(a/N^{1/d}, b/N^{1/d}]$ with $c > (2b)^d-(2a)^d$; by Proposition 1, such an excess of near-duplicate distances rules out Poissonian pair correlations.

Load-bearing premise

The proof rests on the technical lemma that a particular change of basis applied to the generating matrices preserves the digital $(0,e,d)$-sequence property and a row-length bound $L_f \le d f$; for the Niederreiter construction the lemma is cited from earlier work, while for the column-by-column construction it is asserted in one sentence, and if it failed the explicit distance formulas used to count pairs would collapse.

Editorial extensions

If this is right

Uniform distribution is strictly weaker than Poissonian pair correlations for these sequences: each family is uniformly distributed, yet fails the pair-correlation limit along an infinite subsequence of block lengths.
Digital $(0,e,d)$-sequences from the Niederreiter and column-by-column constructions, and Halton sequences in pairwise coprime bases, cannot serve as examples of d-dimensional sequences with Poissonian pair correlations.
The general criterion (Proposition 1) gives a template for analyzing additional $(t,s)$-sequence classes, such as generalized Niederreiter or Niederreiter-Xing constructions, by verifying the same annulus excess.
For Halton sequences, the proof is carried out without resolving an open problem on linear independence of numbers like $1/\log 2$, $1/\log 3$ and $1/\log 5$; if that independence were known, the simultaneous-approximation step would simplify considerably.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Read as a sufficient condition, Proposition 1 offers a concrete test for non-Poissonian behavior: look for long blocks where many shifted pairs land in a narrow distance annulus, and other digit-based sequences beyond those treated here can be checked for the same signature.
The Halton proof's reliance on accumulation points at cube corners suggests that any family built from radical-inverse functions in coprime bases will exhibit structurally similar pair collisions, a prediction that could be tested on generalized Halton variants.
For quasi-Monte Carlo practice, the theorems imply that low discrepancy does not certify random-like local spacing; users who need Poissonian local statistics must look beyond these standard constructions.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline: this paper gives a genuinely new negative result—Halton and Niederreiter sequences in higher dimensions do not have Poissonian pair correlations—and it does so with a general criterion that is clean enough to reuse. The results are not a repackaging of earlier 1D work. The criterion, Proposition 1, is quite elegant: it says enough pairs in a thin annulus around a fixed radius contradicts Poissonian scaling, with the constants chosen so the annulus count exceeds the difference between the two balls. That part is rigorous and complete.

The Halton proof is the stronger half. It spells out the construction of subintervals, the use of Minkowski to find accumulating fractional parts of logs, and the counting of good n; the constants a,b,c are explicit and condition (12) is verified. I checked the reasoning and it holds.

The digital-sequence proof is credible but noticeably terser. The main load-bearing point is Lemma 2, which says that after multiplying by the NUT matrix S, the column-by-column generating matrices still give a (0,e,d)-sequence with row-length bound L_f ≤ d f. For the Niederreiter construction this is cited from [10]; for the column-by-column construction it is justified in one sentence via linearity and basis change. On reading the actual proof of Theorem 1, yes, this bound is exactly what forces the last column of D S to be zero, so the entire shape of Δ depends on it. The stress-test note checked the valuation arithmetic and found no counterexample; I believe the bound is true, but the paper does not show it. That is a real gap in exposition, not a fatal error. A referee should ask for the derivation.

The other small thing: the 'at least Mm/q values of n' claim in Theorem 1 is asserted without proof, but that is a minor counting fact.

Citation pattern is fine. The reliance on [10] is legitimate for the Niederreiter case. No self-citation inflation.

Who should read this? People working on pair correlations of low-discrepancy sequences and uniform distribution—and anyone using Halton or Niederreiter in QMC who wants to know their theoretical fine-scale behavior. It is not a practical integration paper.

My call: send it to peer review. It deserves a serious referee. The verdict will likely be accept after the authors expand Lemma 2's proof and the one-sentence justifications around it.

Referee Report

1 major / 4 minor

Summary. This paper proves that two classical multidimensional low-discrepancy sequences—digital (0,e,d)-sequences generated by the Niederreiter construction or the alternative column-by-column construction, and Halton sequences in pairwise coprime integer bases—do not have Poissonian pair correlations under the d-dimensional sup-norm definition (1). The authors introduce a general criterion (Proposition 1): if along a subsequence N_k there are at least c N_k ordered pairs with sup-norm distance in an annulus (a/N_k^{1/d}, b/N_k^{1/d}] with c > (2b)^d - (2a)^d, then the sequence cannot have Poissonian pair correlations. They then verify this condition for both families. For digital sequences, they use a NUT-scrambling matrix S (Lemma 2) to force the difference vector between paired points to equal a fixed column of S, yielding a precise interval for the sup-norm distance. For Halton sequences, they construct many pairs n, n+M whose distance is controlled by the first coordinate, using congruences and an approximation lemma for irrational rotations (Lemma 3).

Significance. If correct, the paper closes a natural gap in the theory of pair correlations, confirming a conjecture of Larcher and Stockinger for Halton sequences and extending known one-dimensional negative results to two prominent multidimensional families. The general criterion in Proposition 1 is clean, rigorous, and likely to be reused. The Halton proof is self-contained, checks all constants explicitly, and verifies the required inequality (12). The digital proof is conceptually convincing and, modulo Lemma 2, provides the needed annulus count with explicit constants. The main weakness is that Lemma 2's column-by-column half is only sketched; because that lemma is load-bearing for Theorem 1, the manuscript as written is not fully complete, though the gap appears repairable.

major comments (1)

[Section 2.1, Lemma 2] For the column-by-column construction, the proof consists of a single sentence invoking 'linearity' and the fact that (1,x,x^2,...) and (1,p_1(x),p_2(x),...) are both bases. The crucial bound L_f ≤ d f for v|f is not derived. This bound is exactly what makes the last column of D_{m×(m+1)}S_{m+1} vanish in the proof of Theorem 1, forcing S^{-1}Δ = (0,...,0,φ^{-1}(1))^T and hence the explicit form of Δ used to derive the distance interval. If this bound were to fail, the annulus count in Proposition 1 could not be established. Please provide a complete derivation of the row-length bound for the column-by-column construction, or give a precise independent reference.

minor comments (4)

[Section 2.1, after Eq. (3)] The definition of L_f is somewhat ambiguous; please state explicitly that L_f is the maximum, over all first f rows of all generating matrices, of one plus the index of the last nonzero column, and specify how identically zero rows are treated.
[Section 2.2, proof of Theorem 2] In the paragraph after Eq. (6), the line 'if in (n)_{b1} we have that n_{uτ k 1} ≠ b_1 − 1' contains a typo; it should read n_{uτ_1k_1} ≠ b_1 − 1.
[Section 2.2, Lemma 3] The sentence 'if ε_j are chosen small enough the integers z_i^{(0)} will be distinct' is terse; the choice of N and ε_j must satisfy both the Minkowski volume condition and ε_j < 1/2, and distinctness follows because for a fixed z_0 the inequalities |α_j z_0 − z_j| ≤ ε_j determine z_j uniquely when ε_j < 1/2.
[Section 2.1, proof of Theorem 1] After selecting n with the maximal digit difference, the count leading to c = 1/q counts ordered pairs; it may help the reader to state explicitly that each selected pair (n,l) also contributes the reversed ordered pair (l,n).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the target theorems follow from an independent sufficient criterion and external construction facts; the self-citations are not load-bearing in a circular sense.

full rationale

The derivation chain is not circular. Proposition 1 is an independent sufficient condition: assuming Poissonian pair correlations, the paper bounds the count in a small ball by (2b)^d and in a smaller ball by (2a)^d, and the assumed annulus count cN_k with c > (2b)^d - (2a)^d produces a contradiction; no property of Niederreiter or Halton sequences is assumed in Proposition 1 itself. For the digital sequences, Lemma 1 is cited from Faure and Tezuka, and Lemma 2 for the Niederreiter construction is cited from Hofer and Pirsic [10]; although [10] is a self-citation, it supplies a parameter-free construction fact (that C^(j)S generate a digital (0,e,d)-sequence with L_f <= df) whose assumptions do not include the target statement 'not Poissonian', and the target conclusion is obtained only after the subsequent difference-vector and annulus-count argument. The column-by-column half of Lemma 2 is justified in one sentence by linearity and the fact that the p_k(x) form a basis; this is an expository gap if the row-length bound is nontrivial, but it is not circular, because the asserted bound is not the conclusion being proved. No parameters are fitted to data and renamed as predictions: the constants a,b,c in both proofs are explicitly defined from the sequence parameters (w, q, u, xi_j, b_j) and are shown to satisfy the required inequality (3). The Halton proof uses the Chinese Remainder Theorem, Minkowski's theorem via Lemma 3, and an accumulation-point argument for ({n log_{beta_j} beta_1}); this is independent external mathematics, not a renaming of the desired result. No uniqueness theorem or ansatz is imported from the authors' prior work to forbid alternatives. The only caveat worth flagging is the terseness of the column-by-column case of Lemma 2, which is a correctness/exposition concern, not evidence that the paper's derivation is equivalent to its inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters fitted to data and no invented entities. The proof depends on standard QMC constructions, Minkowski's theorem, Euler and CRT order arguments, and one cited structural lemma [10] by an overlapping author; this is independent support rather than circularity.

assumptions (6)

domain assumption Niederreiter and column-by-column constructions generate digital (0,e,d)-sequences with the stated properties.
Standard results in the digital sequence literature, cited to [21, 9] and [8, Theorem 1].
domain assumption Multiplying generating matrices by a NUT matrix preserves the digital (t,e,d)-sequence property (Lemma 1).
Cited as [4, Prop. 1]; needed for the transformation step in Lemma 2.
domain assumption Lemma 2 row-length bound L_f <= d f for the transformed Niederreiter and column-by-column matrices.
For Niederreiter cited from [10]; for the alternative construction asserted with a one-line linearity and basis argument.
standard math Minkowski's theorem on convex symmetric bodies in R^d.
Used in Lemma 3 to prove that ({n alpha}) has an accumulation point at a vertex of the unit cube.
standard math Euler's theorem and the Chinese Remainder Theorem guarantee the periods tau_i exist and control digit shifts.
Used in the Halton proof for the congruences in (6) and for the point counts in elementary intervals.
standard math Freshman's dream binomial congruence over F_q when the exponent is a power of the characteristic.
Used in the digital proof to simplify products of polynomials with exponents u powers of p.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Pair Correlations of Niederreiter and Halton Sequences are not Poissonian." pith.science (2026). https://pith.science/paper/OWSPUWOZ

@misc{pith2026190811147,
  author       = {Pith},
  title        = {Pith review of: Pair Correlations of Niederreiter and Halton Sequences are not Poissonian},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OWSPUWOZ}},
  note         = {Machine review of arXiv:1908.11147}
}

read the original abstract

Niederreiter and Halton sequences are two prominent classes of multi-dimensional sequences which are widely used in practice for numerical integration methods because of their excellent distribution qualities. In this paper, we show that these sequences - even though they are uniformly distributed - fail to satisfy the stronger property of Poissonian pair correlations. This extends already established results for one-dimensional sequences and confirms a conjecture of Larcher and Stockinger. The proofs rely on a general tool which identifies specific regularities of a sequence to be sufficient for not having Poissonian pair correlations.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[10]

Hofer and G

R. Hofer and G. Pirsic, A ﬁnite-row scrambling of Nieder reiter sequences, Monte Carlo and Quasi-Monte Carlo Methods 2012 , pp.427-437, Springer, Berlin, 2013

work page 2012
[1]

Aichinger, C

I. Aichinger, C. Aistleitner and G. Larcher, On Quasi-En ergy-Spectra, Pair Cor- relations of Sequences and Additive Combinatorics, Contemporary Computational Mathematics - a celebration of the 80th birthday of Ian Sloan , pp.1-16, Springer International Publishing, Cham, 2018

work page 2018
[2]

Aisleitner, T

C. Aisleitner, T. Lachmann and F. Pausinger, Pair correl ations and equidistribu- tion, Journal of Number Theory , 182:206-220, 2018

work page 2018
[3]

Dick and F

J. Dick and F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration , Cambridge University Press, New York, 2010 16

work page 2010
[4]

Faure and S

H. Faure and S. Tezuka, Another random scrambling of digi tal ( t, s )-sequences, Monte Carlo and Quasi-Monte Carlo Methods 2000 , pp.242-256, Springer, Berlin, 2002

work page 2000
[5]

Grepstad and G

S. Grepstad and G. Larcher, On pair correlation and discr epancy, Archiv der Mathematik, 109(2):143-149, 2017

work page 2017
[6]

J. H. Halton, On the eﬃciency of certain quasi-random seq uences of points in evaluating multi-dimensional integrals, Numerische Mathematik , 2(1):84-90, 1960

work page 1960
[7]

Hinrichs, L

A. Hinrichs, L. Kaltenböck, G. Larcher, W. Stockinger an d M. Ullrich, On a multi-dimensional Poissonian pair correlation concept an d uniform distribution, Monatshefte für Mathematik , 190(2):333–352, 2019

work page 2019

Show all 24 references

[8]

Hofer, A construction of low-discrepancy sequences i nvolving ﬁnite-row digital (t, s )-sequences, Monatshefte für Mathematik , 171(1):77-89, 2013

R. Hofer, A construction of low-discrepancy sequences i nvolving ﬁnite-row digital (t, s )-sequences, Monatshefte für Mathematik , 171(1):77-89, 2013

2013
[9]

Hofer and H

R. Hofer and H. Niederreiter, A construction of ( t, s )-sequences with ﬁnite-row generating matrices using global function ﬁelds. Finite Fields and Their Applica- tions, 21, 2012

2012
[11]

Larcher and W

G. Larcher and W. Stockinger, On Pair Correlation of Seq uences, arXiv:1903.09978, 2019

1903 arXiv
[12]

Larcher and W

G. Larcher and W. Stockinger, Some negative results rel ated to Poissonian pair correlation problems, to appear in: Discrete Mathematics, arXiv:1803.052361, 2019

2019 arXiv
[13]

M. B. Levin, On the upper bound of the Lp discrepancy of Halton’s sequence and the Central Limit Theorem for Hammersley’s net, arXiv:1806 .11498, 2018

2018
[14]

Minkowski, Geometrie der Zahlen , Chelsea Publishing Company, reprint 1953

H. Minkowski, Geometrie der Zahlen , Chelsea Publishing Company, reprint 1953

1953
[15]

Niederreiter, Low-discrepancy and low-dispersion sequences, Journal of Num- ber Theory, 30(1):51-70, 1988

H. Niederreiter, Low-discrepancy and low-dispersion sequences, Journal of Num- ber Theory, 30(1):51-70, 1988

1988
[16]

Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods , SIAM, Philadelphia, 1992

H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods , SIAM, Philadelphia, 1992

1992
[17]

Marklof, Pair correlations and equidistribution on manifolds, Monatshefte für Mathematik, 2019

J. Marklof, Pair correlations and equidistribution on manifolds, Monatshefte für Mathematik, 2019

2019
[18]

Pillichshammer, On the discrepancy of (0 , 1)-sequences, Journal of Number Theory, 104(2):301-314, 2004 17

F. Pillichshammer, On the discrepancy of (0 , 1)-sequences, Journal of Number Theory, 104(2):301-314, 2004 17

2004
[19]

Steinerberger, Localized quantitative criteria fo r equidistribution, Acta Arith- metica, 180:183-199, 2017

S. Steinerberger, Localized quantitative criteria fo r equidistribution, Acta Arith- metica, 180:183-199, 2017

2017
[20]

Steinerberger, Poissonian pair correlation in high er dimensions, Journal of Number Theory, 2019

S. Steinerberger, Poissonian pair correlation in high er dimensions, Journal of Number Theory, 2019

2019
[21]

Tezuka, On the discrepancy of generalized Niederrei ter sequences, Journal of Complexity, 29(3):240-247, 2013

S. Tezuka, On the discrepancy of generalized Niederrei ter sequences, Journal of Complexity, 29(3):240-247, 2013

2013
[22]

Tezuka, Polynomial Arithmetic Analogue of Halton Se quencesm ACM Trans- actions on Modeling and Computer Simulation , 3:99-107, 1993

S. Tezuka, Polynomial Arithmetic Analogue of Halton Se quencesm ACM Trans- actions on Modeling and Computer Simulation , 3:99-107, 1993

1993
[23]

M. Waldschmidt, Diophantine Approximation on Linear Algebraic Groups: Tra n- scendence Properties of the Exponential Function in Severa l Variables , Grundle- heren der mathematischen Wissenschaften, 326, Springer Be rlin Heidelberg, 2000

2000
[24]

C. P. Xing and H. Niederreiter, A construction of low-di screpancy sequences using global function ﬁelds, Acta Arithmetica, 73(1):87-102, 1995 Author’s Addresses: Roswitha Hofer and Lisa Kaltenböck, Institut für Finanzmat hematik und Angewandte Zahlentheorie, Johannes Kepler U...

1995

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [10]

Hofer and G

R. Hofer and G. Pirsic, A ﬁnite-row scrambling of Nieder reiter sequences, Monte Carlo and Quasi-Monte Carlo Methods 2012 , pp.427-437, Springer, Berlin, 2013

work page 2012

[2] [1]

Aichinger, C

I. Aichinger, C. Aistleitner and G. Larcher, On Quasi-En ergy-Spectra, Pair Cor- relations of Sequences and Additive Combinatorics, Contemporary Computational Mathematics - a celebration of the 80th birthday of Ian Sloan , pp.1-16, Springer International Publishing, Cham, 2018

work page 2018

[3] [2]

Aisleitner, T

C. Aisleitner, T. Lachmann and F. Pausinger, Pair correl ations and equidistribu- tion, Journal of Number Theory , 182:206-220, 2018

work page 2018

[4] [3]

Dick and F

J. Dick and F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration , Cambridge University Press, New York, 2010 16

work page 2010

[5] [4]

Faure and S

H. Faure and S. Tezuka, Another random scrambling of digi tal ( t, s )-sequences, Monte Carlo and Quasi-Monte Carlo Methods 2000 , pp.242-256, Springer, Berlin, 2002

work page 2000

[6] [5]

Grepstad and G

S. Grepstad and G. Larcher, On pair correlation and discr epancy, Archiv der Mathematik, 109(2):143-149, 2017

work page 2017

[7] [6]

J. H. Halton, On the eﬃciency of certain quasi-random seq uences of points in evaluating multi-dimensional integrals, Numerische Mathematik , 2(1):84-90, 1960

work page 1960

[8] [7]

Hinrichs, L

A. Hinrichs, L. Kaltenböck, G. Larcher, W. Stockinger an d M. Ullrich, On a multi-dimensional Poissonian pair correlation concept an d uniform distribution, Monatshefte für Mathematik , 190(2):333–352, 2019

work page 2019