In 1906 Axel Thue [34] started the systematic study of structures in words. Consequently, he studied basic objects of theoretical computer science long before the invention of the computer or DNA. In 1961 Paul Erdös [13] raised the question whether abelian squares can be avoided in infinitely long words. In 1992, we presented in [19], see also [20
23], an abelian square-free (a-2-free) endomorphism 
on the four letter alphabet 
= {a, b, c, d}. The size of 
, i.e. 
(abcd)
, is equal to 4×85. Until now, all known methods for constructing arbitrarily long a-2-free words on 
have been based on the structure of this 
; see Arturo Carpi [4
6]. In this paper, we report of a completely new endomorphism
of 
, the iteration of which produces an infinite abelian square-free word. The size of 
is 4×98, and the image words for letters are constructed, in part, differently from the case of 
. For 
they were directly obtained by permutating letters cyclically. The endomorphism 
is not an a-2-free endomorphism itself, since it does not preserve the a-2-freeness of all words of length 7. However, 
can be used together with 
to produce a-2-free DT0L-languages of unlimited size. Here DT0L-languages mean deterministic context-independent Lindenmayer languages produced by using compositions of endomorphisms - so called tables; see [32, p.188]. Indeed, by using Carpi's algorithm [4] for prefixes of 
(
) and 
(
), and a modified version of this algorithm, one can check the following fact: for any a-2-free words 
and 
, where 
does not contain a certain subword pattern, 
(
) and 
(
) are always a-2-free and avoid all undesirable patterns that would, in the case of 
, lead to an abelian-square in the next iteration step.It is anticipated that later on this new result will lead to a sharper bound for the base number (~1.000021) found in [5], where Carpi showed that the number of a-2-free words over 4 letters of length n is
.We explain extensive computer aided searches that have been carried out over 11 years to find new ways of constructing a-2-free words over 4 letters. In this process, we have encountered some unintuitive non-linear phenomena which, however, are in accordance with the complex behaviour of simple systems studied by Stephen Wolfram in his long-awaited book [35]. For example, two same looking initial values for prefixes and suffixes of image words for letters may yield 1000-fold running times when searching through all possibilities for proper infixes! We also analyse the structure of
in terms of subwords, and discuss some open problems.
= 1 for some natural number n? Among other infinite repetition-free words, cube-free words over a binary alphabet were utilized in showing that certain Burnside groups can be infinite [1, pp.32-33]. 
is not uniformly 4-repetitive. It seems to be an open problem whether 
is uniformly 2-repetitive or 3-repetitive. In all these considerations the use of van der Waerden's theorem has been very central. In Lothaire [27, pp.55
62] van der Waerden's theorem was used to show that every morphism from a free semigroup 
, where A is finite, to 
is repetitive. This means that every long enough sequence on a finite set of integers contains two adjacent segments (not necessarily of the same length) that have the same sum. 
= {a, b, c, d}. However, new examples of relatively short abelian square-free endomorphisms g of 
, possibly with the size 
g(abcd)
< 4
85 = 340 
provided they exist, have turned out to be extremely hard to find. Thus far, after 1992 (when we presented 
in [19]), the only new abelian square-free endomorphisms and substitutions have been found by Carpi [5], cf. also [6, pp.80
81]. However, these mappings are all based on the structure of 
. Moreover, the size of these endomorphisms and substitutions is huge, it is around 4
(
1) 
, or so [actually, a similar favourable result regarding the size 4
(
85) 
is also quoted to be found with the aid of computers]. These substitutions, and the endomorphisms derived from them, are constructed by deleting distinct occurrences of one letter in 
(x), x 
. Indeed, Carpi showed in [5] that there exists exactly one abelian square-free word w 
which can be obtained by deleting an occurrence of a letter in 
(d). The letter that can be deleted is the 6349th letter (a) of 
(d). Furthermore, it turns out that both 
(c) w and w 
(c) are abelian square-free. By using these substitutions Carpi then showed that the number of abelian square-free words of each length grows expenentially, and, interestingly enough, that the monoid of (uniform) abelian square-free endomorphisms of 
is not finitely generated.
(x), x 
, of our morphism are obtained by cyclically permutating the letters in 
(a). This method was already used by Pleasants [31] in connection with five letters. Consequently, both of these endomorphisms are uniformly growing. The size of Pleasants' endomorphism is 5
15 = 75. In our case, we could check by using computers that the morphism size 4
85 = 340, in spite of its largeness, is known to be minimal, as far as we consider those abelian square-free endomorphisms which are constructed by using cyclic permutation of letters in 
(x), x 
.
in terms of reappearing subwords - also as cyclic permutations, so called grey words, and mirror images - turns out to be somewhat surprising as we will see in Section 4 below. An analogous analysis for 
is not available as yet. The frequency of (ordinary) subwords in D0L words was studied in Frid [14]. For a generalization of abelian squares, see Avgustinovich and Frid [2].
is a finite (unless otherwise indicated) string, or sequence, of letters belonging to 
. The set of all words [non-empty words] over 
is denoted by 
[
]. On the 
, the associative binary operation of catenation is defined. For words u and v, it is the juxtaposition uv. The empty word, which is the neutral element of catenation, is denoted by 
. The algebraic structures 
and 
are called, respectively, the free monoid and the free semigroup generated by 
. 
, 
. The length of the word w, denoted by | w |, is the number of occurrences of letters in w, i.e., | w | = m. Let 
= { 
, ... , 
}. The number of occurrences of one letter x 
in w is denoted by 
, or simply by 
if x = 
. The notation 
(w) stands for the Parikh vector of w, i.e., 
(w) = (
, 
, 
). Usually we will omit the subscript 
and write simply 
instead of 
. Quite interchangeably with the Parikh vector notation also formal sums 
(w) = ![Underscript[∑, x ∈ {a _ 1, ..., a _ n}] k _ x x](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_113.gif)
, with 
, are used. For example 
(abacaba) = 4a + 2b + c. Thus 
(w), with w 
, is an element of the abelian free monoid 
generated by 
. We will also consider differences of Parikh vectors and differences of formal sums. Consequently, these vectors and sums are extended into elements of the abelian free group 
generated by 
. The neutral element of 
is denoted by 
.
[s = 
], then u is called a prefix [a suffix] of w. By PREF(w) [SUFF(w)] we mean the set of all prefixes [suffixes] of w. The notation pref(w) [suff(w)] denotes an element in PREF(w) [SUFF(w)]. In the case w 
λ we write first(w) [last(w)] to denote the first [the last] letter of w.
2 be a given integer. A k-repetition [an abelian k-repetition] is a non-empty word of the form 
[
, where 
for all 
, i.e., 
:s are permutations of each other]. Instead of [abelian] 2- and 3-repetitions, terms [abelian] squares and [abelian] cubes are often used. A word or an 
-word (explained below) is called k-repetition free [abelian k-repetition free, or k-free in the abelian sense], or in short k-free [a-k-free], if it does not contain any k-repetition [abelian k-repetition] as a subword. A word sequence or a word set is k-free [a-k-free], if all words in it are k-free [a-k-free]. If, for a fixed k, it is possible to construct arbitrarily long (infinite) a-k-free (or other pattern-free) words over a given alphabet 
, then we say that abelian k-repetitions (or those patterns) are avoidable over 
. 
are called languages over 
. The catenation of languages L and 
, denoted by L
, is the language {uv | u 
L, v 
}. The notation 
, where L is a language and 
, is defined as follows: 
= {
} and 
= 
L. Let 
= 
and 
= 
. If a language contains only one word, say w, then we sometimes write w instead of {w}; especially, 
= {
| i 
0} and 
= {
| i 
1}.
Q(w). Moreover, for 
, we write 
(L) to denote the words in Q(L) of length = n. The notation 
(w) [
(w)] is used for an element in 
(w) [
(w)].
and 
with h(uv) = h(u)h(v) for every u and v in 
. Especially, h(
) = 
. A morphism h: 
, being compatible with the catenation of words, is uniquely defined, if the word h(x) 
is (effectively) given for each 
. If 
, we call h an endomorphism (and usually write g instead of h). For a morphism h and a language L we define h(L) = {h(w) | 
}. A morphism h is termed uniformly growing, if |h(x)| = |h(y)| 
2 for every x and 
.
2, a morphism h: 
is called k-free [a-k-free], if h(w) is k-free [a-k-free] for every k-free [a-k-free] word 
. 
1989), we specify the following concepts. A D0L-system is a triple G = (
, g, 
), where 
is an alphabet, g: 
is an endomorphism, and 
, called the axiom, is a word over 
. The (word) sequence S(G) generated by G consists of the words
= 
(
), 
(
), 
(
), 
(
), ... , 
(
) = g(
(
)) for 
. The language of G is defined by L(G) = {
(
) | 
}. Languages [sequences] defined by a D0L-system are referred to as D0L-languages [D0L-sequences]. D0L-systems provide a very convenient way for defining languages and infinite words. Furthermore, if g and 
are k-free [a-k-free], then the iteration of g will yield a k-free [a-k-free] D0L-sequence. An HD0L-system is a 5-tuple 
= (
, 
, g, h, 
), where (
, g, 
) is a D0L-system, called the underlying D0L-system of 
, Δ is an alphabet, and h: 
is a morphism. The HD0L-sequence S(
) generated by 
consists of the words
) = h(
(
)), h(
(
)), h(
(
)), h(
(
)), ... , 
is the set L(
) = {h(
(
)) | 
}. A DT0L-system is a triple 
= (
, H, 
), where H is a finite non-empty set of morphisms (called tables) and (
, h, 
) is a D0L-system for every 
. The DT0L-language of 
is the set L(
) = {w | w = 
or w = 
, where the compositions 
of morphims are constructed from 
, ..., 
H}. Obviously, a DT0L-system can be regarded as a D0L-system, when H contains only one (endo)morphism. For a thorough discussion of various L-systems we refer the reader to Rozenberg and Salomaa [32].
-word is an infinite sequence, from left to right, of letters of an alphabet 
. Thus an 
-word can be identified with a mapping of 
into 
. One can construct an 
-word, for example, by iterating an endomorphism g: 
such that 
and g(x) = xw for some 
, 
. Such a morphism g is called prefix preserving for the reason that 
(x) is a proper prefix of 
(x) whenever i 
0. An 
-word is obtained as the "limit" of the sequence 
(a); i = 0, 1, 2, ... . 
.
{a, b}
when showing the existence of a cube-free (3-free) infinite word over the binary alphabet {a, b}. We have used extra spaces to make the output more readable:![productions = {"a" -> "ab ", "b" -> "ba "} ; g[x_] := StringReplace[x, productions]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_281.gif)
![NestList[g, "a", 5] // TableForm](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_282.gif){kind=small}
{a, b, c}
produces longer and longer square-free (2-free) strings over the three letter alphabet {a, b, c}:
![NestList[g, "a", 5] // TableForm](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_287.gif){kind=small}
: {a, b, c, d}
{a, b, c, d}
which we found in [19] is as follows:
![g85b = StringReplace[g85a, cyclicPermutation] ; g85c = StringReplace[g85b, cyclicPermutation] ; g85d = StringReplace[g85c, cyclicPermutation] ;](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_294.gif)
![myParikh[x_String] := Apply[Plus, Characters[x]]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_295.gif){kind=small}
(a) as follows:![{StringLength[g85a], myParikh[g85a]}](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_297.gif){kind=small}
in terms of reappearing subwords 
also as cyclic permutations, grey words (in which all letters occur equally often), and mirror images. In the first part, cyclic permutations of subwords of length 26 turn out to be quite surprising. In a sense, one can explain these phenomena by thinking that reappearing subwords reduce the number of different Parikh vectors of longer successive subwords, and thus make avoiding of all abelian repetitions more plausible. Needless to say that we are still far from understanding these structures precisely.
(a) means the following. As explained in the Introduction, Carpi [5] used substitutions derived from 
when showing that the number of abelian square-free words of each length grows expenentially. Basically, he showed that there exists exactly one abelian square-free word w 
which can be obtained by deleting an occurrence of a letter in 
(b). The letter, that can be deleted, is the 6349th letter (c) of 
(b). In this case, both 
(a) w and w 
(a) are also abelian square-free. This 6349th letter of 
(b) lies inside an occurrence of the block 
(a) and is at the 59th position of that occurrence (note that 6349 = 74
85 + 59). The 59th letter of 
(a) is the underlined c below.
also as mirror images:![g85 (a) = abcacdcbcdcadcdbdaba cabadbabcb Overscript[d bcbacbcdcac, 1] babd abaca d cbcdcac Overscript[d bcba cbcdcac, 1] dcbdcdadbdcbca ; g85 (a) = abcacdcbcdcadcd Overscript[bdaba ca, 2] badbabcbdbcbacbcdcacba Overscript[bd abaca, 2] abacad Overscript[cbcdcac d, 3] bcba Overscript[cbcdcacd, 3] cbdcdadbdcbca ; g85 (a) = Overscript[Overscript[abcacdcbc, ==>], 4] dcadcdbdaba cabadbabcbdbcba Overscript[Overscript[cbcdcacba, <==], 4] bd abacadcbcdcac dbcbacbcdcacdcbdcdadbdcbca ; g85 (a) = Overscript[Overscript[abcacdcb, ==>], 5] cd Overscript[cadcdbdab, 6] a cabadbabcbdbcbacbcdcacbab Overscript[Overscript[d abacadc, ==>], 7] bcdcac dbcbacbcdcacdcbdcdadbdcbca ; g85 (c) = Overscript[Overscript[cdacabad, <==], 7] abacbabdbcdc acdcbdcdadbdadca Overscript[Overscript[dabacadc, ==>], 7] d Overscript[Overscript[b cdcacba, <==], 5] dabaca bdadcadabacabadbabcbdbadac ; g85 (b) | g85 (d) = ... aba Overscript[cadcdb | dab, 6] dbc ... ;](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_314.gif)
, two alphabets 
and 
, and a morphism h: 
, let us denote by 
the subgroup of 
generated by 
. Then, the morphism h is an abelian nth power-free (a-n-free) provided that the following conditions are satisfied:
of length 2, 
is linearly independent),
, 
PREF( h(
) ) 
{h(
)} (
) such that
, j = 1, 2 , ... , n
1,
{0,1} such that
= 
, j = 1, 2 , ... , n
1.
) 
6, then an a-n-free morphism h always satisfies conditions (i)
(iii). 
satifies conditions (i)
(iii) of Proposition 1, for n = 2, and is therefore a-2-free.
sequence over 4 letters
as follows:
(x)) = 
(g(x)) for all x 
, where 
: 
is the letter-to-letter endomorphism that performs the cyclic permutation 
(a) = b, 
(b) = c, 
(c) = d and 
(d) = a. Here | g(a) | = 98 and the Parikh vector of g(a) is 
(g(a)) = (18, 28, 27, 25). 
6 in 
, and for all a-2-free words w of length = 7, except for acadbca and acadcba and their cyclic permutations. This means that all words in the set
.
6, we conclude that all words obtained by any cyclic permutation from the words![Underscript[A, _]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_368.gif){kind=small}
A 
![Underscript[D, _]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_371.gif){kind=small}
B 
![Underscript[A, _]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_374.gif){kind=small}
, where 
, 
, 
, 
are in g(
),
(
) = 
(
)
with starting and ending boundaries inside the underlined occurrences of words taken from {A, B, C, D} as indicated in (2).
), by using Carpi's algorithm, that the words of the form (2) and their cyclic permutations, are the only possible subwords in any g(w) that contain abelian squares, provided that w in 
is a-2-free. Moreover, the coding properties of g guarantee that if, for any i 
{0, 1, 2, 3}, 
(A 
A 
D 
B 
A) S, with P, S 
, and 
:s, 
:s as in (2),
(a 
a 
d 
b 
a) s, with P = g(p), 
= g(
), 
= g(
), 
= g(
), 
= g(
), S = g(s),
a 
) = 
A 
and g(
b 
) = 
B 
.
, 
, 
, 
are linearly independent. This implies, together with (3) and the fact 
, that 
in all the factorizations of w in (3).
: 
by the productions:
is a cyclic permutation and i 
{1,2,3}.
(w) are a-2-free, whenever 
is a-2-free and does not have, for any i, a subword of the form 
(a 
a 
b 
d 
a) with 
; i = 0, 1, 2, 3.
(w) or 
(w) can be of the form (4), for any a-2-free 
. This can be checked by modifying Carpi's algorithm, see Proposition 1, for prefixes of 
(
) and 
(
). In order to illustrate this modified, and also the original Carpi's algorithm, that is, part (iii) in Proposition 1, we consider the following. Let | mark the boundaries of the blocks of imagewords of X , Y, Z in {A, B, C, D}. In the case of 
| 
| 
= 
u v 
; with u = 
, v 
, uv as an abelian square; 
= pref(X), 
= suff(X), 
= pref(Y), 
= suff(Y), 
= pref(Z), 
= suff(Z). Thus
= 
= 
, for an abelian square uv, Carpi's idea in Proposition 1 (iii) is to test whether the linear combinations of the Parikh vectors of prefixes, i.e., 
belong to 
(the subgroup of 
generated by 
, where h is the morphism to be tested). In (2) we had X = A, Y = D, Z = A. 
a 
b 
d 
a, with 
, and the natural cyclic permutations in (4), we denote u = a 
a 
b, v = 
d 
a, x = a, left = a, y = b, right = d, z = a (we exclude the natural cyclic permutations for simplicity). From this, and (5), i.e., from 
= 
, we obtain
= 
we now test whether 
. When programming this test for a computer, it is best to include the first letter of u, i.e. x (above x = a) as the last letter of 
to reduce the number of prefixes to be tested. Of course, it is possible to speed the computation even more, in a similar fashion, for other letters as well, if necessary. 
(w), for words 
of length 2, were in turn tested with the following simple pattern matching Mathematica program which works fast enough for words up to length 300 or so. In the pattern matching part, we do not use many subpatterns, otherwise the computation time may become too long for practical purposes. Below the function s is the same as myParikh defined in Section 3.![Clear[myPatterns] ; myPatterns[x_String] := Module[{pattString = {}}, Characters[x] /. {___, "a", w1__, "b", w2__, "a", ___} :> q /; If[s[{w1}] - "a" === s[{w2}] - "d", pattString = Append[pattString, StringJoin["a", w1, "b", w2, "a"]]] ; pattString]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_502.gif)
(w) or 
(w) is of the form (4), for any a-2-free 
, we now draw the conclusion: 
(w), where 
, ... , 
are of the form 
(
) or 
(
); i = 0,1,2,3; are a-2-free, provided that w is a-2-free and does not contain a subword of the form (4) in the case of 
= 
(
). 
all cyclic permutations of 
and 
but not all permutations in general.
(w), obtained by using compositions of morphims, are called DT0L-languages. See [32] for more details. 
4
100 for those endomorphisms g of 
, the words 
(x), x 
, of which are obtained by cyclically permutating the letters in 
(a). Moreover, there is no need for any long computations anymore (in checking the remaining few chances), since all possible candidates for image words have already been constructed. The result is 
almost certainly 
as follows: excluding symmetry (mirror images, cyclic permutations, or renaming letters), there are no other cyclic endomorphisms of 
in the size range 
4
100, except 
and 
, that are a-2-free or generate a-2-free L-sequences. 
, and in thousands other (larger) cases as well, g(w) is a-2-free for all a-2-free w 
= 
. However, no proper g(d) exists for any of the triplets { g(a), g(b), g(c) }:
abacabadacdbd a 
abacadabdadcdbd a 
abcdbcacbdcdadb
acdcbcacbcdbd b 
abacadcbcadcdbd b 
abcbdbadbdcdadb
abdbcdbd c 
abdbcbabd c 
adacadabacbcdcadabacabadb
; with n = 0,1,2,3; have to be a-2-free.
, for which g(w) is a-2-free for every a-2-free 
= 
(i.e. for w of length = 4) but not for all a-2-free 
. Some endomorphisms (of size 4
98 and 4
100) are even a-2-free for every a-2-free 
but not for all a-2-free 
. Thus, we have examples of endomorphisms of 
, each of which produce thousands of a-2-free words of length 
600 (some words being much longer), but still fail to be useful in our search for new endomorphisms generating a-2-free L-sequences on 
. 
(a), g
(b), g
(c)}, and then checked different possibilities for the remaining g(c) and g(d) 
. Here we separated two cases as follows:
(a), g(b) = g
(b), 1 
g(c) 
85, 1 
g(d) 
120 (we had to abort this run)
(a), g(b) = g
(c), 1 
g(c) 
90, 1 
g(d) 
= 
(here w is of length 
7), and g(w) can be extended to the right with a proper prefix of g(d) of length 20 or so. Excluding all symmetrical cases, we found thousands of different triplets. However, one can check that no proper g(d) can be found for any of them, though, in this setting, we found over 20 cases of g, for which g(w) is a-2-free for every a-2-free word 
of length = 4. It is very counterintuitive fact that in Case 1 (with 
), when searching for g(d), the computation time was over 10 times longer than in Case 2 (with 
) ! Even though it is by no means the first time that such a complex non-linear behaviour occurs in our search for strings (timewise or spacewise, and in much shorter and carefully rechecked runs), we plan to recheck Case 1, and maybe extend it, in the near future. Nevertheless, the result file indicates that most likely all possibilities for g(d) were checked already, though the process remained active. Indeed, it seems that sometimes operating systems can cause problems in runs that may take months to complete. For the Cases 1 and 2, we used C++ on a two processor 400 MHz PC running Linux.
which would not be based on the structures of 
or 
.
, over three letters? - Computer experiments show that you can avoid these patterns at least in words of length 450. 
, over two letters? - You can do this at least for words of length 250.![With[{n = 8, k = 3}, NestList[DeleteCases[Flatten[Map[Table[Append[#, i - 1], {i, k}] &, #], 1], {___, u__, v__} /; Sort[{u}] == Sort[{v}]] &, {{}}, n]]](HTMLFiles/NewAbelianSquare-FreeDT0L-LanguagesOver4Letters_593.gif)
37. North-Holland, Amsterdam, 1973.
25. Springer-Verlag, Berlin, 1984.
167. World Sci. Publ. Company, 1993.
167. Elsevier, 1998.
81. Elsevier, 1999.
520, 1990.
226, 1982.
793, 1993.
185, 1979.
491, 1990.
164, 1974.
254, 1961.
41. Otto-von-Guericke-Univ., Magdeburg, 1998.
150, 1967.
355. World Scientific, Singapore, 1989.
188. Springer-Verlag, Berlin, 1987.
52. Springer-Verlag, Berlin, 1992.
266. Computational Mechanics Publications, 1995.
79, 1995.
14. Murmansk State Pedagogical Institute, Murmansk, 1996.
257. Hakapaino, Helsinki, 1996.
297. Hakapaino, Helsinki, 1996.
122, 1985.
187. Springer-Verlag, Berlin, 1985.
129. Springer-Verlag, New York, 1994.
274, 1970.
22, 1906.