On finite pseudorandom binary sequences. II: The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction (Q1277184)

This interesting paper is the continuation of part I, which appeared in Acta Arith. 82, 365-377 (1997; Zbl 0886.11048). The authors consider special sequences over a binary alphabet and present some arithmetic tests for pseudorandomness. As measures of pseudorandomness, well-distribution relative to arithmetic progressions and small (auto) correlation are used. These properties of the Champernowne, the Thue-Morse and the Rudin-Shapiro sequences are studied, and it is shown that these sequences are not sufficiently well distributed to be considered as pseudorandom. Finally, by using the Legendre symbol and permutation polynomials, a nearly ideally pseudorandom sequence is constructed. The proof of this result heavily depends on character sum estimates.