HEXAGONbeta

Low-discrepancy quasi-uniform digital nets in every dimension

Primarily AI-generated textHuman understanding: some partsmath.NA — Numerical Analysismath.MG — Metric Geometrymath.NT — Number Theory

Contributed by Leonhard Gruenschloss ↗

Version 1 / Oct 14, 2026 / CC BY 4.0

Abstract

Dick, Goda and Suzuki asked for low-discrepancy digital nets that are quasi-uniform, with minimum distance δ\delta and covering radius both of the optimal order N−1/sN^{-1/s}, and stated the problem as open in dimension s≥3s\ge3. We construct such nets in every dimension. For every s≥3s\ge3, every base qq whose prime factors are at least s−1s-1, and every k≥1k\ge1, we give explicit digital (0,sk,s)(0,sk,s)-nets over Z/qZ\Z/q\Z with N=qskN=q^{sk} points, covering radius at most s N−1/s\sqrt s\,N^{-1/s}, and δN1/s≥1−as∗/q\delta N^{1/s}\ge1-a^*_s/q once q≥5as∗+4q\ge5a^*_s+4. The constant as∗≤eslog⁡s+O(s)a^*_s\le e^{s\log s+O(s)} is computed from ss by a deterministic polynomial-time lattice algorithm. In dimension three every N=pmN=p^m, m≥3m\ge3, is covered for each prime p≥37p\ge37, and, with computer assistance, every N=2mN=2^m and N=3mN=3^m. In prime bases these families are well separated in the sense of Dick, Goda and Suzuki, and they stay so under every digital shift. One mechanism underlies all constructions. For N=qskN=q^{sk} it reads as follows. The first kk base-qq digits of a point's coordinates select a cube of side q−kq^{-k}, and a (0,sk,s)(0,sk,s)-net has exactly one point in each such cube. Digit k+1k+1 of each coordinate is a linear function of the first kk digits of all coordinates, because the net is digital. We choose this linear function so that, between the planes where this digit wraps around modulo qq or where a carry occurs among the first kk digits, the points lie on a translate of one lattice; for the main theorem this lattice is a slightly distorted copy of Zs\Z^s. All later digits move a point by less than 1/q1/q of the cube side. Part~II studies the constant KK in δN1/s=1−K/q+O(q−2)\delta N^{1/s}=1-K/q+O(q^{-2}). We prove lower bounds on KK when the linear maps have bounded coefficients. At N=q3N=q^3 we find the optimal KK among nets whose points lie on lines parallel to the main diagonal. With the cube-tiling theorems of Haj\'os and Keller we show that idealized lattices with one point per cube, whose points sit independently inside their cubes, cannot exceed δN1/s=1\delta N^{1/s}=1. When the positions inside the cubes are coupled, the value 11 can be exceeded: δN1/3→281/16\delta N^{1/3}\to\sqrt{281}/16 at N=p3N=p^3, δN1/5>1\delta N^{1/5}>1 for (0,5,5)(0,5,5)-nets from p=37p=37 on, and δN1/s→min⁡(s/2,2)\delta N^{1/s}\to\min(\sqrt s/2,\sqrt2) at N=pskN=p^{sk}, which is the E8E_8 value at s=8s=8 (limits as p→∞p\to\infty). The results are formalized in Lean~4, apart from some finite computations, which are checked by scripts.

Provenance statement

The constructions, proofs and Lean formalization were produced by AI systems (Anthropic Claude Opus 5.5; some early exploratory results used Claude Fable 5.1) 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. AI systems are not listed as authors; responsibility for the deposit rests with the author.\n\nAI systems: Anthropic Claude (Claude Opus 5.5; some early exploratory results: Claude Fable 5.1), 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 the formal statement of Theorem A (signed off 2026-10-12); the other library statements the author accepts on the basis of AI-prepared statement-review notes. Human understanding is partial ('some'). Verification: 616 statements of the Lean library checked by Comparator (Lean kernel and NanoDa), Theorem A also as a Palomar entry (PALOMAR-2026-10-13-000011, version 1: https://palomar-registry.org/entry?id=PALOMAR-2026-10-13-000011&version=1); programs recomputing every computed value and figure of the paper (https://github.com/lgruen/separated-nets-lean; archived at Zenodo, doi:10.5281/zenodo.23327748, all versions; release v1.0.0: doi:10.5281/zenodo.23327749); Lean blueprint at https://lgruen.github.io/separated-nets-lean/blueprint/; interactive explainers at https://lgruen.github.io/separated-nets-lean/explainers/. A fuller account is in anc/ai_process_summary.md."
AI provenance filesai_process_summary.md · 7 KB

Formalizations

Tools used

Anthropic
Claude FableVersion 5.1
Anthropic
Claude OpusVersion 5.5
Anthropic
Claude Code
Lean
Lean

References

  1. J. Brakensiek, M. Heule, J. Mackey, D. Narváez, The resolution of Keller's conjecture , J. Automat. Reason. 66 (2022) 277--300, doi:10.1007/s10817-022-09623-5; conference version in: IJCAR 2020, Lecture Notes in Comput. Sci. 12166, Springer, 2020, 48--65, doi:10.1007/978-3-030-51074-9_4; arXiv:1910.03740.arXivDOI
  2. E. S. Barnes, N. J. A. Sloane, New lattice packings of spheres , Canad. J. Math. 35 (1983) 117--130, doi:10.4153/cjm-1983-008-1.DOI
  3. H. Cohn, N. Elkies, New upper bounds on sphere packings I , Ann. of Math. 157 (2003) 689--714, doi:10.4007/annals.2003.157.689; arXiv:math/0110009.arXivDOI
  4. H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, M. Viazovska, The sphere packing problem in dimension 2424 , Ann. of Math. 185 (2017) 1017--1033, doi:10.4007/annals.2017.185.3.8; arXiv:1603.06518.arXivDOI
  5. R. R. Coveyou, R. D. MacPherson, Fourier analysis of uniform random number generators , J. ACM 14 (1967) 100--119, doi:10.1145/321371.321379.DOI
  6. R. L. Cook, Stochastic sampling in computer graphics , ACM Trans. Graph. 5 (1986) 51--72, doi:10.1145/7529.8927.DOI
  7. L. Clozel, H. Oh, E. Ullmo, Hecke operators and equidistribution of Hecke points , Invent. Math. 144 (2001) 327--351, doi:10.1007/s002220100126.DOI
  8. R. Cranley, T. N. L. Patterson, Randomization of number theoretic methods for multiple integration , SIAM J. Numer. Anal. 13 (1976) 904--914, doi:10.1137/0713071.DOI
  9. J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups , 3rd ed., Springer, 1999.
  10. J. Dick, T. Goda, G. Larcher, F. Pillichshammer, K. Suzuki, On the quasi-uniformity properties of quasi-Monte Carlo point sets and sequences, Part I: lattices and Kronecker sequences , Math. Comp. (2026), doi:10.1090/mcom/4264; arXiv:2502.06202 (theorem numbers cited from arXiv v2).arXivDOI
Show all 67 referencesShow fewer references
  1. J. Dick, T. Goda, K. Suzuki, On the quasi-uniformity properties of quasi-Monte Carlo point sets and sequences, Part II: digital nets and sequences , Math. Comp. (2026), doi:10.1090/mcom/4263; arXiv:2501.18226 (theorem numbers cited from arXiv v2).arXivDOI
  2. C.-J. de la Vallée Poussin, Recherches analytiques sur la théorie des nombres premiers , Ann. Soc. Sci. Bruxelles 20 B (1896) 183--256.
  3. L. de Moura, S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699, Springer, 2021, 625--635, doi:10.1007/978-3-030-79876-5_37.DOI
  4. J. Dick, F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration , Cambridge Univ. Press, 2010.
  5. A. Eskin, H. Oh, Ergodic theoretic proof of equidistribution of Hecke points , Ergodic Theory Dynam. Systems 26 (2006) 163--167, doi:10.1017/s0143385705000428; arXiv:math/0409507.arXivDOI
  6. H. Faure, Discrépance de suites associées à un système de numération (en dimension ss) , Acta Arith. 41 (1982) 337--351, doi:10.4064/aa-41-4-337-351.DOI
  7. H. Faure, C. Lemieux, Generalized Halton sequences in 2008: a comparative study , ACM Trans. Model. Comput. Simul. 19 (2009), Art. 15, 1--31, doi:10.1145/1596519.1596520.DOI
  8. T. Goda, R. Hofer, K. Suzuki, Disproving the quasi-uniformity of the Halton sequences and of some Halton-type sequences , J. Complexity 95 (2026) 102047, doi:10.1016/j.jco.2026.102047; arXiv:2511.21153 (theorem numbers cited from arXiv v2).arXivDOI
  9. L. Grünschloß, J. Hanika, R. Schwede, A. Keller, (t,m,s)(t,m,s)-nets and maximized minimum distance , in: A. Keller, S. Heinrich, H. Niederreiter (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer, 2008, 397--412, doi:10.1007/978-3-540-74496-2_23.DOI
  10. L. Grünschloß, A. Keller, (t,m,s)(t,m,s)-nets and maximized minimum distance, Part II , in: P. L'Ecuyer, A. B. Owen (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, Springer, 2009, 395--409, doi:10.1007/978-3-642-04107-5_25.DOI
  11. J. Hadamard, Sur la distribution des zéros de la fonction ζ(s)\zeta(s) et ses conséquences arithmétiques , Bull. Soc. Math. France 24 (1896) 199--220, doi:10.24033/bsmf.545.DOI
  12. G. Hajós, Über einfache und mehrfache Bedeckung des nn-dimensionalen Raumes mit einem Würfelgitter , Math. Z. 47 (1942) 427--467, doi:10.1007/bf01180974.DOI
  13. T. C. Hales, A proof of the Kepler conjecture , Ann. of Math. 162 (2005) 1065--1185, doi:10.4007/annals.2005.162.1065.DOI
  14. J. M. Hammersley, Monte Carlo methods for solving multivariable problems , Ann. New York Acad. Sci. 86 (1960) 844--874, doi:10.1111/j.1749-6632.1960.tb42846.x.DOI
  15. G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers , 6th ed., revised by D. R. Heath-Brown and J. H. Silverman, Oxford Univ. Press, 2008.
  16. X. He, Rotated sphere packing designs , J. Amer. Statist. Assoc. 112 (2017) 1612--1622, doi:10.1080/01621459.2016.1222289.DOI
  17. X. He, Interleaved lattice-based maximin distance designs , Biometrika 106 (2019) 453--464, doi:10.1093/biomet/asy069; arXiv:1807.02289.arXivDOI
  18. X. He, Lattice-based designs with quasi-optimal separation distance on all projections , Biometrika 108 (2021) 443--454, doi:10.1093/biomet/asaa057; arXiv:1709.02062.arXivDOI
  19. M. Hall, L. J. Paige, Complete mappings of finite groups , Pacific J. Math. 5 (1955) 541--549, doi:10.2140/pjm.1955.5.541.DOI
  20. R. Hofer, K. 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, doi:10.2478/udt-2019-0004; arXiv:1807.04383.arXivDOI
  21. R. Kannan, A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix , SIAM J. Comput. 8 (1979) 499--507, doi:10.1137/0208040.DOI
  22. D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms , 3rd ed., Addison-Wesley, 1997.
  23. W. Kositwattanarerk, F. Oggier, Connections between Construction D and related constructions of lattices , Des. Codes Cryptogr. 73 (2014) 441--455, doi:10.1007/s10623-014-9939-3; arXiv:1308.6175.arXivDOI
  24. N. M. Korobov, The approximate computation of multiple integrals , Dokl. Akad. Nauk SSSR 124 (1959) 1207--1210.
  25. R. Kritzinger, Dispersion of digital (0,m,2)(0,m,2)-nets , Monatsh. Math. 195 (2021) 155--171, doi:10.1007/s00605-021-01525-9; arXiv:2004.14760.arXivDOI
  26. H. W. Lenstra, Jr., Euclidean number fields of large degree , Invent. Math. 38 (1976/77) 237--254, doi:10.1007/bf01403131.DOI
  27. C. Lemieux, Tractability using periodized generalized Faure sequences , J. Complexity 31 (2015) 42--56, doi:10.1016/j.jco.2014.08.001.DOI
  28. C. Lemieux, H. Faure, New perspectives on (0,s)(0,s)-sequences , in: P. L'Ecuyer, A. B. Owen (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, Springer, 2009, 113--130, doi:10.1007/978-3-642-04107-5_7.DOI
  29. G. Larcher, H. Niederreiter, W. Ch. Schmid, Digital nets and sequences constructed over finite rings and their application to quasi-Monte Carlo integration , Monatsh. Math. 121 (1996) 231--253, doi:10.1007/bf01298952.DOI
  30. G. Larcher, F. Pillichshammer, Walsh series analysis of the L2L_2-discrepancy of symmetrisized point sets , Monatsh. Math. 132 (2001) 1--18, doi:10.1007/s006050170054.DOI
  31. J. C. Lagarias, P. W. Shor, Keller's cube-tiling conjecture is false in high dimensions , Bull. Amer. Math. Soc. (N.S.) 27 (1992) 279--283, doi:10.1090/s0273-0979-1992-00318-x; arXiv:math/9210222.arXivDOI
  32. J. Mackey, A cube tiling of dimension eight with no facesharing , Discrete Comput. Geom. 28 (2002) 275--279, doi:10.1007/s00454-002-2801-9.DOI
  33. J. Matoušek, On the L2L_2-discrepancy for anchored boxes , J. Complexity 14 (1998) 527--556, doi:10.1006/jcom.1998.0489.DOI
  34. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367--381, doi:10.1145/3372885.3373824.DOI
  35. F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes , North-Holland, 1977.
  36. H. Niederreiter, Point sets and sequences with small discrepancy , Monatsh. Math. 104 (1987) 273--337, doi:10.1007/bf01294651.DOI
  37. A. B. Owen, Randomly permuted (t,m,s)(t,m,s)-nets and (t,s)(t,s)-sequences , in: H. Niederreiter, P. J.-S. Shiue (eds.), Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Lecture Notes in Statist. 106, Springer, 1995, 299--317, doi:10.1007/978-1-4612-2552-2_19.DOI
  38. L. J. Paige, Complete mappings of finite groups , Pacific J. Math. 1 (1951) 111--116, doi:10.2140/pjm.1951.1.111.DOI
  39. O. Perron, Über lückenlose Ausfüllung des nn-dimensionalen Raumes durch kongruente Würfel , Math. Z. 46 (1940) 1--26, doi:10.1007/bf01181421; II , Math. Z. 46 (1940) 161--180, doi:10.1007/bf01181436.DOI
  40. L. Panek, M. Firer, M. M. S. Alves, Symmetry groups of Rosenbloom--Tsfasman spaces , Discrete Math. 309 (2009) 763--771, doi:10.1016/j.disc.2008.01.013.DOI
  41. R. M. Roth, G. Seroussi, On generator matrices of MDS codes (Corresp.) , IEEE Trans. Inform. Theory 31 (1985) 826--830, doi:10.1109/tit.1985.1057113.DOI
  42. M. Yu. Rosenbloom, M. A. Tsfasman, Codes for the mm-metric , Probl. Inf. Transm. 33 (1997) 45--52.
  43. L. Rudolph, The even-order Grünschloß--Keller permutation nets are (0,m,2)(0,m,2)-nets , preprint, Zenodo, version 1.0.0, 2026, doi:10.5281/zenodo.22264675.DOI
  44. N. Sakai, T. Goda, Space-filling lattice designs for computer experiments , arXiv:2602.15390 (2026).arXiv
  45. I. H. Sloan, S. Joe, Lattice Methods for Multiple Integration , Oxford Univ. Press, 1994.
  46. M. M. Skriganov, Coding theory and uniform distributions , Algebra i Analiz 13 (2001) 191--239; English transl. St. Petersburg Math. J. 13 (2002) 301--337; arXiv:math/9909163 (theorem numbers cited from the arXiv version).arXiv
  47. I. 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
  48. I. M. Sobol', B. V. Shukhman, Quasi-random points keep their distance , Math. Comput. Simulation 75 (2007) 80--86, doi:10.1016/j.matcom.2006.09.004.DOI
  49. K. Suzuki, Exact ℓ∞\ell^\infty-separation radius of Sobol' sequences in dimension 22 , arXiv:2508.14803 (2025).arXiv
  50. K. Suzuki, Separation properties of scrambled digital nets and related random point sets , arXiv:2607.29063 (2026).arXiv
  51. S. Tezuka, Polynomial arithmetic analogue of Halton sequences , ACM Trans. Model. Comput. Simul. 3 (1993) 99--107, doi:10.1145/169702.169694.DOI
  52. S. Tezuka, Uniform Random Numbers: Theory and Practice , Kluwer, 1995.
  53. R. Tavildar, P. Viswanath, Approximately universal codes over slow-fading channels , IEEE Trans. Inform. Theory 52 (2006) 3233--3258, doi:10.1109/tit.2006.876226; arXiv:cs/0512017.arXivDOI
  54. E. R. van Dam, B. Husslage, D. den Hertog, H. Melissen, Maximin Latin hypercube designs in two dimensions , Oper. Res. 55 (2007) 158--169, doi:10.1287/opre.1060.0317.DOI
  55. E. R. van Dam, G. Rennen, B. Husslage, Bounds for maximin Latin hypercube designs , Oper. Res. 57 (2009) 595--608, doi:10.1287/opre.1080.0604.DOI
  56. P. O. Vontobel, A. Ganesan, On universally decodable matrices for space-time coding , Des. Codes Cryptogr. 41 (2006) 325--342, doi:10.1007/s10623-006-9019-4; arXiv:cs/0601075.arXivDOI
  57. M. S. Viazovska, The sphere packing problem in dimension 88 , Ann. of Math. 185 (2017) 991--1015, doi:10.4007/annals.2017.185.3.7.DOI

Version history

  1. v1Submitted by Leonhard GruenschlossInitial depositCurrentOct 13, 2026