Technische Universität Graz Institut für Mathematik

Sequences with subword complexity 2n

Günter Rote

Report 204 April 1992

Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

Version 2a This paper appeared in Journal of Number Theory 46 (1993), 196–213. Some typographical errors have been corrected. Figure 2 of this report is not complete in this version because it should contain some hand-drawn additional arcs. The reader, however, is able work out the details for herself.

Title page processed by TEX on February 10, 1995

Sequences with subword complexity 2n

Günter Rote

Abstract

We construct and discuss infinite 0-1-sequences which contain 2n different subwords of length n, for every n.

1 Introduction

For an infinite word w = w_{1}w_{2}w_{3} … over some finite alphabet, we denote by L = { w_{i}w_{i+1} … w_{j} : 1 ≤ i ≤ j } the set of its finite subwords (factors). Let L_{n} = { x ∈ L : |x| = n } denote the set of subwords of length n. Then the function P_{w}(n) := #L_{n} which gives the cardinalities of the sets L_{n} is called the (subword) complexity of the sequence w. Usually, w is fixed by the context and we will write P (n) for P_{w}(n).

This paper considers sequences with complexity P (n) = 2n. We give more general and more specific methods for constructing them.

Infinite words (sequences) over some finite alphabet have been the study of research since the pioneering work of Thue [1906]. Areas of application include such diverse areas as iteration theory, ergodic theory and dynamical systems, formal languages, probability theory, and number theory (see Allouche [1987]).

If P (n) ≤ n for some n, then the word is ultimately periodic, and P (n) is in fact bounded. The lowest possible complexity for an interesting infinite word is thus P (n) = n + 1. Sequences with complexity P (n) ≤ n + 1 are called Sturmian sequences, and they are well understood (cf. Morse and Hedlund [1940] or Coven and Hedlund [1973]). There are several different ways by which one can construct any Sturmian sequence.

Recently, Arnoux and Rauzy [1991] went one step further and investigated sequences with complexity 2n + 1. They showed that, under certain conditions, such sequences can be represented in a geometric way like Sturmian sequences: as the orbit of a point under a simple one-to-one mapping of the unit circle into itself.

In this paper we consider an intermediate case: sequences with complexity 2n. We show how one can in principle construct all such sequences (section 2). The tools that we use are purely combinatorial, similar to the methods of Arnoux and Rauzy [1991].

Since P (1) = 2, the ground alphabet has two symbols, and we will assume that our alphabet is {0, 1}.

In section 2, we give the main graph-theoretic construction. In section 3 we give three concrete examples of sequences with different properties that arise from this construction, and we give alternate methods for constructing special classes of sequences of complexity 2n. The special class of sequences which are closed under complementation has a strong connection with the class of Sturmian sequences. This relation is explored in section 4. The last section mentions some open questions.

2 A construction using graphs

The main tool in this section is the set of directed graphs Γ_{n} which are related to the sets of n-letter subwords L_{n}. The vertices of Γ_{n} are the elements of L_{n}, and the arcs correspond to the elements of L_{n+1}: for each word axb ∈ L_{n+1}, where a, b ∈ {0, 1} and x ∈ {0, 1}^{n−1}, the graph has an arc from ax to xb. For example, the graph Γ_{4} of the word 011001100100110011011001… is shown in figure 1.

[figure: 0011; 1100; 0110; 1001; 1011; 1101; 0010; 0100; 11011; 00100; 01101; 10110; 11001; 10011; 01001; 10010; 01100; 00110; Γ_{4}; 11011; 00100; 01101; 10110; 11001; 10011; 01001; 10010; 01100; 00110; 110110; 011011; 100100; 001001; 101100; 001101; 110010; 010011; 110011; 001100; 011001; 100110; 101101; 010010; D(Γ_{4}); 11011; 00100; 01101; 10110; 11001; 10011; 01001; 10010; 01100; 00110; 110110; 011011; 100100; 001001; 101100; 001101; 110010; 010011; 110011; 001100; 011001; 100110; Γ_{5}]

Figure 1: The graph Γ_{4}, its line graph, and the graph Γ_{5}, for the word 01100110010011001101100110010011…

The line graph D(Γ_{n}) of a word graph Γ_{n} is defined as usual in graph theory: D(Γ_{n}) has a vertex for each arc of Γ_{n}, and two vertices u and v of D(Γ_{n}) are joined by an arc from u to v if the endpoint of the arc u in Γ_{n} coincides with the initial point of v. Figure 1 shows an example. Naturally, the vertices of D(Γ_{n}) are labeled by the words of L_{n+1}, and its arcs are labeled by words of length n + 2: for an arc (u, v), the final n + 1 letters of u must coincide with the first n + 1 letters of v, i. e., we can write u = axb and v = cyd with xb = cy. Then we label the arc (u, v) by axbd = acyd.

In our construction of an infinite word w with complexity P (n) = 2n we will concentrate on successively constructing the graphs Γ_{n}, for n = 1, 2, . . .. Let us therefore discuss the required properties of those graphs, and the relation between Γ_{n} and Γ_{n+1}.

The arcs of the line graph D(Γ_{n}) are all possible words of length n+2 whose (n+1)- letter subwords belong to L_{n+1}. Clearly, L_{n+2} must be a subset of those words. In other words, the graph Γ_{n+1} can be formed from D(Γ_{n}) by removing some edges (or possibly no edges).

Since we are interested in words with complexity 2n, we want Γ_{n} to have 2n vertices and 2n + 2 arcs. In particular, Γ_{1} has 2 vertices and 4 arcs, i. e., we have no choice for Γ_{1}; it must be the “complete” graph with vertex set {0, 1} and arc set {00, 01, 10, 11}.

Thus we can state the following algorithm:

Algorithm for constructing the sequence of graphs Γ_{n}, for n = 1, 2, … Let Γ_{1} be the graph with vertex set {0, 1} and arc set {00, 01, 10, 11}. for n := 1 to infinity do

Construct the line graph D(Γ_{n}) of Γ_{n}.

if D(Γ_{n}) contains 2n + 4 arcs then let Γ_{n+1} := D(Γ_{n}).

if D(Γ_{n}) contains more than 2n + 4 arcs (∗) then remove the correct number of arcs from D(Γ_{n}) to obtain Γ_{n+1}.

if D(Γ_{n}) contains less than 2n + 4 arcs (∗∗) then STOP.

end for.

In the step marked (∗) we actually have a choice of the arcs which we remove. We will therefore derive further necessary properties of Γ_{n+1} and formulate a set of rules that will guide us in step (∗).

Let us consider the number of arcs of D(Γ_{n}). This number decides about the course that the algorithm takes, and in particular it decides whether the algorithm may get stuck in step (∗∗). D(Γ_{n}) has an arc for each pair consisting of an arc of Γ_{n} that leads to a vertex v and an arc leaving this vertex v. The numbers of these arcs of Γ_{n} are called the indegree δ^{−}(v) and the outdegree δ^{+}(v), respectively. Thus D(Γ_{n}) has ∑_{v∈L_{n}} δ^{−}(v) · δ^{+}(v) arcs. Since our alphabet has only two symbols, there are only two possible arcs that can leave a vertex v, namely v0 and v1. Therefore, we always have δ^{+}(v) ≤ 2, and similarly, δ^{−}(v) ≤ 2.

Since the n-letter subsequences of w starting at positions 1, 2, 3, … trace out an infinite path through Γ_{n} which visits every vertex and every arc, the graph must have a vertex from which every other vertex can be reached. We will even insist on the stronger requirement that all graphs Γ_{n} are strongly connected, i. e., every vertex can be reached from every other vertex.

Rule 1: Keep Γ_{n+1} strongly connected.

The following theorem states what this rule amounts to.

Theorem 1 Let w = w_{1}w_{2}w_{3} … be an infinite word. Then the following are equivalent:

(i) All graphs Γ_{n} are strongly connected.

(ii) Every subword that occurs in w occurs at least twice.

(iii) Every subword that occurs in w occurs infinitely often.

Proof. (i) implies (ii): Let x = w_{1}w_{2} … w_{n} be an initial subword of w. Since Γ_{n} has an arc entering x there must be a second occurrence of x in w. Thus (ii) holds for all initial subwords. Since any subword of w is contained in an initial subword, (ii) follows in general.

(ii) implies (iii): Let x be a subword of w. By (ii), there is a subword x′ of w in which x occurs twice. By applying (ii) again, there is a subword x′′ of w in which x′ occurs twice. This word x′′ must contain at least three occurrences of x. Similarly, a word x′′′ which contains x′′ twice contains at least four occurrences of x. Continuing inductively, we conclude that x is contained infinitely often in w.

(iii) implies (i): Consider any two subwords x and y of length n. After any occurrence of x there must still follow another occurrence of y in w, and hence there is a path from x to y in Γ_{n}. □

Rule 1 implies in particular that we will always have δ^{−}(v) ≥ 1 and δ^{+}(v) ≥ 1, for all v. Γ_{n} has P (n) = 2n =: t vertices and P (n + 1) = t + 2 arcs. The possible topologies of strongly connected directed graphs with t vertices and t + 2 arcs and with δ^{−}(v), δ^{+}(v) ≤ 2 are listed in the middle column of figure 2. In these pictures, each curved arrow represents a path of one or more arcs. The cases are classified according to the set of degree pairs (δ^{−}(v), δ^{+}(v)) of Γ_{n}, which is listed in the leftmost column of the figure. The possible degree pairs are subject to the condition that the sum of the indegrees δ^{−}(v) and the sum of the outdegrees δ^{+}(v) of the t vertices v equals the number of arcs, which is t + 2. This leaves only the three possible degree sequences given in the table.

The right column of figure 2 shows the topologies of the resulting line graphs. In these pictures, the curved arrows denote paths consisting of zero or more arcs, whereas the short straight arrows denote single arcs. The table states also in each case the number of arcs that have to be removed from D(Γ_{k}) in order to get a graph Γ_{k+1} with t + 4 arcs. In the bottom-most case, this number is zero, and since we do not have to make any choice in this case, we need not care about the possible topologies.

Since the table lists all possible degree sequences, we see that case (∗∗) cannot arise, and the algorithm can never get stuck.

In the line graphs, some arcs are marked by little lines crossing through them. One way of satisfying rule 1 is the following more specific rule:

Rule 1′: Select the arcs that are to be removed from D(Γ_{n}) only from among the marked arcs in figure 2

As can be checked from the pictures, this ensures that the graph L_{n+1} is strongly connected.

Lemma 1 If a sequence of graphs Γ_{n} with vertex sets L_{n} is constructed according to rule 1, then every word of L_{n} is contained in some word of L_{n+1}, and hence, in some word of L_{n′} for every n′ ≥ n.

Proof. Every vertex x of Γ_{n} has at least one arc incident to it. This arc is a vertex of Γ_{n+1} and therefore a word of L_{n+1} containing x. □

So far, we have succeeded to construct sequences of word sets L_{n} with cardinality #L_{n} = 2n and the property that the language L = ⋃_{n=1}^{∞} L_{n} is closed under taking subwords. However, we must still make sure that L is the set of subwords of an infinite sequence. Therefore, the sequence L_{1}, L_{2}, … that we will construct must have the following property:

Extension property: There is a subsequence L_{n_{1}}, L_{n_{2}}, L_{n_{3}}, … (n_{1} < n_{2} < n_{3} < ⋯) and a sequence of words x_{1}, x_{2}, x_{3}, … with x_{i} ∈ L_{n_{i}} such that x_{i+1} starts with x_{i} and contains all words of L_{n_{i}}.

degree sequence  the graph Γ_{n}  the line graph D(Γ_{n})

1 (2, 2) ; (2, 2) ; (1, 1) ; (1, 1) ; ⋮

2 arcs are to be deleted from the line graph.

[figure: 1A]

[figure]

[figure: 1B]

2 (2, 2) ; (2, 1) ; (1, 2) ; (1, 1) ; (1, 1) ; ⋮

One arc is to be deleted from the line graph.

[figure: 2A]

[figure]

[figure: 2B]

[figure: 2C]

[figure: 2D]

3 (2, 1) ; (2, 1) ; (1, 2) ; (1, 2) ; (1, 1) ; ⋮

No arcs are to be deleted from the line graph in this case. Γ_{n+1} is unique and contains every arc of D(Γ_{n}).

Figure 2: The possible degree sequences and topologies of Γ_{n}, and the corresponding topologies of the line graphs D(Γ_{n}) from which Γ_{n+1} is obtained.

The following elementary lemma states that this property is necessary and sufficient for our purposes.

Lemma 2 A set L of finite words is the set of finite subwords of an infinite word w_{1}w_{2}w_{3} … if and only if

(i) every word of length n in L is contained in some word of length n + 1 in L; and

(ii) the sequence L_{1}, L_{2}, …, where L_{n} = { x ∈ L : |x| = n } is the set of subwords of length n, fulfills the extension property.

Proof. Note first that (i) is the property stated in lemma 1. The two properties are clearly necessary. They are also sufficient because the extension property ensures that the infinite word w = w_{1}w_{2}w_{3} … which is the limit of the sequence x_{1}, x_{2}, x_{3}, … contains every word of L_{n_{1}}, L_{n_{2}}, etc. Together with property (i) this implies that w contains every word of L. □

There are more marked arcs than we must remove; we will use this freedom of choice for achieving the extension property.

Lemma 3 Let x and y be two different vertices in L_{n}, and let d be the distance from x to y. Then we can choose the correct number of arcs to be removed from the line graph D(L_{n}) such that the resulting graph L_{n+1} contains two vertices xa and cy, (which correspond in L_{n} to an arc leaving x and an arc entering y) such that the distance from xa to cy in L_{n+1} is d − 1.

Proof. Let xa and cy be the first and last arc on the shortest path from x to y in L_{n}. Then the line graph contains a (shortest) path from xa to cy of length d − 1.

Now we simply have to check for all possibilities in the table that for any specified shortest path in the line graph, we can always select the correct number of marked arcs to be removed and still leave this shortest path intact. If we have to remove p arcs from among q marked arcs, it suffices to show that no shortest path can contain more than q − p marked arcs.

For example, in case 1A, where two arcs are to be removed, we have to show that a path using three of the four marked arcs cannot be a shortest path. Such a path would have to contain the two marked arcs in the left half of the picture or the two marked arcs in the right half of the picture. In any case, there is an arc from the starting point of the first marked arc to the endpoint of the second marked arc, and this would shortcut the path. □

We will now use this lemma to inductively construct L_{n_{i+1}} and x_{i+1} from L_{n_{i}} and x_{i} so that the extension property is fulfilled. We call this transition from i to i + 1 a stage of the algorithm.

Suppose we have already constructed a graph L_{k} with k ≥ n_{i} and a word u ∈ L_{k} which starts with x_{i} and contains a certain number of other words of L_{n_{i}} as subwords. (At the start of a stage we have k = n_{i} and u = x_{i}.) If u already contains all words of L_{n_{i}} as subwords, we can take n_{i+1} = k and x_{i+1} = u and we have completed the stage and can start the next one. Otherwise, select some word of L_{n_{i}} which is not contained in u and find a word v in L_{k} which contains it. (Such a word v exists by lemma 1.) Declare v to be the current target word and call u the current start word.

Let d be the distance from u to v. By the previous lemma, L_{k+1} contains a word ua whose distance to some word cv containing v is d − 1 in D(Γ_{k}). We declare ua to be the new start word and cv to be the new target word. We can ensure that the distance from ua to cv in Γ_{k+1} is d − 1, if we obey the following rule:

Rule 2: Do not remove any arcs that lie on a shortest path from the start vertex to the target vertex.

We iterate this process of declaring the new start word and the new target word and constructing L_{k+1} by rules 1 and 2. After d steps, we have a graph L_{k+d} and a word uw ∈ L_{k+d} which contains v. This means that the current start word uw contains an additional word of L_{n_{i}}.

In this way, we can pick up one word of L_{n_{i}} after the other until we have a word containing all of them, and the stage is completed. We summarize the result of the preceding arguments in the following lemma.

Lemma 4 By following rule 2 we can ensure that the extension property is fulfilled. □

Together with lemma 2 this implies plainly that sequences of complexity 2n exist. Such sequences can be constructed by following rules 1 and 2. The rules leave some freedom of choice (except in case 3 of figure 2), and thus there are many sequences of complexity 2n.

Note that we need not abide by rule 2 all the time. In fact, we can remove arbitrary arcs subject only to rule 1 as long as we like (but not indefinitely); there is always time for repentantly returning to rule 2 and finishing the stage.

3 Some particular sequences

3.1 A first sequence

By following rules 1 and 2 and choosing among the possibilities offered by these rules according to a particular pattern I constructed a couple of sequences of complexity 2n. One such sequence w can be described in the following way. We start with the word consisting of the single symbol /, and repeatedly transform it by the set of substitutions given in figure 3a. When we apply the substitution, we apply it to all elements of a word in parallel. Since the replacement string for the start symbol / starts with /, the word that results from applying the substitution k + 1 times is an extension of the word which we get after k substitution steps. This means that the sequence of words converges to an infinite sequence, which is shown in the upper part of figure 3c. The little marks above and below the sequence show how far the word extends after 0,1,2,… substitutions. To the infinite word over the four-letter alphabet {/, \, , } we finally apply the letter-to-letter substitution in figure 3b, to obtain the 0-1-sequence w, which is shown in the lower part of figure 3c. The graphs in figure 1 of section 2 are the graphs Γ_{4} and Γ_{5} of this sequence. The four symbols /, \, , and correspond to the four arrows in case 1A of the middle column of figure 2. The up and down movement of the word indicates the transitions between the two vertices of the figure.

In the theory of formal languages, a system like the one above for generating an infinite word is called a tag system (cf. Cobham [1972]), or when it is viewed as a method

\begin{aligned}[figure: (a)] & → [figure] \\ [figure] & → [figure] \\ & → [figure] \\ & → [figure] \end{aligned}  [figure: (b); → 0; → 1; → 0; → 1]

(c)

[figure: …]
01100110010011001101100110010011001101100110011011001100100110011011001100

Figure 3: The substitutions and the infinite word w which they generate.

of generating a sequence of finite words, a CD0L system (cf. the book of Rozenberg and Salomaa [1980]).

We can generate the above sequence w by another mechanism, namely as the orbit of the mapping x ↦ (x + θ) mod 2, with θ = 1 − 1/\sqrt{5} ≈ 0.5528:

w_{n} = \{ \begin{matrix}0, & if nθ mod 2 ∈ [0, 1), \\ 1, & if nθ mod 2 ∈ [1, 2). \end{matrix}  (1)

This construction can be generalized by choosing a different breakpoint than the midpoint of the interval [0, 2) for selecting between the cases w_{n} = 0 and w_{n} = 1. For reasons which will become apparent in section 4, we have chosen the interval [0, 2) as the domain of our iteration mapping. In the following theorem and in the remainder of this section we take the more natural choice [0, 1).

Theorem 2 Let c, φ, and θ be real numbers with 0 < φ < 1, 0 < θ < min(φ, 1 − φ), θ irrational, and nθ ≢ φ (mod 1), for all integers n. Then the sequence w = w_{1}w_{2}w_{3} … which is defined below has complexity P (n) = 2n:

w_{n} = \{ \begin{matrix}1, & if (c + nθ) mod 1 ∈ [0, φ), \\ 0, & if (c + nθ) mod 1 ∈ [φ, 1). \end{matrix}

Proof. Let us first see why the condition θ < min(φ, 1 − φ) is necessary: if θ ≥ φ it is easy to check that the subword 11 cannot occur in w, and similarly, if θ ≥ 1 − φ the subword 00 cannot occur. Thus one of the four words 00, 01, 10, 11 of length 2 is missing and we cannot have P (2) = 4.

For the proof note that the subword w_{n}w_{n+1} … w_{n+l−1} depends only on the value x_{n} := (c + nθ) mod 1. We can view the mapping x ↦ (x + θ) mod 1 that maps x_{n} to x_{n+1} as a rotation of the unit circle by the angle θ · 2π. The real numbers modulo 1, which are represented by the interval [0,1), correspond then to the points on the unit circle. The letter w_{n+d} depends on the position of x_{n+d} = (x_{n}+dθ) mod 1 relative to the interval [0, φ) on the unit circle. In other words, w_{n+d} depends on the relative position of x_{n} with respect to the two points (0 − dθ) mod 1 and (φ − dθ) mod 1. Thus, the 2l points (−dθ) mod 1 and (φ − dθ) mod 1, for d = 0, 1, …, l − 1, dissect the circle into at most 2l half-open circular intervals, and the subword w_{n}w_{n+1} … w_{n+l−1} of length n depends on the interval into which x_{n} falls. It follows that P (n) ≤ 2n. To show equality, we inductively prove the following claim:

Claim: There are exactly 2l circular intervals; and they correspond to 2l different subwords of length l.

The first part of the claim is true because the irrationality assumptions on φ and θ guarantee that the 2l boundary points of the intervals are distinct. The second part is proved by induction on l. It is clearly true for l = 1. For the conclusion from l to l + 1, note that the two “new” boundary points (−lθ) mod 1 and (φ − lθ) mod 1 fall into two different subintervals of the 2l subintervals so far, because they are for example separated by the two previous points (−(l−1)θ) mod 1 and (φ−(l−1)lθ) mod 1. (Here the assumption 0 < θ < min(φ, 1−φ) is used: the four points in question can be rotated to the points 0, φ, θ, and θ + φ, for which the situation is clear.) This implies that for the 2 subintervals which are split by the new points, the corresponding subwords of length l are extended to length l + 1 in two possible ways, whereas the remaining 2l − 2 subwords are extended in only one way. This clearly gives 2l + 2 different words of length l + 1 for the 2l + 2 circular intervals. This concludes the proof of the claim.

Since the points x_{n}, n = 1, 2, …, are dense in [0,1), every half-open circular subinterval contains such a point, and thus every word which correspond to a half-open circular subinterval actually occurs as a subword. □

Remark. Without the assumption 0 < θ < min(φ, 1 − φ), we still have proved P (n) ≤ 2n. In fact, there is some threshold n_{0} such that for all n > n_{0}, even P (n) = 2n is true; i. e., P (n) is deficient only at the beginning.

The following lemma gives two further properties of the sequences which are generated as described above.

Lemma 5 Let an infinite word of complexity 2n be constructed according to theorem 2.

(a) The parameter φ gives the approximate relative frequency of ones in long subwords of w. More precisely, let #_{1}(u) denote the number of ones in the finite subword u, and let L_{n}(w) denote the number of n-letter subwords of w. Then

lim_{n→∞} max \{ \frac{#_{1}(u)}{n} : u ∈ L_{n}(w) \} = lim_{n→∞} min \{ \frac{#_{1}(u)}{n} : u ∈ L_{n}(w) \} = φ.

(b) The number of occurrences of the pattern 01 in a substring of length n+1 is either ⌊nθ⌋ or ⌈nθ⌉. Thus, θ gives the approximate relative frequency of the pattern 01 in long subwords of w.

(c) The number of occurrences of the pattern 10 in a substring of length n+1 is either ⌊nθ⌋ or ⌈nθ⌉. Thus, θ gives the approximate relative frequency of the pattern 10 in long subwords of w.

Proof. (a): This follows from the classical fact that the sequence x_{n} = (c + nθ) mod 1 is uniformly distributed in [0, 1): #_{1}(w_{l}w_{l+1} … w_{l+n−1})/n equals the proportion of the points x_{l}, x_{l+1} … x_{l+n−1} which lie in the interval [0, φ), and this proportion converges to φ as n goes to ∞.

(b): The pattern 01 occurs at position l precisely if y_{l} := c + lθ ∈ [i − 1, i) and y_{l+1} = c+(l +1)θ ∈ [i, i+1), for some integer i. In a sequence of n+1 successive values y_{l}, y_{l+1}, …, y_{l+n} this happens ⌊y_{l+n}⌋ − ⌊y_{l}⌋ = ⌊y_{l} + nθ⌋ − ⌊y_{l}⌋ times. For any value of y_{l}, this number is equal to one of the two values stated in the lemma.

Part (c) is analogous to (b). □

The method of theorem 2 for generating an infinite sequence is very similar to a method for generating Sturmian sequences. There is in fact a very close relation between sequences with φ = 1/2 (like the sequence w of figure 3 and (1)) and Sturmian sequences, which will be investigated in section 4.

3.2 Another sequence

In this subsection give a different sequence which cannot be generated by theorem 2. It is again described by a substitution on a four-letter alphabet {/, \, L, } (see figure 4a). The start symbol is /. The final homomorphism to the alphabet {0, 1}, which is shown in figure 4b, is now not just a letter-to-letter mapping, but maps different symbols to 0-1-words of different lengths. (In formal language theory this is called a HD0L system.) The resulting words are shown in figure 4c. In this sequence, the only case among the rows in figure 2 that arises is case 2D, apart from the trivial case 3.

\begin{aligned}[figure: (a)] & → [figure] \\ [figure] & → [figure] \\ & → [figure] \\ & → [figure] \end{aligned}  [figure: (b); → 0; → 1; → 10110; → 101]

(c)

[figure: …]

010110101100101011001011010110010101101011001011010110010101101011001010110

Figure 4: Another set of substitutions generating an infinite word with complexity 2n. The dots in the last line are for orientation only; they separate the words that correspond to single symbols of the first line.

By studying the eigenvalues of the 4×4-matrix which specifies the number of symbols of each type in the replacement string for each symbol in figure 4a one can compute the limiting relative frequency φ of ones and the limiting relative frequency θ of the subword 01. The exact expression of these numbers by radicals is unwieldy and therefore not given; their approximate values are φ ≈ 0.5346 and θ ≈ 0.3737. By lemma 5, if our sequence is constructed according to theorem 2, it must have these values of φ and θ. It is easily checked that such a sequence contains the subword 0100, which is not contained in the sequence of figure 4. On the other hand, the latter sequence contains 1100, which is contained in no sequence generated by theorem 2 with the given values of φ and θ.

3.3 A third sequence

All sequences considered so far have the property that the distance between any two adjacent occurrences of a given finite word is bounded. I conclude this section with a sequence of complexity 2n for which this is not true. Figure 5 shows the substitution and the resulting sequence. This substitution is particularly simple and works directly with the final alphabet {0, 1}. The start symbol is 0. Clearly, the sequence contains arbitrarily long blocks of ones, and thus there is no bound n_{0} such that, for example, the subword 00 is contained in every subword of length n_{0}.

\begin{aligned}0 & → 001 \\ 1 & → 111 \end{aligned}

[figure: 0; 0; 1; 0; 0; 1; 1; 1; 1; 0; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 1; 0; 0; 1; 1; 1; 1; 0; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; …]

Figure 5: Another substitution generating an infinite word with complexity 2n.

4 A relation with Sturmian sequences

According to Morse and Hedlund [1940], an infinite 0-1-sequence is called Sturmian, if the lengths of any two subwords which start and end with zero and contain the same number of zeros differs by at most one. Equivalently, the number of ones in any two subwords of the same length differ by at most one (see also Coven and Hedlund [1973], section 3).

We recall a few basic facts about Sturmian sequences from the papers cited above. Note that we deal only with one-way infinite sequences (rays), whereas the word “sequences” in the cited papers includes also doubly-infinite sequences (trajectories, series) and finite sequences (blocks).

A Sturmian sequence is either periodic from some point on, in which case the complexity is bounded, or it has complexity P (n) = n + 1. Any sequences with complexity P (n) = n + 1 is an aperiodic Sturmian sequence.

Such an aperiodic Sturmian sequence β = β_{1}β_{2}β_{3} … can be generated in the following way. For given real numbers c and θ between 0 and 1 with θ irrational, we either define β_{n} for n = 1, 2, 3, … as

β_{n} := \{ \begin{matrix}1, & if (c + nθ) mod 1 ∈ [0, θ), \\ 0, & if (c + nθ) mod 1 ∈ [θ, 1). \end{matrix}  (2)

or as

β_{n} := \{ \begin{matrix}1, & if (c − nθ) mod 1 ∈ [0, θ), \\ 0, & if (c − nθ) mod 1 ∈ [θ, 1). \end{matrix}  (2′)

Lemma 6 An infinite sequence has complexity P (n) = n + 1 if and only if it can be constructed by (2) or by (2′) with some irrational θ. □

These aperiodic sequences are called irrational Sturmian sequences. In such a sequence, the number of zeros in a subword of length n is either ⌊nθ⌋ or ⌈nθ⌉. It follows that the proportion of zeros in subwords of increasing length converges to θ. Similarly, the number of ones divided by the number of zeros tends to a limit α = θ/(1 − θ) which is called the frequency of the sequence.

By setting c = θ = 1 − 1/\sqrt{5} and using (2) we get a Sturmian sequence whose close relation to the sequence w which was defined by (1) in the section 3.1 is obvious:

β_{n} := \{ \begin{matrix}1, & if (n + 1)θ mod 1 ∈ [0, θ), \\ 0, & if (n + 1)θ mod 1 ∈ [θ, 1). \end{matrix}

In fact, we have

β_{n} = \{ \begin{matrix}1, & if w_{n+1} ≠ w_{n}, \\ 0, & if w_{n+1} = w_{n}. \end{matrix}

In other words, β_{n} = (w_{n+1} −w_{n}) mod 2 is a kind of difference sequence or derivative of the sequence w. On the other hand, w_{n} = (β_{1} + β_{2} + ⋯ + β_{n−1}) mod 2 can be obtained as the partial sums sequence of the sequence β.

The sequence w has a strong symmetry property with respect to complementation of its symbols (interchanging zeros and ones). For any finite subword of w, the complemented word also occurs in w. This can be easily seen from the definition in figure 3a–b, because the rules are completely symmetric with respect to exchanging / with \, with , and 0 with 1. We call a 0-1-sequence with this property complementation-symmetric. We will show that any sequence with complexity 2n that fulfills this symmetry condition is obtainable from a Sturmian sequence in the way described above, namely as its partial sums sequence.

Theorem 3 An infinite 0-1-sequence w = w_{1}w_{2}w_{3} … is a complementation-symmetric sequence with complexity P (n) = 2n if and only if its difference sequence β = β_{1}β_{2}β_{3} …, which is defined by β_{n} = (w_{n+1} − w_{n}) mod 2, is an irrational Sturmian sequence.

Proof. “Only if”: Consider the set L_{n+1} of subwords of w of length n + 1. Every subword x of β of length n can be obtained as the “difference word” of some word y ∈ L_{n+1}. L_{n+1} contains P_{w}(n + 1) = 2n + 2 different words, but two words y ∈ L_{n+1} which are complements of each other yield the same difference word x. This gives P_{β}(n) = P_{w}(n + 1)/2 = n + 1 different words x of length n.

“If”: For an irrational Sturmian sequence β with complexity n + 1, we have to show that its partial sums sequence w_{n}, which is defined by w_{n} = (w_{1} + β_{1} + β_{2} + ⋯ + β_{n−1}) mod 2, where w_{1} can be arbitrarily set to 0 or 1, has complexity 2n and is complementation-symmetric. Each subword x of β of length n gives rise to one of two complementary subwords y of w of length n + 1, depending on the position where it occurs: for x = β_{l}β_{l+1}β_{l+2} … β_{l+n−1}, the word y = w_{l}w_{l+1}w_{l+2} … w_{l+n} is one of the two words whose difference word is x, depending on w_{l}. If we show that both of these words occur in L_{n+1}, for a given x, we have at once proved that w is complementationsymmetric and that is has the correct complexity: each of the P_{β}(n) = n + 1 words x of length n gives 2 words y of length n + 1, and thus P_{w}(n + 1) = 2(n + 1).

To finish the proof of theorem 3, we will need a definition and an intermediate theorem.

Definition. Suppose that a subword x occurs in two different positions in an infinite word w, i. e., the word w can be written in the form w = ux … = uvx …, for some words u and v. Then we call v the offset between these two occurrences of x.

In other words, the offset is the subword between the “starting points” of the two occurrences. Note that the offset includes the first occurrence of x (or at least part of it if the two occurrences of x overlap).

Theorem 4 Every subword x of an irrational Sturmian sequence has two occurrences with an offset containing an odd number of ones.

Note that this is what is needed for the proof of theorem 3, because the two occurrences x give rise to both words y whose difference word is x.

Note also that the above definition of the offset is somewhat arbitrary because it depends on some “reference point” of x. (In our case this is the starting point.) However, it is easy to see that the parity of the number of ones does not change if we choose a different reference point in the definition of the offset, as long as the reference point lies inside x or at the boundary of x. Proof. In w, each zero is followed either by ⌊α⌋ ones or by ⌈α⌉ ones. If the pattern x consists of at most ⌊α⌋ ones and no zeros, the theorem follows directly: we find in a block of ⌈α⌉ ones two occurrences of x whose offset is a single 1, and the theorem is proved.

Otherwise, we use a transformation which reduces w to another infinite sequence w′ and the pattern x to a shorter pattern x′. (This is essentially the same as the process called derivation in Morse and Hedlund [1940] and transformation (B) in Flor [1962].) This reduction has the property that every occurrence of x′ in w′ corresponds to some occurrence of x in w.

We take the sequence w and cut it before each 0, thus decomposing it into blocks which consist of an initial zero followed by ones. A possible initial block of ones is discarded.

There are two types of blocks, with ⌊α⌋ ones and with ⌈α⌉ ones, respectively. Now we replace each block that has an even number of ones by a 0 and each block with an odd number of ones by a 1, and we call the resulting sequence w′ the reduced sequence. According to Morse and Hedlund [1940, section 8] the reduced sequence is again irrational Sturmian, with frequency α′ = (α − ⌊α⌋)/(1 − (α − ⌊α⌋)) if ⌊α⌋ is even and α′ = (1 − (α − ⌊α⌋))/(α − ⌊α⌋) if ⌊α⌋ is odd.

We also have to reduce the pattern x. Before replacing blocks that start with zero by single letters as above, we apply some “cosmetic” changes to x that do not affect the occurrences of x in w in an essential way. If x starts with ⌈α⌉ ones, we can prepend a zero to x: since any sequence of ⌈α⌉ ones in w is preceded by a zero, this does not change the occurrences of x and is therefore permitted. (An initial occurrence of x as the starting word of w might be lost.)

Now we are sure that x contains at least a zero. If x contains ones before the first zero, there can be at most ⌊α⌋ of them, and we omit them. Again, this does not introduce additional occurrences of x in w. (Remember that, before forming w′, we have deleted initial ones from w; hence there will be no additional occurrence of the shortened x close to the beginning of w.)

If the last zero of x is followed by fewer than ⌈α⌉ ones, we discard this zero and the following ones. (It is possible that x becomes the empty word.) Now we apply the reduction procedure to x, as described above for w, yielding x′. Every occurrence of x′ in w′ corresponds uniquely to an occurrence of x in w. (This is true even if x′ is the empty word; the empty word occurs at every position of w′.) Furthermore, the offset between two occurrences of x′ in w′ contains an odd number of ones if and only if this holds for the offset between the corresponding occurrences of x in w. Thus it is sufficient to prove the theorem for x′ and w′ in place of x and w.

In each reduction step, the pattern x will be shortened: if x contains ones, the ones will either be deleted or they will be merged with a preceding zero into a single letter; and if x consists only of zeros, the last zero will be canceled. It follows that the sequence of reductions eventually bottoms out in a pattern with at most ⌊α⌋ ones for which the direct proof works. (This case includes the empty pattern.) □

With this proof the proof of theorem 3 is also complete.

Note that the proof even proves the existence of two adjacent occurrences of x with an offset containing an odd number of ones (i. e., two occurrences with no other occurrences in between). Since there is nothing special about the symbol 1, we also know that there are adjacent occurrences of x with an offset containing an odd number of zeros. It is an easy matter to prove that every subword x has two (not necessarily adjacent) occurrences with an offset containing an even number of ones (or an even number of zeros).

The technique of the proof of theorem 3 has also been used by Allouche [1992] to relate the complexity of generalized Rudin–Shapiro sequences in the sense of Mendès France and Tenenbaum [1981] to the complexity of paperfolding sequences. (For a survey on various aspects of paperfolding sequences see for example Dekking, Mendès France, and van der Poorten [1982].) A generalized Rudin–Shapiro sequence w is defined as the partial sums sequence of a paperfolding sequence u, and the property of theorem 4 holds for every paperfolding sequence, which yields P_{w}(n) = 2P_{u}(n − 1).

Corollary An infinite 0-1-sequence w = w_{1}w_{2}w_{3} … is a complementation-symmetric sequence with complexity P (n) = 2n if and only if it can be generated according to theorem 2 with φ = 1/2.

Proof. It is easy to see that the sequences generated by theorem 2 with φ = 1/2 are complementation-symmetric. The other direction follows with the help of lemma 6. □

Note that the sequences generated by theorem 2 with φ = 1/2 were essentially already considered by Flor [1962], who investigated sequences of ±1’s that can be written as

sgn sin 2π(c + nθ).

Apart from the possible occurrence of zeros in these sequences, they coincide with the complementation-symmetric sequences considered in this section.

5 Future work

We have presented a general method and a couple of special methods for constructing sequences of complexity 2n, and we have given several examples with different properties. However, the totality of these sequences is far from being well understood.

By a more careful analysis it should be possible to give a scheme for generating all words of complexity 2n using the expressive power of L-systems (see Rozenberg and Salomaa [1980]), as in figures 3, 4, and 5. For Sturmian sequences such a scheme is known, see Rauzy [1985] or Arnoux and Rauzy [1991]. I will investigate this question in a future paper.

It seems less difficult to extend the methods of section 2 to complexity functions like P (n) = 2n + k, for a fixed positive k, or to relax the condition of strong connectedness (rule 1), cf. theorem 1. It would only be necessary to include in figure 2 cases with δ^{−}(v) = 3, δ^{−}(v) = 4, and δ^{+}(v) = 3. It should also be no problem to include doubly infinite sequences.

References

1. J.-P. Allouche [1987], Automates finis en théorie des nombres, Expositiones Math. 5, 239–266.

2. J.-P. Allouche [1992], The number of factors in a paperfolding sequence, Bull. Austral. Math. Soc. 46, 23–32

3. P. Arnoux and G. Rauzy [1991], Représentation géométrique des suites the complexité 2n + 1, Bull. Soc. Math. France 119, 199–215.

4. A. Cobham [1972], On uniform tag systems, Math. Systems Theory 6, 164–192.

5. E. M. Coven and G. A. Hedlund [1973], Sequences with minimal block growth, Math. Systems Theory 7, 138–153.

6. M. Dekking, M. Mendès France, and A. van der Poorten [1982], FOLDS!, Math. Intelligencer 4, 130–138, 173–181, and 190–195; see also L. Auteurs, Corrigendum, Math. Intelligencer 5, 2 (1983), p. 5.

7. P. Flor [1962], Ein Verteilungsproblem für arithmetische Folgen, Abh. Math. Sem. Univ. Hamburg 25, 62–70.

8. M. Mendès France and G. Tenenbaum [1981], Dimension des courbes planes, papiers pliés et suites de Rudin–Shapiro, Bull. Soc. Math. France 109, 207–215.

9. M. Morse and G. A. Hedlund [1940], Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62, 1–42.

10. G. Rauzy [1985], Mots infinis en arithmétique, in: Automata on Infinite Words, École de Printemps d’Informatique Théorique, Le Mont Dore, May 1984, ed. M. Nivat and D. Perrin, Lecture Notes in Computer Science, vol. 192, Springer-Verlag, Berlin etc., pp. 165– 171.

11. G. Rozenberg and A. Salomaa [1980], The Mathematical Theory of L Systems, Academic Press, New York etc.

12. A. Thue [1906], Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I, Math.-Nat. Kl. 7, 1–22.