Problems in between words and abelian words: \(k\)-abelian avoidability (Q714821): Difference between revisions

The sequence of Thue-Morse is a well-known example of a binary sequence avoiding cube factors. However, three symbols are needed to construct a sequence avoiding squares. A natural question arises, how many symbols are needed to avoid the more general patterns of \(k\)-abelian squares or cubes. Two words are \(k\)-abelian equivalent if they have identical prefix and suffix of length \(k-1\), respectively, and every factor of length \(k\) occurs in both words same number of times. \ A \(k\)-abelian square (cube) is a word of the form \(uv\) (\(uvz\)), where \(u,v\) (\(u,v,z\)) are pairwise \(k\)-abelian equivalent words. It is known that abelian (i.e., 1-abelian) squares can be avoided if the alphabet is of size 4. Using computerized search the authors find that at least 4 symbols are needed to avoid 2-abelian squares, since the longest 2-abelian square-free word over a ternary alphabet is of length 537. On the other hand, they find a word longer than 100 000 symbols avoiding 2-abelian cubes. The main result of the paper consists in the construction of an 8-abelian cube-free sequence over a binary alphabet.