Pausinger, Florian
Weak multipliers for generalized van der Corput sequences
Journal de théorie des nombres de Bordeaux, Tome 24 (2012) no. 3 , p. 729-749
MR 3010637 | Zbl 1270.11075
doi : 10.5802/jtnb.819
URL stable : http://www.numdam.org/item?id=JTNB_2012__24_3_729_0

Classification:  11K06,  11K38
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(i)=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(i)=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.

Bibliographie

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

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

[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 2053252 | Zbl 1032.65004

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

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

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

[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 623787 | Zbl 0488.10052

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

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

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

[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 2208705 | Zbl 1096.11028

[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 2743919 | Zbl 1228.11119

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

[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 2904036 | Zbl pre06048388

[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 501760 | Zbl 0356.65007