The Formal Inverse of the Period-Doubling Sequence

Narad Rampersad^{1} Department of Mathematics and Statistics University of Winnipeg 515 Portage Avenue Winnipeg, Manitoba R3B 2E9 Canada

               n.rampersad@uwinnipeg.ca

Manon Stipulanti^{2} Département de Mathématique University of Liège Allée de la Découverte 12 (B37) 4000 Liège Belgium

                m.stipulanti@uliege.be

Abstract

If p is a prime number, consider a p-automatic sequence (u_{n})_{n≥0}, and let U(X) = ∑_{n≥0} u_{n}X^{n} ∈ 𝔽_{p}[[X]] be its generating function. Assume that there exists a formal power series V (X) = ∑_{n≥0} v_{n}X^{n} ∈ 𝔽_{p}[[X]] which is the compositional inverse of U, i.e., U(V (X)) = X = V (U(X)). The problem investigated in this paper is to study the properties of the sequence (v_{n})_{n≥0}. The work was first initiated for the Thue-Morse sequence, and more recently the case of other sequences (variations of the Baum-Sweet sequence, variations of the Rudin-Shapiro sequence and generalized Thue-Morse sequences) has been treated. In this paper, we deal with the case of the period-doubling sequence. We first show that the sequence of indices at which the period-doubling sequence takes the value 0 (resp., 1) is not k-regular for any k ≥ 2. Secondly, we give recurrence relations for its formal inverse, then we show that it is 2-automatic, and we also provide an automaton that generates it. Thirdly, we study the sequence of indices at which this formal inverse takes the value 1, and we show that it is not k-regular for any k ≥ 2 by connecting it to the characteristic sequence of Fibonacci numbers. We leave as an open problem the case of the sequence of indices at which this formal inverse takes the value 0.

1The author is supported by NSERC Discovery Grant 418646-2012.

2The author is supported by FRIA Grant 1.E030.16.

1 Introduction

Let us consider the following problem. Let p be a prime number. Let u = (u_{n})_{n≥0} be a p-automatic sequence and let U(X) = ∑_{n≥0} u_{n}X^{n} ∈ 𝔽_{p}[[X]] be its generating function. Assume that there exists a formal power series V (X) = ∑_{n≥0} v_{n}X^{n} ∈ 𝔽_{p}[[X]] which is the compositional inverse of U, i.e., U(V (X)) = X = V (U(X)). What can be said about properties of the sequence v = (v_{n})_{n≥0}?

Gawron and Ulas [9] initiated work on this problem, and they consider the case where u = t is the well-known Prouhet-Thue-Morse sequence. More precisely, they studied the sequence c = (c_{n})_{n≥0}, which is the sequence of coefficients of the compositional inverse of the generating function of the sequence t. They called this sequence c the inverse Prouhet-Thue-Morse sequence. The 2-automaticity of c is easily deduced using Christol’s theorem [5], but they also exhibited some recurrence relations satisfied by c and provided an automaton that generates c. They studied two increasing sequences a = (a_{n})_{n≥0} and d = (d_{n})_{n≥0} respectively defined by

{a_{n} | n ∈ ℕ} = {m ∈ ℕ | c_{m} = 1},

and

{d_{n} | n ∈ ℕ} = {m ∈ ℕ | c_{m} = 0}.

In particular, they proved that a is 2-regular, but that d is not k-regular for any k ≥ 2.

More recently, this work has been extended to other sequences [10, 11]. The author first obtains results similar to [9] for two variations of the Baum-Sweet sequence, and secondly for generalized Thue-Morse sequences (two specific cases) and two variations of the Rudin-Shapiro sequence.

In this paper, we consider the case where u = d is the period-doubling sequence. This sequence is defined by d_{n} := ν_{2}(n + 1) mod 2, where the function ν_{2} is the exponent of the highest power of 2 dividing its argument.

2 Background

In this section, we recall the necessary background for this paper; see, for instance, [4, 12, 13] for more details.

2.1 Combinatorics on words

Let A be a finite alphabet, i.e., a finite set consisting of letters. A (finite) word w over A is a finite sequence of letters belonging to A. If w = w_{n}w_{n−1} ⋯ w_{0} ∈ A^{∗} with n ≥ 0 and w_{i} ∈ A for all i ∈ {0, …, n}, then the length |w| of w is n + 1, i.e., it is the number of letters that w contains. We let ε denote the empty word. This special word is the neutral element for concatenation of words, and its length is set to be 0. The set of all finite words over A is denoted by A^{∗}, and we let A^{+} = A^{∗} \ {ε} denote the set of non-empty finite words over A. For any n ≥ 0, we let A^{n} denote the set of length-n words in A^{∗}.

A finite word w ∈ A^{∗} is a prefix of another finite word z ∈ A^{∗} if there exists u ∈ A^{∗} such that z = wu. If A is ordered by <, the lexicographic order on A^{∗}, which we denote by <_{lex}, is a total order on A^{∗} induced by the order < on the letters and defined as follows: u <_{lex} v either if u is a strict prefix of v or if there exist a, b ∈ A and p ∈ A^{∗} such that a < b, pa is a prefix of u and pb is a prefix of v.

If L is a subset of A^{∗}, then L is called a language and its complexity function ρ_{L} : ℕ → ℕ is defined by ρ_{L}(n) = L ∩ A^{n}.

An infinite word w over A is any infinite sequence over A. The set of all infinite words over A is denoted by A^{ω}. Note that in this paper infinite words are written in bold. To avoid any confusion, the infinite word w = w_{0}w_{1}w_{2} ⋯ will be written as w = w_{0}, w_{1}, w_{2}, … if necessary.

If w ∈ A^{ω}, we define its sequence of run lengths to be an infinite sequence over ℕ ∪ {∞} giving the number of adjacent identical letters. For example, the sequence of run lengths of 01^{2}0^{3}1^{4}0^{5} ⋯ is 1, 2, 3, 4, 5, . . ..

A morphism on A is a map σ : A^{∗} → A^{∗} such that for all u, v ∈ A^{∗}, we have σ(uv) = σ(u)σ(v). In order to define a morphism, it suffices to provide the image of letters belonging to A. A morphism σ : A^{∗} → A^{∗} is k-uniform if |σ(a)| = k for all a ∈ A. A 1-uniform morphism is called a coding. If there is a subalphabet C ⊂ A such that σ(C) ⊂ C^{∗}, then we call the restriction σ_{C} := σ|_{C^{∗}} : C^{∗} → C^{∗} of σ to C a submorphism of σ.

A morphism σ : A^{∗} → A^{∗} is said to be prolongable on a letter a ∈ A if σ(a) = au with u ∈ A^{+} and lim_{n→+∞} |σ^{n}(a)| = +∞. If σ is prolongable on a, then σ^{n}(a) is a proper prefix of

σ^{n+1}(a) for all n ≥ 0. Therefore, the sequence (σ^{n}(a))_{n≥0} of finite words defines an infinite word w that is a fixed point of σ. In that case, the word w is called pure morphic. A morphic word is the morphic image of a pure morphic word.

Let M be a matrix with coefficients in ℕ. There exists permutation matrix P such that P^{−1}MP is a upper block-triangular matrix with square blocks M_{1}, …, M_{s} on the main diagonal that are either irreducible matrices or zeroes. The Perron-Frobenius eigenvalue of M is max_{1≤i≤s} λ_{M_{i}} where λ_{M_{i}} is the Perron-Frobenius eigenvalue of the matrix M_{i}.

Let f : A^{∗} → A^{∗} be a prolongable morphism having the infinite word w as a fixed point. Let α be the Perron-Frobenius eigenvalue of M_{f}. If all letters of A occur in w, then w is said to be a (pure) α-substitutive word. If g : A^{∗} → B^{∗} is a coding, then g(w) is said to be an α-substitutive word.

We say that two real numbers α, β > 1 are multiplicatively independent if the only integers k, ℓ such that α^{k} = β^{ℓ} are k = ℓ = 0. Otherwise, α and β are multiplicatively dependent. The following result can be found in [7].

Theorem 1 (Cobham-Durand). Let α, β > 1 be two multiplicatively independent real numbers. Let u (resp., v) be a pure α-substitutive (resp., pure β-substitutive) word. Let g and g′ be two non-erasing morphisms. If w = g(u) = g′(v), then w is ultimately periodic. In particular, if an infinite word is α-substitutive and β-substitutive, i.e., in the special case where g and g′ are codings, then it is ultimately periodic.

2.2 Abstract numeration systems, automatic sequences and regular sequences

An abstract numeration system (ANS) is a triple S = (L, A, <) where L is an infinite regular language over a totally ordered alphabet (A, <). The map rep_{S} : ℕ → L is the one-to-one correspondence mapping n ∈ ℕ onto the (n + 1)st word in the genealogically ordered language L, which is called the S-representation of n. The S-representation of 0 is the first word in L. The inverse map is denoted by val_{S} : L → ℕ. If w is a word in L, val_{S}(w) is its S-numerical value. For instance, the base-k numeration system is an ANS; the Zeckendorff numeration system based on the Fibonacci numbers (with initial conditions 1 and 2) is also an ANS.

A deterministic finite automaton with output (DFAO) is a 6-tuple A = (Q, q_{0}, A, δ, B, μ), where Q is a finite set of states, q_{0} ∈ Q is the initial state, A is a finite input alphabet, δ : Q × A → Q is the transition function, B is a finite output alphabet, and μ : Q → B is the output function. If S = (L, A, <) is an ANS, we say that an infinite word w = w_{0}w_{1}w_{2} ⋯ ∈ B^{ℕ} is S-automatic if there exists a DFAO A = (Q, q_{0}, A, δ, B, μ) such that x_{n} = μ(δ(q_{0}, rep_{S}(n))) for all n ≥ 0. The automaton A is called a S-DFAO.

When the ANS is the base-k numeration system with k ≥ 2, we have the following theorem of Cobham [6].

Theorem 2 (Cobham’s theorem on automatic sequences). An infinite word w ∈ B^{ℕ} is k-automatic if and only if there exist a k-uniform morphism f : A^{∗} → A^{∗} prolongable on a letter a ∈ A and a coding g : A^{∗} → B^{∗} such that w = g(f^{ω}(a)).

Let u = (u_{n})_{n≥0} be an infinite sequence and let k ≥ 2 be an integer. We define the k-kernel of u to be the set of subsequences

K_{k}(u) = {(u_{k^{i}·n+r})_{n≥0} | i ≥ 0 and 0 ≤ r < k^{i}}.

We say that a sequence u is k-regular if there exists a finite set S of sequences such that every sequence in K_{k}(u) is a ℤ-linear combination of sequences of S. The following properties can be found in [4, 14].

Proposition 3. Let k ≥ 2 be an integer.

(1) If a sequence differs only in finitely many terms from a k-automatic sequence, then it is k-automatic.

(2) For all m ≥ 1, a sequence is k-automatic if and only if it is k^{m}-automatic.

(2) If the integer sequence (u_{n})_{n≥0} is k-regular, then for all integers m ≥ 1, the sequence (u_{n} mod m)_{n≥0} is k-automatic.

(3) A sequence is k-regular and takes only finitely many values if and only if it is kautomatic.

(4) Let (u_{n})_{n≥0} be a k-regular sequence. Then for a ≥ 1 and b ≥ 0, the sequence (u_{an+b})_{n≥0} is k-regular.

(5) Let u = (u_{n})_{n≥0} be a sequence, and let v = (u_{n+1} − u_{n})_{n≥0} be the first difference of u. Then u is k-regular if and only if v is k-regular.

2.3 Formal power series

Let k ≥ 2. The ring 𝔽_{k}[[X]] of formal power series with coefficients in the field 𝔽_{k} = {0, 1, …, k − 1} is defined by

𝔽_{k}[[X]] = {∑_{n≥0} a_{n}X^{n} | a_{n} ∈ 𝔽_{k}} .

We let 𝔽_{k}(X) denote the the field of rational functions. We say that a formal series A(X) = ∑_{n≥0} a_{n}X^{n} is algebraic (over 𝔽_{k}(X)) if there exist an integer d ≥ 1 and polynomials P_{0}(X), P_{1}(X), …, P_{d}(X), with coefficients in 𝔽_{k} and not all zero, such that

P_{0} + P_{1}A + P_{2}A^{2} + ⋯ + P_{d}A^{d} = 0.

With an infinite sequence w = (w_{n})_{n∈ℕ} over {0, 1, …, k − 1}, we can associate a formal series W (X) = ∑_{n≥0} w_{n}X^{n} over 𝔽_{k}[[X]], which is called the generating function of w. In the case where k = p is a prime number, and if w_{0} = 0 and w_{1} is invertible in 𝔽_{p}, then the series W (X) is invertible in 𝔽_{p}[[X]], i.e., there exists a series U(X) ∈ 𝔽_{p}[[X]] such that W (U(X)) = X = U(W (X)). The formal series U(X) is called the (formal) inverse of W (X).

3 The period-doubling sequence

The following definition can be found in [4].

\begin{matrix}0 \\ 1 \\ 0 \\ 1 \\ 0, 1 \end{matrix}

Figure 1: The 2-DFAO generating the period-doubling sequence d.

Definition 4. Consider the period-doubling sequence (indexed by A096268 in [15])

d = (d_{n})_{n≥0} = 010001010100010001000 · · · .

This sequence is defined by d_{n} := ν_{2}(n + 1) mod 2, where the function ν_{2} is the exponent of the highest power of 2 dividing its argument. Alternatively, we have d = h^{ω}(0), where h(0) = 01 and h(1) = 00. Since h is a 2-uniform morphism, then the period doubling sequence d is 2-automatic. The 2-DFAO drawn in Figure 1 generates the period-doubling sequence d. Note that this automaton reads its input from most significant digit to least significant digit.

Let us define two increasing sequences o = (o_{n})_{n≥0} and z = (z_{n})_{n≥0} respectively satisfying {o_{n} | n ∈ N} = {m ∈ N | d_{m} = 1} and {z_{n} | n ∈ N} = {m ∈ N | d_{m} = 0}. We have

o = 1, 5, 7, 9, 13, 17, 21, 23, 25, 29, 31, 33, 37, 39, 41, 45, 49, 53, 55, 57, 61, 65, 69, 71, 73, 77, …,
z = 0, 2, 3, 4, 6, 8, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 24, 26, 27, 28, 30, 32, 34, 35, 36, 38, 40, ….

Those two sequences are indexed by A079523 and A121539 in [15]. Observe that the binary expansions of the terms of o (resp., z) end with an odd (resp., even) number of 1’s. This can be seen if one considers the language accepted by the 2-DFAO in Figure 1 where the final state is the one outputting 1 (resp., 0). In the following, we study the regularity of the sequences o and z.

Proposition 5. The sequence z = (z_{n})_{n≥0} is not k-regular for any k ∈ ℕ_{≥2}.

Proof. Let d̄ be the image of d under the exchange morphism E : {0, 1}^{∗} → {0, 1}^{∗} : 0 ↦ 1, 1 ↦ 0. In particular, d̄ is the fixed point of the morphism h′(0) = 11 and h′(1) = 10 starting with 1. We also have

z = {m ∈ ℕ | d_{m} = 0} = {m ∈ ℕ | d̄_{m} = 1}.

The sequence d̄ is related to the Thue-Morse sequence in the following way. Let t = (t_{n})_{n≥0} be the Thue-Morse sequence, i.e., the fixed point of the morphism τ : {0, 1}^{∗} → {0, 1}^{∗} : 0 ↦ 01, 1 ↦ 10 which starts with 0. In fact, the sequence d̄ is the first difference modulo 2 of the Thue-Morse sequence t [3], i.e., d̄= (t_{n+1} − t_{n} mod 2)_{n≥0}.

In other words, the sequence z of positions of 1’s in d̄is exactly the sequence of positions in the Thue-Morse sequence t where the letters 0 and 1 alternate. Consequently, the first difference of z, which is the first difference between the positions of 1’s in d̄, gives the length of the blocks of consecutive identical letters in t, i.e., it is the sequence of run lengths of t.

However, the sequence of run lengths of t is the sequence p = (p_{n})_{n≥0} which is the fixed point of the morphism f : {1, 2}^{∗} → {1, 2}^{∗} : 1 ↦ 121, 2 ↦ 12221 which starts with 1 [2]. This sequence p is not 2-automatic [1], and by Proposition 3, p is not 2^{m}-automatic for any m ≥ 1. Let us show that p is not k-automatic for any integer k ≥ 2. Suppose that p is k-automatic for some integer k ≥ 2 which is not a power of 2. Then, by Theorem 2, p is the image under a coding of the fixed point of a k-uniform morphism whose Perron-Frobenius eigenvalue is k. Since the Perron-Frobenius eigenvalue of f is 2, then by Theorem 1, p is ultimately periodic, which is impossible.

Now since p takes only two different values, p is not k-regular for any k ≥ 2 by Proposition 3. Since p is the first difference of z, then z is not k-regular for any k ≥ 2 again by Proposition 3.

The next lemma gives two other morphisms that generate the period-doubling sequence d. Those morphisms are helpful to locate the positions of 1’s in d.

Lemma 6. Let f : {2, 4}^{∗} → {2, 4}^{∗} : 2 ↦ 242, 4 ↦ 24442 and g : {2, 4}^{∗} → {0, 1}^{∗} : 2 ↦ 01, 4 ↦ 0001. For all n ≥ 1, we have h^{2n+1}(0) = g(f^{n}(2)) and h^{2n+1}(10) = g(f^{n}(4)). In particular, d = h^{ω}(0) = g(f^{ω}(2)).

Proof. We proceed by induction on n ≥ 1. The case n = 1 can easily be checked by hand. Now assume that n ≥ 1 and suppose that the result holds for all m ≤ n. We have

h^{2(n+1)+1}(0) = h^{2n+1}(0100) = h^{2n+1}(0)h^{2n+1}(10)h^{2n+1}(0).

Now, by induction hypothesis, we find

h^{2(n+1)+1}(0) = g(f^{n}(2))g(f^{n}(4))g(f^{n}(2)) = g(f^{n}(242)) = g(f^{n+1}(2)),

as expected. Similarly, we have

h^{2(n+1)+1}(10) = h^{2n+1}(01010100) = h^{2n+1}(0)h^{2n+1}(10)h^{2n+1}(10)h^{2n+1}(10)h^{2n+1}(0),

and by induction hypothesis, we get

h^{2(n+1)+1}(0) = g(f^{n}(2))g(f^{n}(4))g(f^{n}(4))g(f^{n}(4))g(f^{n}(2)) = g(f^{n}(24442)) = g(f^{n+1}(4)).

The particular case can be deduced from the first equality of the statement.

Proposition 7. The sequence o = (o_{n})_{n≥0} is not k-regular for any k ∈ ℕ_{≥2}.

Proof. By Lemma 6, we know that d = g(f^{ω}(2)) with f : {2, 4}^{∗} → {2, 4}^{∗} : 2 ↦ 242, 4 ↦ 24442 and g : {2, 4}^{∗} → {0, 1}^{∗} : 2 ↦ 01, 4 ↦ 0001. Observe that |g(2)| = 2 and |g(4)| = 4, and the letter 1 occurs only once at the end of g(2) (resp., g(4)). Consequently, the first difference of the positions of 1’s in d — which is the first difference of o — is given by the shift of the sequence f^{ω}(2), i.e., we drop the first term. By the proof of Proposition 5, we know that f^{ω}(2) is not k-regular for any k ≥ 2. By Proposition 3, o is not k-regular for any k ≥ 2.

Remark 8. Using an argument similar to the one of the proof of Proposition 7, one can also get another way of proving Proposition 5.

4 The formal inverse of the period-doubling word

Let D(X) = ∑_{n≥0} d_{n}X^{n} be the generating function of the period-doubling sequence d. Since d_{0} = 0 and d_{1} = 1 is invertible in 𝔽_{2}, then the series D(X) is invertible in 𝔽_{2}[[X]], i.e., there exists a series

U(X) = ∑_{n≥0} u_{n}X^{n} ∈ 𝔽_{2}[[X]]

such that D(U(X)) = X = U(D(X)). We want to describe the sequence u = (u_{n})_{n≥0}. Mimicking [9], the first step is to get recurrence relations for the coefficients (u_{n})_{n≥0} of the series U(X). To that aim, recall the following result; see [5, p. 412].

Lemma 9. The generating function D(X) = ∑_{n≥0} d_{n}X^{n} of the period-doubling sequence d satisfies

X(1 + X^{2})D(X)^{2} + (1 + X^{2})D(X) + X = 0

over 𝔽_{2}[[X]].

Proof. Observe that, since d = h^{ω}(0), we have d_{2n} = 0 and d_{2n+1} = 1 − d_{n} for all n ≥ 0. Thus we have

D(X) = ∑_{n≥0} d_{n}X^{n} = ∑_{n≥0} d_{2n}X^{2n} + ∑_{n≥0} d_{2n+1}X^{2n+1} = X ∑_{n≥0} X^{2n} − X ∑_{n≥0} d_{n}X^{2n}.

Now recall that, for any prime p and for any series F (X) in 𝔽_{p}[[X]], we have 1/(1 − X) = ∑_{n≥0} X^{n}. Consequently,

D(X) = \frac{X}{1 − X^{2}} − XD(X^{2}).

Now working over 𝔽_{2}[[X]], we have

X(1 + X^{2})D(X^{2}) + (1 + X^{2})D(X) + X = 0,

and since for any prime p and for any series F (X) in 𝔽_{p}[[X]], we have F (X)^{p} = F (X^{p}), we find

X(1 + X^{2})D(X)^{2} + (1 + X^{2})D(X) + X = 0,

as desired.

To prove the next result, we follow the method from [9]. Proposition 10. The series U(X) = ∑_{n≥0} u_{n}X^{n} satisfies each of the following polynomial equations

X^{2}U(X)^{3} + XU(X)^{2} + (X^{2} + 1)U(X) + X = 0,
X^{3}U(X)^{4} + X^{3}U(X)^{2} + U(X) + X = 0

over 𝔽_{2}[[X]]. In particular, the sequence u = (u_{n})_{n≥0} verifies u_{0} = 0, u_{1} = 1, and over 𝔽_{2}

\begin{cases}u_{2n} = 0 ∀ n ≥ 0, \\ u_{4n+1} = u_{2n−1} ∀ n ≥ 1, \\ u_{4n+3} = u_{n} ∀ n ≥ 0. \end{cases}

Proof. First, let us rewrite the equation from Lemma 9 in terms of X. We get

D(X)^{2}X^{3} + D(X)X^{2} + (D(X)^{2} + 1)X + D(X) = 0.

In this new equation, replace X by U(X) to obtain

D(U(X))^{2}U(X)^{3} + D(U(X))U(X)^{2} + (D(U(X))^{2} + 1)U(X) + D(U(X)) = 0. Since U(X) is the formal inverse of D(X), we actually have

X^{2}U(X)^{3} + XU(X)^{2} + (X^{2} + 1)U(X) + X = 0,  (1)

which is the first equation of the statement. This in turn implies that, over 𝔽_{2}[[X]],

U(X)^{3} = \frac{XU(X)^{2} + (X^{2} + 1)U(X) + X}{X^{2}} .  (2)

Now multiply (1) by U(X) and replace U(X)^{3} by its value (2). We obtain first

X^{2}U(X)^{4} + XU(X)^{3} + (X^{2} + 1)U(X)^{2} + XU(X) = 0,

and so

X^{2}U(X)^{4} + X (\frac{XU(X)^{2} + (X^{2} + 1)U(X) + X}{X^{2}} ) + (X^{2} + 1)U(X)^{2} + XU(X) = 0

⇒ X^{3}U(X)^{4} + XU(X)^{2} + (X^{2} + 1)U(X) + X + (X^{3} + X)U(X)^{2} + X^{2}U(X) = 0 ⇒ X^{3}U(X)^{4} + (X^{3} + 2X)U(X)^{2} + (2X^{2} + 1)U(X) + X = 0.

Working over 𝔽_{2}[[X]], this equality becomes X^{3}U(X)^{4} + X^{3}U(X)^{2} + U(X) + X = 0 ⇔ X^{3}U(X^{4}) + X^{3}U(X^{2}) + U(X) + X = 0, which is the second equation of the statement.

Let us now prove that the recurrence relations for the sequence u hold. Writing U(X) = ∑_{n≥0} u_{n}X^{n} in the second equation proven above, we find

X^{3} ∑_{n≥0} u_{n}X^{4n} + X^{3} ∑_{n≥0} u_{n}X^{2n} + ∑_{n≥0} u_{n}X^{n} + X = 0

⇔ ∑_{n≥0} u_{n}X^{4n+3} + ∑_{n≥0} u_{n}X^{2n+3} + ∑_{n≥0} u_{n}X^{n} + X = 0.

Let us inspect the coefficients in the last equality. We immediately have u_{0} = 0 and u_{1} = 1 over 𝔽_{2}. Since the exponents 4n + 3 and 2n + 3 are odd for all n ≥ 0, we also get that, over 𝔽_{2},

u_{2n} = 0 ∀ n ≥ 0.

Looking at the coefficient of X^{4n+3}, we obtain

u_{n} + u_{2n} + u_{4n+3} = 0 ∀ n ≥ 0,

which implies that u_{4n+3} = u_{n} over 𝔽_{2} for all n ≥ 0. Let us now find the coefficient of X^{4n+1} for n ≥ 1. We have

u_{2n−1} + u_{4n+1} = 0 ∀ n ≥ 1,

giving u_{4n+1} = u_{2n−1} over 𝔽_{2} for all n ≥ 1. As a consequence, the sequence u = (u_{n})_{n≥0} verifies u_{0} = 0, u_{1} = 1, and satisfies the following recurrence relations over 𝔽_{2}

\{ \begin{matrix}u_{2n} = 0 ∀ n ≥ 0, \\ u_{4n+1} = u_{2n−1} ∀ n ≥ 1, \\ u_{4n+3} = u_{n} ∀ n ≥ 0. \end{matrix}

From now on, the sequence u = (u_{n})_{n≥0} will be referred to as the inverse period-doubling sequence, iPD sequence for short (sequence A317542 in [15]). We have

u = (u_{n})_{n≥0} = 01000101000001000100000100000101000001000 · · · .

Remark 11. We have d_{n} = u_{n} for all n ≤ 8, but observe that

1 = d_{4·2+1} = d_{9} ≠ u_{9} = u_{4·2+1}u = u_{2·2−1} = u_{3} = 0.

In the following, we show that u is 2-automatic, and we also provide an automaton that generates u, which is deduced from the recurrence relations in Lemma 13.

Corollary 12. The sequence u = (u_{n})_{n≥0} is 2-automatic.

Proof. From Proposition 10, it follows that the formal power series U(X) is algebraic over 𝔽_{2}(X). By Christol’s theorem, the sequence u is thus 2-automatic.

Lemma 13. For all n ≥ 0, r_{1} ∈ {0, 2}, r_{2} ∈ {0, 2, 4, 6} and r_{3} ∈ {0, 2, 4, 6, 8, 10, 12, 14}, we have

u_{n} = u_{4n+3} = u_{16n+15},  (3)
u_{2n} = u_{4n+r_{1}} = u_{8n+r_{2}} = u_{8n+3} = u_{16n+r_{3}} = u_{16n+3} = u_{16n+9} = u_{16n+11} = 0,  (4)
u_{2n+1} = u_{8n+7},  (5)
u_{4n+1} = u_{8n+5} = u_{16n+1} = u_{16n+7} = u_{16n+13},  (6)
u_{8n+1} = u_{16n+5}.  (7)

Proof. We make an extensive use of the recurrence relations from Proposition 10. We show that the 2-kernel K_{2}(u) is finitely generated by the sequences (u_{n})_{n≥0}, (u_{2n})_{n≥0}, (u_{2n+1})_{n≥0}, (u_{4n+1})_{n≥0} and (u_{8n+1})_{n≥0}.

The first equality in (3) is directly given by Proposition 10. For all n ≥ 0, we have

u_{16n+15} = u_{4(4n+3)+3} = u_{4n+3} = u_{n}

using Proposition 10 twice since n, 4n + 3 ≥ 0.

Let us show (4). From Proposition 10, it is clear that for all n ≥ 0,

u_{2n} = 0 = u_{4n+r_{1}} = u_{8n+r_{2}} = u_{16n+r_{3}}.

Now for all n ≥ 0, we have

u_{8n+3} = u_{4(2n)+3} = u_{2n} = 0,
u_{16n+3} = u_{4(4n)+3} = u_{4n} = u_{2n} = 0,

and

u_{16n+11} = u_{4(4n+2)+3} = u_{4n+2} = u_{2n} = 0,

using Proposition 10 since 2n, 4n, 4n + 2 ≥ 0. Similarly, for all n ≥ 0, we have 4n + 2 ≥ 1, thus Proposition 10 gives

u_{16n+9} = u_{4(4n+2)+1} = u_{2(4n+2)−1} = u_{8n+3} = u_{2n} = 0,

where the next-to-last equality comes from (4) above.

Let us prove (5). For all n ≥ 0, we have

u_{8n+7} = u_{4(2n+1)+3} = u_{2n+1},

using Proposition 10 since 2n + 1 ≥ 0.

Let us show that (6) holds. For all n ≥ 0, we have

u_{8n+5} = u_{4(2n+1)+1} = u_{2(2n+1)−1} = u_{4n+1},
u_{16n+7} = u_{4(4n+1)+3} = u_{4n+1},

and

u_{16n+13} = u_{4(4n+3)+1} = u_{2(4n+3)−1} = u_{8n+5} = u_{4n+1},

using Proposition 10 since 2n+1, 4n+3 ≥ 1 and 4n+1 ≥ 0. Now we prove that u_{16n+1} = u_{4n+1} for all n ≥ 0. The result is trivial when n = 0 for we have u_{16n+1} = u_{1} = u_{4n+1}. Now suppose that n ≥ 1. We first obtain from Proposition 10 that

u_{16n+1} = u_{4(4n)n+1} = u_{2(4n)−1} = u_{8n−1}.

Writing n = m + 1 with m ≥ 0, we then get

u_{16n+1} = u_{8n−1} = u_{8m+7} = u_{2m+1}

where the last equality comes from (5) since m ≥ 0. Consequently,

u_{16n+1} = u_{2m+1} = u_{2(m+1)−1} = u_{2n−1} = u_{4n+1}

using Proposition 10 for the last equality since n ≥ 1. This gives the expected recurrence relation.

Finally, for all n ≥ 0, we have 4n + 1 ≥ 0, so Proposition 10 implies that

u_{16n+5} = u_{4(4n+1)+1} = u_{2(4n+1)−1} = u_{8n+1},

which proves (7).

Using the recurrence relations from Lemma 13, we build the 2-DFAO in Figure 2, which generates the iPD sequence u. Note that this automaton reads its input from least significant digit to most significant digit.

Since the iPD sequence u takes the values 0 and 1, it can also be considered as a sequence of complex numbers. We now obtain the transcendence of its generating function.

Proposition 14. The formal power series U(X) = ∑_{n≥0} u_{n}X^{n} ∈ ℂ[[X]] is transcendental over ℂ(X).

Proof. A classical result of Fatou states that a power series whose coefficients take only finitely many values is either rational or transcendental [8]. However, if the rational power series A(X) = ∑_{n≥0} a_{n}X^{n} has bounded integer coefficients, then the sequence (a_{n})_{n≥0} must be ultimately periodic. Since the iPD sequence u is not ultimately periodic, we deduce that U(X) = ∑_{n≥0} u_{n}X^{n} ∈ ℂ[[X]] is transcendental over ℂ(X).

5 Characteristic sequence of 1’s in the iPD sequence u

In this section, we study the characteristic sequence of 1’s in the iPD sequence u. The main result is that this sequence is not k-regular for any k ≥ 2. Surprisingly, it is related to the characteristic sequence of Fibonacci numbers.

\begin{matrix}0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0, 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix}

Figure 2: The 2-DFAO generating the inverse period-doubling sequence u.

Definition 15. Let us define an increasing sequence a = (a_{n})_{n≥0} satisfying {a_{n} | n ∈ N} = {m ∈ N | u_{m} = 1} (sequence A317543 in [15]). We have

a = 1, 5, 7, 13, 17, 23, 29, 31, 37, 49, 55, 61, 65, 71, 77, 95, 101, 113, 119, 125, 127, 133, 145, ….

From Proposition 10, we already know that a only contains odd integers. In the 2-DFAO in Figure 2, if the states outputting 1 are considered to be final, then the binary expansions of the terms of a is the language

L_{a} = {rep_{2}(a_{n}) | n ≥ 0} = {11}^{∗}1 ∪ 1{1, 00}^{∗}0{11}^{∗}1.

For instance, rep_{2}(a_{0}) = 1, rep_{2}(a_{1}) = 101, rep_{2}(a_{2}) = 111, rep_{2}(a_{3}) = 1101.

In the following, we obtain the complexity function of the language L_{a}. To that aim, we define the sequence (F (n))_{n≥0} of the Fibonacci numbers with initial conditions equal to 0 and 1, i.e., F (0) = 0, F (1) = 1 and, for all n ≥ 2, let F (n) = F (n − 1) + F (n − 2).

Proposition 16. The complexity function ρ_{L_{a}} : ℕ → ℕ of the language L_{a} satisfies ρ_{L_{a}}(0) = 0, ρ_{L_{a}}(2n) = F (2n − 1) − 1 for all n ≥ 1, and ρ_{L_{a}}(2n + 1) = F (2n) + 1 for all n ≥ 0.

Proof. Start with the 2-DFAO in Figure 2. If the states outputting 1 are final, then it accepts the language L_{a} if words are read starting with the least significant digit. Let us reverse this 2-DFAO to obtain the non-deterministic automaton in Figure 3. It accepts L_{a} if words are read starting with the most significant digit. Determinizing it leads to an automaton A_{L_{a}} whose state set is {1, …, 8}, with 1 as initial state, with 2, 6 as final states, and whose transition table is given in Table 1. Observe that this automaton accepts L_{a}, and has 8 as a sink state.

\begin{matrix}0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0, 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix}

Figure 3: A non-deterministic automaton accepting the language L_{a}.

(0 1) / (1 8 2)
2 3 4
3 5 6
4 3 2
5 3 5
6 8 7
7 8 6
8 8 8

Table 1: The transition table of a deterministic automaton accepting L_{a}.

Now let M denote the adjacency matrix of A_{L_{a}} without considering the sink state 8, and let

u = (1, 0, 0, 0, 0, 0, 0) and v = (0, 1, 0, 0, 0, 1, 0)^{⊤}.

Note that v codes the final states of A_{L_{a}}. For all n ≥ 0, uM^{n}v is the number of length-n words in L_{a}. An easy induction shows that

M^{2n}v = (F (2n − 1) − 1, F (2n) + 1, F (2n − 1) − 1, F (2n), F (2n), 1, 0)^{⊤} ∀ n ≥ 1,

and

M^{2n+1}v = (F (2n) + 1, F (2n + 1) − 1, F (2n) + 1, F (2n + 1), F (2n + 1) − 1, 0, 1)^{⊤} ∀ n ≥ 0.

The conclusion follows.

The sequence (a_{n} mod 3)_{n≥0} shows a particularly unexpected behavior as explained in the next two results.

Lemma 17. Let n ≥ 0. Then a_{n} mod 3 ≡ r with r ∈ {1, 2}. More precisely, let w_{n} := rep_{2}(a_{n}), and define L_{a,1} = {11}^{∗}1 and L_{a,2} = 1{1, 00}^{∗}0{11}^{∗}1. If w_{n} ∈ L_{a,1}, or if w_{n} ∈ L_{a,2} and |w_{n}| is even, then a_{n} mod 3 ≡ 1; if w_{n} ∈ L_{a,2} and |w_{n}| is odd, then a_{n} mod 3 ≡ 2.

Proof. First, we have

(2^{n} mod 3)_{n≥0} = (1, −1, 1, −1, 1, −1, …).  (8)

Now let n ≥ 0 and set w_{n} := rep_{2}(a_{n}). If w_{n} ∈ L_{a,1}, then from (8) we deduce that a_{n} mod 3 ≡ 1. Assume that w_{n} ∈ L_{a,2} and write w_{n} = p_{n}s_{n} with p_{n} ∈ 1{1, 00}^{∗} and s_{n} ∈ 0{11}^{∗}1. Since |s_{n}| is even, then (8) shows that val_{2}(s_{n}) mod 3 ≡ 1.

As a first case, suppose that |w_{n}| is odd. Then |p_{n}| is also odd, and so p_{n} contains an odd number of 1’s separated by even-length blocks of 0’s. Because the 0’s blocks have even length, the contributions of successive 1’s in p_{n} alternate in value between +1 mod 3 and −1 mod 3. Since |s_{n}| is even, after reading s_{n} then reading p_{n} gives an additional +1 mod 3. Consequently, both p_{n} and s_{n} together give 2 mod 3, i.e., a_{n} mod 3 ≡ val_{2}(p_{n}s_{n}) mod 3 ≡ 2.

As a second case, assume that |w_{n}| is even. Then |p_{n}| is even, and so p_{n} contains an even number of 1’s separated by even-length blocks of 0’s. Again the 1’s in p_{n} contribute alternating +1 mod 3 and −1 mod 3, and since there is an even number of them, the 1’s in p_{n} contribute 0 mod 3 in total. Thus, in this case, a_{n} mod 3 ≡ val_{2}(p_{n}s_{n}) mod 3 ≡ 1.

Proposition 18. The sequence (a_{n} mod 3)_{n≥0} is given by the infinite word

1^{F (1)}2^{F (2)}1^{F (3)}2^{F (4)}1^{F (5)}2^{F (6)} · · · .

In particular, the sequence of run lengths of (a_{n} mod 3)_{n≥0} is the sequence of Fibonacci numbers (F (n))_{n≥1} .

Proof. Recall that L_{a}^{n} = L_{a} ∩ {0, 1}^{n} denotes the set of length-n words in L_{a}. We can order the words of L_{a}^{n} by lexicographic order, i.e.,

L_{a}^{n} = {w_{n,1} <_{lex} w_{n,2} <_{lex} ⋯ <_{lex} w_{n,#L_{a}^{n}}}.

By Proposition 16, #L_{a}^{0} = 0 = #L_{a}^{2}, #L_{a}^{2n} = F (2n − 1) − 1 for all n ≥ 1, and #L_{a}^{2n+1} = F (2n) + 1 for all n ≥ 0.

Let us first consider L_{a}^{2n} for n ≥ 2. From Lemma 17, we know that val_{2}(w_{2n,i}) mod 3 ≡ 1 for all i ∈ {1, 2, …, F (2n − 1) − 1}. In other terms, we get

(val_{2}(w_{2n,i}) mod 3)_{1≤i≤F (2n−1)−1} = 1^{F (2n−1)−1}.

Let us now study L_{a}^{2n+1} for n ≥ 0. In the case where n = 0, then L_{a}^{1} = {w_{1,1}} with w_{1,1} = 1, which of course gives val_{2}(w_{1,1}) mod 3 = 1^{F (1)}. Assume that n ≥ 1. Since the words of L_{a}^{2n+1} are ordered lexicographically, we know that w_{2n+1,i} ∈ L_{a,2} for all i ∈ {1, 2, …, F (2n)}, and w_{2n+1,F (2n)+1} = 1^{2n+1} ∈ L_{a,1}. From Lemma 17, we obtain that val_{2}(w_{2n+1,i}) mod 3 ≡ 2 for all i ∈ {1, 2, …, F (2n)}, and val_{2}(w_{2n+1,F (2n)+1}) mod 3 ≡ 1. In fact, we obtain

(val_{2}(w_{2n+1,i}) mod 3)_{1≤i≤F (2n)+1} = 2^{F (2n)}1.

Observe that, for any n ≥ 1, concatenating the sequences (val_{2}(w_{2n+1,i}) mod 3)_{1≤i≤F (2n)+1} and (val_{2}(w_{2n+2,i}) mod 3)_{1≤i≤F (2n+1)−1} gives (2^{F (2n)}1) · (1^{F (2n+1)−1}) = 2^{F (2n)}1^{F (2n+1)}. Now putting everything together, we find

(a_{n} mod 3)_{n≥0} = 1^{F (1)} · 2^{F (2)}1 · 1^{F (3)−1} · 2^{F (4)}1 · 1^{F (5)−1} · 2^{F (6)}1 ⋯
= 1^{F (1)}2^{F (2)}1^{F (3)}2^{F (4)}1^{F (5)}2^{F (6)} ⋯,

as expected.

To show that a is not k-regular for any k ≥ 2, the idea is to study the sequence of consecutive differences in (a_{n} mod 3)_{n≥0}. Let us define the sequence δ = (δ_{n})_{n≥0} by

δ_{n} = \{ \begin{matrix}1, & if (a_{n+1} − a_{n}) mod 3 ≠ 0; \\ 0, & otherwise. \end{matrix}

From Proposition 18, we know that δ_{n} = 1 if and only if there exists n = F (m) − 2 for some m ≥ 0. If we let x denote the characteristic sequence of Fibonacci numbers, i.e., x_{n} equals 1 if n is a Fibonacci number, 0 otherwise, then δ = (x_{n})_{n≥2} since for all n ≥ 0

δ_{n} = 1 ⇔ n = F (m) − 2 for some m ≥ 0 ⇔ n + 2 = F (m) for some m ≥ 0 ⇔ x_{n+2} = 1.

The goal is now to show that x is not k-automatic for any k ≥ 2; then the non-k-automaticity of δ can easily be deduced. What follows is widely inspired by [12, 13]. In our context, we consider the ANS (L_{F} , {0, 1}, <) where L_{F} = {ε} ∪ 1{0, 01}^{∗} is the language of Fibonacci representations of nonnegative integers with 0 < 1. Observe that the DFA A in Figure 4 accepts the regular language L_{F}.

Lemma 19. The characteristic sequence of Fibonacci numbers x is Fibonacci-automatic.

Proof. The Fibonacci-DFAO B in Figure 5 generates the sequence x in the Zeckendorff numeration system. In particular, this shows that x is Fibonacci-automatic.

When a word is S-automatic for some ANS S, then it is in fact morphic [13].

Theorem 20. An infinite word w is morphic if and only if w is S-automatic for some ANS S.

From Lemma 19 and Theorem 20, we easily deduce that x is morphic. More precisely, we want to build the morphisms that generate x. We follow the constructive proof of Theorem 20 (we refer the reader to [13, Chapter 2] for more details).

\begin{matrix}A \\ B \\ C \\ D \\ E \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0, 1 \end{matrix}

Figure 4: The DFA A accepting the language {ε} ∪ 1{0, 01}^{∗}.

\begin{matrix}0_{0} \\ 1 \\ 0_{1} \\ 0 \\ 1 \\ 0 \\ 1 \\ 0, 1 \end{matrix}

Figure 5: The Fibonacci-DFAO B generating x.

Lemma 21. Let f : {z, a_{0}, a_{1}, …, a_{7}}^{∗} → {z, a_{0}, a_{1}, …, a_{7}}^{∗} be the morphism defined by f(z) = za_{0} and

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ f(a_{i}) & a_{1}a_{2} & a_{1}a_{4} & a_{3}a_{7} & a_{3}a_{6} & a_{4}a_{7} & a_{5}a_{6} & a_{5}a_{7} & a_{7}a_{7} \end{matrix} .

We also define the morphism g : {z, a_{0}, a_{1}, …, a_{7}}^{∗} → {0, 1}^{∗} by g(z) = g(a_{1}) = g(a_{4}) = g(a_{7}) = ε, g(a_{0}) = g(a_{5}) = g(a_{6}) = 0 and g(a_{2}) = g(a_{3}) = 1. Then x = g(f^{ω}(z)). In particular, the word x is morphic.

Proof. First recall that the DFA A in Figure 4 accepts the language L_{F} = {ε}∪1{0, 01}^{∗}, and the Fibonacci-DFAO B in Figure 5 generates the sequence x. Then, the product automaton P = A × B is drawn in Figure 6. If we set

a_{0} := (A, 0_{0}), a_{1} := (E, 0_{0}), a_{2} := (B, 1), a_{3} := (C, 1),
a_{4} := (E, 1), a_{5} := (C, 0_{1}), a_{6} := (D, 0_{1}), a_{7} := (E, 0_{1}),

then we can associate a morphism ψ_{P} : {z, a_{0}, a_{1}, …, a_{7}}^{∗} → {z, a_{0}, a_{1}, …, a_{7}}^{∗} with P as follows. It is defined by ψ_{P}(z) = za_{0} and

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ ψ_{P}(a_{i}) = δ_{P}(a_{i}, 0)δ_{P}(a_{i}, 1) & a_{1}a_{2} & a_{1}a_{4} & a_{3}a_{7} & a_{3}a_{6} & a_{4}a_{7} & a_{5}a_{6} & a_{5}a_{7} & a_{7}a_{7} \end{matrix}

where δ_{P} is the transition function of P. Notice that ψ_{P} = f. We also define the morphism

g : {z, a_{0}, a_{1}, …, a_{7}}^{∗} → {0, 1}^{∗} : z, a_{1}, a_{4}, a_{7} ↦ ε; a_{0}, a_{5}, a_{6} ↦ 0; a_{2}, a_{3} ↦ 1.

It is well known that x = g(f^{ω}(z)), which shows that x is morphic.

\begin{matrix}(A, 0_{0}) \\ (B, 1) \\ (C, 1) \\ (D, 0_{1}) \\ (C, 0_{1}) \\ (E, 0_{0}) \\ (E, 1) \\ (E, 0_{1}) \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0, 1 \end{matrix}

Figure 6: The DFA P which is the product of A and B.

Observe that the morphism g in Lemma 21 is erasing, i.e., the image of some letter is the empty word. In the following lemma (see [12, Chapter 3]), we get rid of the erasure and we later obtain two new non-erasing morphisms that generate x.

Lemma 22. Let w = g(f^{ω}(a)) be a morphic word where g : B^{∗} → A^{∗} is a (possibly erasing) morphism and f : B^{∗} → B^{∗} is a non-erasing morphism. Let C be a subalphabet of {b ∈ B | g(b) = ε} such that f_{C} is a submorphism of f. Let λ_{C} : B^{∗} → B^{∗} be the morphism defined by λ_{C}(b) = ε if b ∈ C, and λ_{C}(b) = b otherwise. The morphisms f_{ε} := (λ_{C} ∘ f)|_{(B\C)^{∗}} and g_{ε} := g|_{(B\C)^{∗}} are such that w = g_{ε}(f_{ε}^{ω}(a)).

Proposition 23. Let ϕ : {a, b, c, d, e}^{∗} → {a, b, c, d, e}^{∗} be the morphism defined by

ϕ : \{a, b, c, d, e\}^{∗} → \{a, b, c, d, e\}^{∗} : \{ \begin{matrix}a & ↦ & ab, \\ b & ↦ & c, \\ c & ↦ & ce, \\ d & ↦ & de, \\ e & ↦ & d \end{matrix}

and let μ : {a, b, c, d, e}^{∗} → {0, 1}^{∗} : a, d, e ↦ 0; b, c ↦ 1 be a coding. Then x = μ(ϕ^{ω}(a)).

Proof. We make use of Lemmas 21 and 22. First, we have

{b ∈ {z, a_{0}, a_{1}, …, a_{7}} | g(b) = ε} = {z, a_{1}, a_{4}, a_{7}},

so we choose C = {a_{1}, a_{4}, a_{7}} for f_{C} is a submorphism of f. Then the morphism

f_{ε} : {z, a_{0}, a_{2}, a_{3}, a_{5}, a_{6}}^{∗} → {z, a_{0}, a_{2}, a_{3}, a_{5}, a_{6}}^{∗}

is defined by f_{ε}(z) = za_{0}, f_{ε}(a_{0}) = a_{2}, f_{ε}(a_{2}) = a_{3}, f_{ε}(a_{3}) = a_{3}a_{6}, f_{ε}(a_{5}) = a_{5}a_{6} and f_{ε}(a_{6}) = a_{5}, while the morphism g_{ε} : {z, a_{0}, a_{2}, a_{3}, a_{5}, a_{6}}^{∗} → {0, 1}^{∗} is given by g_{ε}(z) = ε, g_{ε}(a_{0}) = g_{ε}(a_{5}) = g_{ε}(a_{6}) = 0 and g_{ε}(a_{2}) = g_{ε}(a_{3}) = 1. We also have x = g_{ε}(f_{ε}^{ω}(z)). Note that f_{ε}|_{{a_{2},a_{3},a_{5},a_{6}}^{∗}} is a submorphism of f_{ε}.

Let us define the morphism f′_{ε} : {a_{0}, a_{2}, a_{3}, a_{5}, a_{6}}^{∗} → {a_{0}, a_{2}, a_{3}, a_{5}, a_{6}}^{∗} by f′_{ε}(a_{0}) = a_{0}a_{2}, and f′_{ε} = f_{ε}|_{{a_{2},a_{3},a_{5},a_{6}}^{∗}}. From that definition, f′_{ε} is prolongable on a_{0}. Also consider the morphism g′_{ε} : {a_{0}, a_{2}, a_{3}, a_{5}, a_{6}}^{∗} → {0, 1}^{∗} given by g′_{ε} = g_{ε}|_{{a_{0},a_{2},a_{3},a_{5},a_{6}}^{∗}}. We have

f_{ε}^{ω}(z) = za_{0}f_{ε}(a_{0})f_{ε}^{2}(a_{0})f_{ε}^{3}(a_{0})f_{ε}^{4}(a_{0}) ⋯
= za_{0}f_{ε}(a_{0})f_{ε}(f_{ε}(a_{0}))f_{ε}^{2}(f_{ε}(a_{0}))f_{ε}^{3}(f_{ε}(a_{0})) ⋯
= za_{0}a_{2}f_{ε}(a_{2})f_{ε}^{2}(a_{2})f_{ε}^{3}(a_{2}) ⋯
= za_{0}a_{2}f′_{ε}(a_{2})(f′_{ε}(a_{2}))^{2}(f′_{ε}(a_{2}))^{3} ⋯,

thus we get

x = g_{ε}(f_{ε}^{ω}(z))
= g_{ε}(z)g_{ε}(a_{0})g_{ε}(a_{2})g_{ε}(f′_{ε}(a_{2}))g_{ε}((f′_{ε}(a_{2}))^{2})g_{ε}((f′_{ε}(a_{2}))^{3}) ⋯
= εg′_{ε}(a_{0})g′_{ε}(a_{2})g′_{ε}(f′_{ε}(a_{2}))g′_{ε}((f′_{ε}(a_{2}))^{2})g′_{ε}((f′_{ε}(a_{2}))^{3}) ⋯
= g′_{ε}(a_{0}a_{2}f′_{ε}(a_{2})(f′_{ε}(a_{2}))^{2}(f′_{ε}(a_{2}))^{3} ⋯)
= g′_{ε}((f′_{ε})^{ω}(a_{0})).

Up to a renaming of the letters, we have proven the claim.

Corollary 24. Let φ = \frac{1}{2}(\sqrt{5} + 1) be the golden ratio. The word x is φ-substitutive.

Proof. Let

M_{ϕ} = ( \begin{matrix}1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{matrix} )

be the matrix associated with the morphism ϕ. The Perron-Frobenius eigenvalue of M_{ϕ} is φ = \frac{1}{2}(\sqrt{5} + 1). Since all the letters of \{a, b, c, d, e\} occur in ϕ^{ω}(a), then x is φ-substitutive by Proposition 23.

Proposition 25. The sequence x is not k-automatic for any k ∈ ℕ_{≥2}.

Proof. Proceed by contradiction and suppose that there exists an integer k ≥ 2 such that x is k-automatic. Then, by Theorem 2, x is also k-substitutive. Indeed, it is not difficult to see that the Perron-Frobenius eigenvalue of the matrix associated with a k-uniform morphism is the integer k. Clearly, k and φ are two multiplicatively independent real numbers. Thus, by Theorem 1, x is ultimately periodic. This is impossible.

Corollary 26. The sequence (a_{n})_{n≥0} is not k-regular for any k ∈ ℕ_{≥2}.

Proof. Suppose that the sequence (a_{n})_{n≥0} is k-regular for some k ≥ 2. Then by Proposition 3, the sequence (a_{n} mod 3)_{n≥0} is k-automatic, and so is x. This contradicts Proposition 25.

We end this section with the following open problem.

Problem 27. Let us define an increasing sequence b = (b_{n})_{n≥0} satisfying {b_{n} | n ∈ N} = {m ∈ N | u_{m} = 0} (sequence A317544 in [15]). This is the characteristic sequence of 0’s in the iPD sequence u. We have

b = 0, 2, 3, 4, 6, 8, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, ….

Is the sequence b k-regular for some k ≥ 2?

Remark 28. After submission of the present paper for publication, Ł. Merta contacted us with a different proof of Corollary 26 that uses his work on the Baum-Sweet sequence [10]. In this note, we only sketch this other proof. We let bs = (bs_{n})_{n≥0} denote the Baum-Sweet sequence (indexed by A086747 in [15]). First, using Proposition 10 and recurrence relations satisfied by bs, one can prove that u_{2n+1} = bs_{n+1} for all n ≥ 0. Then, if ℓ = (ℓ_{n})_{n≥0} is the characteristic sequence of 1’s in the Baum-Sweet sequence bs, we deduce that a_{n} = 2ℓ_{n+1} −1 for all n ≥ 0. From the stability properties of k-regular sequences (see [4]), if a was k-regular for some k ≥ 2, then ℓ would also be, which contradicts [10, Theorem 2.6].

6 Acknowledgment

We thank Ł. Merta for pointing out the connection between the iPD sequence u and the Baum-Sweet sequence bs, giving yet another way to prove that the characteristic sequence of 1’s in u is not k-regular for any k ≥ 2.

We also thank the anonymous referee for suggesting the simplified proof of Proposition 16.

References

[1] G. Allouche, J.-P. Allouche and J. Shallit, Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpiński et morphismes de monoïde, Ann. Inst. Fourier (Grenoble) 56 (2006), 2115–2130.

[2] J.-P. Allouche, A. André, J. Berstel, S. Brlek, W. Jockusch, S. Plouffe and B. E. Sagan, A relative of the Thue-Morse sequence, Discrete Math. 139 (1995), 455–461.

[3] J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and Their Applications, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, 1999, pp. 1–16.

[4] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

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

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

[7] F. Durand, Cobham’s theorem for substitutions, J. Eur. Math. Soc. 13 (2011), 1799– 1814.

[8] P. Fatou, Séries trigonométriques et séries de Taylor, Acta Math. 30 (1906), 335–400.

[9] M. Gawron and M. Ulas, On formal inverse of the Prouhet-Thue-Morse sequence, Discrete Math. 339 (2016), 1459–1470.

[10] Ł. Merta, Composition inverses of the variations of the Baum-Sweet sequence, 2018.

Preprint available at https://arxiv.org/abs/1803.00292.

[11] Ł. Merta, Formal inverses of the generalized Thue-Morse sequences and variations of the Rudin-Shapiro sequence, 2018. Preprint available at https://arxiv.org/abs/1810.

03533.

[12] M. Rigo, Formal Languages, Automata and Numeration Systems. 1. Introduction to Combinatorics on Words, Networks and Telecommunications Series, John Wiley & Sons, 2014.

[13] M. Rigo, Formal Languages, Automata and Numeration Systems. 2. Applications to Recognizability and Decidability, Networks and Telecommunications Series, John Wiley & Sons, 2014.

[14] L. Schaeffer, Deciding Properties of Automatic Sequences, Master’s Thesis, University of Waterloo, Waterloo, Ontario, 2013.

[15] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: formal inverse, period-doubling sequence, Fibonacci sequence, automatic sequence, k-regular sequence, Christol’s theorem.

(Concerned with sequences \underline{A079523}, \underline{A086747}, \underline{A096268}, \underline{A121539}, \underline{A317542}, \underline{A317543}, and \underline{A317544}.)

Received September 10 2018; revised versions received December 5 2018. Published in Journal of Integer Sequences, December 5 2018.

Return to Journal of Integer Sequences home page.