Weak multipliers for generalized van der Corput sequences

Florian Pausinger[1]

  • [1] IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400-Klosterneuburg, Austria

Journal de Théorie des Nombres de Bordeaux (2012)

  • Volume: 24, Issue: 3, page 729-749
  • ISSN: 1246-7405

Abstract

top
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 ) = a i ( mod b ) 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.

How to cite

top

Pausinger, Florian. "Weak multipliers for generalized van der Corput sequences." Journal de Théorie des Nombres de Bordeaux 24.3 (2012): 729-749. <http://eudml.org/doc/251049>.

@article{Pausinger2012,
abstract = {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)=a i \hspace\{4.44443pt\}(\@mod \; b)$ 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.},
affiliation = {IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400-Klosterneuburg, Austria},
author = {Pausinger, Florian},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Uniform distribution; diaphony; generalized van der Corput sequence},
language = {eng},
month = {11},
number = {3},
pages = {729-749},
publisher = {Société Arithmétique de Bordeaux},
title = {Weak multipliers for generalized van der Corput sequences},
url = {http://eudml.org/doc/251049},
volume = {24},
year = {2012},
}

TY - JOUR
AU - Pausinger, Florian
TI - Weak multipliers for generalized van der Corput sequences
JO - Journal de Théorie des Nombres de Bordeaux
DA - 2012/11//
PB - Société Arithmétique de Bordeaux
VL - 24
IS - 3
SP - 729
EP - 749
AB - 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)=a i \hspace{4.44443pt}(\@mod \; b)$ 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.
LA - eng
KW - Uniform distribution; diaphony; generalized van der Corput sequence
UR - http://eudml.org/doc/251049
ER -

References

top
  1. E. Aksoy, A. Cesmelioglu, W. Meidl, A. Topuzoglu, On the Carlitz rank of permutation polynomials. Finite Fields Appl. 15 (2009), 428–440. Zbl1232.11124MR2535587
  2. E. Atanassov, On the discrepancy of Halton sequences. Math. Balkanica 18 (2004), 15–32. Zbl1088.11058MR2076074
  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. Zbl1032.65004MR2053252
  4. L. Carlitz, Permutations in a finite field. Proc. Amer. Math. Soc. 4 (1953), 538. Zbl0052.03704MR55965
  5. H. Chaix and H. Faure, Discrépance et diaphonie en dimension un. Acta Arith. 63 (1993), 103–141. Zbl0772.11022MR1206080
  6. M. Drmota and R.F Tichy, Sequences, Discrepancies and Applications. Lecture Notes in Math. 1651. Springer-Verlag, Berlin, 1997. Zbl0877.11043MR1470456
  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. Zbl0488.10052MR623787
  8. H. Faure, Good permutations for extreme discrepancy. J. Number Theory 42 (1992), 47–56. Zbl0768.11026MR1176419
  9. H. Faure, Discrepancy and diaphony of digital ( 0 , 1 ) -sequences in prime base. Acta Arith. 117 (2005), 125–148. Zbl1080.11054MR2139596
  10. H. Faure, Irregularities of distribution of digital ( 0 , 1 ) -sequences in prime base. Electron. J. Combinatorial Number Theory 5 (2005), no. 3. Zbl1084.11041MR2191753
  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. Zbl1096.11028MR2208705
  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. Zbl1288.65003
  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. Zbl1228.11119MR2743919
  14. F. Pausinger and W. Ch. Schmid, A good permutation for one-dimensional diaphony. Monte Carlo Methods Appl. 16 (2010), 307–322. Zbl1206.11096MR2747818
  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. Zbl1313.11096MR2904036
  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. Zbl0356.65007MR501760

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.