Avoiding Abelian Patterns in Words

Veikko Keränen
Rovaniemi Polytechnic

The systematic study of structures in words was started by Axel Thue in 1906. In 1961, Paul Erdös raised the question whether abelian squares can be avoided in infinitely long words. An abelian square means a non-empty word uv, where u and v are permutations of each other. For example, abc acb is an abelian square. A word is called abelian square-free if it does not contain any abelian square as a factor. For example, the word abacaba is abelian square-free, while ab cabdc bcacd ac is not. In 1992, we presented an abelian square-free (a-2-free) endomorphism g85 over the four letter alphabet. The size of g85 is equal to 4×85, and it was found after long computer experiments. Until very recently, all known methods for constructing arbitrarily long a-2-free words have been based on the structure of g85. In 2002, after over 11 years of exhaustive searches, we found a completely new endomorphism g98, the iteration of which produces an infinite abelian square-free word.

In our talk we explain the computer searches carried out for finding new ways of constructing a-2-free words. In this process we have encountered some unintuitive non-linear phenomena, which, however, are in accordance with the complex behavior of simple systems studied by Stephen Wolfram. For example, two candidates for prefix-suffix pairs of image words that look just similar, may yield 1000-fold running times when searching through all possibilities for proper infixes!

We also discuss some open problems related to pattern avoidance and show tentative examples of certain combined abelian patterns where the number of words avoiding these patterns seems to vary in a complicated way.     

Created by Mathematica  (April 20, 2004)