Abstract
We show how to obtain, via a unified framework provided by logic and automata theory, many classical results of Brillhart and Morton on Rudin-Shapiro sums. The techniques also facilitate easy proofs for new results.
Research of Narad Rampersad is supported by NSERC Grant number 2019-04111. Research of Jeffrey Shallit is supported by NSERC Grant number 2018-04118.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
One can make the case that these definitions are “wrong”, in the sense that many results become significantly simpler to state if the sums are taken over the range \(0 \le i < n\) instead. But the definitions of Brillhart-Morton are now very well-established, and using a different indexing would also make it harder to compare our results with theirs.
- 2.
The main exceptions are their results about the limit points of \(s(n)/\sqrt{n}\) and \(t(n)/\sqrt{n}\).
- 3.
In fact, all the Walnut code in this paper runs in a matter of milliseconds.
- 4.
Maple code implementing this algorithm is available from the second author.
References
Allouche, J.-P.: Automates finis en théorie des nombres. Exposition. Math. 5, 239–266 (1987)
Berstel, J., Reutenauer, C.: Noncommutative Rational Series With Applications, vol. 137. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2011)
Brillhart, J., Morton, P.: Über Summen von Rudin-Shapiroschen Koeffizienten. Illinois J. Math. 22, 126–148 (1978)
Brillhart, J., Erdős, P., Morton, P.: On sums of Rudin-Shapiro coefficients. II. Pacific J. Math. 107, 39–69 (1983)
Brillhart, J., Morton, P.: A case study in mathematical research: the Golay-Rudin-Shapiro sequence. Amer. Math. Monthly 103, 854–869 (1996)
Carpi, A., Maggi, C.: On synchronized sequences and their separators. RAIRO Inform. Théor. App. 35, 513–524 (2001)
Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3, 186–192 (1969)
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972)
Dekking, F.M., Mendès France, M., van der Poorten, A.J.: Folds! Math. Intelligencer 4, 130–138, 173–181, 190–195 (1982). Erratum 5, 5 (1983)
Golay, M.J.E.: Multi-slit spectrometry. J. Optical Soc. Amer. 39, 437–444 (1949)
Golay, M.J.E.: Static multislit spectrometry and its application to the panoramic display of infrared spectra. J. Opt. Soc. Am. 41, 468–472 (1951)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston (1979)
Kahane, J.-P.: Some Random Series of Functions. Cambridge Studies in Advanced Mathematics, vol. 5, 2nd edn. Cambridge University Press, Cambridge (1994)
Konieczny, J.: Gowers norms for the Thue-Morse and Rudin-Shapiro sequences. Annales de l’Institut Fourier 69, 1897–1913 (2019)
Lafrance, P., Rampersad, N., Yee, R.: Some properties of a Rudin-Shapiro-like sequence. Adv. Appl. Math. 63, 19–40 (2015)
Mauduit, C., Rivat, J.: Prime numbers along Rudin-Shapiro sequences. J. Eur. Math. Soc. 17, 2595–2642 (2015)
Mendès France, M., Tenenbaum, G.: Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro. Bull. Soc. Math. France 109, 207–215 (1981)
Mendès France, M.: Paper folding, space-filling curves and Rudin-Shapiro sequences. In: Papers in Algebra, Analysis and Statistics, vol. 9. Contemporary Mathematics, American Mathematical Society, pp. 85–95 (1982)
Mousavi, H.: Automatic theorem proving in Walnut. Arxiv preprint arXiv:1603.06017 [cs.FL] (2016)
Rampersad, N., Shallit, J.: Rudin-Shapiro sums via automata theory and logic. Arxiv preprint arXiv:2302.00405 [math.NT], 1 February 2023
Rudin, W.: Some theorems on Fourier coefficients. Proc. Am. Math. Soc. 10, 855–859 (1959)
Shallit, J.: Synchronized sequences. In: Lecroq, T., Puzynina, S. (eds.) WORDS 2021. LNCS, vol. 12847, pp. 1–19. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-85088-3_1
Shallit, J.: The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut, vol. 482. London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (2022)
Shallit, J.: Rarefied Thue-Morse sums via automata theory and logic. Arxiv preprint ArXiv:2302.09436 [math.NT], 18 February 2023. https://arxiv.org/abs/2302.09436
Shapiro, H.S.: Extremal problems for polynomials and power series. Master’s thesis, MIT (1951)
Sloane, N.J.A., et al.: The On-line Encyclopedia of Integer Sequences (2023). https://oeis.org
Acknowledgments
We are grateful to Jean-Paul Allouche and to the referees for several helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Rampersad, N., Shallit, J. (2023). Rudin-Shapiro Sums via Automata Theory and Logic. In: Frid, A., Mercaş, R. (eds) Combinatorics on Words. WORDS 2023. Lecture Notes in Computer Science, vol 13899. Springer, Cham. https://doi.org/10.1007/978-3-031-33180-0_18
Download citation
DOI: https://doi.org/10.1007/978-3-031-33180-0_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33179-4
Online ISBN: 978-3-031-33180-0
eBook Packages: Computer ScienceComputer Science (R0)