A technique to study the correlation measures of binary sequences

Let EN=(e1,e2,…,eN)EN=(e1,e2,…,eN) be a binary sequence with ei∈{+1,−1}ei∈{+1,−1}. For 2≤k≤N2≤k≤N, the correlation measure of order kk of the sequence is defined by Mauduit and Sárközy as Ck(EN)=maxM,d1,…,dk|∑n=1Men+d1en+d2…en+dk| where the maximum is taken over all M≥1M≥1 and 0≤d10c2k>0 such that C2k(EN)≥c2kN for all ENEN for all large enough NN. thus answering a question of Cassaigne, Mauduit, and Sárközy (in stronger form than an earlier result of Kohayakawa, Mauduit, Moreira, and Rödl). We prove a lower bound on the even correlation measures C2k(EM[1:L])C2k(EM[1:L]) when L>k(2k−1)ML>k(2k−1)M and use it to provide an alternate proof of this result. The constant c2kc2k in our proof is better than that of Alon, Kohayakawa, Mauduit, Moreira, and Rödl for k=1k=1, but poorer for all k≥2k≥2.We study C3(EN)C3(EN) via C3(EM[1:L])C3(EM[1:L]). This allows us to strengthen a recent result of Gyarmati which relates C3(EN)C3(EN) and C2(EN)C2(EN). We prove that given any κ>0κ>0 there is an associated c>0c>0 (depending only on κκ) such that, for all sufficiently large NN, if C2(EN)≤κN2/3C2(EN)≤κN2/3 we have C3(EN)≥cN. This also answers a question of Gyarmati.Finally, the study of C3(EM[1:L])C3(EM[1:L]) allows us to verify a conjecture of Mauduit. We prove that there is an absolute constant c>0c>0 such that C2(EN)C3(EN)≥cNC2(EN)C3(EN)≥cN for all ENEN for all large enough NN.