Explaining one failing (semi)systematic trial

Veikko Keränen, 2003

Over forty years of study, nearly all systematic attempts for constructing long abelian square-free words over four letters have failed. Only g85, Carpi's modification of it, and g98 are known examples of such succesful constructions. Both g85 and g98 were found by using exhaustive searches of a large number of candidates.

As an example of a failing semi-systematic method consider the following. Start with the five letter word  abaca  and try to repeatedly continue with a five letter pattern  XYXZX  (X, Y, Z  are letter variables over {a,b,c,d}). By using symbolic computing, we found e.g. that there are  16964  abelian square-free words of length  85  having this form. However, the tree of words will not be expanding beyond this, though some branches are still growing. Finally, there remains only  8  words of length  145,  and no one of them can be continued, in any way, to the left or to the right more than two letters without creating an abelian square. These  8  words are as follows:

abacaXYXZX145 =

{"abacabdbabcacdcabadabcbabdadcdabadacbcacdadbdcacdcbdbabdcdadbabcbadabacbcdcbabdbcdcacdbdadcacbcadacabdbabcacdcbabcbdcdadbabcbadabacdcacbabdbacaba", "abacabdbabcacdcabadabcbabdadcdabadacbcacdadbdcacdcbdbabdcdadbabcbadabacbcdcbabdbcdcacdbdadcacbcadacabdbabcacdcbabcbdcdadbabcbadabacdcacbabdbacada", "abacabdbabcacdcabadabcbabdadcdbcbabcdcacbabdbacadacbcacdadbdcacdcbdbabcdcbcabadabcbabdadcdbabdbcdcacdbdadcacbcadabadcdadbabcbadabacdcacbabdbacaba", "abacabdbabcacdcabadabcbabdadcdbcbabcdcacbabdbacadacbcacdadbdcacdcbdbabcdcbcabadabcbabdadcdbabdbcdcacdbdadcacbcadabadcdadbabcbadabacdcacbabdbacada", "abacadbdadcacbcadabadcdadbabcbadabacdcacbabdbcacbcdbdadbcbabdadcdabadacdcbcdadbdcbcacbdbabcacdcabacadbdadcacbcdadcdbcbabdadcdabadacbcacdadbdacaba", "abacadbdadcacbcadabadcdadbabcbadabacdcacbabdbcacbcdbdadbcbabdadcdabadacdcbcdadbdcbcacbdbabcacdcabacadbdadcacbcdadcdbcbabdadcdabadacbcacdadbdacada", "abacadbdadcacbcadabadcdadbabcbdcdadcbcacdadbdacabacdcacbabdbcacbcdbdadcbcdcadabadcdadbabcbdadbdcbcacbdbabcacdcabadabcbabdadcdabadacbcacdadbdacaba", "abacadbdadcacbcadabadcdadbabcbdcdadcbcacdadbdacabacdcacbabdbcacbcdbdadcbcdcadabadcdadbabcbdadbdcbcacbdbabcacdcabadabcbabdadcdabadacbcacdadbdacada"};

The whole (long) computation can be seen from below.  The first integer in a pair  {x, y}  is the length of the word, the second one is the total number of the words for that length.  

abacaXYXZX continued at steps of 5

The  8  words of length  145  given above are examples of words that are forbidden as proper factors in very long abelian square-free words. It is a challenging task to characterise these forbidden factors in a systematic way.

It should be noted that not all of these forbidden factors are long. For example,  u = abcadbad  is an a-2-free word that cannot appear as a proper factor in a long a-2-free word over four letters. Of course, the same applies to the mirror image  v = dabdacba  and to all 48 naturally derived permutations from  u  and  v.

Created by Mathematica  (November 3, 2003)