The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word

Abstract

We revisit the periodic complexity function $h_{\mathbf{w}}(n)$ introduced by Mignosi and Restivo. This function gives the average of the first $n$ local periods of a recurrent infinite word $\mathbf{w}$. We give a different method than that of Mignosi and Restivo for computing the asymptotics of the periodic complexity function of the Thue-Morse word and show how to apply the method to other automatic sequences, like the Rudin-Shapiro word and the period-doubling word.

arXiv comment8 pages, updated to properly credit Philippe Dumas for Theorem 4, bounds for the periodic complexity function of the period-doubling word added