Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-24T16:17:32.061Z Has data issue: false hasContentIssue false
  • English
  • Français

The Rudin–Shapiro Sequence and Similar Sequences Are Normal Along Squares

Published online by Cambridge University Press:  20 November 2018

Clemens Müllner
Clemens Müllner*
Affiliation:
Institut für Diskrete Mathematik und Geometrie TU Wien, Wiedner Hauptstr. 8-10, 1040 Wien, Austria, e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We prove that digital sequences modulo $m$ along squares are normal, which covers some prominent sequences, such as the sum of digits in base $q$ modulo $m$, the Rudin–Shapiro sequence, and some generalizations. This gives, for any base, a class of explicit normal numbers that can be efficiently generated.

Keywords

11A6311B8511L0311N6060F05Rudin–Shapiro sequencedigital sequencesnormalityexponential sums
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 70 , Issue 5 , 01 October 2018 , pp. 1096 - 1129
Copyright
Copyright © Canadian Mathematical Society 2018

References

[1] Allouche, J.-P. and Shallit, J., Automatic sequences. Cambridge, Cambridge University Press, 2003.Google Scholar
[2] Bêcher, V., Heiber, P. A., and Slaman, T. A., A polynomial-time algorithm for computing absolutely normal numbers. Inform, and Comput. 232 (2013), 1–9. http://dx.doi.org/10.1016/j.ic.2O13.08.013Google Scholar
[3] Bellman, R. and Shapiro, H. N., On a problem in additive number theory. Ann. of Math. (2) 49(1948,333-340. http://dx.doi.org/10.2307/1969281Google Scholar
[4] Bugeaud, Y., Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics, 193. Cambridge University Press, Cambridge, 2012.Google Scholar
[5] Cateland, E., Suites digitales et suites k-régulières. Ph.D. thesis, Université Bordeaux 1, 1992.Google Scholar
[6] Drmota, M., Mauduit, C., and Rivat, J., The Thue-Morse sequence along squares is normal. http://www.dmg.tuwien.ac.at/drmota/alongsquares.pdfGoogle Scholar
[7] Ferenczi, S., Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) no. 1-3, 145–154. http://dx.doi.Org/10.101 6/S0012-365X(98)00400-2Google Scholar
[8] Fogg, N. P., Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics, 1794. Springer-Verlag, Berlin, 2002.Google Scholar
[9] GePfond, A. O., Sur les nombres qui ont des propriétés additives et multiplicatives données. Acta Arith. 13(1967/1968), 259–265.Google Scholar
[10] Kurka, P., Topological and symbolic dynamics. Cours Spécialisés, 11. Société Mathématique de France, Paris, 2003.Google Scholar
[11] Levin, M. B., Absolutely normal numbers. Vestnik Moskov. Univ. Ser. I Mat. Mekh. (1979), no. 1, 31-37, 87.Google Scholar
[12] Mauduit, C. and Rivat, J., La somme des chiffres des carrés. Acta Math. 203 (2009) no. 1,107-148. http://dx.doi.Org/10.1007/s11511-009-0040-0Google Scholar
[13] Mauduit, C. and Rivat, J., Prime numbers along Rudin-Shapiro sequences. J. Eur. Math. Soc. (JEMS) 17 (2015), no. 10, 2595–2642. http://dx.doi.org/10.4171/JEMS/566Google Scholar
[14] France, M. Mendès, Nombres normaux. Applications aux fonctions pseudo-aléatoires. J. Analyse Math. 20 (1967), 1–56.Google Scholar
[15] Moshe, Y., On the subword complexity of Thue-Morse polynomial extractions. Theoret. Comput. Sci. 389 (2007) no. 1-2, 318-329. http://dx.doi.Org/10.1016/j.tcs.2007.10.015Google Scholar
[16] Queffélec, M., Substitution dynamical systems-spectral analysis. Second edition. Lecture Notes in Mathematics, 1294. Springer-Verlag, Berlin, 2010.Google Scholar
[17] Scheerer, A.-M., Computable absolutely normal numbers and discrepancies. Math. Comp. 86 (2017), no. 308, 2911–2926. http://dx.doi.org/10.1090/mcom/3189Google Scholar
[18] Schmidt, W. M., Ûber die Normalitàt von Zahlen zu verschiedenen Basen. Acta Arith. 7(1961/1962), 299-309. http://dx.doi.Org/1 0.4064/aa-7-3-299-309Google Scholar
[19] Sierpinski, W., Démonstration élémentaire du théorème de M. Borel sur les nombres absolument normaux et détermination effective d'une tel nombre. Bull. Soc. Math. France 45 (1917), 125–132. http://dx.doi.org/10.24033/bsmf.977Google Scholar
[20] Turing, A. and Saunders, P., Collected Works of A. M. Turing. North-Holland, Amsterdam, 1992.Google Scholar
[21] Vaaler, J. D., Some extremal functions in Fourier analysis. Bull. Amer. Math. Soc. (N.S.) 12 (1985), no. 2, 183–216., 1985. http://dx.doi.org/10.1090/S0273-0979-1985-15349-2Google Scholar