Generating the Peano curve and counting occurrences of some patterns

Sergey Kitaev Department of Mathematics University of Kentucky Lexington, KY 40506-0027, USA e-mail: kitaev@ms.uky.edu

Toufik Mansour ^{∗} Department of Mathematics Haifa University 31905 Haifa, Israel e-mail: toufik@math2.haifa.ac.il

Patrice Séébold LaRIA, Université de Picardie Jules Verne 5, rue du Moulin Neuf 80000 Amiens, France e-mail: seebold@laria.u-picardie.fr

November 13, 2003

Abstract

We introduce Peano words, which are words corresponding to finite approximations of the Peano space filling curve. We find the number of occurrences of certain patterns in these words. We give a tag-system to generate automatically these words and, by showing that they are almost cube-free, we prove that they cannot be obtained by simply iterating a morphism.

Keywords: Peano words, ordered patterns, tag-system, D0L-system, cubes.

∗Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

1 Introduction

Different notions of pattern can be encountered in several domains of combinatorics.

In algebraic combinatorics, an occurrence of a pattern p in a permutation π is a subsequence of π (of the same length as the length of p) whose elements are in the same relative order as those in p. For example, the permutation π = 536241 contains an occurrence of the pattern p = 2431 : indeed the elements of the subsequence 3641 of π are in the same relative order as those in p. Examples of results concern permutations avoiding a pattern of length 3 in S_{3} (see [12, 20]).

Motivated by the study of Mahonian statistics, Babson and Steingrímsson introduced a generalisation where two adjacent elements of the pattern must also be adjacent in the permutation [1]. In Claeson, 2001 [7] this generalisation provides interesting results related to set partitions, Dyck paths, Motzkin paths, or involutions.

In combinatorics on words, an occurrence of a pattern p in a word u is a factor of u having the same shape as p, i.e., for which there exists a nonerasing morphism transforming p in this factor. For example the word u = abaabaaabab contains an occurrence of the pattern p = ααβααβ : indeed the morphism f(α) = a, f(β) = ba transforms the pattern p in aabaaaba which is a factor of u. The main question is to determine whether or not a given pattern is unavoidable, that is if it is possible to construct an infinite word containing no occurrence of the pattern. The interested reader should refer to Chapter 3 of Lothaire, 2002 [14].

In Burstein, 1998 [3], Burstein and Mansour, 2002, 2003 [4, 5, 6], and Kitaev and Mansour, 2003 [11] the authors realised a “mixing” of these two notions. They consider ordered alphabets. Here, an occurrence of a pattern in a word is a factor or a subsequence having the same shape, and in which the relative order of the letters is the same as in the pattern. For example, on the alphabet {a, b} with a < b, the word u = abaaabab contains an occurrence of the pattern 2111 (the factor baaa) but not of the pattern 1222 (abbb is not a factor of u). To avoid confusion we will call these patterns ordered patterns.

Using this definition, Kitaev and Mansour [11] were interested in counting the number of occurrences of some ordered patterns in words generated by certain morphisms. A motivation for this choice was the interest in studying classes of sequences and words that are defined by iterative schemes [14, 18].

In the present paper we also study the number of occurrences of certain ordered patterns in words defined by an iterative scheme, the Peano words. After some preliminaries (Section 2), we introduce in Section 3 the notion of Peano words. Then we find the number of occurrences of a lot of ordered patterns in these words (Section 4) and we end by showing in Section 5 that they are almost cube-free, and that they are obtained by using a tag-system but not by iterating a single morphism. This is a new example of a phenomenon first observed by Berstel [2] about the Arshon sequence.

2 Preliminaries

2.1 Definitions and notations

The terminology and notations are mainly those of Lothaire, 2002 [14].

Let A be a finite set called alphabet and A^{∗} the free monoid generated by A.

The elements of A are called letters and those of A^{∗} are called words. The empty word ε is the neutral element of A^{∗} for the concatenation of words (the concatenation of two words u and v is the word uv), and we denote by A^{+} the semigroup A^{∗} \ {ε}.

The length of a word u, denoted by |u|, is the number of occurrences of letters in u. In particular |ε| = 0. If n is a nonnegative integer, u^{n} is the word obtained by concatenating n occurrences of the word u. Of course, |u^{n}| = n × |u|. The cases n = 2, n = 3, and n = 4 deserve a particular attention in what follows. A word u^{2} (resp. u^{3}, u^{4}), with u ≠ ε, is called a square (resp. a cube, a 4-power).

A word w is called a factor (resp. a prefix, resp. a suffix) of u if there exist words x, y such that u = xwy (resp. u = wy, resp. u = xw). The factor (resp. the prefix, resp. the suffix) is proper if xy ≠ ε (resp. y ≠ ε, resp. x ≠ ε). A word u is a subsequence of the word v if there exist words u_{1}, …, u_{n}, v_{1}, …, v_{n}, v_{n+1} such that u = u_{1} ⋯ u_{n} and v = v_{1}u_{1}v_{2}u_{2} ⋯ v_{n}u_{n}v_{n+1}.

An infinite word (or sequence) over A is an application a : IN → A. It is written a = a_{0}a_{1} ⋯ a_{i} ⋯, i ∈ IN, a_{i} ∈ A.

The notion of factor is extended to infinite words as follows: a (finite) word u is a factor (resp. prefix) of an infinite word a over A if there exist n ∈ IN (resp. n = 0) and m ∈ IN (m = |u|) such that u = a_{n} ⋯ a_{n+m−1} (by convention a_{n} ⋯ a_{n−1} = ε).

In what follows, we will consider morphisms on A. Let B be an alphabet (often, B = A). A morphism on A (in short morphism) is an application f : A^{∗} → B^{∗} such that

f(uv) = f(u)f(v) for all u, v ∈ A^{∗}. It is uniquely determined by its value on the alphabet A. A morphism f on A is a literal morphism if |f(a)| = 1 for all a ∈ A.

Now, A = B. A morphism is nonerasing if f(a) ≠ ε for all a ∈ A. It is prolongable on x_{0}, x_{0} ∈ A^{+}, if there exists u ∈ A^{+} such that f(x_{0}) = x_{0}u. In this case, for all n ∈ IN the word f^{n}(x_{0}) is a proper prefix of the word f^{n+1}(x_{0}) and this defines a unique infinite word

x = x_{0}uf(u)f^{2}(u) ⋯ f^{n}(u) ⋯

which is the limit of the sequence (f^{n}(x_{0}))_{n≥0}. We write x = f^{ω}(x_{0}) and say that x is generated by f.

A (finite or infinite) word u over A is square-free (resp. cube-free, 4-power-free) if none of its factors is a square (resp. a cube, a 4-power). A morphism f on A is square-free if the word f(u) is square-free whenever u is a square-free word. The morphism f is weakly square-free if f generates a square-free infinite word.

A D0L-system is a triple G = (A, f, u) where A is an alphabet, f a morphism on A and u ∈ A^{∗}. An infinite word x is generated by G if x = (f^{k})^{ω}(u) for some k ∈ IN.

A tag-system is a quintuple T = (A, u, f, g, B) where A and B are alphabets, u ∈ A^{+}, f is a nonerasing morphism on A, prolongable on u, and g is a morphism from A onto B. An infinite word y is generated by G if y = g((f^{k})^{ω}(u)) for some k ∈ IN.

Remark that what we call here a tag-system is sometimes called a HD0L-system. The terminology of tag-system comes from the fundamental study of Cobham [8]. Chapter 5 of [17] is dedicated to a deep study of D0L-systems.

2.2 Ordered patterns

Let A be a totally ordered alphabet and let ℵ be the ordered alphabet whose letters are the first n positive integers in the usual order (thus ℵ = {1, 2, …, n}).

An ordered pattern is any word over ℵ ∪ {#} where # ∉ ℵ.

A word v over A contains an occurrence of the ordered pattern u (or, equivalently the ordered pattern u occurs in v) if, for some integer n ∈ IN, u = u_{1}#u_{2}# ⋯ #u_{n} (u_{i} ∈ ℵ^{∗}), v = w_{0}v_{1}w_{1}v_{2}w_{2} ⋯ w_{n−1}v_{n}w_{n} and there exists a literal morphism f : ℵ^{∗} → A^{∗} such that f(u_{i}) = v_{i}, 1 ≤ i ≤ n, and if x, y ∈ ℵ, x < y ⇒ f(x) < f(y). This means that the word v contains an occurrence of the ordered pattern u if v contains a subsequence v′ which is equal to f(u′) where u′ is obtained from u by deleting all the occurrences of #, with the additional condition that two adjacent letters in u must be adjacent in v.

A special case is when the ordered pattern u occurs at the beginning or at the end of the word v.

• If w_{0} = ε then we write v contains an occurrence of the ordered pattern [u.

• If w_{n} = ε then we write v contains an occurrence of the ordered pattern u].

• If w_{0} = w_{n} = ε then we write v contains an occurrence of the ordered pattern [u].

Example. Let A = {a, b, c, d, e, f} with a < b < c < d < e < f.

The word v = eafdbc contains one occurrence of the ordered pattern 2#31, namely the subsequence efd. In v, the ordered pattern 2#3#1 occurs in three occurrences: efd, efb, and efc; the ordered pattern 231 does not occur in v.

To end, the ordered pattern [3#1#2 occurs in v as ead, eab, eac, or ebc, the ordered pattern 3#1#2] occurs in v as eac, ebc, fbc, or dbc, and the ordered pattern [3#1#2] occurs in v as eac or ebc.

Of course, since # can correspond to anything, the ordered patterns u, #u, u#, and #u# are equal. In particular, if x is a word over ℵ, we will write (x#)^{ℓ} or (#x)^{ℓ} to represent the ordered pattern x#x# ⋯ #x containing l occurrences of the word x.

3 The Peano curve and the Peano words

Peano was the first in 1890 to realize the construction of a fractal curve that fills a square without hole. This construction is obtained by drawing, without pen-up, an infinite succession of unit lines left, right, up, or down. Thus this succession can be represented by an infinite word over the alphabet Σ = {u, ū, r, r̄} where u stands for up, ū stands for down, r stands for right, and r̄ stands for left (about description of pictures by words see the basic study of Maurer, Rozenberg and Welzl, 1982 [16]). The word so obtained, called the Peano infinite word, is denoted by P.

Let us describe the algorithm of Peano. The general idea is to divide, at step n, the unit square in 4^{n} equal subsquares each of them containing an equal length part of the curve (except the first and the last ones which contain a part of length 1/2). The curve so obtained is then depicted by a word of length 4^{n} − 1 which we will call the n-th Peano word P_{n}. When n tends to infinity the curve fills the unit square without hole and the sequence of words P_{n} tends to the Peano infinite word P (see Section 5).

Step by step, the algorithm is the following (let us recall that the drawing of the curves is realized without pen-up; in the following figures ∘ and respectively represent the starting and the ending points of the drawing).

• At step 1 the unit square is divided in 4 equal subsquares and it contains the staplelike curve depicted by the word P_{1} = urū.

• From step n to step n + 1 the curve and grid sizes are decreased by a factor two and four copies are put together to form a new square.

– The first copy is the left lower one, and it is obtained as follows: first realize a vertical flip, then rotate a quarter turn left.

[figure]

– The second and the third copies are the upper two ones: they are placed as they are.

– The fourth copy is the right lower one: first realize a vertical flip, then rotate a quarter turn right.

[figure]

This gives the following.

[figure]

Then, the curve is made continuous by connecting the ending point of the first (resp. the second, the third) copy to the starting point of the second (resp. the third, the fourth) one with three unit segments respectively corresponding to a move up (u), a move right (r), and a move down (ū) – the dashes lines in the following diagram.

[figure]

To end, all the starting and ending points are removed, except the starting point of the first copy and the ending point of the fourth copy.

For more about the construction of Peano see, for example, Gardner, 1989 [9], Gelbaum and Olmsted, 1964 [10], Mandelbrot, 1977 [15], Schwartz, 1967 [19].

Now, let us define on Σ three literal morphisms f, r_{g}, and r_{d} by

f(u) = ū, f(ū) = u, f(r) = r, f(r̄) = r̄,
r_{g}(u) = r̄, r_{g}(ū) = r, r_{g}(r) = u, r_{g}(r̄) = ū,
r_{d}(u) = r, r_{d}(ū) = r̄, r_{d}(r) = ū, r_{d}(r̄) = u.

These three morphisms respectively represent a vertical flip, a quarter turn left rotation, and a quarter turn right rotation.

¿From the construction we have that the Peano word P_{n+1} (which represents the drawing without pen-up of the Peano curve at step n + 1) is obtained from P_{n} as

P_{n+1} = ρ(P_{n}) u P_{n} r P_{n} ū λ(P_{n}),  (1)

where ρ = r_{g} ∘ f and λ = r_{d} ∘ f (ρ : u ↦ r ↦ u, ū ↦ r̄ ↦ ū; λ : u ↦ r̄ ↦ u, ū ↦ r ↦ ū).

One has P_{2} = rur̄ u urū r urū ū r̄ūr
and P_{3} = urūrrur̄urur̄r̄ūr̄u
u
rur̄uurūrurūūr̄ūr
r
rur̄uurūrurūūr̄ūr
ū
ūr̄ur̄r̄ūrūr̄ūrrurū

Now let w be a word over Σ. The word w̄ is obtained from w by replacing each occurrence of u, r, ū, r̄ respectively by ū, r̄, u, r (ε̄ = ε). It is clear that ρ and λ are the literal morphisms defined on Σ by

ρ(u) = r and, for any x ∈ Σ, ρ^{2}(x) = x and ρ(x̄) = \overline{ρ(x)}  (2)
λ(u) = r̄ and, for any x ∈ Σ, λ^{2}(x) = x and λ(x̄) = \overline{λ(x)}  (3)

Let g be the literal morphism defined on Σ by g(u) = g(ū) = u, g(r) = g(r̄) = r, and let us recall that if w is a word over Σ with w = w_{1} ⋯ w_{n}, w_{i} ∈ Σ, then w̃ = w_{n} ⋯ w_{1} (ε̃ = ε).

Together with the literal morphisms ρ, λ, f, and g, the Peano words P_{n} have the following straightforward properties.

Property 1 1. ρ ∘ λ = λ ∘ ρ.

2. For any w ∈ Σ^{∗}, λ(w) = \overline{ρ(w)}.

3. g ∘ ρ = g ∘ λ.

4. For any n ≥ 1,

• f(P_{n}) = P̃_{n},

• g(P_{n}) = g(P̃_{n}) = g̃(P_{n}),

• ρ(P_{n}) = f(λ̃(P_{n})).

5. For any n ≥ 1, the peano word P_{n} is irreducible, that is, it does not contain any factor uū, ūu, rr̄, nor r̄r.

4 Counting occurrences of ordered patterns in the Peano words

In this section, the alphabet Σ is ordered by u < r < ū < r̄.

¿From the construction it is easy to see that, for any positive integer n, |P_{n}| = 4^{n} − 1.

Moreover, we have the following more precise counting of each letter in P_{n}.

Lemma 2 For any n ∈ IN \ {0}, one has |P_{n}|_{u} = |P_{n}|ū = 4^{n−1}, |P_{n}|_{r} = 4^{n−1} + 2^{n−1} − 1, |P_{n}|r̄ = 4^{n−1} − 2^{n−1}.

Proof. The result is obvious for n = 1.

¿From (1) we get, for x ∈ Σ,

|P_{n+1}|_{x} = 2|P_{n}|_{x} + |ρ(P_{n})|_{x} + |λ(P_{n})|_{x} + \{ \begin{matrix}1, & if x = u, r, ū \\ 0, & if x = r̄. \end{matrix}

Then, by the definition of ρ and λ, we obtain

\begin{aligned}|P_{n+1}|_{u} & = & 2|P_{n}|_{u} + |P_{n}|_{r} + |P_{n}|r̄ + 1 \\ |P_{n+1}|ū & = & 2|P_{n}|ū + |P_{n}|r̄ + |P_{n}|_{r} + 1 \\ |P_{n+1}|_{r} & = & 2|P_{n}|_{r} + |P_{n}|_{u} + |P_{n}|ū + 1 \\ |P_{n+1}|r̄ & = & 2|P_{n}|r̄ + |P_{n}|ū + |P_{n}|_{u} \end{aligned}

and the result follows by induction. As an immediate corollary one has the following.

Corollary 3 For any n ≥ 1,

• |g(P_{n})|_{u} = |g(P_{n})|_{r} + 1;

• |g(ρ(P_{n}))|_{u} = |g(λ(P_{n}))|_{u} = |g(ρ(P_{n}))|_{r} − 1 = |g(λ(P_{n}))|_{r} − 1.

In the rest of this section, our purpose is to find the number of occurrences of some ordered patterns in P_{n}. We start with another direct corollary of Lemma 2.

Corollary 4 For any n, l ∈ IN \ {0}, the number of occurrences of the ordered pattern (1#)^{ℓ} in P_{n} is equal to

\binom{4^{n−1} − 2^{n−1}}{ℓ} + 2\binom{4^{n−1}}{ℓ} + \binom{4^{n−1} + 2^{n−1} − 1}{ℓ}.

Proof. Let x ∈ Σ. The number of occurrences of a subsequence x^{ℓ} in P_{n} is obviously given by \binom{|P_{n}|_{x}}{ℓ}. The rest then follows from Lemma 2.

Before continuing, we establish a fundamental general result.

Let R(v) (resp. D(v)) denote the number of occurrences of the ordered pattern 12 (resp. 21), that is the number of rises (resp. descents), in a word v over Σ. Of course these notions depend on the order between the letters, not on geometrical considerations. Here, for example, rū is a rise when ru is a descent!

Proposition 5 Let x_{2}, …, x_{k} be non-empty words over {u, r}, y_{1}, …, y_{k−1} non-empty words over {ū, r̄}, x_{1} a word over {u, r}, and y_{k} a word over {ū, r̄} (maybe x_{1} = ε, or y_{k} = ε, or both).

Let w = x_{1}y_{1}x_{2}y_{2} ⋯ x_{k}y_{k}, then

R(ρ(w)) = \{ \begin{matrix}D(w) − 1, & if x_{1} = y_{k} = ε \\ D(w) + 1, & if x_{1} ≠ ε and y_{k} ≠ ε \\ D(w), & otherwise \end{matrix}

D(ρ(w)) = \{ \begin{matrix}R(w) + 1, & if x_{1} = y_{k} = ε \\ R(w) − 1, & if x_{1} ≠ ε and y_{k} ≠ ε \\ R(w), & otherwise \end{matrix}

R(λ(w)) = D(w) and D(λ(w)) = R(w).

Proof. Let x_{1}, …, x_{k}, y_{1}, …, y_{k} and w be as in the statement.

Clearly D(w) = [∑_{i=1}^{k} D(x_{i}) + D(y_{i})] + k − 1

and R(w) = [∑_{i=1}^{k} R(x_{i}) + R(y_{i})] + \{ \begin{matrix}k − 2, & if x_{1} = y_{k} = ε \\ k − 1, & if x_{1} = ε, y_{k} ≠ ε or if x_{1} ≠ ε, y_{k} = ε \\ k, & if x_{1} ≠ ε and y_{k} ≠ ε. \end{matrix}

Since ρ is the literal morphism which exchanges u and r on the one hand, ū and r̄ on the other hand, one has ρ(w) = x′_{1}y′_{1}x′_{2}y′_{2} ⋯ x′_{k}y′_{k} where x′_{1}, …, x′_{k} are words over {u, r} with |x′_{i}| = |x_{i}|, y′_{1}, …, y′_{k} are words over {ū, r̄} with |y′_{i}| = |y_{i}| and, for 1 ≤ i ≤ k, R(x′_{i}) = D(x_{i}), D(x′_{i}) = R(x_{i}), R(y′_{i}) = D(y_{i}), and D(y′_{i}) = R(y_{i}). Thus

R(ρ(w)) = [∑_{i=1}^{k} R(x′_{i}) + R(y′_{i})] + \{ \begin{matrix}k − 2, & if x′_{1} = y′_{k} = ε \\ k − 1, & if x′_{1} = ε, y′_{k} ≠ ε or if x′_{1} ≠ ε, y′_{k} = ε \\ k, & if x′_{1} ≠ ε and y′_{k} ≠ ε. \end{matrix}

= [∑_{i=1}^{k} D(x_{i}) + D(y_{i})] + \{ \begin{matrix}k − 2, & if x_{1} = y_{k} = ε \\ k − 1, & if x_{1} = ε, y_{k} ≠ ε or if x_{1} ≠ ε, y_{k} = ε \\ k, & if x_{1} ≠ ε and y_{k} ≠ ε. \end{matrix}

This implies R(ρ(w)) = \{ \begin{matrix}D(w) − 1, & if x_{1} = y_{k} = ε \\ D(w) + 1, & if x_{1} ≠ ε and y_{k} ≠ ε \\ D(w), & otherwise \end{matrix}

Since λ is the literal morphism which inverts the order of the letters, it is obvious that λ transforms each rise in a descent and vice-versa. Thus R(λ(w)) = D(w).

The computation of D(ρ(w)) and D(λ(w)) is immediate from what precedes because ρ ∘ ρ and λ ∘ λ are both the identity morphism.

An important corollary of this proposition is the following theorem which gives the number of rises and descents in the Peano words.

Theorem 6 For any k ∈ IN,

R(P_{2k+1}) = \frac{2}{5}(4 · 16^{k} + 1),
R(P_{2k+2}) = \frac{2}{5}(16^{k+1} − 1),
D(P_{2k+1}) = \frac{8}{5}(16^{k} − 1),
D(P_{2k+2}) = \frac{2}{5}(16^{k+1} − 1).

(One can remark here that if n is an even integer then the Peano word P_{n} contains the same number of rises and descents.)

Proof. The word P_{1} = urū contains two rises and no descent.

The word P_{2} = rur̄uurūrurūūr̄ūr contains six rises and six descents.

Thus the relations are verified when k = 0.

Now, from (1), (2), (3), we have that

P_{2k} starts and ends with r,
ρ(P_{2k}) starts and ends with u,
λ(P_{2k}) starts and ends with ū,
P_{2k+1} starts with u and ends with ū,
ρ(P_{2k+1}) starts with r and ends with r̄,
λ(P_{2k+1}) starts with r̄ and ends with r.

Thus

R(P_{2k+1}) = R(ρ(P_{2k})1P_{2k}2P_{2k}3λ(P_{2k}))
= R(ρ(P_{2k})) + 1 + R(P_{2k}) + R(P_{2k}) + 1 + R(λ(P_{2k}))
R(P_{2k+2}) = R(ρ(P_{2k+1})1P_{2k+1}2P_{2k+1}3λ(P_{2k+1}))
= R(ρ(P_{2k+1})) + R(P_{2k+1}) + R(P_{2k+1}) + 1 + R(λ(P_{2k+1}))
D(P_{2k+1}) = D(ρ(P_{2k})1P_{2k}2P_{2k}3λ(P_{2k}))
= D(ρ(P_{2k})) + D(P_{2k}) + D(P_{2k}) + D(λ(P_{2k}))
D(P_{2k+2}) = D(ρ(P_{2k+1})1P_{2k+1}2P_{2k+1}3λ(P_{2k+1}))
= D(ρ(P_{2k+1})) + 1 + D(P_{2k+1}) + 1 + 1 + D(P_{2k+1}) + D(λ(P_{2k+1}))

and, using Proposition 5, the result follows by induction.

Another consequence of Proposition 5 is that we can count the number of occurrences of a lot of ordered pattern in P_{n}.

Let N_{τ} (W) denote the number of occurrences of the pattern τ in the word W.

Using the previous results, we can count, for P_{n}, the number of occurrences of the patterns τ_{1}(x, y) = [x(#y)^{ℓ}, τ_{2}(x, y) = (x#)^{ℓ}y] and τ_{3}(x, y, z) = [x(#y)^{ℓ}#z], where x, y, z ∈ {1, 2, 3}.

If we consider, for instance, the pattern τ_{1}(1, 2) = [1(#2)^{ℓ} then the letter 1 in this pattern must correspond to the leftmost letter of the word P_{n}. Now if n = 2k + 1 then from the proof of Theorem 6 P_{n} = uW for some word W, which means that to the sequence (#2)^{ℓ} there can correspond any subsequence (#i)^{ℓ} in P_{n}, where i = r, ū, r̄. Thus, using Lemma 2 and the way we prove Corollary 4, there are \binom{4^{2k}−2^{2k}}{ℓ} + \binom{4^{2k}}{ℓ} + \binom{4^{2k}+2^{2k}−1}{ℓ} occurrences of the pattern τ_{1}(1, 2) in P_{2k+1}. If n = 2k +2 then P_{n} = rW for some word W and for the sequence (#2)^{ℓ} there corresponds any subsequence (#i)^{ℓ} in P_{n}, where i = ū, r̄. Thus, N_{τ_{1}(1,2)}(P_{2k+2}) = \binom{4^{2k}−2^{2k}}{ℓ} + \binom{4^{2k}}{ℓ}.

In the example above, as well as in the following considerations, we assume ℓ to be greater than 0. If ℓ = 0 then obviously N_{τ_{1}(x,y)}(P_{n}) = N_{τ_{2}(x,y)}(P_{n}) = 1, whereas N_{τ_{3}(x,y,z)}(P_{n}) is equal to 1 if x < z and n = 2k + 1, or x = z and n = 2k + 2, and it is equal to 0 otherwise.

When we consider τ_{3}(x, y, z)(P_{n}), we observe that since P_{2k+2} = rW r for some W, N_{τ_{3}(x,y,z)}(P_{2k+2}) = 0, whenever x ≠ z. Also, since P_{2k+1} = uW ū for some W, N_{τ_{3}(x,y,z)}(P_{2k+1}) = 0, whenever x ≥ z.

Let us consider the pattern τ_{3}(2, 1, 3) = [2(#1)^{ℓ}#3]. As it was mentioned before, N_{τ_{3}(2,1,3)}(P_{2k+2}) = 0. But, if we consider P_{2k+1} = uW ū, then it is easy to see that N_{τ_{3}(2,1,3)}(P_{2k+1}) = 0, since the leftmost letter of P_{2k+1} is the least letter, which means that it cannot correspond to the letter 2 in the pattern. As one more example, we can consider the pattern τ_{3}(1, 1, 2) = [1(#1)^{ℓ}#2]. We are only interested in case P_{n} = P_{2k+1}, since N_{τ_{3}(1,1,2)}(P_{2k+2}) = 0. The number of occurrences of the pattern is obviously given by the number of ways to choose ℓ letters among 4^{2k} − 1 letters u (totally, there are 4^{2k} letters u according to Lemma 2, but we cannot consider the leftmost u since it corresponds to the leftmost 1 in the pattern). Thus, N_{τ_{3}(1,1,2)}(P_{2k+1}) = \binom{4^{2k}−1}{ℓ}.

All the other cases of x, y, z in the patterns τ_{1}(x, y), τ_{2}(x, y) and τ_{3}(x, y, z) can be considered in the same way. Let S_{1} and S_{2} denote the following:

S_{1} = \binom{4^{2k} − 2^{2k}}{ℓ} + \binom{4^{2k}}{ℓ} + \binom{4^{2k} + 2^{2k} − 1}{ℓ}, S_{2} = \binom{4^{2k+1}}{ℓ} + \binom{4^{2k+1} − 2^{2k+1}}{ℓ}.

The tables below give all the results concerning the patterns under consideration, except those triples (x, y, z), for which N_{τ_{3}(x,y,z)}(P_{n}) = 0 for all n.

\begin{matrix}x & y & N_{τ_{1}(x,y)}(P_{2k+1}) & N_{τ_{2}(x,y)}(P_{2k+1}) & N_{τ_{1}(x,y)}(P_{2k+2}) & N_{τ_{2}(x,y)}(P_{2k+2}) \\ 1 & 1 & \binom{4^{2k}−1}{ℓ} & \binom{4^{2k}−1}{ℓ} & \binom{4^{2k+1}+2^{2k+1}−1}{ℓ} & \binom{4^{2k+1}+2^{2k+1}−1}{ℓ} \\ 1 & 2 & S_{1} & \binom{4^{2k}}{ℓ} + \binom{4^{2k}+2^{2k}−1}{ℓ} & S_{2} & \binom{4^{2k+1}}{ℓ} \\ 2 & 1 & 0 & \binom{4^{2k}−2^{2k}}{ℓ} & \binom{4^{2k+1}}{ℓ} & S_{2} \end{matrix}

\begin{matrix}x & y & z & N_{τ_{3}(x,y,z)}(P_{2k+1}) & N_{τ_{3}(x,y,z)}(P_{2k+2}) \\ 1 & 1 & 1 & 0 & \binom{4^{2k+1}−2}{ℓ} \\ 1 & 1 & 2 & \binom{4^{2k}−1}{ℓ} & 0 \\ 1 & 2 & 1 & 0 & S_{2} \\ 1 & 2 & 2 & \binom{4^{2k}−1}{ℓ} & 0 \\ 2 & 1 & 2 & 0 & \binom{4^{2k+1}}{ℓ} \\ 1 & 2 & 3 & \binom{4^{2k}+2^{2k}−1}{ℓ} & 0 \\ 1 & 3 & 2 & \binom{4^{2k}−2^{2k}}{ℓ} & 0 \end{matrix}

5 Generating the Peano infinite word

Preliminary remark. The sequence (P_{n})_{n≥1} has two limits according n is even or odd. An equivalent construction (equivalent in the sense that it provides a curve drawn without pen-up and filling the unit square without hole) can be obtained with no distinction between the even case and the odd one: it is enough at each even step, before computing the corresponding Peano word, to apply to the whole picture a vertical flip followed by a quarter turn left rotation and then each P_{n} is a prefix of P_{n+1}. But the limit for the odd indices is the same in the two cases so, because the properties of the Peano words P_{n} are more interesting with our first construction, we keep the definition of the Peano words P_{n} given in Section 3 and define the Peano infinite word P as the limit of odd rank Peano words, that is, P = lim_{n→∞} P_{2n+1}.

In this section, we will prove that the Peano infinite word P is generated by a tagsystem, it contains no cube except those of only one letter, and it cannot be generated by a single morphism (it is even not generated by a D0L-system).

Let Ω be the eight-letter alphabet Ω = {A, B, C, D, a, b, c, d}, and let γ and h be the following morphisms.

\begin{matrix}γ : Ω^{∗} & → & Ω^{∗} & h : Ω^{∗} & → & Σ^{∗} \\ A & ↦ & BaAbAcD & A & ↦ & urū \\ B & ↦ & AbBaBdC & B & ↦ & rur̄ \\ C & ↦ & DcCdCaB & C & ↦ & ūr̄u \\ D & ↦ & CdDcDbA & D & ↦ & r̄ūr \\ a & ↦ & a & a & ↦ & u \\ b & ↦ & b & b & ↦ & r \\ c & ↦ & c & c & ↦ & ū \\ d & ↦ & d & d & ↦ & r̄ \end{matrix}

Theorem 7 P is the infinite word generated by the tag-system (Ω, A, γ^{2}, h, Σ), i.e., P = h((γ^{2})^{ω}(A)).

The proof of this result will use the following lemma.

Lemma 8 For any n ∈ IN,

• h(γ^{n}(A)) = ρ(h(γ^{n}(B))) = λ(h(γ^{n}(D))),

• h(γ^{n}(B)) = ρ(h(γ^{n}(A))) = λ(h(γ^{n}(C))),

• h(γ^{n}(C)) = ρ(h(γ^{n}(D))) = λ(h(γ^{n}(B))),

• h(γ^{n}(D)) = ρ(h(γ^{n}(C))) = λ(h(γ^{n}(A))).

Proof. The eight equalities are obviously true if n = 0.

Now, let us prove for any integer n ≥ 0 that if the eight equalities are true for n then they are also true for n + 1. One has

h(γ^{n+1}(A)) = h(γ^{n}(BaAbAcD))
= h(γ^{n}(B))h(a)h(γ^{n}(A))h(b)h(γ^{n}(A))h(c)h(γ^{n}(D))
= ρ(h(γ^{n}(A)))uh(γ^{n}(A))rh(γ^{n}(A))ūλ(h(γ^{n}(A))) (by induction)
= ρ(h(γ^{n}(A)))ρ(r)h(γ^{n}(A))ρ(u)h(γ^{n}(A))ρ(r̄)λ(h(γ^{n}(A)))

= ρ(h(γ^{n}(A)))ρ(h(b))ρ(h(γ^{n}(B)))ρ(h(a))ρ(h(γ^{n}(B)))ρ(h(d))ρ(h(γ^{n}(C)))

= ρ(h(γ^{n}(AbBaBdC)))
= ρ(h(γ^{n+1}(B))).

This proves the first equality. The seven others are verified in the same way.

Proof of Theorem 7. We will prove by induction that, for any n ∈ IN, P_{n+1} = h(γ^{n}(A)). The result follows because P = lim_{n→∞} P_{2n+1} = lim_{n→∞} h(γ^{2n}(A)).

The equality is of course true if n = 0 since P_{1} = urū = h(A). Now,

P_{n+2} = ρ(P_{n+1})uP_{n+1}rP_{n+1}ūλ(P_{n+1})
= ρ(h(γ^{n}(A)))h(a)h(γ^{n}(A))h(b)h(γ^{n}(A))h(c)λ(h(γ^{n}(A))) (by induction)

= h(γ^{n}(B))h(γ^{n}(a))h(γ^{n}(A))h(γ^{n}(b))h(γ^{n}(A))h(γ^{n}(c))h(γ^{n}(D)) (Lemma 8)

= h(γ^{n}(BaAbAcD))
= h(γ^{n+1}(A)).

Now, to prove that the Peano infinite word P contains no cube except x^{3}, x ∈ Σ, we need an intermediate lemma. First remark that the morphism γ is clearly not a square-free morphism (for example, γ(CA) contains BB as a factor). It is even not weakly square-free (it does not generate a square-free word because, for example, γ^{4}(A) contains bAbAb as a factor). But we have the following.

Lemma 9 For any n ∈ IN, γ^{n}(A) does not contain any factor Y wY wY with Y ∈ {A, B, C, D} and w ∈ Ω^{∗}.

Proof. The property is straightforward if n = 0 or n = 1.

Let us suppose by way of contradiction that, for some integer n ≥ 2, γ^{n}(A) contains a factor Y wY wY, Y ∈ {A, B, C, D}, w ∈ Ω^{∗}, when γ^{n−1}(A) does not contain any such factor. Moreover, let us suppose that Y = A (the three other cases are symmetrical by definition of γ).

Let u, v ∈ Ω^{∗} be such that γ^{n}(A) = uAwAwAv. By definition of γ, four cases are possible for u: u = γ(w_{1}), u = γ(w_{1})Ba, u =

γ(w_{1})BaAb, or u = γ(w_{1})CdDcDb, for some prefix w_{1} of γ^{n−1}(A).

Before continuing, we remark that γ^{n}(A) is an alternation of lower-case letters and upper-case letters.

1. u = γ(w_{1})

In this case, the first occurrence of A following u is necessarily the first letter of γ(B). This implies that Aw starts with γ(B) = AbBaBdC and, since this last factor can only appear, in γ^{n}(A), as an occurrence of γ(B), it follows that the second occurrence of Aw also starts with γ(B), that is, there exists W′ ∈ Ω^{∗} such that AwAw = γ(BW′BW′) and γ^{n−1}(A) starts with w_{1}BW′BW′. But since AwAw is followed, in γ^{n}(A), by the letter A, the next letter in γ^{n−1}(A) is a B, which implies that γ^{n−1}(A) contains BW′BW′B as a factor, a contradiction.

2. u = γ(w_{1})Ba

In this case, the first occurrence of A after u is followed by bAcD. This implies that Aw starts with AbAcD and, since this last factor can only appear, in γ^{n}(A), in an occurrence of γ(A), it follows that Aw = AbAcDγ(W′)Ba for some W′ ∈ Ω^{∗} where AbAcD and Ba are respectively the suffix and the prefix of γ(A). This means γ^{n−1}(A) starts with w_{1}AW′AW′A, a contradiction.

3. u = γ(w_{1})BaAb

In this case, the first occurrence of A after u is followed by cD. This implies that Aw starts with AcD. Here two cases are possible.

Either w ends with BaAb and, as in the previous case, γ^{n−1}(A) contains a factor AW′AW′A, a contradiction.

Or this factor AcD is the central part of some γ(DcC). But in this case AcD is followed, in Aw, by cCdCaB and, since γ^{n}(A) starts with uAw, this factor cCdCaB should be the beginning of some γ(W′) in γ^{n}(A). This is impossible.

4. u = γ(w_{1})CdDcDb

In this case, the first occurrence of A after u is the last letter of γ(D) and w starts in the same manner as some γ(W′).

Let us consider the letter A at the beginning of the second occurrence of Aw.

• It is impossible that this A is the first letter of γ(B) because γ(W′) (and thus w) cannot start with bBaBdC.

• It is impossible that this A is the first A in γ(A) because γ(W′) (and thus w) cannot start with bAcD.

• It is impossible that this A is the second A in γ(A). Indeed otherwise w starts with cD and since w starts in the same manner as some γ(W′), w starts with cDcCdCaB. But this would imply that CdCaB is the beginning of some γ(Z) which is impossible.

• Thus this A is again the last letter of γ(D). This is also the case for the last A of AwAwA, which implies that γ^{n−1}(A) starts with w_{1}DW′DW′D, a contradiction.

Now, we are ready to prove the main result of this section.

Theorem 10 The infinite word P does not contain any factor xyW xyW xy with x, y letters and W a word. In particular, the only cubes in P are x^{3} with x a letter. Moreover, P is 4-power-free.

Proof. We first suppose that P does not contain any factor xyW xyW xy with x, y letters and W a word. Then if P contains a cube X, one has necessarily X = x^{3} where x is a letter. That P effectively contains all the cubes x^{3} for x ∈ Σ, and also that it contains no factor x^{4}, comes from the following. A factor u^{3} (resp. r^{3}, ū^{3}, r̄^{3}) can only be found in h(CaA) (resp. h(DbB), h(AcC), h(BdD)); a factor CaA (resp. DbB, AcC, BdD) can only be found as the central part of γ(BaB) (resp. γ(AbA), γ(DcD), γ(CdC)); finally BaB (resp. AbA, DcD, CdC) is the central factor of γ(B) (resp. γ(A), γ(D), γ(C)).

Since γ^{2}(A) contains A, B, C, and D, γ^{3}(A) contains BaB, AbA, DcD, and CdC, thus γ^{4}(A) contains CaA, DbB, AcC, and BdD, that is, P_{5} contains u^{3}, r^{3}, ū^{3}, and r̄^{3}.

It is interesting to remark here that, starting from the index 0, we find in the infinite word P the first occurrence of r^{3} (resp. u^{3}, r̄^{3}, ū^{3}) at the index 30 (resp. 94, 222, 478).

Now, we prove the first part of the theorem.

Suppose that P contains a factor xyW xyW xy with x, y letters and W a word, and let T be such that T xyW xyW xy is a prefix of P, i.e., T xyW xyW xy is a prefix of h(γ^{2n}(A)) for some n ∈ IN.

There are four possible cases depending on the value of |T | mod 4.

• If |T | mod 4 = 0 then x is the first letter of h(X) for some X ∈ {A, B, C, D}. We suppose X = A (the other cases are symmetrical).

Then x = u, y = r and W starts with ū: W = ūW′. By definition of h and γ, the factor urū can only appear, in P, as h(A). This implies that there exists a word w′ ∈ Ω^{∗} such that T xyW xyW xy = T h(Aw′Aw′)ur. But, by construction, w′ ends with a lower-case letter thus, in γ^{2n}(A), Aw′Aw′ is followed by an upper-case letter. Since the image of this letter by h starts with ur, this letter is necessarily A. Thus γ^{2n}(A) contains Aw′Aw′A, a contradiction with Lemma 9.

• If |T | mod 4 = 1 then x is the second letter of h(X), X ∈ {A, B, C, D}, y is the third letter of h(X), and W ends with the first letter of h(X). As in the previous case, we obtain a contradiction with Lemma 9.

• If |T | mod 4 = 2 then x is the third letter of h(X), X ∈ {A, B, C, D}. We suppose X = A which implies x = ū. Since, in γ^{2n}(A), A is necessarily followed by b or c, we have y = r or y = ū.

First suppose |W x| mod 4 ≠ 3. Then if y = r the only possibility is |W | mod 4 = 1 (that is, after T the second occurrence of xy = ūr is at the end of h(D)) and if y = ū the only possibility is |W | mod 4 = 3 (that is, after T the second occurrence of xy = ūū is such that x is the image by h of a lower-case letter and y is the beginning of the image of an upper-case letter.) In the two cases |T xyW xyW | mod 4 = 0 which implies that the third occurrence of xy is the beginning of some h(Y) with Y ∈ {A, B, C, D} : this is impossible because xy = ūr or xy = ūū.

Thus |W x| mod 4 = 3 which implies that W x ends with the image by h of an uppercase letter. Since x = ū this letter is A and, as previously, we obtain that γ^{2n}(A) contains Aw′Aw′A for some word w′ ∈ Ω^{∗}, a contradiction with Lemma 9.

• If |T | mod 4 = 3 then x is the image by h of a lower-case letter. Then y is the first letter of h(X) for some X ∈ {A, B, C, D}. This implies that T xyW xyW xy is a prefix of T xh(X)W′xh(X)W′xh(X) where W′ is the word such that yW = h(X)W′. Again, this means that γ^{2n}(A) contains Xw′Xw′X, a contradiction with Lemma 9.

A direct corollary is the following.

Corollary 11 The infinite word P cannot be generated by a D0L-system.

Proof. If P was generated by a D0L-system (f, Σ, v) then P = f^{n}(P) for some n ∈ IN\{0}. Consequently f(u^{3}), f(r^{3}), f(ū^{3}), and f(r̄^{3}) are factors of P. Since P does not contain any cube except u^{3}, r^{3}, ū^{3}, and r̄^{3}, this implies that |f(x)| ≤ 1 for any x ∈ Σ. A contradiction because, to generate an infinite word, f must be prolongable on at least one letter.

6 Aknowledgment

The authors thank Gwénaël Richomme for suggesting valuable improvments on a preliminary version of this paper.

References

[1] E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp.

[2] J. Berstel, Mots sans carré et morphismes itérés, Discrete Math. 29 (1980), 235– 244.

[3] A. Burstein, Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.

[4] A. Burstein, T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electronic J. of Combinatorics 9:2 (2002), #R3.

[5] A. Burstein, T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals of Combinatorics 7 (2003), 1–14.

[6] A. Burstein, T. Mansour, Counting occurrences of some subword patterns, Discrete Mathematics and Theoretical Computer Science 6:1 (2003), 1–12.

[7] A. Claesson, Generalised Pattern Avoidance, European J. Combin. 22 no. 7 (2001), 961–971.

[8] A. Cobham, Uniform tag sequences, Math. Systems Th. 6 (1972), 164–192.

[9] M. Gardner, Penrose Tiles to Trapdoor Ciphers, W.H. Freeman and Co, NY, 1989.

[10] B. Gelbaum, J. Olmsted, Counterexamples in Analysis, Holden-day, San Francisco, London, Amsterdam, 1964.

[11] S. Kitaev, T. Mansour, Counting the occurrences of generalized patterns in words generated by a morphism, 2003, preprint math.CO/0210170.

[12] D. E. Knuth, The Art of Computer Programming, 2nd ed., Addison-Wesley, Reading, MA, 1973.

[13] M. Lothaire, Combinatorics on Words, vol. 17 of Encyclopedia of Mathematics and Applications, Addison-Wesley, Reading, Mass., 1983. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK, 1997.

[14] M. Lothaire, Algebraic Combinatorics on Words, vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, UK, 2002.

[15] B. Mandelbrot, The Fractal Geometry of Nature, W.H. Freeman and Co, NY, 1977.

[16] H. A. Maurer, G. Rozenberg, E. Welzl, Using String Languages to Describe Picture Languages, Inform. and Control 54 (1982), 155–185.

[17] G. Rozenberg, A. Salomaa (Eds), Handbook of Formal Languages Vol. 1, Springer, 1997.

[18] A. Salomaa, Jewels of Formal Language Theory, Computer Science Press, 1981.

[19] L. Schwartz, Analyse Mathématique I, Hermann, 1967.

[20] R. Simion, F. Schmidt, Restricted permutations, European J. Combin. 6 no. 4 (1985), 383–406.