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
Poland

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

Abstract:

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