The cross-correlation measure of families of finite binary sequences: limiting distributions and minimal values (Q317423): Difference between revisions

\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.].