The cross-correlation measure of families of finite binary sequences: limiting distributions and minimal values
type: Item
instance of: scholarly article
title: The cross-correlation measure of families of finite binary sequences: limiting distributions and minimal values
zbMATH Open document ID: 1371.11122
author: László Mérai
published in: Discrete Applied Mathematics
publication date: 2016-09-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1608.02354
review text: \textit{K. Gyarmati} et al. [in: Applied algebra and number theory. Essays in honor of Harald Niederreiter on the occasion of his 70th birthday. Cambridge: Cambridge University Press. 126--143 (2014; Zbl 1368.11082)] introduced the notion of the cross-correlation measure of order \(k\) to measure the quality of pseudorandom properties of families of finite binary \(\{-1,+1\}\)-sequences instead of single sequences. Let \(G_{N,S}:\{1,2,\dots,S\}\to \{-1,+1\}^N\) and \(G_{N,S}(s)=(e_1(s),\dots,e_N(s))\). The cross-correlation measure \(\Phi_k(G_{N,S})\) of order \(k\) of \(G_{N,S}\) is defined as \(\Phi_k(G_{N,S})=\max\left|\sum^M_{n=1}e_{n+d_1}(s_1)\dots e_{n+d_k}(s_k)\right|\) where the maximum is taken over all the reasonable values of the involved parameters. In the above mentioned paper, only injective maps \(G_{N,S}\) were considered and the cross-correlation measure was defined only for families of \(G_{N,S}(s)\) of size \(S\). In the first main result, the author proves that analogously to the correlation measure of binary sequences [\textit{L. Mérai}, Monatsh. Math. 180, No. 1, 83--99 (2016; Zbl 1336.11057)] the cross-correlation measure of families \(\Phi_k(G_{N,S})\) is concentrated around its mean \({\mathbb E}[\Phi_k(G_{N,S})]\) if \(k\) is small enough. Then, the asymptotic distribution of the cross-correlation measure is obtained and sharp upper and lower bounds on the minimum values of the cross-correlation measure \(\Phi(G_{N,S})\) are proved, thereby answering almost completely a problem posed by Gyarmati, Mauduit and Sárközy [loc. cit.].
reviewed by: Štefan Porubský
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11K36
Mathematics Subject Classification ID: 11K38
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6631748
zbMATH Keywords: pseudorandom sequence
zbMATH Keywords: binary sequence
zbMATH Keywords: correlation measure
zbMATH Keywords: cross-correlation measure
MaRDI profile type: Publication
OpenAlex ID: W2498897242
arXiv ID: 1608.02354
cites work: On the correlation of binary sequences
cites work: Measures of Pseudorandomness for Finite Sequences: Minimal Values
cites work: Measures of pseudorandomness for finite sequences: typical values
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Q3682518
cites work: On finite pseudorandom binary sequences VII: The measures of pseudorandomness
cites work: Q5538132
cites work: Q5496104
cites work: The cross-correlation measure for families of binary sequences
cites work: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
cites work: On the measures of pseudorandomness of binary sequences.
cites work: Q3496342
cites work: On the typical values of the cross-correlation measure
cites work: The peak sidelobe level of random binary sequences
DOI: 10.1016/J.DAM.2016.06.024
Recommended article: The cross-correlation measure for families of binary sequences
Recommended article: On the typical values of the cross-correlation measure
Recommended article: Family complexity and cross-correlation measure for families of binary sequences
Recommended article: On the measures of pseudorandomness of binary sequences.
Recommended article: On finite pseudorandom binary sequences VII: The measures of pseudorandomness
Recommended article: Families of Pseudorandom Binary Sequences with Low Cross-Correlation Measure
Recommended article: On a pseudorandom property of binary sequences
Recommended article: Correlation measure, linear complexity and maximum order complexity for families of binary sequences
Recommended article: More constructions of pseudorandom sequences of \(k\) symbols
description: scientific article; zbMATH DE number 6631748