Van der Corput sequences towards general (0,1)–sequences in base b

Faure, Henri

Journal de théorie des nombres de Bordeaux, Volume 19 (2007) no. 1, pp. 125-140.

As a result of recent studies on unidimensional low discrepancy sequences, we can assert that the original van der Corput sequences are the worst distributed with respect to various measures of irregularities of distribution among two large families of $(0,1)$–sequences, and even among all $(0,1)$–sequences for the star discrepancy $D^{*}$. We show in the present paper that it is not the case for the extreme discrepancy $D$ by producing two kinds of sequences which are the worst distributed among all $(0,1)$–sequences, with a discrepancy $D$ essentially twice greater. In addition, we give an unified presentation for the two generalizations presently known of van der Corput sequences.

A la suite de travaux récents sur les suites à faible discrépance unidimensionnelles, on peut affirmer que les suites de van der Corput originales sont les plus mal distribuées pour diverses mesures d’irrégularités de distribution parmi deux grandes familles de $(0,1)$–suites, et même parmi toutes les $(0,1)$–suites pour la discrépance à l’origine $D^{*}$. Nous montrons ici que ce n’est pas le cas pour la discrépance extrême $D$ en produisant deux types de suites qui sont les plus mal distribuées parmi les $(0,1)$–suites, avec une discrépance $D$ essentiellement deux fois plus grande. En outre, nous donnons une présentation unifiée pour les deux généralisations connues des suites de van der Corput.

[1] H. Chaix, H. Faure, Discrépance et diaphonie en dimension un. Acta Arith. 63.2 (1993), 103–141. | MR | Zbl

[2] J. Dick, P. Kritzer, A best possible upper bound on the star discrepancy of $(t,m,2)$–nets. Monte Carlo Meth. Appl. 12.1 (2006), 1–17. | MR | Zbl

[3] M. Drmota, G. Larcher, F. Pillichshammer, Precise distribution properties of the van der Corput sequence and related sequences. Manuscripta Math. 118 (2005), 11–41. | MR | Zbl

[4] H. Faure, Discrépance de suites associées à un système de numération (en dimension $un$). Bull. Soc. math. France 109 (1981), 143–182. | Numdam | MR | Zbl

[5] H. Faure, Good permutations for extreme discrepancy. J. Number Theory. 42 (1992), 47–56. | MR | Zbl

[6] H. Faure, Discrepancy and diaphony of digital $(0,1)$–sequences in prime base. Acta Arith. 117.2 (2005), 125–148. | MR | Zbl

[7] H. Faure, Irregularities of distribution of digital $(0,1)$–sequences in prime base. Integers, Electronic Journal of Combinatorial Number Theory 5(3) A07 (2005), 1–12. | MR | Zbl

[8] P. Kritzer, A new upper bound on the star discrepancy of $(0,1)$–sequences. Integers, Electronic Journal of Combinatorial Number Theory 5(3) A11 (2005), 1–9. | MR | Zbl

[9] G. Larcher, F. Pillichshammer, Walsh series analysis of the $L_2$–discrepancy of symmetrisized points sets. Monatsh. Math. 132 (2001), 1–18. | MR | Zbl

[10] G. Larcher, F. Pillichshammer, Sums of distances to the nearest integer and the discrepancy of digital nets. Acta Arith. 106.4 (2003), 379–408. | MR | Zbl

[11] W. J. Morokoff, R. E. Caflisch, Quasi random sequences and their discrepancies. SIAM J. Sci. Comput. 15.6 (1994), 1251–1279. | MR | Zbl

[12] H. Niederreiter, Random number generation and quasi-Monte Carlo methods. CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1992. | MR | Zbl

[13] H. Niederreiter, C. P. Xing, Quasirandom points and global functions fields. Finite Fields and Applications (S. Cohen and H. Niederreiter, eds), London Math. Soc. Lectures Notes Series Vol. 233 (1996), 269–296. | MR | Zbl

[14] H. Niederreiter, C. P.Xing, Nets, $(t,s)$–sequences and algebraic geometry. Random and Quasi-random Point Sets (P. Hellekalek and G. Larcher, eds), Lectures Notes in Statistics, Springer Vol. 138 (1998), 267–302. | MR | Zbl

[15] F. Pillichshammer, On the discrepancy of (0,1)–sequences. J. Number Theory 104 (2004), 301–314. | MR | Zbl

[16] S. Tezuka, Polynomial arithmetic analogue of Halton sequences. ACM Trans. Modeling and Computer Simulation 3 (1993), 99–107. | Zbl