Balance and pattern distribution of sequences derived from pseudorandom subsets of Z_q

DOI10.2478/UDT-2021-0009zbMATH Open1490.11075arXiv2111.05662OpenAlexW4210328168MaRDI QIDQ2129367FDOQ2129367

Huaning Liu, Arne Winterhof

Publication date: 22 April 2022

Published in: Uniform distribution theory (Search for Journal in Brave)

Abstract: Let $q$ be a positive integer and $mathcalS=left{x}_0,x_1,ldots,x_{T-1}ightsubseteqmathbb{Z}_q=0,1,ldots,q-1$ with ${\displaystyle }$0leq x_0<x_1<ldots< x_{T-1}leq q-1.${\displaystyle }$ We derive from $mathcalS$ three (finite) sequences. 1. For an integer $Mgeq2$ let $(s_n)$ be the $M$-ary sequence defined by �egin{eqnarray*} s_nequiv x_{n+1}-x_n �mod M, qquad n=0,1,ldots, T-2. end{eqnarray*} 2. For an integer $mgeq2$ let $(t_n)$ be the binary sequence defined by �egin{eqnarray*} t_n=left{�egin{array}{ll} 1, & hbox{if } 1leq x_{n+1}-x_nleq m-1, \ 0, & hbox{otherwise}, end{array} ight. qquad n=0,1,ldots, T-2. end{eqnarray*} 3. Let $(u_n)$ be the characteristic sequence of $mathcalS$, �egin{eqnarray*} u_n=left{�egin{array}{ll} 1, & hbox{if } nin mathcal{S}, \ 0, & hbox{otherwise}, end{array} ight. qquad n=0,1,ldots, q-1. end{eqnarray*} We study the balance and pattern distribution of the sequences $(s_n)$, $(t_n)$ and $(u_n)$. For sets $mathcalS$ 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-frac12^{1/(m-1)}ight)q$. 3. The sequence $(u_n)$ is balanced and has uniform pattern distribution if $T$ is approximately $fracq2$. 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.

Full work available at URL: https://arxiv.org/abs/2111.05662

zbMATH Keywords

balancecorrelation measuresequencepattern distributionpseudorandom subset

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Pseudo-random numbers; Monte Carlo methods (11K45) Miscellaneous applications of number theory (11Z05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Automatic Sequences
• On large families of subsets of the set of the integers not exceeding \(N\)
• On a family of pseudorandom binary sequences
• Pattern distributions of Legendre sequences
• On the pseudo-randomness of subsets related to primitive roots
• On pseudo-random subsets of the set of the integers not exceeding \(N\)
• On the distribution of primitive roots mod p
• On pseudo-random subsets of \({\mathbb{Z}}_n\)
• Pseudo-random subsets constructed by using Fermat quotients
• A note on pseudorandom subsets formed by generalized cyclotomic classes
• On multi-dimensional pseudorandom subsets
• Large families of pseudo-random subsets formed by generalized cyclotomic classes
• Binary sequences derived from differences of consecutive quadratic residues
• Binary Sequences Derived From Differences of Consecutive Primitive Roots

Cited In (1)

• Camel sequences and quadratic residues

   Recommendations

• Algorithmic classification of noncorrelated binary pattern sequences 👍 👎
• On Irregularities of Distribution of Binary Sequences Relative to Arithmetic Progressions, II (Constructive Bounds) 👍 👎
• Title not available (Why is that?) 👍 👎
• Uniform distribution of the weighted sum-of-digits functions 👍 👎
• Linear recursion properties of uncorrelated binary sequences 👍 👎
• On a Problem of Steinhaus Concerning Binary Sequences 👍 👎
• Binary odd-periodic complementary sequences 👍 👎
• On the discrepancy and pseudorandomness of new sequences 👍 👎
• A New Class of Sequences With Zero or Low Correlation Zone Based on Interleaving Technique 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Balance and pattern distribution of sequences derived from pseudorandom subsets of \(\mathbb{Z}_q\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2129367)