HEXAGONbeta

Low-discrepancy quasi-uniform digital sequences in every dimension

A mix of human-written and AI-generated textHuman understanding: some partsmath.NA — Numerical Analysismath.MG — Metric Geometrymath.NT — Number Theory

Contributed by Leonhard Gruenschloss ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

A sequence of points in the unit cube is quasi-uniform if its first NN points are spread like a grid for every NN: no two of them are closer, and no empty ball between them is larger, than a constant times N−1/sN^{-1/s} in dimension ss. Dick, Goda and Suzuki asked for such sequences among the digital sequences of quasi-Monte Carlo integration, and Goda, Hofer and Suzuki asked whether any Halton-type sequence is quasi-uniform. We show that in dimension two and higher no Halton-type sequence, no Sobol' sequence, no classical Niederreiter sequence and no Faure sequence is quasi-uniform, and that linear scrambles of all coordinates but one do not help: a carry in the last digits of one coordinate leaves the leading digits of all others unchanged, giving explicit pairs of points that are far too close. We then show that one fixed linear scramble of a generalized Faure sequence, the same for all numbers of points, repairs this. In it, the digits of all coordinates at one scale are residues of one rational function, each taken at the coordinate's own point of the projective line, so the residue theorem ties the coordinates together and a carry in one coordinate is seen by the others. For every dimension ss and every prime base p>2sp>2^s this gives explicit quasi-uniform digital (0,s)(0,s)-sequences, hence of low discrepancy, whose first N=psK−1N=p^{sK-1} points are at least (1−2p−1/s)N−1/s(1-2p^{-1/s})N^{-1/s} apart, for every KK; in dimensions two and three, for every prime p≥5p\ge5, a variant keeps its first NN points at least (1−2/p)N−1/s(1-2/p)N^{-1/s} apart whenever NN is a power of ps2p^{s^2}. For such scrambles, exact linear rules that place every point inside its cell as a function of the last few digits of the cell's index can hold at no more than about one in ss of the sizes psKp^{sK}; with allowed ranges instead of exact rules we certify all of these sizes, with points at least (1−O(1/p))N−1/s(1-O(1/p))N^{-1/s} apart for large pp. Quasi-uniform digital sequences follow in every prime base p≥3p\ge3 in dimension three, and in every prime base in dimension two, base two included. Some steps are computer-assisted.

Provenance statement

The constructions, proofs and Lean formalization were produced by an AI system (Anthropic Claude Opus 5.5) under the author's direction. The author selected the problems, steered the research and reviewed the formal statements, but has not verified every proof by hand; the computer-assisted parts are exact finite computations whose scope is stated with each result. AI systems are not listed as authors; responsibility for this work rests with the author.\n\nAI system: Anthropic Claude Opus 5.5, run as agentic Claude Code sessions with sub-agents, explored constructions, proved the results, wrote the computational programs and the Lean 4 formalization, drafted the manuscript and ran adversarial review rounds. The author chose the problems and direction, steered and redirected the work, selected the results, and reviewed and signed off the four statements of the Palomar entry and its abstract (2026-10-29); the other library statements the author accepts on the basis of AI-prepared statement-review notes. Human understanding is partial ('some'). Verification: the formalized results are checked by Comparator (Lean kernel and NanoDa); two headline results are also a Palomar entry (PALOMAR-2026-10-29-000041: https://palomar-registry.org/entry?id=PALOMAR-2026-10-29-000041&version=1); the computer-assisted parts are checked by at least two programs each, archived with their data (https://github.com/lgruen/quasi-uniform-sequences-lean, directory archive/; Zenodo doi:10.5281/zenodo.23769767, all versions; release v1.0.0: doi:10.5281/zenodo.23769768); interactive explainers at https://lgruen.github.io/quasi-uniform-sequences-lean/explainers/. Companion paper: hexagon:2610.00217v1. A fuller account is in anc/ai_process_summary.md.
AI provenance filesai_process_summary.md · 5 KB

Formalizations

Tools used

Anthropic
Claude OpusVersion 5.5
Lean
LeanVersion v4.35.0-rc3

References

  1. Abdalla G. M. Ahmed and Peter Wonka, Optimizing dyadic nets , ACM Trans. Graph. 40 (2021), no. 4, 141:1--141:17.
  2. I. A. Antonov and V. M. Saleev, An economic method of computing LPτLP_\tau -sequences , USSR Comput. Math. Math. Phys. 19 (1979), no. 1, 252--256.
  3. Nicolas Bonneel, David Coeurjolly, and Victor Ostromoukhov, Perfectly equidistributed quasi- M onte C arlo sequences from A rtin-- S chreier polynomials , 2026, arXiv:2607.15141.arXiv
  4. Paul Bratley and Bennett L. Fox, Algorithm 659: Implementing S obol's quasirandom sequence generator , ACM Trans. Math. Software 14 (1988), no. 1, 88--100.
  5. Per Christensen, Andrew Kensler, and Charlie Kilpatrick, Progressive multi-jittered sample sequences , Comput. Graph. Forum 37 (2018), no. 4, 21--33, Proc. EGSR 2018.
  6. Gilles Christol, Ensembles presque périodiques kk-reconnaissables , Theoret. Comput. Sci. 9 (1979), no. 1, 141--145.
  7. Gilles Christol, Teturo Kamae, Michel Mendès France, and Gérard Rauzy, Suites algébriques, automates et substitutions , Bull. Soc. Math. France 108 (1980), 401--419.
  8. John H. Conway and Neil J. A. Sloane, Sphere packings, lattices and groups , 3 ed., Springer, 1999.
  9. Josef Dick, Takashi Goda, Gerhard Larcher, Friedrich Pillichshammer, and Kosuke Suzuki, On the quasi-uniformity properties of quasi- M onte C arlo point sets and sequences, P art I : lattices and K ronecker sequences , Math. Comp. (2026), Published online; arXiv:2502.06202 (theorem numbers cited from arXiv v2).arXiv
  10. Josef Dick, Takashi Goda, and Kosuke Suzuki, On the quasi-uniformity properties of quasi- M onte C arlo point sets and sequences, P art II : digital nets and sequences , Math. Comp. (2026), Published online; arXiv:2501.18226 (theorem numbers cited from arXiv v2).arXiv
Show all 42 referencesShow fewer references
  1. Josef Dick and Friedrich Pillichshammer, Digital nets and sequences: Discrepancy theory and quasi- M onte C arlo integration , Cambridge Univ. Press, 2010.
  2. Henri Faure, Discrépance de suites associées à un système de numération (en dimension ss) , Acta Arith. 41 (1982), 337--351.
  3. Henri Faure and Shu Tezuka, Another random scrambling of digital (t,s)(t,s)-sequences , Monte C arlo and Quasi- M onte C arlo Methods 2000 (Kai-Tai Fang, Harald Niederreiter, and Fred J. Hickernell, eds.), Springer, Berlin, 2002, pp. 242--256.
  4. Takashi Goda, The S obol' sequence is not quasi-uniform in dimension 2 , Proc. Amer. Math. Soc. 152 (2024), no. 8, 3209--3213, arXiv:2311.05830.arXiv
  5. — , Algebraic constructions of point sequences with quasi-uniform two-dimensional projections , 2026, arXiv:2608.12690.arXiv
  6. Takashi Goda, Roswitha Hofer, and Kosuke Suzuki, Disproving the quasi-uniformity of the H alton sequences and of some H alton-type sequences , J. Complexity 95 (2026), 102047, arXiv:2511.21153 (theorem numbers cited from arXiv v2).arXiv
  7. Takashi Goda and Hengjun Xu, Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling , 2026, arXiv:2609.05986.arXiv
  8. Leonhard Gruenschloss, Low-discrepancy quasi-uniform digital nets in every dimension , Hexagon preprint hexagon:2610.00217v1, 2026, Version 1, 2026-10-13; manuscript, Lean formalization and blueprint deposited at Zenodo, doi:10.5281/zenodo.23327748; Lean entry in the Palomar registry, PALOMAR-2026-10-13-000011.hexagonDOI
  9. Leonhard Grünschloß, Johannes Hanika, Ronnie Schwede, and Alexander Keller, (t,m,s)(t,m,s)-nets and maximized minimum distance , Monte Carlo and Quasi-Monte Carlo Methods 2006 (Alexander Keller, Stefan Heinrich, and Harald Niederreiter, eds.), Springer, 2008, pp. 397--412.
  10. Leonhard Grünschloß and Alexander Keller, (t,m,s)(t,m,s)-nets and maximized minimum distance, P art II , Monte Carlo and Quasi-Monte Carlo Methods 2008 (Pierre L'Ecuyer and Art B. Owen, eds.), Springer, 2009, pp. 395--409.
  11. Andrew Helmer, Per Christensen, and Andrew Kensler, Stochastic generation of (t,s)(t,s) sample sequences , Eurographics Symposium on Rendering -- DL-only Track (Adrien Bousseau and Morgan McGuire, eds.), The Eurographics Association, 2021, pp. 21--33.
  12. Roswitha Hofer, A construction of low-discrepancy sequences involving finite-row digital (t,s)(t,s)-sequences , Monatsh. Math. 171 (2013), no. 1, 77--89.
  13. — , Halton-type sequences in rational bases in the ring of rational integers and in the ring of polynomials over a finite field , Math. Comput. Simulation 143 (2018), 78--88.
  14. Roswitha Hofer and Kosuke Suzuki, A complete classification of digital (0,m,3)(0,m,3)-nets and digital (0,2)(0,2)-sequences in base 22 , Unif. Distrib. Theory 14 (2019), 43--52, arXiv:1807.04383.arXiv
  15. Stephen Joe and Frances Y. Kuo, Constructing S obol sequences with better two-dimensional projections , SIAM J. Sci. Comput. 30 (2008), no. 5, 2635--2654.
  16. N. M. Korobov, The approximate computation of multiple integrals , Dokl. Akad. Nauk SSSR 124 (1959), 1207--1210.
  17. Gerhard Larcher and Friedrich Pillichshammer, Walsh series analysis of the L2L_2 -discrepancy of symmetrisized point sets , Monatsh. Math. 132 (2001), no. 1, 1--18.
  18. Jiří Matoušek, On the L2L_2 -discrepancy for anchored boxes , J. Complexity 14 (1998), 527--556.
  19. David J. S. Mayor and Harald Niederreiter, A new construction of (t,s)(t,s)-sequences and some improved bounds on their quality parameter , Acta Arith. 128 (2007), no. 2, 177--191.
  20. Harald Niederreiter, Point sets and sequences with small discrepancy , Monatsh. Math. 104 (1987), 273--337.
  21. — , Random number generation and quasi- M onte C arlo methods , CBMS-NSF Regional Conf. Ser. in Appl. Math., vol. 63, SIAM, Philadelphia, 1992.
  22. Harald Niederreiter and Ferruh Ö zbudak, Low-discrepancy sequences using duality and global function fields , Acta Arith. 130 (2007), no. 1, 79--97.
  23. Art B. Owen, Randomly permuted (t,m,s)(t,m,s)-nets and (t,s)(t,s)-sequences , Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (Harald Niederreiter and Peter Jau-Shyong Shiue, eds.), Lecture Notes in Statist., vol. 106, Springer, 1995, pp. 299--317.
  24. Luc Pronzato and Anatoly Zhigljavsky, Quasi-uniform designs with optimal and near-optimal uniformity constant , J. Approx. Theory 294 (2023), 105931, arXiv:2112.10401.arXiv
  25. Naoki Sakai and Takashi Goda, Space-filling lattice designs for computer experiments , 2026, arXiv:2602.15390.arXiv
  26. Ian H. Sloan and Stephen Joe, Lattice methods for multiple integration , Oxford Univ. Press, 1994.
  27. I. M. Sobol' and B. V. Shukhman, Quasi-random points keep their distance , Math. Comput. Simulation 75 (2007), no. 3--4, 80--86.
  28. Ilya M. Sobol', On the distribution of points in a cube and the approximate evaluation of integrals , Zh. Vychisl. Mat. Mat. Fiz. 7 (1967), 784--802, English transl. USSR Comput. Math. Math. Phys. 7 (1967) 86--112, doi:10.1016/0041-5553(67)90144-9.DOI
  29. Kosuke Suzuki, Separation properties of scrambled digital nets and related random point sets , 2026, arXiv:2607.29063.arXiv
  30. — , Exact ℓ∞\ell^\infty-separation radius of the S obol' sequence in dimension 22 , J. Approx. Theory 321--322 (2027), 106356, arXiv:2508.14803 (titled `` of S obol' sequences in dimension 2'' there).arXiv
  31. Shu Tezuka, Polynomial arithmetic analogue of H alton sequences , ACM Trans. Model. Comput. Simul. 3 (1993), 99--107.
  32. — , Uniform random numbers: Theory and practice , Kluwer, 1995.

Version history

  1. v1Submitted by Leonhard GruenschlossInitial depositCurrentOct 30, 2026