Complexity of generalized Rudin-Shapiro sequences (Q1320516)

This is a useful paper for meeting and understanding the principles governing our understanding of the class of sequences on a finite alphabet termed automatic sequences. Let \((u_ n)\) be an infinite sequence. Then any word \(u_ n u_{n1} \cdots u_{nk-1}\) is called a factor of length \(k\). If \(P_ u (k)\) denotes the number of different factors of length \(k\) appearing in the sequence \(u\) then the map \(P_ u\) is called the complexity of the sequence. For example, the sequence is ultimately periodic if \(P_ u (n)\leq n\) for some \(n\). The present paper studies the generalized Rudin- Shapiro sequence \((u_{d,n} )= (u_ n)\) counting the number mod 2 of occurrences of a factor \(1*\cdots *1\), in the binary representation of \(n\), where \(*\cdots *\) is an arbitrary word of length \(d-1\). The authors show that asymptotically \(P_ u (n)\) is linear.