Article
Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of Zq
Authors
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
Citation
Published by: Engineering Journals


