A family of Sequences Generalizing the Thue–Morse and Rudin-Shapiro Sequences

Abstract: For $m \ge 1,$ let $P_m =1^m,$ the binary string of $m$ ones. Further define the infinite sequence $s_m$ by $s_{m,n} = 1$ iff the number of (possibly overlapping) occurrences of $P_m$ in the binary representation of $n$ is odd, $n \ge 0.$ For $m=1,2$ respectively $s_m$ is the Thue-Morse and Rudin-Shapiro sequences. This paper shows: (i) $s_m$ is automatic; (ii) the minimal, DFA (deterministic finite automata) accepting $s_m$ has $2m$ states; (iii) it suffices to use prefixes of length $2^{m-1}$ to distinguish all sequences in the 2-kernel of $s_m$; and (iv) the characteristic function of the length $2^{m-1}$ prefix of the 2-kernel sequences of $s_m$ can be formulated using the Vile and Jacobstahl sequences. The proofs exploit connections between string operations on binary strings and the numbers they represent. Both Mathematica and Walnut are employed for exploratory analysis of patterns. In particular, we generalize the famous result about the Thue-Morse sequence that the orders of squares in the sequence are of the form $(2^i)_{i \ge 0} \cup 3 \times (2^i)_{i \ge 0.}$

combinatoricsnumber theory

Audience: researchers in the topic

New York Number Theory Seminar