Thesis for the Degree of Licentiate of Philosophy

Symbolic Sequences, Crucial Words and

Iterations of a Morphism

Sergey Kitaev

Department of Mathematics

Chalmers University of Technology and Göteborg University SE-412 96 Göteborg, Sweden

Göteborg, October 2000 Symbolic Sequences, Crucial Words and Iterations of a Morphism Sergey Kitaev

\begin{matrix}c \\ ◯ \end{matrix}Sergey Kitaev, 2000 ISSN 0347-2809/NO 2000:62

Department of Mathematics Chalmers University of Technology and Göteborg University SE-412 96 Göteborg, Sweden

Göteborg, Sweden, October 2000

Abstract

In the present thesis there are included three papers. In the first paper we introduce the concepts of sets of prohibitions, complete sets and crucial words. The basic purpose of the paper is to investigate the extremal lengths of crucial words for four chosen sets of prohibitions. Two of these sets have been considered in different branches of mathematics such as number theory, algebra and dynamical systems. The other two papers are concerned with the concept of morphism. Since there are many techniques to study sequences generated by morphisms, it is reasonable to ask if a given sequence can be obtained by iteration of a morphism. We consider two sequences that have been used to solve different problems. These sequences are the Arshon sequence and the sequence of σ. We prove that these sequences cannot be defined by iteration of a morphism.

Keywords: Symbolic sequence, combinatorics on words, morphism, iteration of a morphism, set of prohibitions, complete set of prohibitions, crucial word, Arshon sequence, sequence of σ

AMS 2000 subject classification: 68R15, 11B85

Acknowledgements

First of all I would like to thank Alexander Evdokimov for suggesting interesting unsolved problems to me, for his permanent interest in my work and his encouragement and support during my student life. I would also like to thank Sergei Avgustinovich for useful discussions as well as being the first one to show me the beauty of discrete mathematics when I was a pupil of the Physics and Mathematics School at Novosibirsk State University. I would like to thank Einar Steingrímsson for helpful remarks on my papers, for good advice and for making me feel very welcome during my stay in Sweden.

I thank all the people at the Laboratory of Discrete Analysis of Sobolev Institute of Mathematics and all the people at the Department of Mathematics of Chalmers University of Technology and Göteborg University for creating such a friendly atmosphere.

Special thanks to all my friends for making my life full of fun.

Finally, I would like to thank my parents for supporting me during all my life, the Shuiskii family, my aunt Valentina Semenova for pointing out the right way of living and a special thanks to my wife, Dariya, for continuous support and patience.

Sergey Kitaev Göteborg, October 2000

Contents

Preface i

1 On Crucial Words for Some Sets of Prohibitions 1 1.1 Introduction and Background . . . . . . . . . . . . . . . . . . 3 1.2 The Set of Prohibitions S_{1}^{n} . . . . . . . . . . . . . . . . . . . . 5 1.3 The Set of Prohibitions S_{2}^{n} . . . . . . . . . . . . . . . . . . . . 7 1.4 The Sets of Prohibitions S_{3}^{n,k_{1},...,k_{n}} and S_{4}^{n,k} . . . . . . . . . . . 11

2 On Non-Existence of an Iterative Morphism that Defines the Arshon Sequence 23 2.1 Introduction and Background . . . . . . . . . . . . . . . . . . 25 2.2 The Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 There is no Iterative Morphism which Defines the Sequence of σ 33 3.1 Introduction and Background . . . . . . . . . . . . . . . . . . 35 3.2 The Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Preface

Combinatorics on words is a relatively new subject. The reasons to study it come from different branches of mathematics (algebra, discrete mathematics, number theory, dynamical systems and probability), computer science (coding theory and complexity of formal languages), physics (structure of quasicrystals) and biology (investigating DNA).

The goal of the subject is to study various combinatorial properties of finite and infinite words on a finite set of symbols which usually is called an alphabet.

The history of combinatorics on words begins with work of Axel Thue on nonrepetitive sequences of symbols at the beginning of this century. However, only in 1983, after the publication of Lothaire’s book (Combinatorics on Words) has the field developed systematically and rapidly.

In the present thesis there are included three papers.

In the first paper we introduce the concepts of sets of prohibitions, complete sets and crucial words.

A set of prohibitions S is a set of words in some alphabet A.

If there exists an infinite sequence that has no words from S as subword, then the set of prohibitions S is called an incomplete set. Otherwise it is called a complete set.

A crucial word X is a word in the alphabet A that has two properties:

1) X has no words from S as subwords

2) For any letter a ∈ A the word Xa has a word from S as its subword (in other words Xa is not free from S).

The notion of a complete set is related to the notion of unavoidable set which appears in the literature.

The basic purpose of the paper is to investigate the extremal lengths of crucial words for four chosen sets of prohibitions. These sets are S_{1}^{n}, S_{2}^{n}, S_{3}^{n,k_{1},...,k_{n}}, S_{4}^{n,k}, where the parameter n is the number of letters in an alphabet.

To be more precise, by S_{1}^{n} we prohibit the repetition of two equal consecutive subwords; by S_{2}^{n} we prohibit the repetition of two equal consecutive subwords that have the same number of occurrences of a_{i} ∈ A for i = 1, …, n; by S_{3}^{n,k_{1},...,k_{n}} we prohibit words, in which the number of letters a_{i} is congruent with zero modulo k_{i} for i = 1, …, n; by S_{4}^{n,k} we prohibit any two consecutive subwords of the length greater then k such that the number of positions in which these words differ is less then or equal to k.

The choice of these sets is not random. The interest in S_{1}^{n} appeared in number theory, algebra and dynamical systems. One was considering the problems related to the question on existence or non-existence of infinite sequences without repetitions.

The set of prohibitions S_{2}^{n} is a generalisation of the first one. For a long time one was not able to answer to the so called “New Problem of Four Colours”. The problem was to construct in a four letter alphabet an infinite sequence that avoids (has no subwords from) S_{2}^{4}. A construction of such a sequence was given in 1991, with the help of computer.

The remaining two sets do not seem to have appeared in the literature, but they certainly have some combinatorial interest. For the set S_{4}^{n,k} and any n ≥ 3 we prove the theorem of incompleteness of this set of prohibitions.

The other two papers are concerned with the concept of morphism.

For those who are not familiar with this concept we recommend the book by Salomaa “Jewels of Formal Language Theory”. This book is a nice introduction to the subject under consideration.

Let Σ be an alphabet. A map φ : Σ^{∗} → Σ^{∗} is called a morphism, if we have φ(uv) = φ(u)φ(v) for any u, v ∈ Σ^{∗}. It easy to see that a morphism φ can be defined by defining φ(i) for each i ∈ Σ.

Since there are many techniques to study sequences generated by morphisms, it is reasonable to ask if a given sequence can be obtained by iteration of a morphism.

In these two papers we consider two sequences that were used to solve different problems.

The Arshon sequence has the property that it is free from the set of prohibitions S_{1}^{n}. There exists a lot of sequences with this property, but the Arshon sequence was the first one, constructed in 1937. This sequence is still interesting from different points of view.

The sequence of σ was used by Evdokimov to build chains of maximal length in the n-dimensional unit cube in 1969. We note that this sequence has at least two different definitions.

In 1979, Berstel proved that the Arshon sequence can be generated by a tag-system, but cannot be obtained by iteration of a morphism. He proved the latter of these by proving a more general statement. In this thesis we give an alternative proof of this fact. An interesting aspect of this proof is that it includes a consideration of the letter frequencies in the Arshon sequence.

Finally, we prove that the sequence of σ cannot be defined by iteration of a morphism.

So far there are unfortunately no universal criteria to determine whether a given sequence can be obtained by iteration of a morphism. The purpose of the papers presented here is to demonstrate different approaches to this problem.

Chapter 1 On Crucial Words for Some Sets of Prohibitions

Introduced the notation of a set of prohibitions; given definitions of a complete set and a crucial word with respect to a given set of prohibitions. Considered 4 particular sets which appear in different areas of mathematics and for each of them examined the length of a crucial word. One of these sets proved to be incomplete.

1.1 Introduction and Background

In defining or characterising sets of objects in discrete mathematics, ”languages of prohibitions” are often used to define a class of objects by listing those prohibited subobjects that are not contained in the objects of the class. To this end the notion of a subobject is defined in different ways. The notion depends on the set under consideration. These sets are subwords for partially bounded languages, subgraphs for families of graphs and so on. One of the classes of interest that have appeared and are considered in different areas of mathematics is the class of nonrecurrent symbolic sequences defined by prohibiting strong periodicity in them, or, to be more exact, by prohibiting the repetition of subwords in these symbolic sequences, for example of type XX.

In this paper we consider 4 types of ”prohibitions” connected with a generalisation of the notion of nonrecurrent symbolic sequences, and for each of these sets we consider the structure of crucial words and find their lengths.

Let A = {a_{1}, …, a_{n}} be an alphabet of n letters. A word in the alphabet A is a finite sequence of letters of the alphabet. Any i consecutive letters of a word X generate a subword of length i. If X is a subword of a word Y, we write X ⊆ Y.

The set A^{∗} is the set of all the words of the alphabet A. Let S ⊆ A^{∗}. Then S is called a set of prohibited words. A word that does not contain any words from S as its subwords is called free from S. The set of all words that are free from S is denoted by Ŝ.

Example 1. Let A = {a, b}. The set of prohibitions is S = {aa, ba}. The word abbb is in Ŝ.

If there exists a k ∈ N with the property that the length of any word in Ŝ is less than k, then the set of prohibitions S is called a complete set.

Example 2. A = {1, 2, 3, 4}. The set of prohibitions is

S = {123, 13, 14, 11, 22, 33, 44 }.

Then S is incomplete, since the word \underbrace{124124 … 124}_{3k} is in Ŝ for any k.

Example 3. A = {1, 2, 3}. The set of prohibitions is

S = {12, 23, 31, 32, 11, 22, 33}.

Simple sorting shows S to be complete.

A word X ∈ Ŝ is called a crucial word (with respect to S), if the word Xa_{i} contains a prohibited subword for any letter a_{i} ∈ A. This means that Xa_{i} has the structure BB_{i}a_{i}, where B is some word and B_{i}a_{i} ∈ S. The subword B_{i} is called the i-ending of crucial word X. If for each letter of the alphabet we consider minimal i-ending (with respect to inclusion) we obtain a system of included i-endings, which we will use to investigate crucial words.

Example 4. A = {a, b, c}. The set of prohibitions is S = {aa, cab, acac}. The word abaca is crucial with respect to S.

A crucial word of minimal (maximal) length, if it exists, is called a minimal (maximal) crucial word.

Example 5. A = {a, b, c}. The set of prohibitions is S = {aa, cab, acac}. The word aca is a minimal crucial word with respect to S. There do not exist any maximal crucial words, since the word \underbrace{b … b}_{k} aca is crucial for all k ∈ N.

Let L_{min}(S) (L_{max}(S)) denote of the length of a minimal (maximal) crucial word with respect to S.

In this paper we consider four sets of prohibitions denoted S_{1}^{n}, S_{2}^{n}, S_{3}^{n,k_{1},...,k_{n}}, S_{4}^{n,k}. Here we use n for indicating of the number of letters of the alphabet under consideration and k, k_{1}, …, k_{n} are natural numbers.

We now give the definitions of these sets:

S_{1}^{n} = {XX | X ∈ A^{∗}}, that is, we prohibit the repetition of two equal consecutive subwords.

S_{2}^{n} = \{XY | \overline{ν}(X) = \overline{ν}(Y)\}, where \overline{ν}(X) = (ν_{1}(X), …, ν_{n}(X)) is the content vector of X, in which ν_{i}(X) is the number of occurrences of the letter a_{i} in X. That is, we prohibit the repetition of two consecutive subwords of the same content.

S_{3}^{n,k_{1},...,k_{n}} = {X | ν_{i}(X) ≡ 0 (mod k_{i}), k_{i} ∈ N, i = 1, …, n}, that is, we prohibit words in which the number of letters a_{i} is congruent to zero modulo k_{i} for each i = 1, …, n.

S_{4}^{n,k} = {XY | d(X, Y) ≤ k, |X| = |Y | ≥ k + 1, k ∈ N}, where d(X, Y) is the number of letters in which the words X and Y differ (Hamming metric) and |X| is the length of the word X. That is we prohibit any two consecutive subwords of the length greater then k such that the number of positions in which these words differ is less then or equal to k.

The proofs of Theorems 1–6 consist of the constructions of extremal crucial words and of the proofs of their optimality, i. e. the lower bound for L_{min}(S) and the upper bound for L_{max}(S).

1.2 The Set of Prohibitions S_{1}^{n}

Theorem 1. We have

L_{min}(S_{1}^{n}) = 2^{n} − 1.

Proof:

We define a crucial word X by induction:

X_{1} = a_{1}, X_{i} = X_{i−1}a_{i}X_{i−1}, X = X_{n}.

From this construction it follows that |X| = 2^{n} − 1. We will prove that X is a minimal crucial word with respect to S_{1}^{n}.

Let U be an arbitrary minimal crucial word. We show that U coincides with the word X up to a permutation of letters in A.

From the definition of a crucial word it follows that in the word Ua_{i} there is a prohibited word of the form B_{i}a_{i}B_{i}a_{i}, where B_{i} is a certain word and B_{i}a_{i}B_{i}a_{i} is the ending of the word Ua_{i} (the ending may coincide with Ua_{i}). In this case the i-ending is the subword B_{i}a_{i}B_{i}. Let ℓ_{i} = B_{i}a_{i}B_{i}.

We assume that ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n}, since we can make such ordering by permuting the letters of the alphabet, which obviously does not affect the cruciality and minimality of a word.

Note that the minimal crucial word U has the form

U = B_{n}a_{n}B_{n} = B_{n}a_{n}Y_{n}a_{1},

where Y_{n} is a certain word. Actually, if on the right of B_{n}a_{n}B_{n} there is a certain word, then it contradicts the minimality of a crucial word, and if instead of a_{1} there stands a_{k} (k > 1) then it contradicts ℓ_{1} ⊂ ℓ_{k}.

We show that ℓ_{n−1} coincides with B_{n}. We have ℓ_{n−1} = B_{n−1}a_{n−1}B_{n−1} and let a_{n}B_{n} be a subword of ℓ_{n−1}. Now ℓ_{n−1} has the form Ka_{n}P a_{n−1}Ka_{n}P, where Ka_{n}P = B_{n−1}), but then

ℓ_{n} = P a_{n−1}Ka_{n}P a_{n−1}Ka_{n}P, where P a_{n−1}Ka_{n}P = B_{n},

and the word U contains the prohibited subword a_{n}P a_{n}P. This can not be the case. It means that ℓ_{n−1} is a subword of the word B_{n}, and the word U has the form:

U = ℓ_{n} = Z_{n}ℓ_{n−1}a_{n}Z_{n}ℓ_{n−1},

where Z_{n} is a certain word. Since we explore a minimal crucial word, we have Z_{n} = ∅, and then B_{n} = ℓ_{n−1}. In the same way we can show that B_{i} = ℓ_{i−1} for each i = 2, …, n − 1 and B_{1} = ∅.

Hence the structure of a minimal crucial word U coincides with that of the word X as required.

Remark

From the proof of Theorem 1 it follows that the word X is the unique minimal crucial word to within a transposition of the letters of the alphabet A.

1.3 The Set of Prohibitions S_{2}^{n}

Proposition 1.

A minimal crucial (with respect to S_{2}^{n}) word can not have three letters, each of which appears twice in the word.

Proof:

Since the proposition is obviously true for |A| = 1, 2, 3, we will consider the case |A| ≥ 4.

Let X be a minimal crucial word, and suppose the system of included i-endings for it is ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} = X. Suppose the letters a_{i_{1}}, a_{i_{2}}, a_{i_{3}} occur twice in X and that i_{1} < i_{2} < i_{3} < n (the fact that i_{1}, i_{2}, i_{3} do not equal n follows from the fact that a_{n} must occur an odd number of times).

When we pass from ℓ_{i_{3}−1} to ℓ_{i_{3}} (ℓ_{i_{3}−1} is determined, since there are i_{1}, i_{2} < i_{3}) there must appear a letter a_{i_{3}}, and when we pass from ℓ_{i_{3}} to ℓ_{i_{3}+1} (ℓ_{i_{3}+1} is determined, since i_{3} < n) there must appear one more letter a_{i_{3}}; Hence, since there are two letters a_{i_{3}} in X, there are no letters a_{i_{3}} for 2 < j < i_{3} in ℓ_{j} whence there are no letters a_{i_{3}} in the X to the left of ℓ_{i_{2}} (both letters a_{i_{3}} lie to the left respecting of ℓ_{i_{2}}).

Obviously, the letter a_{i_{1}} must be in ℓ_{i_{1}}. The second letter a_{i_{1}} appears when we pass from ℓ_{i_{1}} to ℓ_{i_{2}}. Since there are only two letters a_{i_{1}}, there are no letters a_{i_{1}} in the word X to the left of ℓ_{i_{2}}.

If we write the letter a_{i_{3}+1} to the right of the word X we obtain a prohibited word (a word from S_{2}^{n}). Words from S_{2}^{n} are divided into two parts which have the same content. Obviously, the letters a_{i_{3}} must be in different parts of the prohibited word, and letters a_{i_{1}} must be in different parts of the same word which is impossible, since the letters a_{i_{3}} lie strictly to the left of a_{i_{1}}, and this contradicts the assumption.

Remark.

From the proof of proposition 1 we have that if letters a_{i} and a_{j} occur twice in a word X (in which ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} = X), then either i = j + 1 or j = i + 1.

Theorem 2. For any n > 2 we have

L_{min}(S_{2}^{n}) = 4n − 7.

Proof:

Note that a natural approach to the construction of a crucial word is possible. It consists of an algorithm of step-by-step optimisation: We ascribe to a crucial word of an n-letter alphabet a minimum number of letters to obtain a crucial word of an (n + 1)-letter alphabet.

The algorithm can be written recursively in the following way:

X_{n} = B_{n−1}a_{n}B_{n−1} B_{n−1} = B_{n−3}a_{n−1}B_{n−3} B_{1} = a_{1}, B_{2} = a_{2}, B_{−1} = B_{0} = X_{0} = ∅.

Some initial values when implementing the algorithm are:

X_{1} = a_{1}, X_{2} = a_{1}a_{2}a_{1}, X_{3} = a_{2}a_{3}a_{1}a_{2}a_{1}, X_{4} = a_{1}a_{3}a_{1}a_{4}a_{2}a_{3}a_{1}a_{2}a_{1}, X_{5} = a_{2}a_{4}a_{2}a_{5}a_{1}a_{3}a_{1}a_{4}a_{2}a_{3}a_{1}a_{2}a_{1}.

This is an algorithm by which the minimal crucial word X_{n} for the set of prohibitions S_{1}^{n} can be built. For S_{2}^{n} such a construction gives an upper bound of the form exp(n/2), or, to be more exact,

(3 − (n mod 2))2^{⌊ \frac{n+1}{2} ⌋} − 3.

We now give an upper bound that is a linear function. We introduce, as before, a system of included i-endings: ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂

ℓ_{n} (we permute the letters of the alphabet if it is necessary). We show that the passage from ℓ_{i−1} to ℓ_{i} is possible by adding only two symbols (letters of alphabet A).

When we passed from ℓ_{i−1} to ℓ_{i} let there appear symbols y and z. ℓ_{i−1} may be denoted by AB, where A is a certain word, B consists of the letters of the word A (which are somehow mixed) and B contains one letter a_{i−1} less than A does. Let x be the last letter of the word A on the right. Then ℓ_{i} may be denoted by yzKxB, where A = Kx. From the definition of ℓ_{i} we have the equation

y ∪ z ∪ K = B ∪ x ∪ a_{i}.

which from the definition of K and B is equivalent to

2x ∪ a_{i} = y ∪ z ∪ a_{i}.

It follows necessarily that x = a_{i−1} and either y = a_{i−1}, z = a_{i} or y = a_{i}, z = a_{i−1}.

Suppose y = a_{i−1}, z = a_{i}.

For example, we have the following crucial word for a 6-letter alphabet:

a_{4}a_{5}a_{3}a_{4}a_{2}a_{3}a_{1}a_{2}|a_{6}a_{4}a_{3}a_{2}a_{1}a_{2}a_{3}a_{4}a_{6},

(the vertical line was drawn for a more convenient visual perception of the word).

This word is crucial and its length is equal to 17.

We consider a case of an arbitrary n ≥ 3 defining the word W as

W = a_{n−2}a_{n−1}a_{n−3}a_{n−2} … a_{1}a_{2}|a_{n}a_{n−2}a_{n−3} … a_{2}a_{1}a_{2} … a_{n−3}a_{n−2}a_{n}.

Then |W | = 2(n − 2) + n − 1 + n − 2 = 4n − 7.

Let us verify that the word W is crucial.

If we write the letters a_{1}, a_{2}, a_{n} to the right of the word W we will obviously have prohibited subwords. Let 2 < i < n. Then if we write the letters a_{i} we will have the prohibition

a_{i−1}a_{i} … a_{1}a_{2}a_{n}a_{n−2} … a_{i}|a_{i−1} … a_{2}a_{1}a_{2} … a_{n−2}a_{n}a_{i},

since the composition vectors of the left and right subwords with respect to the vertical line are equal.

Before proving that W ∈ Ŝ_{2}^{n} we make the following remark.

In the word W we have ℓ_{n} ⊂ ℓ_{1} ⊂ … ⊂ ℓ_{n−2} ⊂ ℓ_{n−1}. Substituting a_{1} for a_{n}, a_{2} for a_{1}, …, a_{n} for a_{n−1} we obtain another word

U = a_{n−1}a_{n} … a_{2}a_{3}|a_{1}a_{n−1} … a_{3}a_{2}a_{3} … a_{n−1}a_{1},

for which ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n}.

In both cases (before and after substitution of letters of the alphabet) we have the construction of a crucial word (which will be proved below) hence the same upper bound of the length of a minimal crucial word.

For W it is more convenient to show further that W ∈ Ŝ_{2}^{n}.

We rewrite W making in it the marks (1),(2), …,(2n-4), which number the gaps between letters of a word like this:

(2n − 4)a_{n−2}(2n − 5)a_{n−1} … (2)a_{1}(1)a_{2}|a_{n}a_{n−2} … a_{2}a_{1}a_{2} … a_{n−2}a_{n}.

In a possible prohibition we mark the left and right bounds. Note that the length of a prohibition is an even number, and each letter must occur an even number of times in a prohibition. The left bound of the prohibition must lie to the right of the mark (2n-5), since the letter a_{n−1} enters W once;

It must lie to the left of the mark (1), since to the right of the mark (1) there is one letter a_{1}.

Note that if m is even then (m) is not the left bound of the possible prohibition. Actually in this case two variants are possible:

1) the prohibition does not cover the left letter a_{n}.

2) the prohibition covers the left letter a_{n}.

In the second case we have not a prohibition, since if the prohibition begins from the even mark, then it can not cover the second a_{n}.

In the first case the right bound of the prohibition lies to the left of a_{n}, hence the letter a_{\frac{m}{2} +1} enters the prohibition only once.

Suppose the prohibition begins from the mark (m) and m is odd.

There are two possible cases.

1) The prohibition does not cover the left letter a_{n} (this case is impossible since the letter a_{⌊ \frac{m}{2} ⌋} occurs the prohibition once).

2) The prohibition covers the left a_{n}. Then it covers the right a_{n} too, and the letter a_{⌊ \frac{m}{2} ⌋} occurs an odd number of times in the prohibition. So W ∈ Ŝ_{2}^{n} and hence L_{min}(S_{2}^{n}) ≤ 4n − 7 for n > 2.

We give now a lower bound.

Since the length of a minimal crucial word must be odd, and the passage from ℓ_{i} to ℓ_{i+1} requires at least two letters, we have that a trivial lower bound of the length of a minimal crucial word is 2n − 1.

Let us now improve the lower bound. Obviously a minimal crucial word in which ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} has an even number of occurrences of the letter a_{i} for i = 1, …, n − 1 and an odd number of occurrences of the letter a_{n}. The word U has two letters a_{1}, two letters a_{2}, one letter a_{n} and four of any other letter. From proposition 1 we know that there does not exist a crucial word that has the fewer number of letters, hence the word U gives us the lower bound of the length of a minimal crucial word.

1.4 The Sets of Prohibitions S_{3}^{n,k_{1},...,k_{n}} and S_{4}^{n,k}

Theorem 3. We have

L_{min}(S_{3}^{n,k_{1},...,k_{n}}) = ∑_{i=1}^{n} k_{i} − 1.

Proof:

Let us give a lower bound.

Let X be a minimal crucial word. Considering a system of included iendings gives us that X has at least k_{i}t_{i} letters a_{i}, i = 1, …, n − 1 and k_{n}t_{n} − 1 letters a_{n}, where t_{i} ∈ N, i ∈ {1, …, n} and hence:

L_{min}(S_{3}^{n,k_{1},...,k_{n}}) ≥ ∑_{i=1}^{n} k_{i} − 1.

An upper bound is given by the construction

a_{n−1} \underbrace{a_{n} … a_{n}}_{k_{n}−1} a_{n−2} \underbrace{a_{n−1} … a_{n−1}}_{k_{n−1}−1} … a_{1} \underbrace{a_{2} … a_{2}}_{k_{2}−1} \underbrace{a_{1} … a_{1}}_{k_{1}−1}

Obviously this word is crucial and its length equals ∑_{i=1}^{n} k_{i} − 1.

Theorem 4. We have

L_{min}(S_{4}^{n,k}) = 2k + 1.

Proof:

For the set of prohibitions S_{4}^{n,k} we must have |A| = |B| ≥ k + 1, where AB is an arbitrary prohibition. So we have

L_{min}(S_{4}^{n,k}) ≥ 2k + 1.

An upper bound is given by the construction p_{1}p_{2} … p_{k}xp_{1}p_{2} … p_{k}, where x, p_{i} ∈ A, i = 1, …, k and x ≠ p_{i}.

Theorem 5. We have

L_{max}(S_{3}^{n,k_{1},...,k_{n}}) = ∏_{i=1}^{n} k_{i} − 1.

Proof:

We give an upper bound. Any word z_{1} … z_{ℓ} free from S_{3}^{n,k_{1},...,k_{n}} has the property that all vectors

\overline{ν}(z_{1} … z_{i}) are different modulo k = (k_{1}, …, k_{n}) for i = 1, 2, …, ℓ, since else, if for example \overline{ν}(z_{1} … z_{j}) = \overline{ν}(z_{1} … z_{i}) and j > i, we have

\overline{ν}(z_{i+1} … z_{j}) = \overline{ν}(z_{1} … z_{j}) − \overline{ν}(z_{1} … z_{i}) ≡ \overline{0} (mod k),

which contradicts the word z_{1} … z_{ℓ} is free from S_{3}^{n,k_{1},...,k_{n}}. The number of different words whose content vector is not congruent to

the zero vector modulo k is ∏_{i=1}^{n} k_{i} − 1, hence

L_{max}(S_{3}^{n,k_{1},...,k_{n}}) ≤ ∏_{i=1}^{n} k_{i} − 1.

A lower bound is given by the construction

A_{1} = a_{1} … a_{1} (k_{1} − 1 letters a_{1})
A_{n} = A_{n−1}a_{n}A_{n−1} … A_{n−1}a_{n}A_{n−1} (k_{n} blocks A_{n−1}).

This word is obviously crucial and its length is ∏_{i=1}^{n} k_{i} − 1.

Remark. The crucial word with respect to S_{4}^{1,k} is unique and its length is 2k + 1.

Theorem 6. We have

L_{max}(S_{4}^{2,k}) = 3k + 3.

Proof:

Let

ā = \{ \begin{matrix}1, & if a = 2, \\ 2, & if a = 1. \end{matrix}

Moreover, let us consider an arbitrary crucial word A, with respect to S_{4}^{2,k}, of length greater then 3k + 3. It is easy to see that if a_{1}a_{2} … a_{k+1} are the first k+1 letters of A then the next k+1 letters of A must be ā_{1}ā_{2} … ā_{k+1}, because otherwise the first 2k +2 letters of A will form a prohibited subword. By the same argument, we can show that

A = a_{1}a_{2} … a_{k+1}ā_{1}ā_{2} … ā_{k+1}a_{1}a_{2} … a_{k+1}ā_{1} ….

Let us consider the subwords A_{i} of A of the length 2k + 4 which start from the ith letter, where 1 ≤ i ≤ k:

A_{i} = \underbrace{a_{i}a_{i+1} … a_{k+1}ā_{1} … ā_{i}}_{k+2} \underbrace{ā_{i+1} … ā_{k+1}a_{1} … a_{i+1}}_{k+2}

If a_{i} = ā_{i+1} then the underbraced subwords of A_{i} are the same in the first and in the last positions, so they differ in at most k positions, hence A_{i} is prohibited. So we must have a_{i} = a_{i+1} for i = 1, …, k.

Without loss of generality we can assume that a_{1} = 1, so

A = \underbrace{11 … 1}_{k+1} \underbrace{22 … 2}_{k+1} \underbrace{11 … 1}_{k+1} 2 ….

It is easy to see that if the length of A is greater then 3k + 3 then A has a prohibited subword of length 2k + 4:

A = \underbrace{11 … 1}_{k} \overbrace{1 \underbrace{22 … 2}_{k+1}} \overbrace{\underbrace{11 … 1}_{k+1} 2} 2 ….

(here and then two braces above an word show us a disposition of a prohibited subword and, in particular, a disposition of parts of this subword that correspond to X and Y from the definition of the set of prohibitions S_{4}^{n,k}).

So L_{max}(S_{4}^{2,k}) ≤ 3k + 3.

To prove the theorem it is sufficient to check that there are no prohibited

subwords in the word A = \underbrace{11 … 1}_{k+1} \underbrace{22 … 2}_{k+1} \underbrace{11 … 1}_{k+1}.

Obviously the left end of a possible prohibition can be only in the left

block \underbrace{1 … 1}_{k+1}:

\overbrace{\underbrace{1 … 1}_{j} \underbrace{2 … 2}_{i}} \overbrace{\underbrace{2 … 2}_{k−i+1} \underbrace{1 … 1}_{2i+j−k−1}}

with

j + i ≥ k + 1  (1.1)

Two cases are possible:

1. j ≥ k − i + 1
2. j < k − i + 1

In the first case there is non-coincidence between the left and right parts of the prohibition in the first k − i + 1 letters and in the last i letters that is non-coincidence in k + 1 letters. So this case is impossible.

In the second case we have non-coincidence in the first j letters and in the last 2i + j − k − 1 letters. Hence we have non-coincidence in 2(i + j) − k − 1 letters, that according to (1) is greater than or equal to k + 1.

It follows that the word \underbrace{1 … 1}_{k+1} \underbrace{2 … 2}_{k+1} \underbrace{1 … 1}_{k+1} does not contain a prohibition

and thus the theorem is proved.

Theorem 7. [Incompleteness] The set of prohibitions S_{4}^{n,k} for n ≥ 3 is incomplete.

Proof:

Since the alphabet A is finite, there is no trivial solution of the problem (such as taking all letters of A and obtaining an infinite sequence with the properties needed). So to prove the incompleteness of the set S_{4}^{n,k} we have to show the existence of an infinite word which is free from the set of prohibitions S_{4}^{n,k}.

We consider the case n = 3 and the alphabet A = {1, 2, 3}, since the incompleteness of the set of prohibitions S_{4}^{n,k} for the case n > 3 will follow from the incompleteness of the set of prohibitions for the case n = 3.

Let B = {a, b, c} be an alphabet. B^{∗} is the set of all words of the alphabet B.

We define the mapping f as follows:

\underbrace{1 … 1}_{k+1} → a, \underbrace{2 … 2}_{k+1} → b, \underbrace{3 … 3}_{k+1} → c.

The domain of the mapping f is the set of words of the alphabet

C = \{ \underbrace{1 … 1}_{k+1}, \underbrace{2 … 2}_{k+1}, \underbrace{3 … 3}_{k+1} \}.

The image of the mapping f is the set B^{∗}. Let the set of prohibitions S′ = {XX|X ∈ B^{∗}}. Obviously, the set S′

coincides with the set S_{2}^{n} whenever A = B.

It is known [1] that for the alphabet B there exists the infinite sequence L′ which is free from the set of prohibitions S′. L′ is built by iteration of morphisms:

a → abc
b → ac
c → b

The morphism iteration procedure is as follows. We start from the letter a. Then we substitute this letter with abc. Then

we substitute each letter in abc by the rule above. We obtain after this step abcacb. And so on. Executing this procedure an infinite number of times gives us the sequence L′.

Let us prove that the sequence L = f^{−1}(L′) does not contain words prohibited by S_{4}^{3,k}.

We are going to prove the statement by considering L and all possible dispositions of words prohibited by S_{4}^{3,k}.

The sequence L is built up from the letters of the alphabet C or in other words from the blocks \underbrace{x … x}_{k+1}, where x ∈ \{1, 2, 3\}. It means that there are

only three different cases for a disposition of a possible prohibition in L.

Case 1. \overbrace{\underbrace{x … x}_{k+1} … \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} … \underbrace{t … t}_{k+1}} ;

Case 2. \underbrace{x … x}_{i} \overbrace{\underbrace{x … x}_{k−i+1} … \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} … \underbrace{t … t}_{k−i+1}} \underbrace{t … t}_{i} ,

where 0 < i < k + 1;

Case 3. \underbrace{x … x}_{i} \overbrace{\underbrace{x … x}_{k−i+1} … \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} … \underbrace{t … t}_{k−j+1}} \underbrace{t … t}_{j} ,

where 0 ≤ i, j, l ≤ k + 1.

Now we will consider these cases and show that each of them is impossible.

Case 1. Let P denote the prohibited subword (prohibition) under consideration, R and L denote the right and the left parts of P respectively.

It is obvious that L and R have the same number of blocks. Moreover, the ith block of L (from the left to the right) is equal to the ith block of R, because otherwise we have non-coincidence of L and R in at least k + 1 letters which contradicts the fact that P ∈ S_{4}^{3,k}. So we have that P = W W for some W ∈ C^{∗}.

Now, f(P) = f(W)f(W) is a subword of L′. But f(W)f(W) ∈ S′ which is impossible by the properties of L′. So Case 1 is impossible.

Note. As an important consequence of Case 1 we have the following. If

\underbrace{x … x}_{k+1} \underbrace{y … y}_{k+1} is a subword of L then x ≠ y.

Case 2. If there are no letters between \underbrace{x … x}_{k+1} and \underbrace{y … y}_{k+1}, that is

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{t … t}_{k−i+1}} ,

then we must have x = z, because otherwise we have x ≠ z and y ≠ z which gives us that L and R differ in the first k + 1 positions, but this contradicts P ∈ S_{4}^{3,k}.

By the same argument we have y = t, so

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1}} \overbrace{\underbrace{x … x}_{k+1} \underbrace{y … y}_{k−i+1}} .

But if we consider now f(L) = L′ then it has

P′ = \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{y … y}_{k+1})} \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{y … y}_{k+1})} .

as a subword, which is impossible since P′ ∈ S′.

So there is some non-empty subword in L between \underbrace{x … x}_{k+1} and \underbrace{y … y}_{k+1}, and

P can be written as

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{x_{1} … x_{1}}_{k+1} … \underbrace{x_{p} … x_{p}}_{k+1} \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k−i+1}} .

There are two possible subcases here.

1. x = z. Since x ≠ x_{1} we have x_{1} ≠ z. If x_{1} ≠ z_{1} then L and R differ in k + 1

position starting from the (k − i + 2)th position, which is impossible since P ∈ S_{4}^{3,k}. So x_{1} = z_{1}.

In the same way, for each of x_{2}, x_{3}, … x_{p}, y, we can obtain that

P = \overbrace{\underbrace{z … z}_{k−i+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k−i+1}}

which leads us to the fact that L has a subword W W for some W ∈ C^{∗}, hence L′ has a subword f(W)f(W) which is impossible.

So the subcase 1 is impossible.

2. x ≠ z. If x_{1} ≠ z then L and R differ in k + 1 position starting from the first

position, which is impossible since P ∈ S_{4}^{3,k}. So x_{1} = z.

If x_{2} ≠ z_{1} then L and R differ in k +1 position starting from the (k +2)th position, what is impossible by the same arguments as above. So x_{2} = z_{1}. And so on.

We have

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k−i+1}} .

Applying f to L gives us a subword P′ of L′,

P′ = \overbrace{f(\underbrace{z … z}_{k+1})f(\underbrace{z_{1} … z_{1}}_{k+1}) … f(\underbrace{z_{p} … z_{p}}_{k+1})} \overbrace{f(\underbrace{z … z}_{k+1})f(\underbrace{z_{1} … z_{1}}_{k+1}) … f(\underbrace{z_{p} … z_{p}}_{k+1})},

which is prohibited in L′ by S′.

We have got that subcase 2 is impossible and hence Case 2 is impossible.

Case 3. We can assume that ℓ ≠ 0 and ℓ ≠ k + 1, because otherwise we deal with either Case 1 or Case 2 which are impossible.

We suppose that i ≥ ℓ (the case i < ℓ can be considered in the same way).

If there are no letters between \underbrace{y … y}_{k−ℓ+1} and \underbrace{t … t}_{k−j+1}, then we have either

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} \underbrace{t … t}_{k−j+1}}

or

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{z … z}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} \underbrace{t … t}_{k−j+1}} .

In the first of these cases we have that x ≠ y and y ≠ t which gives us that L and R have non-coincidence in at least k + 1 letters, but this contradicts P ∈ S_{4}^{3,k}.

In the second case we must have z = t, because otherwise since z ≠ y and t ≠ y, L and R have non-coincidence in the last k + 1 letters which is impossible. So in the second case we have

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{t … t}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} \underbrace{t … t}_{k−j+1}} .

If x ≠ y then L and R have non-coincidence in the first k −ℓ+1 positions and in the last ℓ positions, that is they have non-coincidence in at least k + 1 positions which is impossible. So x = y.

Now applying f to L gives us that L′ has a subword

P′ = \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{t … t}_{k+1})} \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{t … t}_{k+1})}

which is impossible.

So there is some non-empty subword in R between \underbrace{y … y}_{k−ℓ+1} and \underbrace{t … t}_{k−j+1}, and

P can be written in the form

P = \overbrace{\underbrace{x … x}_{k−i+1} L_{1} … L_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} ,

where L_{s}, R_{m} ∈ C, for 1 ≤ s ≤ p, 1 ≤ m ≤ p′, and either p = p′ or p = p′+1. We define △(L_{s}) = x_{s} if L_{s} = \underbrace{x_{s} … x_{s}}_{k+1}. In the same way we define

△(R_{m}).

Let us consider two cases:

1. p = p′. There are two subcases here:

a) x = y; Since △(L_{1}) ≠ x we must have L_{1} = R_{1}, because otherwise L and R have non-coincidence in the k +1 letters starting from the (k −i+2)th position, which is impossible.

Since △(L_{2}) ≠ △(L_{1}), that is △(L_{2}) ≠ △(R_{1}), we must have L_{2} = R_{2}, because otherwise L and R have non-coincidence in the k + 1 letters starting from the (2k − i + 3)th position, which is impossible. And so on. For each of of L_{3}, …, L_{p} we have that

P = \overbrace{\underbrace{y … y}_{k−i+1} R_{1} … R_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{t … t}_{k−j+1}} .

So we have got that L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p},

but it means that L′ has f(W)f(W) as a subword which is impossible.

b) x ≠ y; There are two special subcases here, namely either △(L_{1}) = y or L_{1} = R_{1}.

When △(L_{1}) = y it must be that L_{2} = R_{1}, because otherwise, since △(R_{1}) ≠ y, L and R have non-coincidence in the k + 1 letters starting from the (k − l + 2)th position, which is impossible.

By similar reasoning for L_{3}, …, L_{p} we have that

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1} R_{1} … R_{p−1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{t … t}_{k−j+1}} .

Again, L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p−1}, which is

impossible by the same reasons as above.

So L_{1} = R_{1}.

Using the same technique of as above we can easily obtain that in this case

P = \overbrace{\underbrace{x … x}_{k−i+1} R_{1} … R_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{t … t}_{k−j+1}} .

If y ≠ t then L and R have non-coincidence in the first k −ℓ+1 positions and in the last ℓ positions, so they have non-coincidence in k + 1 positions which contradicts P ∈ S_{4}^{3,k}.

If y = t then

P = \overbrace{\underbrace{x … x}_{k−i+1} R_{1} … R_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{y … y}_{k−j+1}}

and L has W W as a subword, where W = R_{1} … R_{p} \underbrace{y … y}_{k+1} which is impossi-

ble.

2. p = p′ + 1. There are two subcases here:

a) x = y; It must be that L_{1} = R_{1}, because otherwise L and R differ in k + 1 positions starting from the (k − i + 2)th position. Then we consider L_{2}, L_{3}, …,L_{p}.

We can see that in this subcase

P = \overbrace{\underbrace{y … y}_{k−i+1} R_{1} … R_{p′} \underbrace{t … t}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} ,

and L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p′} \underbrace{t … t}_{k+1} which is

impossible.

b) x ≠ y; There are two special subcases here, namely either △(L_{1}) = y or L_{1} = R_{1}.

If △(L_{1}) = y then

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1} R_{1} … R_{p′} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} ,

and L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p′} which is impos-

sible.

So L_{1} = R_{1}. In this case we have

P = \overbrace{\underbrace{x … x}_{k−i+1} R_{1} … R_{p′} \underbrace{t … t}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} .

Since y ≠ x, y ≠ △(R_{1}) and y ≠ t, L and R have non-coincidence in the first k−l+1 positions and in the last l positions, so they have non-coincidence in k + 1 positions which contradicts P ∈ S_{4}^{3,k}.

We have got that Case 3 is impossible.

We have proved that the infinite word L contains no word from the set S_{4}^{3,k} as a subword, therefore S_{4}^{n,k} is incomplete for n ≥ 3.

References

1 Evdokimov A. Complete Sets of Words and their Numeral Characteristics, Methods of discrete analysis in research of extremal structures, Novosibirsk, IM SB RAS, Issue 39, (1983), 7-32.

2 Salomaa A. Jewels of Formal Language, Theory Computer Science Press, (1981).

3 Choffrutc, Karhumäk Handbook of formal languages. Vol. 1: Word, language, grammar, Berlin, Springer, (1997), 329-438.

4 Lothaire M. Combinatorics on Words, Encyclopedia of Mathematics, Vol. 17, Addison-Wesley (1986).

Chapter 2

On Non-Existence of an Iterative Morphism that Defines the Arshon Sequence

In [2], Berstel proved that the Arshon sequence cannot be obtained by iteration of a morphism. An alternative proof of this fact is given here.

2.1 Introduction and Background

In 1937, Arshon gave a construction of a symbolic sequence w, which in the alphabet {1, 2, 3} is built as follows: Let w_{1} = 1. For k ≥ 1, w_{k+1} is obtained by replacing the letters of w_{k} in odd positions thus:

1 → 123, 2 → 231, 3 → 312

and in even positions thus:

1 → 321, 2 → 132, 3 → 213.

Then

w_{2} = 123, w_{3} = 123132312,

and each w_{i} is the initial subword of w_{i+1}, so the infinite symbolic sequence w = lim_{n→∞} w_{n} is well defined. It is called the Arshon sequence.

This method of constructing w is called the Arshon Method (AM), and ψ will denote the indicated map of the letters 1, 2, 3, according to position as described above.

We will denote the natural decomposition of w in 3-blocks by lower braces:

w = \underbrace{123} \underbrace{132} \underbrace{312} ….

The paper by Arshon [1] was published in connection with the problem of building a nonrepetitive sequence in a 3-letter alphabet, that is, a sequence that does not contain any subwords of the type XX = X^{2}, where X is any word of a 3-letter alphabet. The sequence w has that property. The question of the existence of such a sequence was studied in algebra, discrete analysis and in dynamical systems.

Let Σ be an alphabet and Σ^{∗} be the set of all words of Σ. A map φ : Σ^{∗} → Σ^{∗} is called a morphism, if we have φ(uv) = φ(u)φ(v) for any u, v ∈ Σ^{∗}. It easy to see that a morphism φ can be defined by defining φ(i) for each i ∈ Σ.

Suppose a word φ(a) begins with a for some a ∈ Σ, and that the length of φ^{k}(a) increases without bounds. The symbolic sequence lim_{k→∞} φ^{k}(a) is called a fixed point of the morphism φ.

We now study classes of sequences, that are defined by iterative schemes. There are many techniques to study sequences generated by morphisms. So it is reasonable to try to determine if a sequence under consideration can be obtained by iteration of a morphism.

Let us consider the following classical sequence as an example of such a sequence. This sequence has two different definitions (actually it has at least 4 different definitions).

The Thue-Morse sequence t:

t_{0}, t_{1}, t_{2}, t_{3}, …

is defined by the conditions:

t_{0} = 0,
t_{2n+1} ≡ t_{n} + 1 (mod 2),
t_{2n} = t_{n}.

So the initial letters of t are

0110100110010110 ….

This sequence is defined by the morphism σ:

σ(0) = 01 ,
σ(1) = 10 .

Since the construction of the Arshon sequence w is similar to the iteration morphism scheme, and because w is constructed by two morphisms f_{1} and f_{2}, applied depending on whether the letter position is even or odd, we might expect that there exists a morphism f which generates w.

But this turns out not to be true, due to the following theorem.

2.2 The Theorem

Theorem. There does not exist a morphism, whose fixed point is the Arshon sequence.

Note. A corollary of this theorem is the non-existence of a morphism which defines the Arshon sequence. In fact, if such a morphism exists, it must have the property that is 1 mapped to 1X by the action of the morphism, where X is some word, and from this it follows that the Arshon sequence is a fixed point of this morphism.

Proof ( of the theorem ):

It is enough to prove the non-existence of a morphism f with the property w = f(w), since from the definition of a fixed point we have that if w is a fixed point of the morphism f then w = f(w). Suppose there exists a morphism f such that

f(1) = X, f(2) = Y, f(3) = Z and w = f(w).

From all such morphisms we choose a morphism with minimal length of X.

The morphism f is not an erasing morphism, that is |X| ≥ 1, |Y | ≥ 1, |Z| ≥ 1, since otherwise w = f(w) contains a subword of the type P P (where P is some word) which cannot belong to w. Now |X| + |Y | + |Z| ≠ 3, since otherwise |f^{l}(1)| = 1 for l = 1, 2..., and w is not a fixed point of the morphism f.

f(w) = w = XY ZXZY ZXY...

Hence X consists of |X| of the first letters of w, Y is |Y | of the following letters, and Z is |Z| of the letters following that.

We will use upper braces to show the decomposition of w into f-blocks (that is, to show the disposition of the words X, Y and Z in w). We have

w = \overbrace{\underbrace{123} \underbrace{132} … a_{|X|}}^{X} \overbrace{a_{|X|+1} … a_{|X|+|Y |}}^{Y} \overbrace{a_{|X|+|Y |+1} … a_{|X|+|Y |+|Z|}}^{Z} \overbrace{a_{|X|+|Y |+|Z|+1} …}^{X} …,

where all a_{i} are letters of the alphabet {1, 2, 3}.

Lemma 1. We have |X| + |Y | + |Z| ≡ 0 (mod 3).

Proof: From the structure of w, the frequencies of 1, 2, 3 in w coincide, hence the frequencies of these letters in f(w) = w coincide as well. But this is only possible when |X| + |Y | + |Z| ≡ 0 (mod 3), since otherwise there are two letters, whose frequencies in f(w) = w do not coincide.

Lemma 2. The situation |X| ≡ |Y | ≡ |Z| ≡ 0 (mod 3) is impossible.

Proof: Suppose |X| ≡ |Y | ≡ |Z| ≡ 0 (mod 3). Then X, Y and Z consist of a whole number of 3-blocks. Hence we can consider the words X′ = ψ^{−1}(X), Y′ = ψ^{−1}(Y), Z′ = ψ^{−1}(Z). The properties of ψ give

w = ψ^{−1}(w) = X′Y′Z′X′Z′Y′Z′X′Y′...

so there exists a morphism f′ which maps 1 to X′, 2 to Y′, 3 to Z′ and w = f′(w). Since |X′| = |X|/3, we have |X′| < |X|. This contradicts the choice of the morphism f.

Lemma 3. With the assumption of the existence of the morphism f, |X| ≤ 5.

Proof: Suppose |X| ≥ 6, that is, X = 123132 . . .. If |X| ≡ 2 (mod 3) (|X| ≡ 1 (mod 3)), then |X| ≥ 7 and using Lemma 1 we consider the 4th f-block X = 12 \underbrace{313} … (X = 1 \underbrace{231} \underbrace{323} …). This contradicts the AM. Hence |X| ≡ 0 (mod 3).

It follows from Lemma 2 that the situation |Y | ≡ 0 (mod 3) is impossible. If |Y | ≡ 1 (mod 3) (|Y | ≡ 2 (mod 3)), then we consider the 10th (3rd) f-block X = 12 \underbrace{313} 2 … and it brings us to a contradiction with the AM. Hence if |X| ≥ 6 then the morphism f can not exist.

Lemma 4. With the assumption of the existence of the morphism f, |X| ≠ 1.

Proof: If |X| = 1, then X = 1 and the length of the words f^{k}(1) for k = 1, 2, … does not increase, whence w is not a fixed point of the morphism f. This is a contradiction.

Lemma 5. With the assumption of the existence of the morphism f, |X| ≠ 2.

Proof: Suppose |X| = 2, that is X = 12.

We have |X| ≡ 2 (mod 3), hence, using Lemma 1, we have |Y |+|Z| ≡ 1 (mod 3).

We consider the 2nd f-block X and the f-block Z next after it. It can be seen that Z begins with 3. We consider the 4th f-block X and Y preceding it and find that Y ends with 3. But then, considering Y Z, which is a subword of w, we see, that 33 is a subword of w, which is impossible. That is for |X| = 2 the morphism f cannot exist.

The 3-blocks 123, 231, 312 are said to be odd 3-blocks. All other 3-blocks are said to be even.

Lemma 6. With the assumption of the existence of the morphism f, |X| ≠ 3.

Proof: Suppose |X| = 3, that is X = 123.

We have |X| ≡ 0 (mod 3), hence, using Lemma 1 we have |Y | + |Z| ≡ 0 (mod 3). Considering the AM, the 2nd f-block X must be an odd 3-block, hence |Y | + |Z| ≡ 1 (mod 2).

Let |Z| ≥ 2. Then the 2nd f-block Z begins with an even 3-block, and the 3rd Z begins with an odd 3-block. This is impossible since 2 letters define the evenness of the 3-block unambiguously. Thus |Z| = 1.

Let |Y | ≥ 2. In XY Z (or in an arbitrary permutation of these letters) there is an even number of 3-blocks, so the 9th f-block Y begins with an odd 3-block, but the 1st Y begins with an even 3-block. Hence |Y | = 1.

This is a contradiction with |Y | + |Z| ≡ 0 (mod 3) (and also a contradiction with |Y | + |Z| ≡ 1 (mod 2)). That is for |X| = 3 the morphism f cannot exist.

Lemma 7. With the assumption of the existence of the morphism f, |X| ≠ 4.

Proof: Suppose |X| = 4, that is X = 1231.

We have |X| ≡ 1 (mod 3), hence, using Lemma 1, we have |Y |+|Z| ≡ 2 (mod 3).

We have |Y | ≥ 2, since otherwise Y = 3 and hence XY X which is a subword of w, contains 3131, which is impossible. Hence Y = 32 . . .. We consider ZX and ZY and see that Z ends with 2. Now |Z| ≥ 2, since otherwise Z = 2 and XZX which is a subword of w, contains 1212, which is impossible. Hence Z = … 32, or Z = … 12. The former is impossible since 3232 is contained in ZY, and hence in w. The latter is impossible too, since considering the 9th f-block Z and the f-block X following it, we obtain ZX = … \underbrace{121} \underbrace{231}, which contradicts the AM. That is for |X| = 4 the morphism f cannot exist.

Lemma 8. With the assumption of the existence of the morphism f, |X| ≠ 5.

Proof: Suppose |X| = 5, that is X = 12313.

We have |X| ≡ 2 (mod 3), hence, using Lemma 1, we have |Y |+|Z| ≡ 1 (mod 3). Then the 4th f-block is X = 12 \underbrace{313}, which is a contradiction with the AM. That is if |X| = 5 then the morphism f cannot exist.

From Lemmas 3 - 8 we have a contradiction with the assumption of the existence of the morphism f. This proves the Theorem.

References

1 Arshon S. E. The Proof of the Existence of n - letter Non-Repeated Asymmetric Sequences, Math. collected papers, New series, Publ. H. AS USSR, Vol. 2, Issue 3, Moscow (1937), 769-779.

2 Berstel J. Mots sans carré et morphismes itérés, Discrete Math. 29 (1979), 235-244.

3 Cobham A. Uniform tag sequences, Math. Systems Theory 6 (1972), 164-192.

4 Lothaire M. Combinatorics on Words, Encyclopedia of Mathematics, Vol. 17, Addison-Wesley (1986).

5 Salomaa A. Jewels of Formal Language, Theory Computer Science Press, (1981).

Chapter 3 There is no Iterative Morphism which Defines the Sequence of σ

The sequence of σ was constructed by Evdokimov in order to build chains of maximal length in the n-dimensional unit cube. We prove that the sequence can not be defined by iteration of a morphism.

3.1 Introduction and Background

Any natural number n can be presented unambiguously as n = 2^{t}(4s + σ), where σ < 4, and t is the greatest natural number such that 2^{t} divides n. If n runs through the natural numbers then σ runs through the sequence that we will call the sequence of σ. We let w denote that sequence. Obviously, w consists of 1s and 3s. The initial letters of w are 11311331113313 . . ..

Defining a morphism we will follow [4].

Let Σ be an alphabet and Σ^{∗} be the set of all words of Σ. A map φ : Σ^{∗} → Σ^{∗} is called a morphism, if we have φ(uv) = φ(u)φ(v) for any u, v ∈ Σ^{∗}. It easy to see that a morphism φ can be defined by defining φ(i) for each i ∈ Σ.

A sequence α is defined by the iteration of a morphism φ, if α = lim_{k→∞} φ^{k}(a), where a is the first letter of α.

In [1], Evdokimov built chains of maximal length in the n-dimensional unit cube using the sequence of σ. Naturally a question arises as to the possibility of constructing w using the iteration of a morphism, since the possibility of such a constructing could help us with studying of w.

We now give an alternative definition of the sequence w, by the following inductive scheme:

C_{1} = 1, D_{1} = 3

C_{k+1} = C_{k}1D_{k}, D_{k+1} = C_{k}3D_{k}
k = 1, 2, …

and w = lim_{k→∞} C_{k}.

3.2 The Theorem

Theorem. There does not exist a morphism whose iteration defines the sequence w.

Proof ( of the theorem ): Suppose there exists a morphism f, such that f(1) = X, f(3) = Y and w = lim_{k→∞} f^{k}(1). Obviously, X consists of the first |X| letters of w, where |X| is the length of X.

Lemma 1. The subsequence of w consisting of the letters in odd positions is the alternating sequence of 1s and 3s: 1313131 ….

Proof: The odd positions of w correspond to the odd numbers n = 2^{0}(4s + σ) = 4s + σ, so cleary σ alternates between 1 and 3.

Lemma 2. If there exists a morphism f whose iteration gives w then |X| ≡ 0 (mod 4).

Proof: It is easy to see that f(1) = 1X^{(1)}, where |X^{(1)}| ≥ 1, since otherwise |f^{k}(1)| = 1, for k = 1, 2, 3 …, so w cannot be obtained by iterating f.

Suppose |X^{(1)}| = 1, that is f(1) = 11. But then w consists of 1s only, which is impossible, hence f(1) = 11X^{(2)}, where |X^{(2)}| ≥ 1.

Suppose |X^{(2)}| = 1, that is f(1) = 113. Since w has the subword 111, then w has a subword f(111) = 113113113. If f(111) begins with a letter in an odd position, then the marked letters 113113113, read from left to right will make up consecutive letters of w in odd positions. This contradicts Lemma 1. If f(111) begins with a letter in an even position, then marking letters in odd positions will lead to the same contradiction with Lemma 1, hence f(1) = 113X^{(3)}, where |X^{(3)}| ≥ 1.

Suppose |X^{(3)}| = 1, that is f(1) = 1131. Then f^{2}(1) = 11311131Y 1131 and the marked letter does not coincide with the letter of w standing in the same place, hence f(1) = 1131X^{(4)}, where |X^{(4)}| ≥ 1.

If |X| is odd, then the marked letters in f^{2}(1) = 1131X^{(4)}1131X^{(4)} … are two consecutive letters in odd places. This contradicts Lemma 1. Hence |X| is even.

We have f^{2}(1) = XX … = X1131X^{(4)} …, whence the next-to-last letter of X is in an odd position and is equal to 3, since otherwise two consequent 1 in w stand at odd places, which contradicts Lemma 1. The natural number which corresponds to the next-to-last letter of X is written as 2^{0}(4s + 3), the next number is equal to |X| and to 2^{0}(4s + 3) + 1 = 4(s + 1) ≡ 0 (mod 4).

The following Lemma is straightforword to prove.

Lemma 3. If n_{1} = 2^{t_{1}}(4s_{1} + 1), n_{2} = 2^{t_{2}}(4s_{2} + 1), n_{3} = 2^{t_{3}}(4s_{3} + 3) and n_{4} = 2^{t_{4}}(4s_{4} + 3) then n_{1}n_{2}, n_{3}n_{4} can be written as 2^{t}(4s + 1), and n_{1}n_{3} as 2^{t}(4s + 3).

It follows from Lemma 2 that |X| = 4t.

Suppose X ends with 1 (the case when X ends with 3 is similar), that is at the (4t)th position in X we have 1. According to the multiplication by 2 does not change σ, so at the (2t)th position in X we have 1.

Consider f^{2}(1) = XX . . .. The letters of the marked X occupy the positions of f^{2}(1) from (4t + 1)th to (8t)th. Since X = X, then at the (6t)th place we have 1. But 6t = 3(2t), whence, by Lemma 3, at the (2t)th and the (6t)th places there must stand different letters. This is a contradiction and the Theorem is proved.

References

1 Berstel J. Mots sans carré et morphismes itérés, Discrete Math. 29 (1979), 235-244.

2 Evdokimov A. On the Maximal Chain Length of an Unit n-dimensional Cube, Maths Notes 6, No. 3 (1969), 309-319.

3 Lothaire M. Combinatorics on Words, Encyclopedia of Mathematics, Vol. 17, Addison-Wesley (1986).

4 Salomaa A. Jewels of Formal Language, Theory Computer Science Press, (1981).

5 Discrete Mathematics and Mathematical Questions of Cybernetics, Vol. 1, Moscow (1974), 112-116.