Low-discrepancy quasi-uniform digital nets in every dimension
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 and covering radius both of the optimal order , and stated the problem as open in dimension . We construct such nets in every dimension. For every , every base whose prime factors are at least , and every , we give explicit digital -nets over with points, covering radius at most , and once . The constant is computed from by a deterministic polynomial-time lattice algorithm. In dimension three every , , is covered for each prime , and, with computer assistance, every and . 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 it reads as follows. The first base- digits of a point's coordinates select a cube of side , and a -net has exactly one point in each such cube. Digit of each coordinate is a linear function of the first 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 or where a carry occurs among the first digits, the points lie on a translate of one lattice; for the main theorem this lattice is a slightly distorted copy of . All later digits move a point by less than of the cube side. Part~II studies the constant in . We prove lower bounds on when the linear maps have bounded coefficients. At we find the optimal 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 . When the positions inside the cubes are coupled, the value can be exceeded: at , for -nets from on, and at , which is the value at (limits as ). The results are formalized in Lean~4, apart from some finite computations, which are checked by scripts.
Provenance statement
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
- 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
- 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
- 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
- H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, M. Viazovska, The sphere packing problem in dimension , Ann. of Math. 185 (2017) 1017--1033, doi:10.4007/annals.2017.185.3.8; arXiv:1603.06518.arXivDOI
- 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
- R. L. Cook, Stochastic sampling in computer graphics , ACM Trans. Graph. 5 (1986) 51--72, doi:10.1145/7529.8927.DOI
- L. Clozel, H. Oh, E. Ullmo, Hecke operators and equidistribution of Hecke points , Invent. Math. 144 (2001) 327--351, doi:10.1007/s002220100126.DOI
- 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
- J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups , 3rd ed., Springer, 1999.
- 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
- 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
- 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.
- 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
- J. Dick, F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration , Cambridge Univ. Press, 2010.
- 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
- H. Faure, Discrépance de suites associées à un système de numération (en dimension ) , Acta Arith. 41 (1982) 337--351, doi:10.4064/aa-41-4-337-351.DOI
- 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
- 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
- L. Grünschloß, J. Hanika, R. Schwede, A. Keller, -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
- L. Grünschloß, A. Keller, -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
- J. Hadamard, Sur la distribution des zéros de la fonction et ses conséquences arithmétiques , Bull. Soc. Math. France 24 (1896) 199--220, doi:10.24033/bsmf.545.DOI
- G. Hajós, Über einfache und mehrfache Bedeckung des -dimensionalen Raumes mit einem Würfelgitter , Math. Z. 47 (1942) 427--467, doi:10.1007/bf01180974.DOI
- T. C. Hales, A proof of the Kepler conjecture , Ann. of Math. 162 (2005) 1065--1185, doi:10.4007/annals.2005.162.1065.DOI
- 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
- 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.
- X. He, Rotated sphere packing designs , J. Amer. Statist. Assoc. 112 (2017) 1612--1622, doi:10.1080/01621459.2016.1222289.DOI
- X. He, Interleaved lattice-based maximin distance designs , Biometrika 106 (2019) 453--464, doi:10.1093/biomet/asy069; arXiv:1807.02289.arXivDOI
- 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
- 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
- R. Hofer, K. Suzuki, A complete classification of digital -nets and digital -sequences in base , Unif. Distrib. Theory 14 (2019) 43--52, doi:10.2478/udt-2019-0004; arXiv:1807.04383.arXivDOI
- 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
- D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms , 3rd ed., Addison-Wesley, 1997.
- 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
- N. M. Korobov, The approximate computation of multiple integrals , Dokl. Akad. Nauk SSSR 124 (1959) 1207--1210.
- R. Kritzinger, Dispersion of digital -nets , Monatsh. Math. 195 (2021) 155--171, doi:10.1007/s00605-021-01525-9; arXiv:2004.14760.arXivDOI
- H. W. Lenstra, Jr., Euclidean number fields of large degree , Invent. Math. 38 (1976/77) 237--254, doi:10.1007/bf01403131.DOI
- C. Lemieux, Tractability using periodized generalized Faure sequences , J. Complexity 31 (2015) 42--56, doi:10.1016/j.jco.2014.08.001.DOI
- C. Lemieux, H. Faure, New perspectives on -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
- 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
- G. Larcher, F. Pillichshammer, Walsh series analysis of the -discrepancy of symmetrisized point sets , Monatsh. Math. 132 (2001) 1--18, doi:10.1007/s006050170054.DOI
- 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
- 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
- J. Matoušek, On the -discrepancy for anchored boxes , J. Complexity 14 (1998) 527--556, doi:10.1006/jcom.1998.0489.DOI
- 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
- F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes , North-Holland, 1977.
- H. Niederreiter, Point sets and sequences with small discrepancy , Monatsh. Math. 104 (1987) 273--337, doi:10.1007/bf01294651.DOI
- A. B. Owen, Randomly permuted -nets and -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
- L. J. Paige, Complete mappings of finite groups , Pacific J. Math. 1 (1951) 111--116, doi:10.2140/pjm.1951.1.111.DOI
- O. Perron, Über lückenlose Ausfüllung des -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
- 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
- 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
- M. Yu. Rosenbloom, M. A. Tsfasman, Codes for the -metric , Probl. Inf. Transm. 33 (1997) 45--52.
- L. Rudolph, The even-order Grünschloß--Keller permutation nets are -nets , preprint, Zenodo, version 1.0.0, 2026, doi:10.5281/zenodo.22264675.DOI
- N. Sakai, T. Goda, Space-filling lattice designs for computer experiments , arXiv:2602.15390 (2026).arXiv
- I. H. Sloan, S. Joe, Lattice Methods for Multiple Integration , Oxford Univ. Press, 1994.
- 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
- 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
- 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
- K. Suzuki, Exact -separation radius of Sobol' sequences in dimension , arXiv:2508.14803 (2025).arXiv
- K. Suzuki, Separation properties of scrambled digital nets and related random point sets , arXiv:2607.29063 (2026).arXiv
- S. Tezuka, Polynomial arithmetic analogue of Halton sequences , ACM Trans. Model. Comput. Simul. 3 (1993) 99--107, doi:10.1145/169702.169694.DOI
- S. Tezuka, Uniform Random Numbers: Theory and Practice , Kluwer, 1995.
- 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
- 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
- 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
- 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
- M. S. Viazovska, The sphere packing problem in dimension , Ann. of Math. 185 (2017) 991--1015, doi:10.4007/annals.2017.185.3.7.DOI
Version history
- v1 · 128 pagesSubmitted by Leonhard GruenschlossInitial depositCurrentOct 13, 2026