Uniform Distribution Theory
Journal license

Journal

Uniform Distribution Theory


Volume
& Issue

Volume 16, Issue 2


Published
on

November 9, 2021


Pages

89-108


DOI

Article

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

Check for updates


Authors

Huaning Liu Affiliation:
Research Center for Number Theory and its Applications School of Mathematics Northwest University Xi’an 710127 CHINA
and Arne Winterhof Affiliation:
Johann Radon Institute for Computational and Applied Mathematics Austrian Academy of Sciences Altenberger Straße 69 4040 Linz AUSTRIA


Abstract

Let \( q \) be a positive integer and

\[
\mathcal{S} = \{x_0, x_1, \ldots, x_{T-1}\} \subseteq \mathbb{Z}_q = \{0, 1, \ldots, q-1\}
\]

with

\[
0 \leq x_0 < x_1 < \cdots < x_{T-1} \leq q-1 \]

We derive from \( \mathcal{S} \) three (finite) sequences:

(1) For an integer \( M \geq 2 \) let \( (s_n) \) be the M-ary sequence defined by

\[
s_n \equiv x_{n+1} - x_n \bmod M, \qquad n = 0, 1, \ldots, T-2,
\]

(2) For an integer \( m \geq 2 \) let \( (t_n) \) be the binary sequence defined by

\[
t_n = \begin{cases} 1 & \text{if } 1 \leq x_{n+1} - x_n \leq m-1, \\ 0, & \text{otherwise,} \end{cases} \qquad n = 0, 1, \ldots, T-2,
\]

(3) Let \( (u_n) \) be the characteristic sequence of \( \mathcal{S} \),

\[
u_n = \begin{cases} 1 & \text{if } n \in \mathcal{S}, \\ 0, & \text{otherwise,} \end{cases} \qquad n = 0, 1, \ldots, q-1.
\]

We study the balance and pattern distribution of the sequences \( (s_n) \), \( (t_n) \) and \( (u_n) \). For sets \( \mathcal{S} \) with desirable pseudorandom properties, more precisely, sets with low correlation measures, we show the following:

(1) The sequence \( (s_n) \) is (asymptotically) balanced and has uniform pattern distribution if \( T \) is of smaller order of magnitude than \( q \).

(2) The sequence \( (t_n) \) is balanced and has uniform pattern distribution if \( T \) is approximately \( \left(1 - \dfrac{1}{2^{1/(m-1)}}\right)q \).

(3) The sequence \( (u_n) \) is balanced and has uniform pattern distribution if \( T \) is approximately \( \dfrac{q}{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.


Keywords

sequence, pseudorandom subset, balance, pattern distribution, correlation.


Citation

Liu, H. & Winterhof, A. (2021). Balance and pattern distribution of sequences derived from pseudorandom subsets of zq. Uniform Distribution Theory, 16(2), 89–108. https://doi.org/10.2478/UDT-2021-0009

Published by: Engineering Journals

Engineering Journals Logo