1. bookVolume 16 (2021): Edition 2 (December 2021)
Détails du magazine
License
Format
Magazine
eISSN
2309-5377
Première parution
30 Dec 2013
Périodicité
2 fois par an
Langues
Anglais
access type Accès libre

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

Publié en ligne: 02 Feb 2022
Volume & Edition: Volume 16 (2021) - Edition 2 (December 2021)
Pages: 89 - 108
Reçu: 15 Oct 2021
Accepté: 09 Nov 2021
Détails du magazine
License
Format
Magazine
eISSN
2309-5377
Première parution
30 Dec 2013
Périodicité
2 fois par an
Langues
Anglais
Abstract

Let q be a positive integer and 𝒮={x0,x1,,xT1}q={0,1,,q1} {\scr S} = \{{x_0},{x_1}, \cdots ,{x_{T - 1}}\}\subseteq {{\rm{\mathbb Z}}_q} = \{0,1, \ldots ,q - 1\} with 0x0<x1<<xT1q1. 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 (sn)be the M-ary sequence defined by sn ≡ xn+1 − xn mod M, n =0, 1,...,T − 2.

(2) For an integer m ≥ 2let (tn) be the binary sequence defined by snxn+1xnmodM,n=0,1,,T2. \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 (un) be the characteristic sequence of S, tn={1if1xn+1xnm1,0,otherwise,n=0,1,,T2. \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 (sn), (tn)and (un). For sets S with desirable pseudorandom properties, more precisely, sets with low correlation measures, we show the following:

(1) The sequence (sn) is (asymptotically) balanced and has uniform pattern distribution if T is of smaller order of magnitude than q.

(2) The sequence (tn) is balanced and has uniform pattern distribution if T is approximately un={1ifn𝒮,0,otherwise,n=0,1,,q1. \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 (un) is balanced and has uniform pattern distribution if T is approximately q2.

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

MSC 2010

ALLOUCHE, J.-P.—SHALLIT, J.: Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003.10.1017/CBO9780511546563Search in Google Scholar

CHEN, Z.: Large families of pseudo-random subsets formed by generalized cyclotomic classes, Monatsh. Math. 161 (2010), no. 2, 161–172.Search in Google Scholar

COBELI, C.—ZAHARESCU, A.: On the distribution of primitive roots mod p, Acta Arith. 83 (1998), no. 2, 143–153.Search in Google Scholar

DARTYGE, C.—MOSAKI, E.—SÁRKÖZY, A.: On large families of subsets of the set of the integers not exceeding N, Ramanujan J. 18 (2009), no. 2, 209–229.Search in Google Scholar

DARTYGE, C.—SÁRKÖZY, A.: On pseudo-random subsets of the set of the integers not exceeding N, Period. Math.Hungar. 54 (2007), no. 2, 183–200.Search in Google Scholar

DARTYGE, C.—SÁRKÖZY, A.: Large families of pseudorandom subsets formed by power residues, Unif. Distrib. Theory 2 (2007), no. 2, 73–88.Search in Google Scholar

DARTYGE, C.—SÁRKÖZY, A.: On pseudo-random subsets ofn, Monatsh. Math. 157 (2009), no. 1, 13–35.Search in Google Scholar

DARTYGE, C.—SÁRKÖZY, A.—SZALAY, M.: On the pseudo-randomness of subsets related to primitive roots, Combinatorica 30 (2010), no. 2, 139–162.Search in Google Scholar

DING, C.: Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory 44 (1998), no. 4, 1693–1698.Search in Google Scholar

GYARMATI, K.: On a family of pseudo-random binary sequences, Period. Math. Hungar. 49 (2004), no. 2, 45–63.Search in Google Scholar

HARDY, G. H.—WRIGHT, E. M.: An introduction to the theory of numbers. Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979.Search in Google Scholar

LIU, H.—QI, Y.: On multi-dimensional pseudorandom subsets, J. Number Theory 181 (2017), 73–88.10.1016/j.jnt.2017.05.025Search in Google Scholar

LIU, H.—SONG, E.: A note on pseudorandom subsets formed by generalized cyclotomic classes, Publ. Math. Debrecen 85 (2014), no. 3-4, 257–271.Search in Google Scholar

LIU, H.—ZHANG, G.: Pseudo-random subsets constructed by using Fermat quotients, Publ. Math. Debrecen 94 (2019), no. 1-2, 55–74.Search in Google Scholar

WINTERHOF, A.—XIAO, Z.: Binary sequences derived from differences of consecutive primitive roots, IEEE Trans. Inform.Theory 67 (2021), no. 8, 5334–5338.Search in Google Scholar

WINTERHOF, A.—XIAO, Z.: Binary sequences derived from differences of consecutive quadratic residues, Adv. Math. Commun. to be published, doi: 10.3934/amc.2020100.10.3934/amc.2020100Search in Google Scholar

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo