Extremal square-free words (Q2309218)

Summary: A word is square-free if it does not contain nonempty factors of the form \(XX\). \textit{A. Thue} [Über unendliche Zeichenreihen (Norwegian). Christiana Vidensk. Selsk. Skr. 1906. Nr. 7. 22 S. Lex. \(8^{\circ}\). (1906; JFM 37.0066.17)] proved that there exist arbitrarily long square-free words over a \(3\)-letter alphabet. We consider a new type of square-free words with additional property. A square-free word is called extremal if it cannot be extended to a new square-free word by inserting a single letter at any position. We prove that there exist infinitely many square-free extremal words over a \(3\)-letter alphabet. Some parts of our construction relies on computer verifications. It is not known if there exist any extremal square-free words over a \(4\)-letter alphabet.