<abstract xmlns="http://www.w3.org/1999/xhtml">

Let <italic>q</italic> be a positive integer and 
<inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2021-0009_ineq_001.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>𝒮</mi><mo>=</mo><mo>{</mo><msub><mi>x</mi><mn>0</mn></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>⋯</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>T</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>}</mo><mo>⊆</mo><msub><mi>ℤ</mi><mi>q</mi></msub><mo>=</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>}</mo></mrow></math>
<tex-math>{\scr S} = \{{x_0},{x_1}, \cdots ,{x_{T - 1}}\}\subseteq {{\rm{\mathbb Z}}_q} = \{0,1, \ldots ,q - 1\}</tex-math>
</alternatives>
</inline-formula>
 with 
<inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2021-0009_ineq_002.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mn>0</mn><mo>≤</mo><msub><mi>x</mi><mn>0</mn></msub><mo>&lt;</mo><msub><mi>x</mi><mn>1</mn></msub><mo>&lt;</mo><mo>⋯</mo><mo>&lt;</mo><msub><mi>x</mi><mrow><mi>T</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>≤</mo><mi>q</mi><mo>−</mo><mn>1.</mn></mrow></math>
<tex-math>0 \le {x_0} &lt; {x_1} &lt;\cdots&lt; {x_{T - 1}} \le q - 1.</tex-math>
</alternatives>
</inline-formula>
. We derive from <italic>S </italic>three (finite) sequences: (1) For an integer <italic>M ≥ </italic>2let (<italic>sn</italic>)be the <italic>M</italic>-ary sequence defined by <italic>sn ≡ xn</italic>+1 <italic>− xn</italic> mod <italic>M, n</italic> =0<italic></italic>, 1,...<italic>,T −</italic> 2<italic>.</italic>
(2) For an integer <italic>m ≥</italic> 2let (<italic>tn</italic>) be the binary sequence defined by 
<inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2021-0009_ineq_003.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mtable><mtr><mtd><mrow><msub><mi>s</mi><mi>n</mi></msub><mo>≡</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>x</mi><mi>n</mi></msub><mtext> </mtext><mi>mod</mi><mtext> </mtext><mi>M</mi><mo>,</mo></mrow></mtd><mtd><mrow><mi>n</mi><mo>=</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>⋯</mo><mo>,</mo><mi>T</mi><mo>−</mo><mn>2.</mn></mrow></mtd></mtr></mtable></mrow></math>
<tex-math>\matrix{{{s_n} \equiv {x_{n + 1}} - {x_n}\,\bmod \,M,} &amp;#38; {n = 0,1, \cdots ,T - 2.}\cr}</tex-math>
</alternatives>
</inline-formula>
 <italic>n</italic> =0<italic></italic>, 1,...<italic>,T −</italic> 2<italic>.</italic>
(3) Let (<italic>un</italic>) be the characteristic sequence of <italic>S</italic>, 
<inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2021-0009_ineq_004.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mtable><mtr><mtd><mrow><msub><mi>t</mi><mi>n</mi></msub><mo>=</mo><mrow><mo>{</mo><mrow><mtable columnalign="left"><mtr columnalign="left"><mtd columnalign="left"><mn>1</mn></mtd><mtd columnalign="left"><mrow><mtext>if</mtext><mtext> </mtext><mn>1</mn><mo>≤</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>x</mi><mi>n</mi></msub><mo>≤</mo><mi>m</mi><mo>−</mo><mn>1</mn><mo>,</mo></mrow></mtd></mtr><mtr columnalign="left"><mtd columnalign="left"><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd columnalign="left"><mrow><mtext>otherwise</mtext><mo>,</mo></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd><mtd><mrow><mi>n</mi><mo>=</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>T</mi><mo>−</mo><mn>2.</mn></mrow></mtd></mtr></mtable></mrow></math>
<tex-math>\matrix{{{t_n} = \left\{{\matrix{1 \hfill &amp;#38; {{\rm{if}}\,1 \le {x_{n + 1}} - {x_n} \le m - 1,} \hfill\cr{0,} \hfill &amp;#38; {{\rm{otherwise}},} \hfill\cr}} \right.} &amp;#38; {n = 0,1, \ldots ,T - 2.}\cr}</tex-math>
</alternatives>
</inline-formula>
 <italic>n</italic> =0<italic></italic>, 1,...<italic>,q −</italic> 1.
We study the balance and pattern distribution of the sequences (<italic>sn</italic>), (<italic>tn</italic>)and (<italic>un</italic>). For sets <italic>S </italic>with desirable pseudorandom properties, more precisely, sets with low correlation measures, we show the following:
(1) The sequence (<italic>sn</italic>) is (asymptotically) balanced and has uniform pattern distribution if <italic>T </italic>is of smaller order of magnitude than <italic>q</italic>.
(2) The sequence (<italic>tn</italic>) is balanced and has uniform pattern distribution if <italic>T </italic>is approximately 
<inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2021-0009_ineq_005.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mtable><mtr><mtd><mrow><msub><mi>u</mi><mi>n</mi></msub><mo>=</mo><mrow><mo>{</mo><mrow><mtable columnalign="left"><mtr columnalign="left"><mtd columnalign="left"><mn>1</mn></mtd><mtd columnalign="left"><mrow><mtext>if</mtext><mtext> </mtext><mi>n</mi><mo>∈</mo><mi>𝒮</mi><mo>,</mo></mrow></mtd></mtr><mtr columnalign="left"><mtd columnalign="left"><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd columnalign="left"><mrow><mtext>otherwise</mtext><mo>,</mo></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd><mtd><mrow><mi>n</mi><mo>=</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>q</mi><mo>−</mo><mn>1.</mn></mrow></mtd></mtr></mtable></mrow></math>
<tex-math>\matrix{{{u_n} = \left\{{\matrix{1 \hfill &amp;#38; {{\rm{if}}\,n \in {\scr S},} \hfill\cr{0,} \hfill &amp;#38; {{\rm{otherwise}},} \hfill\cr}} \right.} &amp;#38; {n = 0,1, \ldots ,q - 1.}\cr}</tex-math>
</alternatives>
</inline-formula>
.
(3) The sequence (<italic>un</italic>) is balanced and has uniform pattern distribution if <italic>T </italic>is approximately <italic>q</italic>2.
These results are motivated by earlier results for the sets of quadratic residues and primitive roots modulo a prime. We unify these results and derive many further (asymptotically) balanced sequences with uniform pattern distribution from pseudorandom subsets.
</abstract>

Let q be a positive integer and 



𝒮={x0,x1,⋯,xT−1}⊆ℤq={0,1,…,q−1}
{\scr S} = \{{x_0},{x_1}, \cdots ,{x_{T - 1}}\}\subseteq {{\rm{\mathbb Z}}_q} = \{0,1, \ldots ,q - 1\}


 with 



0≤x0<x1<⋯<xT−1≤q−1.
0 \le {x_0} < {x_1} <\cdots< {x_{T - 1}} \le q - 1.


. We derive from S three (finite) sequences: (1) For an integer M ≥ 2let (sn)be the M-ary sequence defined by sn ≡ xn+1 − xn mod M, n =0, 1,...,T − 2.
(2) For an integer m ≥ 2let (tn) be the binary sequence defined by 



sn≡xn+1−xn mod M,n=0,1,⋯,T−2.
\matrix{{{s_n} \equiv {x_{n + 1}} - {x_n}\,\bmod \,M,} &#38; {n = 0,1, \cdots ,T - 2.}\cr}


 n =0, 1,...,T − 2.
(3) Let (un) be the characteristic sequence of S, 



tn={1if 1≤xn+1−xn≤m−1,0,otherwise,n=0,1,…,T−2.
\matrix{{{t_n} = \left\{{\matrix{1 \hfill &#38; {{\rm{if}}\,1 \le {x_{n + 1}} - {x_n} \le m - 1,} \hfill\cr{0,} \hfill &#38; {{\rm{otherwise}},} \hfill\cr}} \right.} &#38; {n = 0,1, \ldots ,T - 2.}\cr}


 n =0, 1,...,q − 1.
We study the balance and pattern distribution of the sequences (sn), (tn)and (un). For sets S with desirable pseudorandom properties, more precisely, sets with low correlation measures, we show the following:
(1) The sequence (sn) is (asymptotically) balanced and has uniform pattern distribution if T is of smaller order of magnitude than q.
(2) The sequence (tn) is balanced and has uniform pattern distribution if T is approximately 



un={1if n∈𝒮,0,otherwise,n=0,1,…,q−1.
\matrix{{{u_n} = \left\{{\matrix{1 \hfill &#38; {{\rm{if}}\,n \in {\scr S},} \hfill\cr{0,} \hfill &#38; {{\rm{otherwise}},} \hfill\cr}} \right.} &#38; {n = 0,1, \ldots ,q - 1.}\cr}


.
(3) The sequence (un) is balanced and has uniform pattern distribution if T is approximately q2.
These results are motivated by earlier results for the sets of quadratic residues and primitive roots modulo a prime. We unify these results and derive many further (asymptotically) balanced sequences with uniform pattern distribution from pseudorandom subsets.

Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of ℤ<italic>q</italic>

Research Center for Number Theory and Its Applications

Johann Radon Institute for Computational and Applied Mathematics

Uniform distribution theory

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

Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of ℤ

Let q be a positive integer and 



𝒮={x0,x1,⋯,xT−1}⊆ℤq={0,1,…,q−1}
{\scr S} = \{{x_0},{x_1}, \cdots ,{x_{T - 1}}\}\subseteq {{\rm{\mathbb Z}}_q} = \{0,1,...

Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of ℤ_q

Pubblicato online: 02 feb 2022

Pagine: 89 - 108

Ricevuto: 15 ott 2021

Accettato: 09 nov 2021

DOI: https://doi.org/10.2478/udt-2021-0009

Parole chiave
sequence, pseudorandom subset, balance, pattern distribution, correlation measure

© 2021 Huaning Liu et al., published by Sciendo

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

Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of ℤq

Pubblicato online: 02 feb 2022

Pagine: 89 - 108

Ricevuto: 15 ott 2021

Accettato: 09 nov 2021

DOI: https://doi.org/10.2478/udt-2021-0009

Parole chiavesequence, pseudorandom subset, balance, pattern distribution, correlation measure

© 2021 Huaning Liu et al., published by Sciendo

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

Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of ℤ_q

Parole chiave
sequence, pseudorandom subset, balance, pattern distribution, correlation measure