Abstract
A systematic theory of a class of point sets called (t, m, s)-nets and of a class of sequences called (t, s)-sequences is developed. On the basis of this theory, point sets and sequences in thes-dimensional unit cube with the smallest discrepancy that is currently known are constructed. Various connections with other areas arise in this work, e.g. with orthogonal latin squares, finite projective planes, finite fields, and algebraic coding theory. Applications of the theory of (t, m, s)-nets to two methods for pseudorandom number generation, namely the digital multistep method and the GFSR method, are presented. Several open problems, mostly of a combinatorial nature, are stated.
Similar content being viewed by others
References
Chen, W. W. L.: On irregularities of distribution II. Quart. J. Math. (2)34, 257–279 (1983).
Dénes, J., Keedwell, A. D.: Latin Squares and Their Applications. New York: Academic Press. 1974.
Faure, H.: Discrépances de suites associées à un système de numération (en dimension un). Bull. Soc. Math. France109, 143–182 (1981).
Faure, H.: Discrépance de suites associées à un système de numération (en dimensions). Acta Arith.41, 337–351 (1982).
Hall, M.: Combinatorial Theory. Waltham: Blaisdell. 1967.
Halton, J. H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math.2, 84–90 (1960); Berichtigung, ibid., 196.
Hammersley, J. M.: Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci.86, 844–874 (1960).
Hlawka, E.: Zur angenäherten Berechnung mehrfacher Integrale. Mh. Math.66, 140–151 (1962).
Hlawka, E.: Uniform distribution modulo 1 and numerical analysis. Compositio Math.16, 92–105 (1964).
Hua, L. K., Wang, Y.: Applications of Number Theory to Numerical Analysis. Berlin-Heidelberg-New York: Springer. 1981.
Knuth, D. E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. 2nd ed. Reading: Addison-Wesley. 1981.
Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. New York: Wiley-Interscience. 1974.
Lidl, R., Niederreiter, H.: Finite Fields. Reading: Addison-Wesley. 1983.
Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge: Cambridge Univ. Press. 1986.
Macwilliams, F. J., Sloane, N. J. A.: The Theory of Error-Correcting Codes. Amsterdam: North-Holland. 1977.
Mcdonald, B. R.: Finite Rings with Identity. New York: Dekker. 1974.
Muir, T.: History of Determinants, Vol. IV. London: Macmillan. 1923.
Niederreiter, H.: Pseudo-random numbers and optimal coefficients. Adv. in Math.26, 99–181 (1977).
Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc.84, 957–1041 (1978).
Niederreiter, H.: Existence of good lattice points in the sense of Hlawka. Mh. Math.86, 203–219 (1978).
Niederreiter, H.: The serial test for pseudo-random numbers generated by the linear congruential method. Numer. Math.46, 51–68 (1985).
Niederreiter, H.: Multidimensional numerical integration using pseudorandom numbers. Math. Programming Study27, 17–38 (1986).
Niederreiter, H.: Low-discrepancy point sets. Mh. Math.102, 155–167 (1986).
Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Österr. Akad. Wiss. Math.-Naturwiss. Kl.195, 109–138 (1986).
Niederreiter, H.: A statistical analysis of generalized feedback shift register pseudorandom number generators. SIAM J. Sci. Statist. Comp. (To appear.)
Niederreiter, H.: The serial test for digitalk-step pseudorandom numbers. Math. J. Okayama Univ. (To appear.)
Roth, K. F.: On irregularities of distribution. Mathematika1, 73–79 (1954).
Schmidt, W. M.: Irregularities of distribution. VII. Acta Arith.21, 45–50 (1972).
Sobol', I. M.: The distribution of points in a cube and the approximate evaluation of integrals. Zh. Vychisl. Mat. i Mat. Fiz.7, 784–802 (1967). (Russian.)
Sobol', I. M.: Multidimensional Quadrature Formulas and Haar Functions. Moscow: Nauka. 1969. (Russian.)
Tezuka, S.: On optimal GFSR pseudorandom number generators. Submitted to Math. Comp.
Author information
Authors and Affiliations
Additional information
The author wants to thank the Universität Hannover (West Germany) for its hospitality during the period when most of this research was carried out. The results of this paper were presented at the Colloquium on Irregularities of Partitions at Fertöd (Hungary), July 7–11, 1986.
Rights and permissions
About this article
Cite this article
Niederreiter, H. Point sets and sequences with small discrepancy. Monatshefte für Mathematik 104, 273–337 (1987). https://doi.org/10.1007/BF01294651
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01294651