Generalized (𝑡,𝑠)-sequences, Kronecker-type sequences, and Diophantine approximations of formal Laurent series

Larcher, Gerhard; Niederreiter, Harald

doi:10.1090/S0002-9947-1995-1290724-1

Generalized $(t,s)$-sequences, Kronecker-type sequences, and Diophantine approximations of formal Laurent series
HTML articles powered by AMS MathViewer

by Gerhard Larcher and Harald Niederreiter PDF

Trans. Amer. Math. Soc. 347 (1995), 2051-2073 Request permission

Abstract:

The theory of $(t,s)$-sequences leads to powerful constructions of low-discrepancy sequences in an $s$-dimensional unit cube. We generalize this theory in order to cover arbitrary sequences constructed by the digital method and, in particular, the Kronecker-type sequences introduced by the second author. We define diophantine approximation constants for formal Laurent series over finite fields and show their connection with the distribution properties of Kronecker-type sequences. The main results include probabilistic theorems on the distribution of sequences constructed by the digital method and on the diophantine approximation character of $s$-tuples of formal Laurent series over finite fields.

References

Martin Eichler, Ein Satz über Linearformen in Polynombereichen, Arch. Math. 10 (1959), 81–84 (German). MR 104655, DOI 10.1007/BF01240765
Henri Faure, Discrépance de suites associées à un système de numération (en dimension $s$), Acta Arith. 41 (1982), no. 4, 337–351 (French). MR 677547, DOI 10.4064/aa-41-4-337-351
Tom Hansen, Gary L. Mullen, and Harald Niederreiter, Good parameters for a class of node sets in quasi-Monte Carlo integration, Math. Comp. 61 (1993), no. 203, 225–234. MR 1182244, DOI 10.1090/S0025-5718-1993-1182244-1
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
Gerhard Larcher, Nets obtained from rational functions over finite fields, Acta Arith. 63 (1993), no. 1, 1–13. MR 1201615, DOI 10.4064/aa-63-1-1-13
Gerhard Larcher, On the distribution of an analog to classical Kronecker-sequences, J. Number Theory 52 (1995), no. 2, 198–215. MR 1336745, DOI 10.1006/jnth.1995.1065
G. Larcher, A. Lauss, H. Niederreiter, and W. Ch. Schmid, Optimal polynomials for $(t,m,s)$-nets and numerical integration of multivariate Walsh series, SIAM J. Numer. Anal. 33 (1996), no. 6, 2239–2253. MR 1427461, DOI 10.1137/S0036142994264705
Gerhard Larcher and Harald Niederreiter, Kronecker-type sequences and non-Archimedean Diophantine approximations, Acta Arith. 63 (1993), no. 4, 379–396. MR 1218466, DOI 10.4064/aa-63-4-379-396
Kurt Mahler, An analogue to Minkowski’s geometry of numbers in a field of series, Ann. of Math. (2) 42 (1941), 488–522. MR 4272, DOI 10.2307/1968914
Harald Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), no. 4, 273–337. MR 918037, DOI 10.1007/BF01294651
Harald Niederreiter, Quasi-Monte Carlo methods for multidimensional numerical integration, Numerical integration, III (Oberwolfach, 1987) Internat. Schriftenreihe Numer. Math., vol. 85, Birkhäuser, Basel, 1988, pp. 157–171. MR 1021532, DOI 10.1007/978-3-0348-6398-8_{1}5
Harald Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), no. 1, 51–70. MR 960233, DOI 10.1016/0022-314X(88)90025-X
Harald Niederreiter, The probabilistic theory of linear complexity, Advances in cryptology—EUROCRYPT ’88 (Davos, 1988) Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, 1988, pp. 191–209. MR 994663, DOI 10.1007/3-540-45961-8_{1}7
Harald Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak Math. J. 42(117) (1992), no. 1, 143–166. MR 1152177, DOI 10.21136/CMJ.1992.128322
H. Niederreiter, Constructions of low-discrepancy point sets and sequences, Sets, graphs and numbers (Budapest, 1991) Colloq. Math. Soc. János Bolyai, vol. 60, North-Holland, Amsterdam, 1992, pp. 529–559. MR 1218217
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Wolfgang M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21 (1972), 45–50. MR 319933, DOI 10.4064/aa-21-1-45-50
I. M. Sobol′, Distribution of points in a cube and approximate evaluation of integrals, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 784–802 (Russian). MR 219238

Polynomial arithmetic analogue of Halton sequences

3