Power-free Complementary Binary Morphisms

• Published in: arXiv.org 2023-12
• Main Authors: Shallit, Jeffrey, Shur, Arseny M, Zorcic, Stefan
• Format: Article
• Language: English
• Subjects: Combinatorial analysis
• ISSN: 2331-8422

We revisit the topic of power-free morphisms, focusing on the properties of the class of complementary morphisms. Such morphisms are defined over a \(2\)-letter alphabet, and map the letters 0 and 1 to complementary words. We prove that every prefix of the famous Thue-Morse word \(\mathbf{t}\) gives a complementary morphism that is \(3^+\)-free and hence \(\alpha\)-free for every real number \(\alpha>3\). We also describe, using a 4-state binary finite automaton, the lengths of all prefixes of \(\mathbf{t}\) that give cubefree complementary morphisms. Next, we show that \(3\)-free (cubefree) complementary morphisms of length \(k\) exist for all \(k\not\in \{3,6\}\). Moreover, if \(k\) is not of the form \(3\cdot2^n\), then the images of letters can be chosen to be factors of \(\mathbf{t}\). Finally, we observe that each cubefree complementary morphism is also \(\alpha\)-free for some \(\alpha