CANONICAL POSITIONS FOR THE FACTORS

IN THE PAPERFOLDING SEQUENCES

Jean-Paul ALLOUCHE and Mireille BOUSQUET-MÉLOU

C. N. R. S. U. R. A. 0226 and U. R. A. 1304 CeReMaB and LaBRI Mathématiques et Informatique 351, cours de la Libération F-33405 TALENCE Cedex FRANCE

Abstract. It has been proved by the first author that the number of factors of length k in any paperfolding sequence is equal to 4k once k ≥ 7. We prove here that for every integer k, there exists a set of integers P_{k} of cardinality 4k for k ≥ 7 such that the factors of length k of any paperfolding sequence are exactly the factors beginning at the places indexed by the integers in P_{k}: this gives a “bijective” proof of the result mentioned above. Then we give an explicit uniform linear upper bound for the recurrence function of the paperfolding sequences. Finally we study the set of all factors of all paperfolding sequences, evaluating their number for a given length, and studying the language of these words.

1. Introduction

A factor of length k of an infinite sequence u = (u(n))_{n≥1} with values in the set A, is a word on A occurring as u(n)u(n + 1) ⋯ u(n + k − 1) for some index n.

The study of the factors of infinite sequences was initiated by Thue ([33], [34]). This is now a classical part of combinatorics on words, which is used in theoretical computer science, number theory, symbolic dynamics, group theory, physics ⋯

One of the questions in this field is the computation of the complexity function P_{u} of a sequence u: P_{u}(k) is defined as the number of factors of length k in the sequence u. This function can be a very simple one: the complexity of a periodic sequence is ultimately constant (moreover the condition P_{u}(n) ≤ n for a single integer n implies that the sequence u is ultimately periodic, see [15] for instance), Sturmian sequences can be defined as sequences having a complexity function satisfying P_{u}(n) = n + 1 for every n ≥ 1, (see [25] and [26], see also [15]), (2n + 1)-sequences have been studied by Arnoux and Rauzy [9] and (2n)-sequences have been studied by Rote [29]. The generalization of Sturmian

Typeset by AMS-TEX

A.M.S. Math. Subject Classification 68R15, 68Q45, 05A99, 11B83

sequences to the multidimensional case has been treated by Arnoux, Mauduit, Tamura and Shiokawa (see [8]). On the other hand the complexity of sequences generated by finite automata (see [14], see also [32]) satisfies P_{u}(n) = O(n). The case of the celebrated Thue-Morse sequence has been studied in [12] and [21], its complexity function P is given (for m ≥ 3) by:

P (m) = \{ \begin{matrix}6.2^{r−1} + 4p, if 0 < p ≤ 2^{r−1}, \\ 8.2^{r−1} + 2p, if 2^{r−1} < p ≤ 2^{r}, \end{matrix}

where r and p are uniquely determined by the equation m = 2^{r} + p + 1, 0 < p ≤ 2^{r}.

For another example (the generalized Rudin-Shapiro sequences introduced in [5]) one can read [7], and for general automatic sequences one can read [32].

In [3] the first author studied the case of the paperfolding sequences. These sequences are obtained by repeatedly folding a piece of paper, according to an arbitrary sequence of folding instructions (see [16], [11] and [22]; a more precise definition will be given below) and their complexities have the surprising properties:

- the complexity function is the same for all paperfolding sequences,

- this complexity function has the very simple form P_{u}(k) = 4k, ∀k ≥ 7.

The method in [3] uses the definition of paperfolding sequences as Toeplitz sequences (see below). Once the result is known, it is very appealing to search for a “bijective” proof, indeed to find a bijection between the sets of factors of given length for, say, the regular paperfolding sequence and any other paperfolding sequence, then to deduce the general case from the easy case of the regular paperfolding sequence (this sequence is 2-automatic, and hence its complexity function can be obtained by standard techniques).

In this paper we give something which resembles the desired bijection, but the method gives also the complexity function, without even studying directly the case of the regular paperfolding. More precisely we construct a family (P_{k}) of subsets of ℕ, such that:

* Card P_{k} = 4k

* the factors of length k of any paperfolding sequence beginning at the indices in P_{k} are all its factors of length k, (in particular, they occur exactly once if k ≥ 7).

This property can be seen as a “synchronization” of the factors of the paperfolding sequences.

In the second part of this paper we prove that there exists a uniform linear bound for the recurrence functions of all the paperfolding sequences: any factor of length ≥ 44k of a paperfolding sequence contains all the factors of length k of this sequence.

The last part of the paper is devoted to the study of the language of all the factors of all the paperfolding sequences.

2. Some definitions and notations

A recursive definition of paperfolding sequences is: the sequence (u(n))_{n≥1} is a paperfolding sequence if and only if

u(4n + 1) = 0 (resp. 1), ∀n ≥ 0,
u(4n + 3) = 1 (resp. 0), ∀n ≥ 0,
(u(2n))_{n≥1} is a paperfolding sequence.

Note that our paperfolding sequences are indexed by ℕ^{∗} = {1, 2, ⋯ }, which is slightly different from the definition in [3], where they are indexed by ℕ = {0, 1, 2, ⋯ }.

An alternative way of obtaining these sequences is to view them as Toeplitz sequences (see [19]; a general survey of Toeplitz sequences can be found in [4]). Given an infinite binary sequence f = (f(n))_{n≥0} (sequence of “folding instructions”), one defines the paperfolding sequence u_{f} = (u_{f}(n))_{n≥1} with folding instructions f by successively “filling holes”: (we use the notation \overline{x} = 1 − x)

- first step, one writes down the sequence (f(0)\overline{f(0)})^{∞} at the odd places, which gives

f(0) • \overline{f(0)} • f(0) • \overline{f(0)} • f(0) • \overline{f(0)} • ⋯

- second step, one writes down the sequence (f(1)\overline{f(1)})^{∞} at the odd holes, which gives

f(0) f(1) \overline{f(0)} • f(0) \overline{f(1)} \overline{f(0)} • f(0) f(1) \overline{f(0)} • ⋯

and so on. The limit obtained after an infinite number of steps is the sequence u_{f}.

In particular if f is the constant sequence (0), one obtains the regular paperfolding sequence, wich begins by

0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 ⋯

One can also notice that changing 0’s in 1’s and 1’s in 0’s in a paperfolding sequence gives another paperfolding sequence. The following lemma will be useful:

Lemma.

If u_{f} = (u_{f}(n))_{n≥1} is the paperfolding sequence associated with the folding instructions f, then

∀m, j ≥ 0, u_{f}(2^{m}(2j + 1)) = j + f(m) (mod 2)

Proof.

This is easily done by induction on m.

In what follows we will make use of the following notations: let u = (u(n))_{n≥1} be a sequence taking its values in a finite set (alphabet). For k ≥ 1, we define

- the set of factors of u of length k, F_{u}(k) = {u(n)u(n + 1) ⋯ u(n + k − 1); n ≥ 1}, and the complexity of u, p_{u}(k) = Card F_{u}(k),

- the set of o-factors of u of length k, F_{u}^{o}(k) = {u(2n+1)u(2n+2) ⋯ u(2n+k); n ≥ 0}, and the odd complexity of u, p_{u}^{o}(k) = Card F_{u}^{o}(k),

- the set of e-factors of u of length k, F_{u}^{e}(k) = {u(2n)u(2n + 1) ⋯ u(2n + k − 1); n ≥ 1}, and the even complexity of u, p_{u}^{e}(k) = Card F_{u}^{e}(k). Moreover if X is a subset of ℕ and a and b two integers, we denote by aX + b the set {an + b, n ∈ X}.

3. The main theorem

We can now, using the above notations, state a first theorem:

Theorem 1.

Let P_{k}^{o} and P_{k}^{e} be two families of subsets of ℕ defined, for k ≥ 1, by: P_{1}^{o} ⊂ 2ℕ + 1, P_{1}^{e} ⊂ 2ℕ^{∗}, Card P_{1}^{o} = Card P_{1}^{e} = 2, for any paperfolding sequence u, Card {u(n); n ∈ P_{1}^{o}} = Card {u(n); n ∈ P_{1}^{e}} = 2, ∀k ≥ 1, P_{2k}^{o} = 2(P_{k}^{o} ∪ P_{k}^{e}) − 1 and P_{2k}^{e} = 2(P_{k}^{o} ∪ P_{k}^{e}), ∀k ≥ 1, P_{2k+1}^{o} = 2(P_{k}^{o} ∪ P_{k}^{e}) − 1 and P_{2k+1}^{e} = 2(P_{k+1}^{o} ∪ P_{k+1}^{e}).

Then, for all k ≥ 1, for all α ∈ {o, e}, and for any paperfolding sequence u, one has: Card P_{k}^{α} = p_{u}^{α}(k), Card {u(n)u(n + 1) ⋯ u(n + k − 1), n ∈ P_{k}^{α}} = p_{u}^{α}(k).

As a consequence, taking for instance P_{1}^{o} = {1, 3} and P_{1}^{e} = {2, 6}, and checking that, for any paperfolding sequence u, p_{u}^{o}(1) = p_{u}^{e}(1) = 2, one has for any paperfolding sequence u, and any integer k ≥ 1:

\begin{aligned}p_{u}^{o}(2k) & = 4k, \\ p_{u}^{e}(2k) & = 4k, \\ p_{u}^{o}(2k + 1) & = 4k, \\ p_{u}^{e}(2k + 1) & = 4(k + 1). \end{aligned}

Proof.

We prove this result by induction on k:

- for k = 1, there is nothing to prove. For the forthcoming choice of the sets P_{1}^{o} and P_{1}^{e}, one checks that for any paperfolding sequence u, one has \{u(1), u(3)\} = \{f(0), \overline{f(0)}\} = \{0, 1\}, and \{u(2), u(6)\} = \{f(1), \overline{f(1)}\} = \{0, 1\}, hence p_{u}^{o}(1) = 2, p_{u}^{e}(1) = 2, and P_{1}^{o} = {1, 3} and P_{1}^{e} = {2, 6} satisfy the desired properties.

Note that one can choose any four integers α, β, γ, δ and define P_{1}^{o} = {4α + 1, 4β + 3} and P_{1}^{e} = {8γ + 2, 8δ + 6}. This gives actually all possible sets P_{1}^{o} and P_{1}^{e}.

- let us suppose that we proved the result for every j < 2k, where k ≥ 1 and let us prove it for 2k and 2k + 1: given a paperfolding sequence u_{f} with folding instructions f, and an integer n ≥ 0, the factor

u_{f}(2n + 1)u_{f}(2n + 2) ⋯ u_{f}(2n + 2k)

is equal to

((n+f(0)) mod 2)u_{Sf}(n+1)((n+1+f(0)) mod 2) ⋯ ((n+k−1+f(0)) mod 2)u_{Sf}(n+k),

where the sequence Sf is the shifted sequence (Sf(n))_{n≥0} = (f(n))_{n≥1}.

Hence an element of F_{u}^{o}(2k) occurring in u at the index 2n + 1 is obtained

- either by writing the prefix of length k of the word (f(0)\overline{f(0)})^{k} at its odd places, and a word of the set F_{u_{Sf}}^{o} (k) at the even places, (if n is even),

- or by writing the prefix of length k of the word (\overline{f(0)}f(0))^{k} at its odd places, and a word of the set F_{u_{Sf}}^{e} (k) at the even places, (if n is odd).

As these two types of elements are different, (the first letter being either f(0) or \overline{f(0)}), one deduces that:

p_{u_{f}}^{o} (2k) = p_{u_{Sf}}^{o} (k) + p_{u_{Sf}}^{e} (k),

and that the set P_{2k}^{o} = 2(P_{k}^{o} ∪ P_{k}^{e}) − 1 has the desired properties, (of course P_{k}^{o} ∩ P_{k}^{e} is empty).

In exactly the same way one looks then at:

- the factors u_{f}(2n)u_{f}(2n+1) ⋯ u_{f}(2n+2k−1), which gives p_{u_{f}}^{e} (2k) = p_{u_{Sf}}^{e} (k)+p_{u_{Sf}}^{o} (k) and P_{2k}^{e} = 2(P_{k}^{e} ∪ P_{k}^{o}),

- the factors u_{f}(2n+1)u_{f}(2n+2) ⋯ u_{f}(2n+2k+1), which gives p_{u_{f}}^{o} (2k+1) = p_{u_{Sf}}^{e} (k)+ p_{u_{Sf}}^{o} (k) and P_{2k+1}^{o} = 2(P_{k}^{e} ∪ P_{k}^{o}) − 1,

- the factors u_{f}(2n)u_{f}(2n + 1) ⋯ u_{f}(2n + 2k), which gives p_{u_{f}}^{e} (2k + 1) = p_{u_{Sf}}^{o} (k + 1) + p_{u_{Sf}}^{e} (k + 1) and P_{2k+1}^{e} = 2(P_{k+1}^{o} ∪ P_{k+1}^{e}).

Now, before proving our main theorem, we need a lemma. We state a more general result than needed here, as we will use it later on (note that the case u = v in the lemma below has already been proved in [3]).

Lemma.

Let u_{f} and u_{g} be two paperfolding sequences, (with folding instructions f and g), and let F_{u_{f}}^{o} (k) and F_{u_{g}}^{e}(k) be defined as above, then

∀k ≥ 7, F_{u_{f}}^{o} (k) ∩ F_{u_{g}}^{e}(k) = ∅.

Proof.

Suppose for instance that

u_{f}(2m + 1)u_{f}(2m + 2) ⋯ u_{f}(2m + k) = u_{g}(2n)u_{g}(2n + 1) ⋯ u_{g}(2n + k − 1),

then this can be written

((m + f(0)) mod 2)u_{Sf}(m + 1) ⋯ = u_{Sg}(n)((n + g(0)) mod 2) ⋯,

hence, putting a = ((m + f(0)) mod 2):

u_{Sg}(n)u_{Sg}(n + 1) ⋯ u_{Sg}(n + ⌊\frac{k + 1}{2}⌋ − 1) = a\overline{a}a\overline{a} ⋯,

this factor is of length ⌊\frac{k+1}{2}⌋ ≥ 4, hence it suffices to prove that no factor a\overline{a}a\overline{a} can occur in a paperfolding sequence u_{g}. But this is clear, as for any paperfolding sequence u_{g}, and any integer n, one has u_{g}(2n + 1) = (n + g(0)) mod 2, which implies that u_{g}(2n − 1) and u_{g}(2n + 1) are always different.

We can now prove our main theorem:

Theorem 2.

Define a family of subsets of ℕ by:

P_{1} = P_{1}^{o} ∪P_{1}^{e}, where the sets P_{1}^{o} and P_{1}^{e} satisfy the conditions of theorem 1 (for instance one can take P_{1} = {1, 2, 3, 6}),

∀k ≥ 1, P_{2k} = (2P_{k} − 1) ∪ 2P_{k} and P_{2k+1} = (2P_{k} − 1) ∪ 2P_{k+1}.

Let u be a paperfolding sequence. We recall that p_{u}(k) is the number of factors of length k in the sequence u.

Then:

∀k ≥ 1, Card P_{k} = 4k,

∀k ≥ 7, Card {u(n)u(n + 1) ⋯ u(n + k − 1), n ∈ P_{k}} = p_{u}(k) = 4k.

Proof.

The proof is an easy consequence of Theorem 1 and of the lemma above, (notice that P_{k} = P_{k}^{e} ∪ P_{k}^{o} and that this union is disjoint as P_{k}^{e} is included in 2ℕ and P_{k}^{o} is included in 2ℕ + 1).

Remarks:

- Theorem 2 above says how one can find the different factors of a paperfolding sequence. Moreover, as the positions we give are universal (independent of the paperfolding sequence one considers), they can be seen as a sort of “synchronization”. Note that Theorem 1 says the same thing about o-factors and e-factors.

- what is the “best” choice for P_{1}? One wants the elements in the P_{k}’s to be small: defining for any integer k ≥ 1 the quantities M_{k} = max P_{k}, m_{k} = min P_{k}, and H(k) as the element in ℤ such that 2^{H(k)} < k ≤ 2^{H(k)+1}, one can prove

M_{k} = 2^{H(k)+1}M_{1},

m_{k} = 2^{H(k+1)}(m_{1} − 1) + 1.

As all possible choices for P_{1} are the sets {4α + 1, 4β + 3, 8γ + 2, 8δ + 6} with α, β, γ and δ four integers (see the proof of Theorem 1), the minimal value of M_{k} is obtained for (and only for) P_{1} = {1, 2, 3, 6} and P_{1} = {2, 3, 5, 6}. The first choice gives rather simple sets P_{k} (see below). The other choice gives actually the minimal value of the diameters M_{k} − m_{k} and will be used in Section 5.

4. Some more properties of the sets P_{k}

We give here some equivalent definitions - or properties - of the sets P_{k}, in the case where P_{1} = {1, 2, 3, 6}.

1) Let us first recall the definition:

P_{1} = {1, 2, 3, 6},

∀k ≥ 1, P_{2k} = (2P_{k} − 1) ∪ 2P_{k} and P_{2k+1} = (2P_{k} − 1) ∪ 2P_{k+1}.

2) An explicit expression for P_{k}:

P_{1} = {1, 2, 3, 6}:

For k ≥ 2, P_{k} is the union of the following five intervals (in increasing order):

\begin{matrix}P_{k} = [1 & , 3.2^{H(k)}] ∪ [5.2^{H(k)} − k + 1, 4.2^{H(k)}] ∪ [6.2^{H(k)} − k + 1, 6.2^{H(k)}] \\ ∪ [12.2^{H(k)} − k + 1, 11.2^{H(k)}] ∪ [13.2^{H(k)} − k + 1, 12.2^{H(k)}], \end{matrix}

where H(k) is the element of ℤ defined by 2^{H(k)} < k ≤ 2^{H(k)+1}.

These five intervals are disjoint (some of them being possibly reduced to a single point) if k is not a power of 2, and this union can be written as the union of two disjoint intervals when k = 2^{m}:

P_{2^{m}} = [1, 3.2^{m}] ∪ [5.2^{m} + 1, 6.2^{m}].

The proof is easily done by induction.

Remark:

an unexpected consequence of this explicit expression of the P_{k}’s is that, defining z(k) as z(k) = 3.2^{H(k)} if k is not a power of 2, and z(2^{m}) = 3.2^{m}, then, for k ≥ 7, the first z(k) factors of length k of any paperfolding sequence are different.

What is the best way to compute the sets P_{k}? One can use the formula above, one can also construct P_{k} step by step by computing P_{k} from P_{k+1}, which is pretty easy, as shown below. A last possibility will be given in 4).

3) How to deduce P_{k+1} from P_{k}?

- It is easy to deduce from the recursive definition of the set P_{k}, that for every k ≥ 1, one has P_{k} ⊂ P_{k+1}.

- Putting A_{k} = P_{k+1} \ P_{k}, one checks easily that ∀k ≥ 1, one has A_{2k} = 2A_{k} and A_{2k+1} = 2A_{k} − 1. This allows us to compute quickly the P_{k}’s, one obtains:

P_{1} =[1, 3] ∪ {6},
P_{2} =[1, 6] ∪ [11, 12],
P_{3} =[1, 6] ∪ {8} ∪ [10, 12] ∪ {22} ∪ {24},
P_{4} =[1, 12] ∪ [21, 24],
P_{5} =[1, 12] ∪ {16} ∪ [20, 24] ∪ {44} ∪ {48},
P_{6} =[1, 12] ∪ [15, 16] ∪ [19, 24] ∪ [43, 44] ∪ [47, 48],
P_{7} =[1, 12] ∪ [14, 16] ∪ [18, 24] ∪ [42, 44] ∪ [46, 48],
P_{8} =[1, 24] ∪ [41, 48],
P_{9} =[1, 24] ∪ {32} ∪ [40, 48] ∪ {88} ∪ {96},

4) Generating the sets P_{k} by finite automata:

as one might suspect from the very definition of the sets P_{k}, it is possible to construct them with a (bidimensional) 2-automaton. A 2-automaton is essentially a “machine” which constructs the n^{th} term of a sequence from the binary expansion of n, (see the survey [2] for the 1-dimensional case, and see [30] and [31] for the multidimensional case). The following result can be used to compute the sets P_{k}, but it has also a theoretical interest.

Proposition.

Let (f_{k}(n))_{n} (k ≥ 1, n ≥ 1) be the characteristic function of the set P_{k}, defined by f_{k}(n) = 1 if n ∈ P_{k}, and f_{k}(n) = 0 otherwise. Then the double sequence (f_{k}(n))_{k,n} is 2-automatic.

Proof.

Define as above A_{k} = P_{k+1} \P_{k} for k ≥ 1, and A_{0} = P_{1}, and let χ_{k} be the characteristic function of the set A_{k}. As the A_{k}’s are pairwise disjoint, (the P_{k}’s form an increasing sequence of sets), and as P_{k} = ∪_{0≤j≤k−1}A_{j}, one has:

f_{k}(n) = ∑_{0≤j≤k−1} χ_{j}(n) = ∑_{0≤j≤k−1} χ_{j}(n) mod 2.

It is easy to check that the double sequence (f_{k}(n))_{k,n} is 2-automatic if and only if the double sequence (χ_{k}(n))_{k,n} is 2-automatic. Now as A_{k} is included in ℕ^{∗}, we define a new family of subsets of ℕ by:

A′_{k} = A_{k} − 1.

Let χ′_{k} be the characteristic function of the set A′_{k}, hence χ′_{k}(n) = χ_{k}(n + 1), and it is sufficient to prove that the double sequence (χ′_{k}(n))_{k,n} is 2-automatic.

To show that a double sequence (a(k, n))_{k,n} with values in {0, 1} is 2-automatic, one has to prove (see [30]) that there exists a finite set of sequences S included in {0, 1}^{ℕ^{2}} such that

- the sequence (a(k, n)_{k,n}) belongs to S,

- for every sequence (x(k, n))_{k,n} belonging to S, the four sequences (x(2k, 2n))_{k,n}, (x(2k + 1, 2n))_{k,n}, (x(2k, 2n + 1))_{k,n} and (x(2k + 1, 2n + 1))_{k,n} belong also to S.

But the equalities

∀k ≥ 1, A_{2k} = 2A_{k} and A_{2k+1} = 2A_{k} − 1

imply

∀k ≥ 1, A′_{2k} = 2A′_{k} + 1 and A′_{2k+1} = 2A′_{k},

which gives

χ′_{2k}(2n) = 0, χ′_{2k}(2n + 1) = χ′_{k}(n), χ′_{2k+1}(2n) = χ′_{k}(n), χ_{2k+1}(2n + 1) = 0,

and this permits to construct a set S as above, indeed S = {χ′, 0}.

5. Recurrence function for paperfolding sequences

Let us recall (see [25] and [26]) that an infinite sequence u is said minimal if, for every integer n ≥ 1, there exists an integer r such that every factor of u of length r contains all the factors of u of length n. The smallest such r is denoted by R_{u}(n), and the map R_{u} is called the recurrence function of the sequence u.

Note that R_{u}(n) ≥ p_{u}(n) + n − 1 and that the recurrence function of a non-periodic minimal word satisfies R_{u}(n) ≥ 2n for every n in ℕ^{∗} where the constant 2 is optimal. For the study of the recurrence function of infinite sequences generated by morphisms, one can read [27].

In what follows, we shall prove that the paperfolding sequences are minimal, and give an explicit uniform linear upper bound for their recurrence functions.

We begin with a proposition:

Proposition.

Let [a, b] be an interval of ℕ such that, for every paperfolding sequence u, the factor u(a)u(a + 1) ⋯ u(b) contains all the factors of u of length k for a given k. Define the integer m by 2^{m} ≤ b < 2^{m+1}.

Then every factor of length greater than or equal to b − a + 2^{m+2} of a paperfolding sequence contains all its factors of length k.

Proof.

Let u = u_{f} be a paperfolding sequence with sequence of instructions f:

∀i, j ≥ 0, u(2^{i}(2j + 1)) = f(i) + j mod 2.

For any r ≥ 0, one has

u(2^{i}(2j + 1) + r2^{i+2}) = u(2^{i}(2(j + 2r) + 1))
= f(i) + (j + 2r) mod 2
= f(i) + j mod 2
= u(2^{i}(2j + 1)).

Let i ≥ 0. Any n < 2^{i+1} can be written as 2^{p}(2j + 1) for some j, p with p ≤ i. Hence, for n < 2^{i+1}, one has:

∀r ≥ 0 u(n) = u(n + r2^{i+2}).

Now, if m is the smallest integer i for which b < 2^{i+1}, one has:

∀r ≥ 0 u(a)u(a + 1) ⋯ u(b) = u(a + r2^{m+2})u(a + 1 + r2^{m+2}) ⋯ u(b + r2^{m+2}).

Hence, every factor u(a + r2^{m+2}) ⋯ u(b + r2^{m+2}) contains all the factors of u of length k. Now, denote by I_{r} the interval of integers [a + r2^{m+2}, b + r2^{m+2}]. These intervals all have the same length independent of r, and the distance between I_{r} and I_{r+1} is also independent of r. Moreover one has: b − a + 2^{m+2} ≥ 2b > b. Hence every interval of integers of length greater than or equal to (max I_{r+1} − min I_{r}) = b − a + 2^{m+2} contains at least one of the intervals I_{r}, which concludes the proof of the proposition.

Theorem 3.

Let H(k) be defined, for k ≥ 1, by 2^{H(k)} < k ≤ 2^{H(k)+1}. Then the recurrence function of any paperfolding sequence u satisfies:

∀k ≥ 1, R_{u}(k) ≤ 44.2^{H(k)} − 2^{H(k+1)} + k − 2.

In particular, one has for any paperfolding sequence u and any k ≥ 1:

R_{u}(k) < 44k.

Proof.

Following the second remark after Theorem 2 one takes P_{1} = {2, 3, 5, 6}. Then max P_{k} = 12.2^{H(k)} and min P_{k} = 2^{H(k+1)} + 1.

Hence, taking a = 2^{H(k+1)} + 1 and b = 12.2^{H(k)} + k − 1 and noticing that the smallest i for which b < 2^{i+1} is m = H(k) + 3, one can apply the proposition above, which gives:

R_{u}(k) ≤ 44.2^{H(k)} − 2^{H(k+1)} + k − 2.

To get the bound 44k, it is sufficient to notice that H is increasing. Hence:

R_{u}(k) ≤ 43.2^{H(k)} + k − 2 < 44k.

6. The paperfolding words

In this chapter we shall address the question of studying all paperfolding words (i.e. all factors of all paperfolding sequences). This question arises in particular from the corresponding question for the Sturmian words: the definition of an infinite Sturmian sequence has been recalled in the introduction, a (finite) word is called Sturmian if it is a factor of a Sturmian sequence. These words have been studied by Dulucq and Gouyou-Beauchamps [17] and by Mignosi [24] (see also the paper of Berstel and Pocchiola [10]). The number of Sturmian words of length k is equal to

1 + ∑_{i=1}^{k}(k − i + 1)φ(i),

where φ is the Euler function, and the set of all the Sturmian words is a non-context-free language, whose complement is ambiguous context-free.

We shall give here the number of paperfolding words of given length, prove that their language is not context-free (note that a slightly different proof has been given recently by Lehr [20]). We have been unable yet to prove (or disprove!) that the complement of this language is context-free, but we shall give a proof that its generating function is transcendental (hence if this complement is context-free, it is ambiguous context-free).

In what follows we shall denote by W(k) the set of all paperfolding words of length k, by W^{o}(k) the set of all paperfolding words of length k starting at an odd position in a paperfolding sequence, and by W^{e}(k) the set of all paperfolding words of length k starting at an even position in a paperfolding sequence, in other words:

W^{o}(k) = {u(2n + 1) ⋯ u(2n + k); n ≥ 0; u paperfolding sequence}, W^{e}(k) = {u(2n) ⋯ u(2n + k − 1); n ≥ 1; u paperfolding sequence}, W(k) = {u(n) ⋯ u(n + k − 1); n ≥ 1; u paperfolding sequence} = W^{o}(k) ∪ W^{e}(k). We also define: h^{o}(k) = Card W^{o}(k), h^{e}(k) = Card W^{e}(k), h(k) = Card W(k). Our first tool is a lemma partially proved above:

Lemma.

For k ≥ 7, one has W^{o}(k) ∩ W^{e}(k) = ∅, hence for k ≥ 7, one has h(k) = h^{o}(k) + h^{e}(k). Moreover:

W^{o}(1) ∩ W^{e}(1) = W^{o}(1) = W^{e}(1) = W(1) = {0, 1}, W^{o}(2) ∩ W^{e}(2) = W^{o}(2) = W^{e}(2) = W(2) = {00, 01, 10, 11}, W^{o}(3) ∩ W^{e}(3) = W^{o}(3) = {001, 011, 100, 110}, W^{o}(4) ∩ W^{e}(4) = {0011, 0110, 1001, 1100}, W^{o}(5) ∩ W^{e}(5) = {00110, 01100, 10011, 11001}, W^{o}(6) ∩ W^{e}(6) = {001100, 011001, 100110, 110011}.

Hence:

h(1) = h^{o}(1) = h^{e}(1) = 2, and

for 2 ≤ k ≤ 6, one has: h(k) = h^{o}(k) + h^{e}(k) − 4.

Proof.

The first claim has been proved in the lemma given in Paragraph 3, the second assertion is straightforward (by inspection, but it can also be deduced from the proof of the next proposition).

Proposition.

The functions h, h^{o} and h^{e} defined above satisfy: h(1) = h^{o}(1) = h^{e}(1) = 2, ∀k ≥ 1 h^{o}(2k) = h^{e}(2k) = h^{o}(2k + 1) = 2h(k), ∀k ≥ 1 h^{e}(2k + 1) = 2h(k + 1).

Proof.

The first assertion is trivial. Then, by definition:

h^{o}(2k) = Card W^{o}(2k) = Card {u(2n+1) ⋯ u(2n+2k); n ≥ 0; u paperfolding sequence}.

But, if f is the sequence of folding instructions of the paperfolding sequence u, the word

u(2n + 1) ⋯ u(2n + 2k)

is equal to the word

((n + f(0)) mod 2)u′(n + 1)((n + 1 + f(0)) mod 2)u′(n + 2) ⋯ u′(n + k),

where u′ is the paperfolding sequence associated with the sequence of folding instructions Sf. Hence, such a factor is obtained either by writing the prefix of length k of the word (01)^{k} at its odd places and a factor of the set W(k) at the even places, or by writing the prefix of length k of the word (10)^{k} at the odd places and a factor of the set W(k) at the even places. Hence h^{o}(2k) = 2h(k).

The other relations are proved in the same way.

We can now compute the values of h:

Theorem 4.

∗ the function h satisfies:

∀k ≥ 4, h(2k) = 4h(k),

∀k ≥ 3, h(2k + 1) = 2(h(k) + h(k + 1)).

∗ one has the “explicit” values:

h(1) = 2, h(2) = 4, h(3) = 8,

and, for k ≥ 4,

h(k) = 2^{m+1}k − 5.4^{m−1} if  2^{m} ≤ k ≤ 2^{m} + 2^{m−1},
h(k) = 3.2^{m}k − 11.4^{m−1} if  2^{m} +2^{m−1} ≤ k ≤ 2^{m} + 2^{m−1} + 2^{m−2},
h(k) = 2^{m+1}k − 4^{m}  if 2^{m}+2^{m−1}+2^{m−2} ≤ k ≤ 2^{m+1}.

Proof.

To prove the first assertion one uses the lemma and the proposition above. The second assertion is proved using the first assertion and computing by hand the first few values of h.

Remarks:

- one deduces easily from the above explicit values that ∀k ≥ 1, \frac{3}{4}k^{2} ≤ h(k) ≤ k^{2},

- writing down explicit values for the functions h^{o} and h^{e} is straightforward using the proposition above,

- the relations given in the first part of Theorem 4 prove that the sequence h is 2-regular in the sense of [6].

Let us now study the language L = ∪_{k≥0}W(k) of all paperfolding words.

Theorem 5.

The language L = ∪_{k≥0}W(k) of all paperfolding words is not context-free (this result has also been proved by Lehr, see [20]).

The generating series of L (and hence the generating series of {0, 1}^{∗} \ L) is a transcendental function.

Remark:

the last assertion implies that, if the language {0, 1}^{∗} \ L is context-free, then it is ambiguous context-free. By analogy with the language of Sturmian words one could imagine that this language is indeed context-free, but we did not succeed in proving (or disproving!) this property.

Proof of the Theorem.

We use the pumping lemma for context-free languages (see [18] for instance): if L were context-free, then, for every sufficiently long word z in L, there would exist a factorization z = uvwxy, with vx ≠ ε, (where ε is the empty word), such that ∀k ≥ 1, uv^{k}wx^{k}y ∈ L. Hence the set of all paperfolding words would contain arbitrarily large powers (notice that a factor of a paperfolding word is still a paperfolding word).

But it has been proved in [1] that any factor of a paperfolding sequence of the form z^{2} satisfies length(z) ≤ 5, hence a factor of a paperfolding sequence cannot be of the form w^{a} for an integer a ≥ 12, (if w^{a} is a paperfolding word, with a ≥ 12, then w^{12} = (w^{6})^{2} is a paperfolding word, with length(w^{6}) ≥ 6), which gives the desired contradiction.

Let us now study the generating function of L, say F (X) = ∑_{k=1}^{∞} h(k)X^{k}. Using Theorem 4, one has:

\begin{aligned}F (X) & = ∑_{k=1}^{6} h(k)X^{k} + ∑_{k=3}^{∞} h(2k + 1)X^{2k+1} + ∑_{k=4}^{∞} h(2k)X^{2k} \\ & = ∑_{k=1}^{6} h(k)X^{k} + 2 ∑_{k=3}^{∞}(h(k) + h(k + 1))X^{2k+1} + 4 ∑_{k=4}^{∞} h(k)X^{2k} \end{aligned}

This can also be written as

XF (X) = 2(X + 1)^{2}F (X^{2}) − 2X^{2}(1 + 2X + 2X^{2} + 2X^{3} + 2X^{4} + 2X^{5}).

As F is a power series with radius of convergence equal to 1 and with integral coefficients, the Polya-Carlson theorem ensures that F is either a rational function or a transcendental function with the unit circle as natural boundary (see [28] for instance).

If F were rational, say F = \frac{A}{B}, where A and B are two coprime polynomials in ℤ[X], one would have:

(∗) XA(X)B(X^{2}) = 2(X + 1)^{2}A(X^{2})B(X) − 2X^{2}(1 + 2X + 2X^{2} + 2X^{3} + 2X^{4} + 2X^{5})B(X)B(X^{2}).

Let a = deg(A) and b = deg(B), then

deg(XA(X)B(X^{2})) = 2b + a + 1,

deg(2(X + 1)^{2}A(X^{2})B(X)) = 2 + 2a + b,

deg(2X^{2}B(X)B(X^{2})(1 + 2X + 2X^{2} + 2X^{3} + 2X^{4} + 2X^{5})) = 3b + 7.

One first notices that 2 + 2a + b ≠ 3b + 7 (otherwise 2(a − b) = 5, which is impossible). Then:

- if 2 + 2a + b > 3b + 7, which can be written 2a > 2b + 5, hence 2a ≥ 2b + 6, i.e. a ≥ b + 3, then the relation (∗) implies

2b + a + 1 = 2 + 2a + b, hence b = a + 1,

which contradicts a ≥ b + 3

- if 2 + 2a + b < 3b + 7, which can be written 2a < 2b + 5, hence 2a ≤ 2b + 4, i.e. a ≤ b + 2, then the relation (∗) implies

2b + a + 1 = 3b + 7, hence a = b + 6,

which contradicts a ≤ b + 2.

Finally F cannot be rational, hence it is a transcendental function.

Remark:

let L be a language such that every factor of a word of L is also in L. Now consider the following properties that L may have:

i) there exists a constant C such that if z^{2} is a word of L, then length(z) ≤ C; ii) there exists an integer k such that for every word w ≠ ε, w^{k} ∉ L; iii) for every word w ≠ ε there exists an integer k = k(w) such that w^{k} ∉ L; It is clear that i) ⟹ ii) ⟹ iii). To apply the pumping lemma for context-free

languages to L, it is sufficient to prove one of the above properties. In the case of the language L studied above, we used ii) (itself stated as a consequence of i)) in a first version of this paper. Then we found the recent paper of Lehr [20] whose proof uses iii), but we decided to keep our proof as it gives a more precise property of the paperfolding words.

Final remark: in a paper in preparation the authors address similar questions for the generalized Rudin-Shapiro sequences in the sense of [23], the main tool being the correspondence between the factors of the paperfolding sequences and the factors of the generalized Rudin-Shapiro sequences which has been used in [3]. Let us recall that for any paperfolding sequence u = (u(n))_{n≥1} the sequence v = (v(n))_{n≥0} defined by

∀n ≥ 0, v(n) = ∑_{i=1}^{n} u(i) mod 2

is a generalized Rudin-Shapiro sequence in the sense of [23].

References

[1] J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux (1983–1984), 20-01–20-11, Exposé 20.

[2] J.-P. Allouche, Automates finis en théorie des nombres, Expo. Math. 5 (1987), 239–266.

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

[4] J.-P. Allouche and R. Bacher, Toeplitz sequences, paperfolding, Hanoi towers and progression-free sequences of integers, Ens. Math. 38 (1992), 315–327.

[5] J.-P. Allouche and P. Liardet, Generalized Rudin-Shapiro sequences, Acta Arith. 60 (1) (1991), 1–27.

[6] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theor. Comp. Sci. 98 (1992), 163–187.

[7] J.-P. Allouche and J. Shallit, Suites à complexité ultimement affine, Congrès “Thémate”, Luminy (1991), to appear.

[8] P. Arnoux, C. Mauduit, I. Shiokawa and J. Tamura, Complexity of sequences defined by billiards in the cube, Preprint.

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

[10] J. Berstel and M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words, Prépublication Liens 92–21 (1992).

[11] A. Blanchard and M. Mendès France, Symétrie et transcendance, Bull. Sci. Math. 106 (1982), 325–335.

[12] S. Brlek, Enumeration of factors in the Thue-Morse word, Discr. Appl. Math. 24 (1989), 83–96.

[13] G. Christol, T. Kamae, M. Mendès France and G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401–419.

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

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

[16] M. Dekking, M. Mendès France and A. van der Poorten, FOLDS!, Math. Intell. 4 (1982), 130–138, 173–181; 190–195..

[17] S. Dulucq and D. Gouyou-Beauchamp, Sur les facteurs des suites de Sturm, Theor. Comp. Sci. 71 (1990), 381–400.

[18] J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.

[19] K. Jacobs and M. Keane, 0-1-sequences of Toeplitz type, Z. Wahrsch. verw. Geb. 13 (1969), 123–131.

[20] S. Lehr, A result about languages concerning paperfolding sequences, Math. Systems Theory 25 (1992), 309–313.

[21] A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence, Theor. Comput. Sci. 63 (1989), 333–348.

[22] M. Mendès France and A. J. van der Poorten, Arithmetic and analytic properties of paperfolding sequences (dedicated to K. Mahler), Bull. Austr. Math. Soc. 24 (1981), 123–131.

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

[24] F. Mignosi, Sturmian words and ambiguous context-free languages, Internat. J. Found. Comp. Sci. 1 (3) (1990), 309–323.

[25] M. Morse and G. A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), 815–866.

[26] M. Morse and G. A. Hedlund, Symbolic Dynamics, II, Sturmian trajectories, Amer. J. Math. Soc. 62 (1940), 1–42.

[27] J. Mouline, Contribution à l’étude de la complexité des suites substitutives, Thèse, Université de Provence, 1990.

[28] G. Polya, Collected papers, Vol. 1, Singularities of analytic functions, R. P. Boas ed., the M. I. T. Press, Cambridge 1974.

[29] G. Rote, Sequences with subword complexity 2n, Preprint.

[30] O. Salon, Suites automatiques à multi-indices, Séminaire de Théorie des Nombres de Bordeaux (1986– 1987), 4-01–4-27, followed by an appendix of J. Shallit.

[31] O. Salon, Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris t. 305, Sér. I (1987), 501–504.

[32] T. Tapsoba, Complexité de suites automatiques, Thèse de troisième cycle, Université d’Aix-Marseille II (1987).

[33] A. Thue, Über unendliche Zeichenreihen, Norske vid. Selsk. Skr., I. Mat. Nat. Kl., Christiana 7 (1906), 1–22.

[34] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr., I. Mat. Nat. Kl., Christiana 1 (1912), 1–67.