arXiv:2104.04841math.CO
Square-free extensions of words
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
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. It was proved recently [7] 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 square-free words by a single-letter right-most extension. We present the results of computer experiments supporting a supposition that this procedure gives an infinite square-free word over any alphabet of size at least three.
Cool! This paper is also quite readable: https://arxiv.org/pdf/2104.04841 On p.2 they follow my idea of adding the lowest possible letter at the end, although they generalise it to adding the letter as close to the end as possible. They conjecture that this process does not…
n4r9View on HNParent context