Balance and pattern distribution of sequences derived from pseudorandom subsets of \(\mathbb{Z}_q\) (Q2129367): Difference between revisions

For a positive integer $q$, let $\mathcal S=\{x_0,x_1,\dots,x_{T-1}\}\subseteq\mathbb Z_q$ with $0\le x_0<x_1<\dots<x_{T-1}\le q-1$. In this paper, the balance and pattern distribution are studied for the three finite sequences $(s_n)$, $(t_n)$ and $(u_n)$ derived from $\mathcal S$. For sets $\mathcal S$ with low correlation measures, the following is shown: (1) For an integer $M\ge 2$, $(s_n)$ ($n=0,1,\dots,T-2$) is the $M$-ary sequence defined by $s_n\equiv x_{n+1}-x_n\mod{M}$. Then the sequence $(s_n)$ is (asymptotically) balanced and has uniform pattern distribution if $T$ is of smaller order of magnitude than $q$. (2) For an integer $m\ge 2$, $(t_n)$ ($n=0,1,\dots,T-2$) is the binary sequence defined by $$ t_n=\begin{cases} 1&\text{ if }1\le x_{n+1}-x_n\le m-1,\\ 0&\text{otherwise}. \end{cases} $$ Then, the sequence $(t_n)$ is balanced and has uniform pattern distribution if $T$ is approximately $(1-2^{-1/(m-1)})q$. (3) $(u_n)$ ($n=0,1,\dots,q-1$) is the characteristic sequence of $\mathcal S$, defined by $$ u_n=\begin{cases} 1&\text{ if }n\in\mathcal S,\\ 0&\text{otherwise}. \end{cases} $$ Then, the sequence $(u_n)$ is balanced and has uniform pattern distribution if $T$ is approximately $q/2$. The approach of \textit{A. Winterhof} and \textit{Z. Xiao} [IEEE Trans. Inf. Theory 67, No. 8, 5334--5338 (2021; Zbl 1486.11155); Adv. Math. Commun. 16, No. 1, 83--93 (2022; Zbl 1481.94079)] is generalized for the sets of quadratic residues and primitive roots modulo $p$ to any pseudorandom subset. This unifies previous results and provides many further (asymptotically) balanced sequences with uniform pattern distribution from pseudorandom subsets.