Extremal Square-Free Words

Abstract

A word is square-free if it does not contain nonempty factors of the form $XX$. In 1906 Thue 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.