Gaps in the Thue--Morse word

Lukas Spiegelhofer

Published 2021-02-01Version 1

The Thue--Morse sequence is a prototypical automatic sequence found in diverse areas of mathematics, and in computer science. We study occurrences of factors $w$ within this sequence, more precisely the sequence of gaps between consecutive occurrences. This sequence is substitutive; we prove that it is not automatic as soon as the length of $w$ is greater than $1$, thereby answering a question by J.~Shallit in the affirmative.