Measures of Pseudorandomness for Finite Sequences: Minimal Values
Noga Alon, Yoshiharu Kohayakawa, Christian Mauduit, Carlos Gustavo Moreira, Vojtch Rödl · Combinatorics Probability Computing · 2006
Abstract. Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ {−1, 1} N in order to measure their ‘level of randomness’. Two of these parameters are the normality measure N (EN) and the correlation measure Ck(EN) of order k, which focus on different combinatorial aspects of EN. In their work, amongst others, Mauduit and Sárközy investigated the minimal possible value of these parameters. In this paper, we continue the work in this direction and prove a lower bound for the correlation measure Ck(EN) (k even) for arbitrary sequences EN, establishing one of their conjectures. We also give an algebraic construction for a sequence EN with small normality measure N (EN). Contents