A technique to study the correlation measures of binary sequences (Q998356): Difference between revisions

Consider a binary sequence \(E^N=\{e_1,e_2,\dots,e_N\}\), \(e_n=-1,+1\) and denote \[ C_k(E^N)=\max_{M,d_1,\dots,d_k}|\sum_{n=1}^Me_{n+d_1}e_{n+d_2}\dots e_{n+d_k}|, \] where the maximum is taken over all \(M\) and \(0\leq d_1<d_2<\dots<d_k\leq N-M\). This measure of pseudorandomness was introduced by \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 82, No. 4, 365--377 (1997; Zbl 0886.11048)]. In this paper the author studies a lower bound of \(C_k(E^N)\) via maximum \(|\sum_{n=1}^Me_n[d_1]e_n[d_2]\dots e_n[d_k]|\) over \(1\leq d_1<\dots<d_k\leq L\) for fixed \(M,L,k\) and for an arbitrary family of sequences \(E^M[d]=\{e_1[d],e_2[d],\dots,e_M[d]\}\), \(d=1,2,\dots,L\), \(e_n[d]=-1,+1\). Using simple combinatorial methods he found a lower and upper bound of \(\sum_{d_1,\dots,d_k=1}^L(\sum_{n=1}^Me_n[d_1]e_n[d_2]\dots e_n[d_k])^2\). Applying this technique the author generalizes a result of \textit{K. Gyarmati} [Stud. Sci. Math. Hung. 42, No. 1, 79--93 (2005; Zbl 1089.11041)] to the form that if \(C_2(E^N)\leq c_1N^{2/3}\) then \(C_3(E^N)\geq c_2\sqrt{N}\) for all sufficiently large \(N\), where the constant \(c_2\) depends on a constant \(c_1\). He also proves a conjecture of C. Mauduit which was mentioned by Gyarmati [cited above] that there exists an absolute constant \(c>0\) such that \(C_2(E^N)C_3(E^N)\geq cN\) for all sufficiently large \(N\).