December, 2021

89-108

Huaning Liu and Arne Winterhof

Let q be a positive integer and 𝒮={x0,x1,⋯,xT−1}⊆ℤq={0,1,…,q−1} with 0≤x0<x1<⋯<xT−1≤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. 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. 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. .

(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.

Liu, H. & Winterhof, A. (2021). Balance and Pattern Distribution of Sequences Derived from Pseudorandom Subsets of ℤq. Uniform distribution theory, 16(2), 89-108. https://doi.org/10.2478/udt-2021-0009