zbMATH — the first resource for mathematics

A lower bound on a quantity related to the quality of polynomial lattices. (English) Zbl 1247.11097
For \(b\) be a prime, let \(\mathbb{F}_b\) be a finite field consisting of \(b\) elements. Let \(f\in \mathbb{F}_b[x]\) be a polynomial over \(\mathbb{F}_b\). For a vector \(\mathbf{g}=(g_1,\ldots, g_s)\in\mathbb{F}_b[x]^s\), let \(P(\mathbf{g},f)\) be a polynomial lattice with \(N=b^m\) points in dimension \(s\). Let \(G_{b,m}=\{a\in\mathbb{F}_b[x]: \deg(a)<m\}\). A quantity \(R_b(\mathbf{g},f)\) is used for studying the quality of \(P(\mathbf{g},f)\). It was shown by H. Niederreiter [Random number generation and quasi-Monte Carlo methods. Philadelphia, PA: SIAM (1992; Zbl 0761.65002)] that the star discrepancy of \(P(\mathbf{g},f)\) satisfies \(D_N^*(P(\mathbf{g},f))\leq s/N+R_b(\mathbf{g},f)\) and there exists a vector \(\mathbf{g}\in G_{b,m}^s\) such that \(R_b(\mathbf{g},f)\leq C_{s,b}m^s/b^m\) for some \(C_{s,b}>0\). These results yield the existence of \(P(\mathbf{g},f)\) with \(D_N^*(P(\mathbf{g},f))=O((\log N)^s/N)\). In the paper under review, the authors prove that Niederreiter’s upper bound for \(R_b(\mathbf{g},f)\) is essentially best possible.

11K06 General theory of distribution modulo \(1\)
11K38 Irregularities of distribution, discrepancy
Zbl 0761.65002
Full Text: DOI Euclid
[1] J. Dick, P. Kritzer, G. Leobacher, F. Pillichshammer, Constructions of general polynomial lattice rules based on the weighted star discrepancy , Finite Fields Appl. 13 (2007), 1045-1070. · Zbl 1132.11039
[2] J. Dick, F. Y. Kuo, F. Pillichshammer, I. H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration , Math. Comp. 74 (2005), 1895-1921. · Zbl 1079.65007
[3] J. Dick, G. Leobacher, F. Pillichshammer, Construction algorithms for digital nets with small weighted star discrepancy , SIAM J. Numer. Anal. 43 (2005), 76-95. · Zbl 1084.11040
[4] J. Dick, F. Pillichshammer, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces , J. Complexity 21 (2005), 149-195. · Zbl 1085.41021
[5] J. Dick, F. Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration , Cambridge University Press, 2010. · Zbl 1282.65012
[6] M. Drmota, R. F. Tichy, Sequences, Discrepancies and Applications , Springer, Berlin, 1997. · Zbl 0877.11043
[7] M. Fuchs, Kettenbrüche im Körper der formalen Laurentreihen und Anwendungen , Master thesis, Vienna University of Technology, 2000 (available at http://dmg.tuwien.ac.at/drmota/ (state: August 17, 2011)). · Zbl 1016.68105
[8] L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences . John Wiley, New York, 1974. · Zbl 0281.10001
[9] G. Larcher, On the distribution of sequences connected with good lattice points , Monatsh. Math. 101 (1986), 135-150. · Zbl 0584.10030
[10] G. Larcher, A best lower bound for good lattice points , Monatsh. Math. 104 (1987), 45-51. · Zbl 0624.10043
[11] G. Larcher, Digital point sets: analysis and applications , in: Random and Quasi-Random Point Sets, P. Hellekalek and G. Larcher (eds.), Lecture Notes in Statistics Vol. 138, Springer, New York, 1998, 167-222. · Zbl 0920.11055
[12] G. Larcher, A. Lauss, H. Niederreiter, W. Ch. Schmid, Optimal polynomials for \((t,m,s)\)-nets and numerical integration of multivariate Walsh series , SIAM J. Numer. Anal. 33 (1996), 2239-2253. · Zbl 0861.65019
[13] P. L’Ecuyer, Polynomial integration lattices , in: Monte Carlo and Quasi-Monte Carlo Methods 2002, H. Niederreiter (ed.), Springer, Berlin, 2004, 73-98. · Zbl 1041.65008
[14] C. Lemieux, P. L’Ecuyer, Randomized polynomial lattice rules for multivariate integration and simulation , SIAM J. Sci. Comput. 24 (2003), 1768-1789. · Zbl 1071.11049
[15] H. Niederreiter, Point sets and sequences with small star discrepancy . Monatsh. Math. 104 (1987), 273-337. · Zbl 0626.10045
[16] H. Niederreiter, Sequences with almost perfect linear complexity profile , in: Advances in Cryptology–EUROCRYPT ’87, D. Chaum and W.L. Price (eds.), Lecture Notes in Computer Science Vol. 304, Springer, Berlin, 1988, 37-51. · Zbl 0651.94003
[17] H. Niederreiter, Low discrepancy point sets obtained by digital constructions over finite fields . Czechoslovak Math. J. 42 (1992), 143-166. · Zbl 0757.11024
[18] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods , SIAM, Philadelphia, 1992. · Zbl 0761.65002
[19] I. H. Sloan, S. Joe, Lattice methods for multiple integration , Oxford University Press, Oxford, 1994. · Zbl 0855.65013
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.