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)