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.
Speakers 1
Past sessions
Discussion 0 Open full thread →
Similar Events
Claim this event
If you are the organizer of this event on researchseminars.org, you can request to claim it on Androma. This will let you manage the event, add prerequisites, and link it to your Androma profile.
Claim submitted. An admin will review your request.