×

Point sets and sequences with small discrepancy. (English) Zbl 0626.10045

Summary: 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 the s-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.

MSC:

11K06 General theory of distribution modulo \(1\)
05A05 Permutations, words, matrices
05B25 Combinatorial aspects of finite geometries
11T99 Finite fields and commutative rings (number-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] Chen, W. W. L.: On irregularities of distribution II. Quart. J. Math. (2)34, 257-279 (1983). · Zbl 0533.10045
[2] Dénes, J., Keedwell, A. D.: Latin Squares and Their Applications. New York: Academic Press. 1974. · Zbl 0283.05014
[3] Faure, H.: Discrépances de suites associées à un système de numération (en dimension un). Bull. Soc. Math. France109, 143-182 (1981). · Zbl 0488.10052
[4] Faure, H.: Discrépance de suites associées à un système de numération (en dimensions). Acta Arith.41, 337-351 (1982). · Zbl 0442.10035
[5] Hall, M.: Combinatorial Theory. Waltham: Blaisdell. 1967.
[6] 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. · Zbl 0090.34505
[7] Hammersley, J. M.: Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci.86, 844-874 (1960). · Zbl 0111.12405
[8] Hlawka, E.: Zur angenäherten Berechnung mehrfacher Integrale. Mh. Math.66, 140-151 (1962). · Zbl 0105.04603
[9] Hlawka, E.: Uniform distribution modulo 1 and numerical analysis. Compositio Math.16, 92-105 (1964). · Zbl 0146.27602
[10] Hua, L. K., Wang, Y.: Applications of Number Theory to Numerical Analysis. Berlin-Heidelberg-New York: Springer. 1981. · Zbl 0465.10045
[11] Knuth, D. E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. 2nd ed. Reading: Addison-Wesley. 1981. · Zbl 0477.65002
[12] Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. New York: Wiley-Interscience. 1974. · Zbl 0281.10001
[13] Lidl, R., Niederreiter, H.: Finite Fields. Reading: Addison-Wesley. 1983. · Zbl 0554.12010
[14] Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge: Cambridge Univ. Press. 1986. · Zbl 0629.12016
[15] Macwilliams, F. J., Sloane, N. J. A.: The Theory of Error-Correcting Codes. Amsterdam: North-Holland. 1977. · Zbl 0369.94008
[16] Mcdonald, B. R.: Finite Rings with Identity. New York: Dekker. 1974. · Zbl 0294.16012
[17] Muir, T.: History of Determinants, Vol. IV. London: Macmillan. 1923. · JFM 49.0078.01
[18] Niederreiter, H.: Pseudo-random numbers and optimal coefficients. Adv. in Math.26, 99-181 (1977). · Zbl 0366.65004
[19] Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc.84, 957-1041 (1978). · Zbl 0404.65003
[20] Niederreiter, H.: Existence of good lattice points in the sense of Hlawka. Mh. Math.86, 203-219 (1978). · Zbl 0395.10053
[21] Niederreiter, H.: The serial test for pseudo-random numbers generated by the linear congruential method. Numer. Math.46, 51-68 (1985). · Zbl 0554.65006
[22] Niederreiter, H.: Multidimensional numerical integration using pseudorandom numbers. Math. Programming Study27, 17-38 (1986). · Zbl 0619.65012
[23] Niederreiter, H.: Low-discrepancy point sets. Mh. Math.102, 155-167 (1986). · Zbl 0593.10045
[24] Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Österr. Akad. Wiss. Math.-Naturwiss. Kl.195, 109-138 (1986). · Zbl 0616.10040
[25] Niederreiter, H.: A statistical analysis of generalized feedback shift register pseudorandom number generators. SIAM J. Sci. Statist. Comp. (To appear.) · Zbl 0634.65003
[26] Niederreiter, H.: The serial test for digitalk-step pseudorandom numbers. Math. J. Okayama Univ. (To appear.) · Zbl 0666.65003
[27] Roth, K. F.: On irregularities of distribution. Mathematika1, 73-79 (1954). · Zbl 0057.28604
[28] Schmidt, W. M.: Irregularities of distribution. VII. Acta Arith.21, 45-50 (1972). · Zbl 0244.10035
[29] 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.)
[30] Sobol’, I. M.: Multidimensional Quadrature Formulas and Haar Functions. Moscow: Nauka. 1969. (Russian.) · Zbl 0195.16903
[31] Tezuka, S.: On optimal GFSR pseudorandom number generators. Submitted to Math. Comp. · Zbl 0644.65004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.