<abstract xmlns="http://www.w3.org/1999/xhtml"><p>A permuted van der Corput sequence <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0003_eq_001.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><msubsup><mi>S</mi><mi>b</mi><mi>σ</mi></msubsup></math><tex-math>$S_b^\sigma$</tex-math></alternatives></inline-formula> in base <italic>b</italic> is a one-dimensional, infinite sequence of real numbers in the interval [0, 1), generation of which involves a permutation σ of the set {0, 1,..., <italic>b −</italic> 1}. These sequences are known to have low discrepancy DN, i.e. <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0003_eq_002.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mi>t</mi><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>b</mi><mi>σ</mi></msubsup></mrow><mo>)</mo></mrow><mo>:</mo><mo>=</mo><mtext>lim</mtext><mi> </mi><msub><mtext>sup</mtext><mrow><mi>N</mi><mo>→</mo><mo>∞</mo></mrow></msub><msub><mi>D</mi><mi>N</mi></msub><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>b</mi><mi>σ</mi></msubsup></mrow><mo>)</mo></mrow><mo>/</mo><mtext>log</mtext><mi> </mi><mi>N</mi></math><tex-math>$t\left({S_b^\sigma } \right): = {\rm{lim}}\,{\rm{sup}}_{N \to \infty } D_N \left({S_b^\sigma } \right)/{\rm{log}}\,N$</tex-math></alternatives></inline-formula> is finite. Restricting to prime bases <italic>p</italic> we present two families of generating permutations. We describe their elements as polynomials over finite fields 𝔽<italic>p</italic> in an explicit way. We use this characterization to obtain bounds for <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0003_eq_003.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mi>t</mi><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>p</mi><mi>σ</mi></msubsup></mrow><mo>)</mo></mrow></math><tex-math>$t\left({S_p^\sigma } \right)$</tex-math></alternatives></inline-formula> for permutations <italic>σ</italic> in these families. We determine the best permutations in our first family and show that all permutations of the second family improve the distribution behavior of classical van der Corput sequences in the sense that <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0003_eq_004.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mi>t</mi><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>p</mi><mi>σ</mi></msubsup></mrow><mo>)</mo></mrow><mo>&lt;</mo><mi>t</mi><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>p</mi><mrow><mi>i</mi><mi>d</mi></mrow></msubsup></mrow><mo>)</mo></mrow></math><tex-math>$t\left({S_p^\sigma } \right) &lt; t\left({S_p^{id} } \right)$</tex-math></alternatives></inline-formula>.</p></abstract>

A permuted van der Corput sequence Sbσ$S_b^\sigma$ in base b is a one-dimensional, infinite sequence of real numbers in the interval [0, 1), generation of which involves a permutation σ of the set {0, 1,..., b − 1}. These sequences are known to have low discrepancy DN, i.e. t(Sbσ):=lim supN→∞DN(Sbσ)/log N$t\left({S_b^\sigma } \right): = {\rm{lim}}\,{\rm{sup}}_{N \to \infty } D_N \left({S_b^\sigma } \right)/{\rm{log}}\,N$ is finite. Restricting to prime bases p we present two families of generating permutations. We describe their elements as polynomials over finite fields 𝔽p in an explicit way. We use this characterization to obtain bounds for t(Spσ)$t\left({S_p^\sigma } \right)$ for permutations σ in these families. We determine the best permutations in our first family and show that all permutations of the second family improve the distribution behavior of classical van der Corput sequences in the sense that t(Spσ)<t(Spid)$t\left({S_p^\sigma } \right) < t\left({S_p^{id} } \right)$.

On the Discrepancy of Two Families of Permuted Van der Corput Sequences

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"On the Discrepancy of Two Families of Permuted Van der Corput Sequences"}

A permuted van der Corput sequence Sbσ$S_b^\sigma$ in base b is a one-dimensional, infinite sequence of real numbers in the interval [0, 1), generation of...

On the Discrepancy of Two Families of Permuted Van der Corput Sequences

Data publikacji: 20 lip 2018

Zakres stron: 47 - 64

Otrzymano: 31 mar 2017

Przyjęty: 10 lip 2017

DOI: https://doi.org/10.1515/udt-2018-0003

Słowa kluczowe
van der Corput sequence, extreme discrepancy, permutation, permutation polynomial, Carlitz rank,

© 2018 Florian Pausinger et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

On the Discrepancy of Two Families of Permuted Van der Corput Sequences

Data publikacji: 20 lip 2018

Zakres stron: 47 - 64

Otrzymano: 31 mar 2017

Przyjęty: 10 lip 2017

DOI: https://doi.org/10.1515/udt-2018-0003

Słowa kluczowevan der Corput sequence, extreme discrepancy, permutation, permutation polynomial, Carlitz rank,

© 2018 Florian Pausinger et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Słowa kluczowe
van der Corput sequence, extreme discrepancy, permutation, permutation polynomial, Carlitz rank,