×

Low-discrepancy point sets obtained by digital constructions over finite fields. (English) Zbl 0757.11024

In the paper under review, low-discrepancy point sets in \([0,1)^ s\) are constructed in which the coordinates of the points are given by digit expansions in a base \(q^ m\), \(q\) prime. These point sets are \((t,m,s)\)- nets in the sense of the author [Monatsh. Math. 104, 273-337 (1987; Zbl 0626.10045)]. Thus upper and lower bounds for the star discrepancy \(D^*_ N\) of the constructed point sets can be established. An average upper bound is \(D^*_ N=O(N^{-1}(\log N)^ s)\), where \(N=q^ m\).
For the efficient implementation of the point sets, a further specialization is investigated where the digit expansion is derived from Laurent series expansions. Then the point sets can be calculated by linear recurrence relations as in [the author, J. Number Theory 30, 51-70 (1988; Zbl 0651.10034)]. A two-dimensional point set with \(D^*_ N=O(N^{-1}\log N)\) is also constructed. The proofs depend among other things on the theory of arithmetic functions on a Galois field as developed by Carlitz.

MSC:

11K38 Irregularities of distribution, discrepancy
65C05 Monte Carlo methods
65D30 Numerical integration
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] D. A. André, G. L. Mullen, and H. Niederreiter: Figures of merit for digital multistep pseudorandom numbers. Math. Comp. 54 (1990), 737-748. · Zbl 0699.65003 · doi:10.2307/2008509
[2] M. Car: Sommes de carrés dans \(F_{q}[X]\). Dissertationes Math. 215 (1983). · Zbl 0531.12016
[3] L. Carlitz: The arithmetic of polynomials in a Galois field. Amer. J. Math. 54 (1932), 39-50. · Zbl 0003.19502 · doi:10.2307/2371075
[4] L. Carlitz: The singular series for sums of squares of polynomials. Duke Math. J. 14 (1947), 1105-1120. · Zbl 0032.00204 · doi:10.1215/S0012-7094-47-01484-1
[5] H. Faure: Discrépance de suites associées à un système de numération (en dimension \(s\)). Acta Arith. 41 (1982), 337-351. · Zbl 0442.10035
[6] D. R. Hayes: The expression of a polynomial as a sum of three irreducibles. Acta Arith. 11 (1966), 461-488. · Zbl 0151.03902
[7] L. K. Hua and Y. Wang: Applications of Number Theory to Numerical Analysis. (1981), Springer, Berlin. · Zbl 0465.10045
[8] R. Lidl and H. Niederreiter: Finite Fields. Addison-Wesley, Reading, MA, 1983. · Zbl 0554.12010
[9] G. L. Mullen and H. Niederreiter: Optimal characteristic polynomials for digital multistep pseudorandom numbers. Computing 39 (1987), 155-163. · Zbl 0618.65004 · doi:10.1007/BF02310104
[10] H. Niederreiter: On the distribution of pseudorandom numbers generated by the linear congruential method. III. Math. Comp. 30 (1976), 571-597. · Zbl 0342.65002 · doi:10.2307/2005328
[11] H. Niederreiter: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc. 84 (1978), 957-1041. · Zbl 0404.65003 · doi:10.1090/S0002-9904-1978-14532-7
[12] H. Niederreiter: Low-discrepancy point sets. Monatsh. Math. 102 (1986), 155-167. · Zbl 0584.10034 · doi:10.1007/BF01490206
[13] H. Niederreiter: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Osterr. Akad. Wiss. Math.-Naturwiss. Kl. Abt. II 195 (1986), 109-138. · Zbl 0616.10040
[14] H. Niederreiter: Rational functions with partial quotients of small degree in their continued fraction expansion. Monatsh. Math. 103 (1987), 269-288. · Zbl 0624.12011 · doi:10.1007/BF01318069
[15] H. Niederreiter: A statistical analysis of generalized feedback shift register pseudorandom number generators. SIAM J. Sci. Statist. Computing 8 (1987), 1035-1051. · Zbl 0634.65003 · doi:10.1137/0908084
[16] H. Niederreiter: Point sets and sequences with small discrepancy. Monatsh. Math. 104 (1987), 273-337. · Zbl 0626.10045 · doi:10.1007/BF01294651
[17] H. Niederreiter: Quasi-Monte Carlo methods for multidimensional numerical integration. Numerical Integration III (Oberwolfach 1987), Internat. Series of Numer. Math., Vol. 85, Birkhäuser, Basel, 1988, pp. 157-171. · Zbl 0662.65021
[18] H. Niederreiter: Low-discrepancy and low-dispersion sequences. J. Number Theory 30 (1988), 51-70. · Zbl 0651.10034 · doi:10.1016/0022-314X(88)90025-X
[19] H. Niederreiter: A combinatorial problem for vector spaces over finite fields. Discrete Math. · Zbl 0747.11063 · doi:10.1016/0012-365X(91)90315-S
[20] W. M. Schmidt: Irregularities of distribution. VII. Acta Arith. 21 (1972), 45-50. · Zbl 0244.10035
[21] I. M. Sobol’: The distribution of points in a cube and the approximate evaluation of integrals. Zh. Vychisl. Mat. i Mat. Fiz. 7 (1967), 784-802. · Zbl 0185.41103 · doi:10.1016/0041-5553(67)90144-9
[22] S. Tezuka: A new family of low-discrepancy point sets, Tech.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.