Journal of Integer Sequences, Vol. 24 (2021), Article 21.8.7

Squarefree Extensions of Words

Jarosław Grytczuk and Hubert Kordulewski
Faculty of Mathematics and Information Science
Warsaw University of Technology
00-662 Warsaw

Bartłomiej Pawlik
Institute of Mathematics
Silesian University of Technology
44-100 Gliwice


A word is squarefree if it does not contain nonempty factors of the form XX. In 1906 Thue proved that there exist arbitrarily long squarefree words over a 3-letter alphabet. It was proved recently that among these words there are infinitely many extremal ones, that is, having a square in every single-letter extension.

We study diverse problems concerning extensions of words preserving the property of avoiding squares. Our main motivation is the conjecture stating that there are no extremal words over a 4-letter alphabet. We also investigate a natural recursive procedure of generating squarefree words by a single-letter rightmost extension. We present the results of computer experiments supporting a supposition that this procedure gives an infinite squarefree word over any alphabet of size at least three.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A006742.)

Received May 1 2021; revised versions received May 4 2021; August 17 2021; August 30 2021. Published in Journal of Integer Sequences, September 23 2021.

Return to Journal of Integer Sequences home page