Weak multipliers for generalized van der Corput sequences

Pausinger, Florian

Journal de théorie des nombres de Bordeaux, Tome 24 (2012) no. 3, pp. 729-749.

Les suites de Van der Corput généralisées sont des suites unidimensionnelles et infinies dans l’intervalle de l’unité. Elles sont générées par permutations des entiers de la base $b$ et sont les éléments constitutifs des suites multi-dimensionnelles de Halton. Suites aux progrès récents d’Atanassov concernant le comportement de distribution uniforme des suites de Halton nous nous intéressons aux permutations de la formule $P\left(i\right)=ai(modb)$ pour les entiers premiers entre eux $a$ et $b$. Dans cet article nous identifions des multiplicateurs $a$ générant des suites de Van der Corput ayant une mauvaise distribution. Nous donnons les bornes inférieures explicites pour cette distribution asymptotique associée à ces suites et relions ces dernières aux suites générées par permutation d’identité, qui sont, selon Faure, les moins bien distribuées des suites généralisées de Van der Corput dans une base donnée.

Generalized van der Corput sequences are onedimensional, infinite sequences in the unit interval. They are generated from permutations in integer base $b$ and are the building blocks of the multi-dimensional Halton sequences. Motivated by recent progress of Atanassov on the uniform distribution behavior of Halton sequences, we study, among others, permutations of the form $P\left(i\right)=ai(modb)$ for coprime integers $a$ and $b$. We show that multipliers $a$ that either divide $b-1$ or $b+1$ generate van der Corput sequences with weak distribution properties. We give explicit lower bounds for the asymptotic distribution behavior of these sequences and relate them to sequences generated from the identity permutation in smaller bases, which are, due to Faure, the weakest distributed generalized van der Corput sequences.

Classification : 11K06, 11K38
Mots clés : Uniform distribution, diaphony, generalized van der Corput sequence

[1] E. Aksoy, A. Cesmelioglu, W. Meidl, A. Topuzoglu, On the Carlitz rank of permutation polynomials. Finite Fields Appl. 15 (2009), 428–440. | MR | Zbl

[2] E. Atanassov, On the discrepancy of Halton sequences. Math. Balkanica 18 (2004), 15–32. | MR | Zbl

[3] E. Atanassov and M. Durchova, Generating and testing the modified Halton sequences. In: Fifth International Conference on Numerical Methods and Applications, Borovets 2002, Springer-Verlag, Ed. Lecture Notes in Computer Science, vol. 2542 (2003), Berlin, 91–98. | MR | Zbl

[4] L. Carlitz, Permutations in a finite field. Proc. Amer. Math. Soc. 4 (1953), 538. | MR | Zbl

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

[6] M. Drmota and R.F Tichy, Sequences, Discrepancies and Applications. Lecture Notes in Math. 1651. Springer-Verlag, Berlin, 1997. | MR | Zbl

[7] 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

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

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

[10] H. Faure, Irregularities of distribution of digital $(0,1)$-sequences in prime base. Electron. J. Combinatorial Number Theory 5 (2005), no. 3. | MR | Zbl

[11] H. Faure, Selection criteria for (random) generation of digital $(0,s)$-sequences. In: Monte Carlo and Quasi-Monte Carlo Methods 2004, H. Niederreiter and D. Talay, Ed. Springer (2006), 113–126. | MR | Zbl

[12] H. Faure and C. Lemieux, Generalized Halton sequences in 2008: A comparative study. ACM Trans. Model. Comp. Sim. 19 (2009), Article 15:1–31.

[13] V. Ostromoukhov, Recent progress in improvement of extreme discrepancy and star discrepancy of one-dimensional Sequences. In: Monte Carlo and Quasi-Monte Carlo Methods 2008 (2009), Springer, 561–572. | MR | Zbl

[14] F. Pausinger and W. Ch. Schmid, A good permutation for one-dimensional diaphony. Monte Carlo Methods Appl. 16 (2010), 307–322. | MR | Zbl

[15] F. Pausinger and W. Ch. Schmid, A lower bound for the diaphony of generalised van der Corput sequences in arbitrary base b. Unif. Distrib. Theory 6 (2011), no. 2, 31–46. | MR

[16] X. Wang, C. Lemieux and H. Faure, A note on Atanassov’s discrepancy bound for the Halton sequence. Technical report, Department of Statistics and Actuarial Science, University of Waterloo, (2008).

[17] P. Zinterhof, Über einige Abschätzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden. Österr. Akad. Wiss. SB II 185 (1976) 121–132. | MR | Zbl