Existence of arbitrarily long square-free words with one possible mismatch

We are concerned with problems of the existence of periodic structures in words from formal languages. We consider both squares (that is, fragments of the form $xx$, where $x$ is an arbitrary word) and squares with one mismatch (that is, fragments of the form $xy$, where a word $x$ differs from a word $y$ by exactly one letter). Given natural numbers $l_0$ and $l_1$, we study conditions for the existence of arbitrarily long words not containing squares with length larger than $l_0$ and squares with one mismatch and length larger than $l_1$. For all possible pairs $l_1\geq l_0$ a minimal alphabet cardinality is found which permits to construct such a word.

\linebreak This research was carried out with the financial support of the Russian Foundation for Basic Research (grant no. 14-01-00598) and of the Branch of Mathematics of the Russian Academy of Sciences Program “Algebraic and combinatorial methods of mathematical cybernetics and new generation information systems” (the project “Problem of optimal synthesis of control systems”).