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

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 (s_n)be the M-ary sequence defined by s_n ≡ x_n+1 − x_n mod M, n =0, 1,...,T − 2.

(2) For an integer m ≥ 2let (t_n) be the binary sequence defined by sn≡xn+1−xnmodM,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 (u_n) be the characteristic sequence of S, tn={1if1≤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 (s_n), (t_n)and (u_n). For sets 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 un={1ifn∈𝒮,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 (u_n) is balanced and has uniform pattern distribution if T is approximately ^q₂.

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.