The Thue-Morse Transform

Abstract: We define a transform $T$ on binary words. Given a binary word, we use the positions of its zeros and ones to build a new binary word. Applied to the alternating word $a_0 = 0101\ldots$, the transform gives the Thue-Morse word. We then study the orbit $a_m = T^m(a_0)$, together with the sequences $u_m$ and $v_m$ giving the positions of the ones and the zeros in $a_m$. We obtain an explicit formula for $a_m(n)$ in terms of the binary digits of $n$ and $m-1$. From this formula we derive Prouhet-Tarry-Escott identities, composition formulas that generalize the identities for evil and odious numbers, and a recurrence formula for the factor complexity of $a_m$. We end with a few directions, such as applying the transform to the Fibonacci word, which yields the Fibonacci-Thue-Morse word.

formal languages and automata theorycombinatoricsdynamical systems

Audience: researchers in the topic

One World Combinatorics on Words Seminar

Series comments: Please write to Anna Frid to receive the Zoom password and further announcements.