zbMATH — the first resource for mathematics

On finite pseudorandom binary sequences. II: The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction. (English) Zbl 0916.11047
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.
Reviewer: R.F.Tichy (Graz)

11K45 Pseudo-random numbers; Monte Carlo methods
11B83 Special sequences and polynomials
Full Text: DOI
[1] Allouche, J.P., The number of factors in a paperfolding sequence, Bull. austral. math. soc., 46, 23-32, (1992) · Zbl 0753.11011
[2] Champernowne, D.G., The construction of decimals normal in the scale of ten, J. London math. soc., 8, 254-260, (1933) · Zbl 0007.33701
[3] Fouvry, E.; Mauduit, C., Sommes des chiffres et nombres presque premiers, Math. ann., 305, 571-599, (1996) · Zbl 0858.11050
[4] Gelfond, A.O., Sur LES nombres qui ont des propriétés additives et multiplicatives données, Acta arith., 13, 259-265, (1968) · Zbl 0155.09003
[5] Knuth, D.E., The art of computer programming, (1981), Addison- Wesley Reading · Zbl 0191.17903
[6] Lidl, R.; Mullen, G.L.; Turnwald, G., Dickson polynomials, Pitman monographs, 65, (1993), Longman Harlow
[7] Lidl, R.; Niederreiter, H., Finite fields, Encyclopedia of math. appl., 20, (1983), Addison-Wesley Reading
[8] C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. · Zbl 0886.11048
[9] Queffelec, M., Substitution dynamical systems—spectral analysis, Lecture notes in math., 1294, (1987), Springer-Verlag New York/Berlin
[10] Rudin, W., Some theorems on Fourier coefficients, Proc. amer. math. soc., 10, 855-859, (1959) · Zbl 0091.05706
[11] Shapiro, H.S., Extremal problems for polynomials and power series, (1951), M.I.T
[12] Weil, A., Sur LES courbes algébriques et LES variétés qui s’en déduisent, Actualités sci. indust., (1948), Hermann Paris · Zbl 0036.16001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.