On the Correlation of Subsequences

In 1997 Sárközy and Mauduit introduced the well-distribution measure (W ) and the correlation measure of order ℓ (C ℓ) of binary sequences as measures of their pseudorandomness. For a truly random binary sequence these measures are small (≪ N1/2(log N)c for a sequence of length N). Several constructions have been given for which these measures are small, namely they are ≪ N1/2(log N)c, so the sequence E N has strong pseudorandom properties. But in certain applications, e.g. in cryptography, it is not enough to know that the sequence has strong pseudorandom properties, it is also important that the subsequences E M (where E M is of the form {ex, e x+1, ..., e x+M−1}) also have strong pseudorandom properties for values M possibly small in terms of N. In this paper I will deal with this problem in case of values M ≫ N1/4+ε.