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 nonempty word uv, where u and v are permutations of each other. For example, abc acb is an abelian square. A word is called abelian squarefree if it does not contain any abelian square as a factor. For example, the word abacaba is abelian squarefree, while ab cabdc bcacd ac is not. In 1992, we presented an abelian squarefree (a2free) 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 a2free 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 squarefree word.
In our talk we explain the computer searches carried out for finding new ways of constructing a2free words. In this process we have encountered some unintuitive nonlinear phenomena, which, however, are in accordance with the complex behavior of simple systems studied by Stephen Wolfram. For example, two candidates for prefixsuffix pairs of image words that look just similar, may yield 1000fold 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)
