Abelian Complexity Function of the Tribonacci Word

Ondřej Turek Nuclear Physics Institute Academy of Sciences of the Czech Republic 250 68 Řež Czech Republic and Bogolyubov Laboratory of Theoretical Physics Joint Institute for Nuclear Research 141980 Dubna Russia

                  o.turek@ujf.cas.cz

Abstract

According to a result of Richomme, Saari and Zamboni, the abelian complexity of the Tribonacci word satisfies ρ^{ab}(n) ∈ {3, 4, 5, 6, 7} for each n ∈ ℕ. In this paper we derive an automaton that evaluates the function ρ^{ab}(n) explicitly. The automaton takes the Tribonacci representation of n as its input; therefore, (ρ^{ab}(n))_{n∈ℕ} is an automatic sequence in a generalized sense. Since our evaluation of ρ^{ab}(n) uses O(log n) operations, it is fast even for large values of n. Our result also leads to a solution of an open problem proposed by Richomme et al. concerning the characterization of those n for which ρ^{ab}(n) = c with c belonging to {4, 5, 6, 7}. In addition, we apply the same approach on the 4-bonacci word. In this way we find a description of the abelian complexity of the 4-bonacci word, too.

1 Introduction

The abelian complexity of a word u is a function ℕ → ℕ that counts the number of pairwise non-abelian-equivalent factors of u of length n. The term was introduced by Richomme, Saari and Zamboni [14] in 2009, and since then it has been extensively studied [2, 3, 6, 8, 11, 18, 19]. In one of the first papers on the subject, Richomme, Saari and Zamboni [15] examined the Tribonacci word t \underline{A080843}, which is the fixed point of the substitution 0 ↦ 01, 1 ↦ 02, 2 ↦ 0, and they showed that ρ_{t}^{ab}(n) ∈ {3, 4, 5, 6, 7} for all n. They also characterized those n for which ρ_{t}^{ab}(n) = 3, and proposed the following open problem: for each c ∈ {4, 5, 6, 7}, characterize those n for which ρ_{t}^{ab}(n) = c.

Explicit characterization of ρ_{u}^{ab}(n) of a given infinite word u is generally a difficult task, particularly in case of words defined over alphabets consisting of more than two letters. For example, despite the fact that a recurrent word over a ternary alphabet with constant abelian complexity equal to 3 for all n ∈ ℕ has been already constructed [14], there seems to be no other nontrivial example to date of a recurrent m-ary word with m ≥ 3 whose abelian complexity function has been precisely determined. In particular, the problem of precise characterization of the abelian complexity ρ_{t}^{ab}(n) of the Tribonacci word t, which is a ternary word, has remained open since 2009.

Recently Mousavi and Shallit [12] showed that many properties of the Tribonacci word, such as the aperiodicity, powers, palindromes etc., could be examined purely mechanically with the help of finite automata. Although in principle their method could also be used for the study of the characteristics of the abelian complexity function of the Tribonacci word, it turns out to be not computationally feasible. In this paper we propose a related method that is particularly designed for dealing with abelian properties (primarily with abelian complexity and the balance properties). Our approach is less general than the one of Mousavi and Shallit, but it is efficient enough to explicitly obtain a finite automaton that computes the function ρ_{t}^{ab}(n). The automaton in question features a very small set of states, consisting of less than 70 elements. Consequently, it can be easily implemented on any computer (a powerful machine is not needed), and the calculation can be even performed by hand. The automaton takes the Tribonacci representation of n as its input, which means that the sequence (ρ_{t}^{ab}(n))_{n∈ℕ} \underline{A216190} is T -automatic (or “Tribonacci-automatic”) in the sense of Shallit [1, 16].

Our approach relies on the technique of abelian co-decomposition [19], which was originally developed as a tool for proving that the abelian complexity of a recurrent word attains a certain value infinitely often. As a result, our construction of the automaton can be generalized to certain other words as well.

The paper is organized as follows. In Section 2 we provide the necessary notation related to abelian complexity, the Tribonacci word and finite automata. Section 3 summarizes basic facts about abelian co-decomposition. Section 4 contains the core of the paper: we show that there exists a finite number of sets Z_{1}, …, Z_{M} such that each n ∈ ℕ can be associated with a certain Z_{q} via the Tribonacci representation of n. Since each of those sets is related to a certain value of the abelian complexity, the indices 1, …, M can be regarded as states of a finite automaton that evaluates ρ_{t}^{ab}(n). Section 5 is devoted to the first and easy application of the findings from Section 4: we demonstrate that the abelian complexity of the Tribonacci word takes values in {3, 4, 5, 6, 7}. Although this fact is already known [15], it illustrates the applicability of our approach. The main result of the paper is presented in Section 6. We derive a formula for evaluating the abelian complexity of the Tribonacci word on the basis of results of Section 4. In particular, we show that the abelian complexity can be calculated by a finite automaton with 278 states. This result is further improved in Section 7, where the size of the automaton is reduced from 278 to 68 states. It is easy to transform this automaton into an automaton that decides, for any n ∈ ℕ, whether ρ_{t}^{ab}(n) attains a given value c ∈ {3, 4, 5, 6, 7}, which provides a solution of the problem of Richomme et al. In Section 8, we demonstrate that the method allows one to examine the abelian complexity function of other m-bonacci words. In particular, we present results on the 4-bonacci word; they show that the abelian complexity of m-bonacci words gains new properties when m exceeds 3. The paper is concluded by Section 9, in which we discuss other applications and generalizations of the method.

2 Preliminaries

Let us consider a set A = {0, 1, 2, …, m − 1} (alphabet) consisting of m symbols (letters) 0, 1, …, m − 1. Concatenations of letters from A are called words. Let A^{∗} denote the free monoid of all finite words over A including the empty word ε. The length of a word w = w_{0}w_{1}w_{2} ⋯ w_{n−1} ∈ A^{∗} is the number of its letters, |w| = n. The symbol |w|_{ℓ} for ℓ ∈ A and w ∈ A^{∗} stands for the number of occurrences of the letter ℓ in the word w.

The set of all infinite words over A is denoted by A^{ℕ}. We say that an infinite word u is recurrent if every factor of u occurs infinitely many times in u.

A finite word w is a factor of a (finite or infinite) word u if there exists a finite word x and a (finite or infinite, respectively) word y such that u = xwy. If x = ε, the factor w is called a prefix of u.

For any word w ∈ A^{∗} and k ∈ ℕ we write w^{k} = \overbrace{ww ⋯ w}^{k times}. Similarly, we set w^{0} = ε. If a word v ∈ A^{ℕ} has the prefix w^{k} for k ∈ ℕ, then the symbol w^{−k}v stands for the word satisfying w^{k}w^{−k}v = v.

The Parikh vector of w is the m-tuple Ψ(w) = (|w|_{0}, |w|_{1}, …, |w|_{m−1}); note that |w|_{0} + |w|_{1} + ⋯ + |w|_{m−1} = |w|. For any given infinite word u, let P_{u}(n) denote the set of all Parikh vectors corresponding to factors of u having the length n, i.e.,

P_{u}(n) = {Ψ(w) | w is a factor of u, |w| = n} .

The abelian complexity of a word u is the function ρ_{u}^{ab} : ℕ → ℕ defined as

ρ_{u}^{ab}(n) = #P_{u}(n),  (1)

where # denotes the cardinality.

It is useful to introduce the relative Parikh vector [19], which is defined for any factor w of u of length n as

Ψ_{u}^{rel}(w) = Ψ(w) − Ψ(u_{[n]}) ,

where u_{[n]} is the prefix of u of length n. Since the subtrahend Ψ(u_{[n]}) depends only on the length of w and not on w itself, the set of relative Parikh vectors corresponding to the length n,

P_{u}^{rel}(n) := {Ψ_{u}^{rel}(w) | w is a factor of u, |w| = n} ,

has the same cardinality as P_{u}(n). Hence we obtain, with regard to (1),

ρ_{u}^{ab}(n) = #P_{u}^{rel}(n) .  (2)

An infinite word u is said to be b-balanced for a certain b ∈ ℕ if for every ℓ ∈ A and for every pair of factors v, w of u such that |v| = |w|, the inequality ||v|_{ℓ} − |w|_{ℓ}| ≤ b holds. If u is a b-balanced word, the components of relative Parikh vectors are bounded by b [19]. Therefore, the set of all relative Parikh vectors ⋃_{n∈ℕ} P_{u}^{rel}(n) is finite for any b-balanced word u.

This paper is primarily concerned with the Tribonacci word t, which is defined over the alphabet A = {0, 1, 2} as the fixed point of the substitution

\begin{aligned}φ_{t} : & 0 & ↦ & 01 \\ & 1 & ↦ & 02 \\ & 2 & ↦ & 0 \end{aligned}  (3)

i.e.,

t = lim_{k→∞} φ_{t}^{k}(0) = 01020100102010102010010201020100102010102010 · · · .

It is easy to check that φ_{t}^{j}(0) = φ_{t}^{j−1}(0)φ_{t}^{j−2}(0)φ_{t}^{j−3}(0) for every j ≥ 3. Hence, the lengths of factors φ_{t}^{j}(0) satisfy the recurrence relation |φ_{t}^{j}(0)| = |φ_{t}^{j−1}(0)| + |φ_{t}^{j−2}(0)| + |φ_{t}^{j−3}(0)|. Comparing this relation with the Tribonacci recurrence relation T_{j} = T_{j−1} + T_{j−2} + T_{j−3}, we conclude that |φ_{t}^{j}(0)| = T_{j+3} for every j ∈ ℕ ∪ {0}, where (T_{j})_{j≥0} = (0, 0, 1, 1, 2, 4, 7, …) is the sequence of Tribonacci numbers \underline{A000073}. Any n ∈ ℕ can be written as a sum of Tribonacci numbers with binary coefficients,

n = ∑_{j=0}^{k} d_{j}T_{j+3} for d_{j} ∈ {0, 1}, k ∈ ℕ ∪ {0} .  (4)

If coefficients d_{j} ∈ {0, 1} are obtained by the greedy algorithm, they form the normal T - representation (also called the Tribonacci representation) of n, which we denote by the symbol ⟨n⟩_{T}:

⟨n⟩_{T} = d_{k}d_{k−1} ⋯ d_{1}d_{0} .  (5)

For n = 0, we have ⟨0⟩_{T} = ε. Table 1 shows normal T -representations of several small integers. The constant k in expansion (5) does not need to be chosen minimal, i.e., a normal T -representation can start with a block of zeros. For example, the representations ⟨n⟩_{T} = 011 and ⟨n⟩_{T} = 00011 are both equivalent to ⟨n⟩_{T} = 11 and correspond to n = 3.

\begin{matrix}n & ⟨n⟩_{T} & n & ⟨n⟩_{T} & n & ⟨n⟩_{T} & n & ⟨n⟩_{T} & n & ⟨n⟩_{T} \\ 1 & 1 & 4 & 100 & 7 & 1000 & 10 & 1011 & 13 & 10000 \\ 2 & 10 & 5 & 101 & 8 & 1001 & 11 & 1100 & 14 & 10001 \\ 3 & 11 & 6 & 110 & 9 & 1010 & 12 & 1101 & 15 & 10010 \end{matrix}

Table 1: Normal T -representations of the numbers 1, …, 15.

The substitution (3) is a special case of a simple Parry substitution, defined over the alphabet A = {0, 1, …, m − 1} in the way

φ : 0 ↦ 0^{α_{0}}1 ; 1 ↦ 0^{α_{1}}2 ; ⋮ ; m − 2 ↦ 0^{α_{m−2}}(m − 1) ; m − 1 ↦ 0^{α_{m−1}}  (6)

with α_{i} ∈ ℕ ∪ {0} satisfying the conditions α_{0} ≥ 1 and α_{ℓ} ≤ α_{0} for all ℓ ∈ A [9, 13]. We call the fixed point of (6) a simple Parry word; in this sense the Tribonacci word is an example of a simple Parry word. Simple Parry words appear in nonstandard numeration systems. Without going into details, let us mention here that the order of letters in the fixed point of (6) corresponds to the order of lengths of gaps between so-called β-integers for β > 1 being a zero of the polynomial α_{m−1}x^{m−1} + α_{m−2}x^{m−2} + ⋯ + α_{1}x + α_{0} [17]. Since all simple Parry substitutions have common structure, the combinatorial properties of their fixed points can be often examined in a similar way. In particular, the approach we are going to apply in this paper is based on a method that can handle fixed points of all substitutions of type (6). Therefore, it is convenient here to formulate the representation (5) more generally. Consider a simple Parry substitution φ, and set U_{j} = |φ^{j}(0)| for every j ∈ ℕ ∪ {0}. Any n ∈ ℕ can be represented as a sum

n = ∑_{j=0}^{k} d_{j}U_{j}

with integer coefficients d_{j}. If coefficients d_{j} are obtained by the greedy algorithm, the sequence d_{k}d_{k−1} ⋯ d_{1}d_{0} is called the normal U-representation of n [10] and denoted

⟨n⟩_{U} = d_{k}d_{k−1} ⋯ d_{1}d_{0} .  (7)

It can be shown that the coefficients in (7) satisfy d_{j} ∈ {0, 1, …, α_{0}} for all j = 0, 1, …, k.

A deterministic finite automaton with output (DFAO) [1] is an extension of the deterministic finite automaton (DFA) model. A DFAO is defined as a 6-tuple (Q, Σ, δ, q_{0}, Δ, τ), where Q is a finite set of states, Σ is the finite input alphabet, δ : Q × Σ → Q is the transition function, q_{0} is the initial state, Δ is the output alphabet, and τ : Q → Δ is the output function. If we extend the domain of δ to Q × Σ^{∗} by defining δ(q, ϵ) = q for all q ∈ Q, and δ(q, xa) = δ(δ(q, x), a) for all q ∈ Q, x ∈ Σ^{∗} and a ∈ Σ, a DFAO defines a function f : Σ^{∗} → Δ, given as

f(w) = τ(δ(q_{0}, w)) for w ∈ Σ^{∗}.

Let [n]_{k} denote the representation of n ∈ ℕ in base k for a certain integer k ≥ 2. A sequence (a_{n})_{n∈ℕ} over a finite alphabet Δ is called k-automatic if there exists a DFAO with Σ = {0, 1, …, k − 1} such that a_{n} = τ(δ(q_{0}, [n]_{k})) for all n ∈ ℕ.

Shallit [16] introduced the concept of generalized automatic sequences, which are generated by automata using nonstandard representations instead of ordinary base-k representations. In particular, we say that a sequence (a_{n})_{n∈ℕ} with values in a finite alphabet Δ is U-automatic if there exists a DFAO (Q, Σ, δ, q_{0}, Δ, τ) such that

a_{n} = τ(δ(q_{0}, ⟨n⟩_{U})) for all n ∈ ℕ,

where ⟨n⟩_{U} is the normal U-representation defined above.

3 Abelian co-decomposition

Abelian co-decomposition, which we briefly summarize in this section, has been developed as a tool for calculating ρ_{u}^{ab}(n) of recurrent words [19]. The main idea is roughly the following: the method uses the normal U-representation ⟨n⟩_{U} to associate any n ∈ ℕ with a certain set Z_{u}(n) of pairs of factors. At the same time the structure of the set Z_{u}(n) is designed in a way that allows to find quickly the set of relative Parikh vectors P_{u}^{rel}(n), and, consequently, to obtain the value ρ_{u}^{ab}(n) by formula (2).

Let v, w be any factors of u such that Ψ(v) = Ψ(w) (in particular, |v| = |w|). We factorize them as follows:

\begin{aligned}v & = & z_{0} z_{1} z_{2} ⋯ z_{h} \\ w & = & z̃_{0} z̃_{1} z̃_{2} ⋯ z̃_{h} \end{aligned}  (8)

where z_{0}, z_{1}, …, z_{h} and z̃_{0}, z̃_{1}, …, z̃_{h} are non-empty words satisfying Ψ(z̃_{j}) = Ψ(z_{j}) for all j ∈ {0, 1, …, h}. The set of pairs

{(z_{0} ; z̃_{0}) , (z_{1} ; z̃_{1}) , (z_{2} ; z̃_{2}) , ⋯, (z_{h} ; z̃_{h})}  (9)

is called the abelian co-decomposition of the pair ( \begin{matrix}v \\ w \end{matrix} ).

An abelian co-decomposition (9) exists for any v, w such that Ψ(v) = Ψ(w), because one can take, e.g., \{( \begin{matrix}v \\ w \end{matrix} )\}. The decomposition (8) is in general not unique (see Example 1 below), but it can be made unique by an additional requirement. Here we will adopt, throughout the whole paper, the following convention: The number h in equation (8) is chosen to be maximal. The abelian co-decomposition satisfying this requirement will be denoted Dec( \begin{matrix}v \\ w \end{matrix} ).

Example 1. Let v = 0102, w = 1020. There exist two possible decompositions (8):

\begin{aligned}v & = & \overbrace{0102}^{z_{0}} \\ w & = & \underbrace{1020}_{z̃_{0}} \end{aligned}  or  \begin{aligned}v & = & \overbrace{01}^{z_{0}} \overbrace{02}^{z_{1}} \\ w & = & \underbrace{10}_{z̃_{0}} \underbrace{20}_{z̃_{1}} \end{aligned}

Hence the abelian co-decomposition of the pair ( \begin{matrix}0102 \\ 1020 \end{matrix} ), obeying our convention of maximality of number of elements, is

Dec (\begin{matrix}v \\ w \end{matrix}) = \{(\begin{matrix}01 \\ 10 \end{matrix}) , (\begin{matrix}02 \\ 20 \end{matrix})\} .

For any pair ( \begin{matrix}v \\ w \end{matrix} ) of factors of u such that |v| = |w|, we introduce the following set of vectors:

Vect (\begin{matrix}v \\ w \end{matrix}) := \{Ψ(s) − Ψ(r) | r is a prefix of v, s is a prefix of w, |s| = |r|\} .  (10)

Example 2.

Vect (\begin{matrix}0102 \\ 1020 \end{matrix}) =\{ Ψ(1) − Ψ(0), Ψ(10) − Ψ(01), Ψ(102) − Ψ(010), Ψ(1020) − Ψ(0102) \}
={(−1, 1, 0), (0, 0, 0), (−1, 0, 1)}.

Let u be the fixed point of (6). For every n ∈ ℕ, we define the set [19, Def. 3.7 and Prop. 4.8]

Z_{u}(n) := Dec (\begin{matrix}φ^{K+R}(0) \\ u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} \end{matrix}) ,  (11)

where K is any integer such that n ≤ U_{K} and R is a constant that we choose using the formula

R = m − 1 + min{j | (∀ℓ ∈ A)(φ^{j}(ℓ) has the prefix 0)} .  (12)

Note that the factors φ^{K+R}(0) and u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} are obviously abelian equivalent, thus we are allowed to consider their abelian co-decomposition. In Proposition 3 we will see that the right-hand side of (11) is independent of the choice of K, i.e., the symbol Z_{u}(n) is well-defined.

Proposition 3. Let R be given by equation (12). For any n ∈ ℕ and for any integer K such that n ≤ U_{K} we have

Dec (\begin{matrix}φ^{K+R}(0) \\ u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} \end{matrix}) = ⋃_{ℓ∈A} Dec (\begin{matrix}φ^{K_{0}+R−m+1}(ℓ) \\ u_{[n]}^{−1}φ^{K_{0}+R−m+1}(ℓ)u_{[n]} \end{matrix}) ,  (13)

where K_{0} = min{K′ ∈ ℕ∪{0} | n ≤ U_{K′}}. In particular, the right-hand side of equation (11) is independent of the choice of K.

Proof. Let us take an arbitrary K such that n ≤ U_{K}. Since we have R ≥ m − 1 by (12), we can write

φ^{K+R}(0) = φ^{K_{0}}(φ^{R−m+1}(φ^{m−1+K−K_{0}}(0))) .

It is easy to see that for every j ≥ m − 1, the factor φ^{j}(0) contains each letter from A, which follows from (6). We have K ≥ K_{0}, thus m − 1 + K − K_{0} ≥ m − 1. Therefore, the factor φ^{m−1+K−K_{0}}(0) contains each letter ℓ ∈ A. Hence

φ^{K+R}(0) = φ^{K_{0}}(w_{0}w_{1}w_{2} ⋯ w_{h}) ,  (14)

where

{w_{0}, w_{1}, w_{2}, …, w_{h}} = {φ^{R−m+1}(ℓ) | ℓ ∈ A} .

The definition of R requires that the factor φ^{R−m+1}(ℓ) has the prefix 0 for any ℓ ∈ A. As a result, each factor of type φ^{K_{0}}(φ^{R−m+1}(ℓ)) has the prefix φ^{K_{0}}(0). At the same time we know, with regard to the assumption n ≤ U_{K_{0}}, that u_{[n]} is a prefix of φ^{K_{0}}(0). To sum up, the words φ^{R−m+1}(ℓ) for ℓ ∈ A have u_{[n]} as their prefixes. Now we can rewrite equation (14) as follows:

φ^{K+R}(0) = φ^{K_{0}}(w_{0})φ^{K_{0}}(w_{1})φ^{K_{0}}(w_{2}) ⋯ φ^{K_{0}}(w_{h}) = z_{0}z_{1}z_{2} ⋯ z_{h} ,

where the factors z_{0}, z_{1}, z_{2}, …, z_{h} satisfy

{z_{0}, z_{1}, z_{2}, …, z_{h}} = {φ^{K_{0}+R−m+1}(ℓ) | ℓ ∈ A} ,  (15)

and, moreover, u_{[n]} is a prefix of z_{j} for every j ∈ {0, 1, …, h}. This allows us to decompose

φ^{K+R}(0)  =  z_{0}  z_{1}  z_{2}  ⋯  z_{h}
u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} = u_{[n]}^{−1}z_{0}u_{[n]} u_{[n]}^{−1}z_{1}u_{[n]} u_{[n]}^{−1}z_{2}u_{[n]} ⋯ u_{[n]}^{−1}z_{h}u_{[n]}

Factors z_{j} and z̃_{j} = u_{[n]}^{−1}z_{j}u_{[n]} are abelian equivalent for every j = 0, 1, … h, thus ⋃_{j=0}^{h} {( z_{j} ; z̃_{j} )}

is an abelian co-decomposition of ( \begin{matrix}φ^{K_{0}+R}(0) \\ u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} \end{matrix} ). The “maximal” (i.e., having maximal

number of elements) abelian co-decomposition of ( \begin{matrix}φ^{K_{0}+R}(0) \\ u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} \end{matrix} ) is obviously obtained as

the union of the “maximal” abelian co-decompositions of \binom{z_{j}}{z̃_{j}} for j = 0, 1, … h, i.e.,

Dec (\begin{matrix}φ^{K+R}(0) \\ u_{[n]}^{−1}φ^{K+R}(0)u_{[n]} \end{matrix}) = ⋃_{j=0}^{h} Dec (\begin{matrix}z_{j} \\ u_{[n]}^{−1}z_{j}u_{[n]} \end{matrix}) .  (16)

Finally, equation (15) gives the identity

⋃_{j=0}^{h} Dec (\begin{matrix}z_{j} \\ u_{[n]}^{−1}z_{j}u_{[n]} \end{matrix}) = ⋃_{ℓ∈A} Dec (\begin{matrix}φ^{K_{0}+R−m+1}(ℓ) \\ u_{[n]}^{−1}φ^{K_{0}+R−m+1}(ℓ)u_{[n]} \end{matrix}) .  (17)

Combining equations (16) and (17) one gets equation (13).

The set Z_{u}(n) together with the map Vect allow to determine the set of relative Parikh vectors corresponding to the number n. Indeed, one can prove that [19, Prop. 3.8]

P_{u}^{rel}(n) = ⋃_{(z ; z̃)∈Z_{u}(n)} Vect (z ; z̃)  (18)

for any n ∈ ℕ. Consequently, if Z_{u}(n) is known, it is a trivial task to calculate ρ_{u}^{ab}(n) using the formula

ρ_{u}^{ab}(n) = # ⋃_{(z ; z̃)∈Z_{u}(n)} Vect (z ; z̃) ,  (19)

which follows immediately from equations (2) and (18).

Example 4. Let us calculate Z_{t}(1). We have t_{[1]} = 0. Since 1 ≤ T_{0} = 1 and R = 3 − 1 + min{1, 2, 3, …} = 3, we shall use formula (11) with K + R = 0 + 3 = 3. Therefore, from (11),

Z_{t}(1) = Dec (\begin{matrix}φ_{t}^{3}(0) \\ 0^{−1}φ_{t}^{3}(0)0 \end{matrix}) .

We have

\begin{aligned}φ_{t}^{3}(0) & = & 01 02 01 0 \\ 0^{−1}φ_{t}^{3}(0)0 & = & 10 20 10 0 \end{aligned}

whence we obtain

Z_{t}(1) = \{(\begin{matrix}0 \\ 0 \end{matrix}) , (\begin{matrix}01 \\ 10 \end{matrix}) , (\begin{matrix}02 \\ 20 \end{matrix})\} .

Let us continue the example and demonstrate the application of equations (18) and (19). We have

Vect\binom{0}{0} = \{(0, 0, 0)\}, Vect\binom{01}{10} = \{(−1, 1, 0), (0, 0, 0)\}, Vect\binom{02}{20} = \{(−1, 0, 1), (0, 0, 0)\}.

Equation (18) then gives P_{t}^{rel}(1) = {(0, 0, 0), (−1, 1, 0), (−1, 0, 1)}, and hence, from Eq. (19) we get ρ_{t}^{ab}(1) = 3. This calculation has an illustrative purpose only – the result ρ_{t}^{ab}(1) = 3 could be of course found much easier from equation (1).

The essential point is that sets Z_{u}(n) does not need to be calculated from definition (11) for each n ∈ ℕ. We are going to present a recurrence relation that will allow us to express Z_{u}(N) in terms of Z_{u}(n) for a certain n < N. Let N ∈ ℕ be an integer with the normal U-representation ⟨N⟩_{U} = d_{k}d_{k−1} ⋯ d_{1}d_{0}. Let us take a j ∈ [1, k], and split the sequence d_{k}d_{k−1} ⋯ d_{1}d_{0} into two parts in the way d_{k} ⋯ d_{j+1}, d_{j} ⋯ d_{0}. Note that both parts are valid normal U-representations of certain integers; we write them as n and p, as shown in equation (20).

⟨N⟩_{U} = \underbrace{d_{k} ⋯ d_{j+1}}_{⟨n⟩_{U}} \underbrace{d_{j} ⋯ d_{0}}_{⟨p⟩_{U}}  (20)

Then we have the following result [19, Prop. 5.1]: Proposition 5. Let the numbers N, n, p and k, j obey (20). If φ^{j+1}(z̃) has the prefix u_{[p]} for

all (z ; z̃) ∈ Z_{u}(n), then Z_{u}(N) can be calculated from Z_{u}(n) using the formula

Z_{u}(N) = ⋃_{(z ; z̃)∈Z_{u}(n)} Dec (\begin{matrix}φ^{j+1}(z) \\ u_{[p]}^{−1}φ^{j+1}(z̃)u_{[p]} \end{matrix}) .  (21)

For dealing with the Tribonacci word, the following corollary will come in handy. It is obtained straightforwardly from equation (21) by choosing j = 0 and p = 0 or p = 1. Corollary 6. We have

⟨N⟩_{T} = ⟨n⟩_{T} 0  ⇒  Z_{t}(N) = ⋃_{(z ; z̃)∈Z_{t}(n)} Dec (\begin{matrix}φ_{t}(z) \\ φ_{t}(z̃) \end{matrix}) ,

⟨N⟩_{T} = ⟨n⟩_{T} 1  ⇒  Z_{t}(N) = ⋃_{(z ; z̃)∈Z_{t}(n)} Dec (\begin{matrix}φ_{t}(z) \\ 0^{−1}φ_{t}(z̃)0 \end{matrix}) .

Since the abelian co-decompositions Dec (\begin{matrix}φ_{t}(z) \\ φ_{t}(z̃) \end{matrix}) and Dec (\begin{matrix}φ_{t}(z) \\ 0^{−1}φ_{t}(z̃)0 \end{matrix}) will be often

used throughout the paper, we introduce a shorthand for them. Let z, z̃ be factors of t satisfying Ψ(z) = Ψ(z̃), and let ζ stand for \binom{z}{z̃}. We define the symbols

D_{0}(ζ) := Dec (\begin{matrix}φ_{t}(z) \\ φ_{t}(z̃) \end{matrix})  and D_{1}(ζ) := Dec (\begin{matrix}φ_{t}(z) \\ 0^{−1}φ_{t}(z̃)0 \end{matrix}) .  (22)

Recall that the numbers d_{i} in the normal T -representation (5) attain the values 0 and 1 only. The statement of Corollary 6 can be thus formulated as

⟨N⟩_{T} = ⟨n⟩_{T} d  ⇒  Z_{t}(N) = ⋃_{ζ∈Z_{t}(n)} D_{d}(ζ) .  (23)

Formula (23) is crucial for us. It says how the set Z_{t}(n) is transformed when a digit d is added to ⟨n⟩_{T}. For this reason it will be sometimes refered to as the “transformation formula”.

From now on we will focus on the Tribonacci word. Therefore, we can simplify the notation by dropping the subscript t from symbols ρ_{t}^{ab}, P_{t}^{rel}, φ_{t}, Z_{t}.

4 Sets Z(n)

This section can be regarded as the core of the paper. Examining the structure of sets Z(n), we find out that only finitely many of them are mutually different. In other words, we show that there exist sets Z_{1}, Z_{2}, …, Z_{M} such that for any n ∈ ℕ, the set Z(n) is equal to Z_{q} for a certain q ∈ {1, …, M}. In addition, we express Z_{1}, Z_{2}, …, Z_{M} explicitly.

Lemma 7. Let an N ∈ ℕ have the representation ⟨N⟩_{T} = 1d_{k−1} ⋯ d_{1}d_{0}. Let n be the number with the representation ⟨n⟩_{T} = 1d_{k−1} ⋯ d_{1}, i.e., ⟨N⟩_{T} = ⟨n⟩_{T} d_{0}. Then

Z(N) = ⋃_{ζ∈Z(n)} D_{0}(ζ)  or  Z(N) = ⋃_{ζ∈Z(n)} D_{1}(ζ) .  (24)

Lemma 7 is just a trivial consequence of the transformation formula (23). The main result of this section follows.

Theorem 8. There exist a 56-element set

Z_{super} = {ζ_{1}, ζ_{2}, ζ_{3}, …, ζ_{56}}

and 277 of its subsets Z_{1}, Z_{2}, …, Z_{277} ⊂ Z_{super} such that

(∀n ∈ ℕ) (∃q ∈ {1, 2, …, 277}) (Z(n) = Z_{q}) .  (25)

Proof. We begin the proof by exploring Z(n) for n having a 1-digit representation, i.e., ⟨n⟩_{T} = d_{0}. Trivially, there is one single positive number having such representation, namely n = 1. We know from Example 4 that

Z(1) = {ζ_{1}, ζ_{2}, ζ_{3}}

for

ζ_{1} = (\begin{matrix}0 \\ 0 \end{matrix}) , ζ_{2} = (\begin{matrix}01 \\ 10 \end{matrix}) , ζ_{3} = (\begin{matrix}02 \\ 20 \end{matrix}) .

From now on we let Z_{1} denote the set Z(1).

In the next step we proceed to exploring Z(N) for those N having 2-digit representations, i.e., ⟨N⟩_{T} = 1d_{0} for d_{0} ∈ {0, 1}. We apply Lemma 7 with k = 1. Writing ⟨N⟩_{T} = 1d_{0} in the form ⟨n⟩_{T} d_{0} implies ⟨n⟩_{T} = 1, and hence n = 1. For such N and n, equations (24) read

Z(N) = ⋃_{ζ∈Z_{1}} D_{0}(ζ) or Z(N) = ⋃_{ζ∈Z_{1}} D_{1}(ζ) .

Since Z_{1} = {ζ_{1}, ζ_{2}, ζ_{3}}, we need to find D_{0}(ζ_{j}) and D_{1}(ζ_{j}) for j = 1, 2, 3, which is an easy task. Let us start with D_{0}(ζ_{j}). With regard to (22), we have to calculate

\begin{aligned}φ(0) & = & 0 1 & φ(01) & = & 0 102 & φ(02) & = & 0 10 \\ φ(0) & = & 0 1 & φ(10) & = & 0 201 & φ(20) & = & 0 01 \end{aligned}

Hence

D_{0}(ζ_{1}) = {ζ_{1}, ζ_{4}} , D_{0}(ζ_{2}) = {ζ_{1}, ζ_{5}} , D_{0}(ζ_{3}) = {ζ_{1}, ζ_{6}} ,  (26)

where ζ_{1} = ( \begin{matrix}0 \\ 0 \end{matrix} ) has been defined above and

ζ_{4} = (\begin{matrix}1 \\ 1 \end{matrix}) , ζ_{5} = (\begin{matrix}102 \\ 201 \end{matrix}) , ζ_{6} = (\begin{matrix}10 \\ 01 \end{matrix}) .

A similar calculation leads to sets D_{1}(ζ_{j}) for j = 1, 2, 3; see (22). We have

\begin{aligned}φ(0) & = & 01 & φ(01) & = & 0102 & φ(02) & = & 0 1 0 \\ 0^{−1}φ(0)0 & = & 10 & 0^{−1}φ(10)0 & = & 2010 & 0^{−1}φ(20)0 & = & 0 1 0 \end{aligned}

hence

D_{1}(ζ_{1}) = {ζ_{2}} ,  D_{1}(ζ_{2}) = {ζ_{7}} ,  D_{1}(ζ_{3}) = {ζ_{1}, ζ_{4}}  (27)

for ζ_{1}, ζ_{2}, ζ_{4} defined above and

ζ_{7} = (\begin{matrix}0102 \\ 2010 \end{matrix}) .

To sum up, if ⟨N⟩_{T} = 1d_{0}, then

Z(N) = {ζ_{1}, ζ_{4}, ζ_{5}, ζ_{6}} := Z_{2} or Z(N) = {ζ_{1}, ζ_{2}, ζ_{4}, ζ_{7}} := Z_{3} .  (28)

We will list sets Z_{q} in Table 2. The elements ζ_{j} together with D_{0}(ζ_{j}) and D_{1}(ζ_{j}) will be listed in Table 3.

Now we can apply Lemma 7 again, this time for k = 2, in order to explore Z(N) for those N having 3-digit representations, ⟨N⟩_{T} = 1d_{1}d_{0}. Any such N can be written in the form ⟨n⟩_{T} d_{0} for ⟨n⟩_{T} = 1d_{1} and d_{0} ∈ {0, 1}. The representation of n has two digits, and hence Z(n) = Z_{2} or Z(n) = Z_{3} due to the result of the previous step. We thus need to apply equations (24) for Z(n) = Z_{2} and Z(n) = Z_{3}, which requires the knowledge of D_{0}(ζ_{j}) and D_{1}(ζ_{j}) for j = 1, …, 7. Sets D_{0}(ζ_{j}) and D_{1}(ζ_{j}) for j = 1, 2, 3 are already known; see equations (26), (27). Concerning j = 4, …, 7, a short calculation gives

\begin{matrix}D_{0}(ζ_{4}) = \{ζ_{1}, ζ_{8}\}, & D_{0}(ζ_{5}) = \{ζ_{1}, ζ_{9}\}, & D_{0}(ζ_{6}) = \{ζ_{1}, ζ_{10}\}, & D_{0}(ζ_{7}) = \{ζ_{1}, ζ_{6}, ζ_{11}\}, \\ D_{1}(ζ_{4}) = \{ζ_{3}\}, & D_{1}(ζ_{5}) = \{ζ_{1}, ζ_{10}\}, & D_{1}(ζ_{6}) = \{ζ_{12}\}, & D_{1}(ζ_{7}) = \{ζ_{1}, ζ_{4}, ζ_{8}\} \end{matrix} (29)

for

ζ_{8} = (\begin{matrix}2 \\ 2 \end{matrix}) , ζ_{9} = (\begin{matrix}2010 \\ 0102 \end{matrix}) , ζ_{10} = (\begin{matrix}201 \\ 102 \end{matrix}) , ζ_{11} = (\begin{matrix}20 \\ 02 \end{matrix}) , ζ_{12} = (\begin{matrix}0201 \\ 1020 \end{matrix}) .

Once we substitute Z(n) = Z_{2} and Z(n) = Z_{3} into equation (24) and use the known structure of Z_{2}, Z_{3} (cf. (28)) together with equations (26), (27) and (29), we get

Z(n) = Z_{2} ⇒
Z(N) = {ζ_{1}, ζ_{4}, ζ_{8}, ζ_{9}, ζ_{10}} =: Z_{4} or Z(N) = {ζ_{1}, ζ_{2}, ζ_{3}, ζ_{10}, ζ_{12}} =: Z_{6} ;
Z(n) = Z_{3} ⇒
Z(N) = {ζ_{1}, ζ_{4}, ζ_{5}, ζ_{6}, ζ_{8}, ζ_{11}} =: Z_{5} or Z(N) = {ζ_{1}, ζ_{2}, ζ_{3}, ζ_{4}, ζ_{7}, ζ_{8}} =: Z_{7} .

q {j | ζ_{j} ∈ Z_{q}}
1 1 ; 2 ; 3
2 1 ; 4 ; 5 ; 6
3 1 ; 2 ; 4 ; 7
4 1 ; 4 ; 8 ; 9 ; 10
5 1 ; 4 ; 5 ; 6 ; 8 ; 11
6 1 ; 2 ; 3 ; 10 ; 12
7 1 ; 2 ; 3 ; 4 ; 7 ; 8
8 1 ; 2 ; 4 ; 8 ; 9 ; 10
9 1 ; 4 ; 5 ; 6 ; 7 ; 13
10 1 ; 2 ; 3 ; 14 ; 15
11 1 ; 2 ; 3 ; 10 ; 12 ; 16
12 1 ; 2 ; 4 ; 7 ; 15 ; 17

⋮

277 1 ; 2 ; 4 ; 7 ; 15 ; 17 ; 22 ; 23 ; 24 ; 36 ; 43 ; 50

Table 2: Structure of sets Z_{q}.

j ζ_{j}  {i | ζ_{i} ∈ D_{0}(ζ_{j})} {i | ζ_{i} ∈ D_{1}(ζ_{j})} {i | ψ_{i}^{r} ∈ Vect(ζ_{j})}
1 ( \begin{matrix}0 \\ 0 \end{matrix} )  1;4  2  0
2 ( \begin{matrix}01 \\ 10 \end{matrix} )  1;5  7  0;1
3 ( \begin{matrix}02 \\ 20 \end{matrix} )  1;6  1;4  0;2
4 ( \begin{matrix}1 \\ 1 \end{matrix} )  1;8  3  0
5 ( \begin{matrix}102 \\ 201 \end{matrix} )  1;9  1;10  0;3
6 ( \begin{matrix}10 \\ 01 \end{matrix} )  1;10  12  0;4
7 ( \begin{matrix}0102 \\ 2010 \end{matrix} )  1;6;11  1;4;8  0;2;3
8 ( \begin{matrix}2 \\ 2 \end{matrix} )  1  1  0
9 ( \begin{matrix}2010 \\ 0102 \end{matrix} )  1;2;3  14  0;5;6
10 ( \begin{matrix}201 \\ 102 \end{matrix} )  1;7  15  0;6
11 ( \begin{matrix}20 \\ 02 \end{matrix} )  1;2  16  0;5
12 ( \begin{matrix}0201 \\ 1020 \end{matrix} )  1;13  17  0;1;6

⋮

54 ( \begin{matrix}0010201010201 \\ 1020101020100 \end{matrix} ) 1;18;19;56  1;22;23;41  0;1;2
55 ( \begin{matrix}00102010201 \\ 10201020100 \end{matrix} ) 1;18;19;37  1;13;22;23  0;1;2
56 ( \begin{matrix}10010201020 \\ 02010201001 \end{matrix} ) 1;25;26;52  1;27;28;29  0;3;4

Table 3: Possible elements of sets Z(n). The table shows the elements ζ_{j} and the structure of sets D_{0}(ζ_{j}), D_{1}(ζ_{j}). It also shows the structure of sets Vect(ζ_{j}), cf. Sect. 5.

k new Z_{q} found  new ζ_{j} found  k new Z_{q} found new ζ_{j} found
0 Z_{1}  ζ_{1}, ζ_{2}, ζ_{3}  15 Z_{201}, …, Z_{221} ζ_{56}
1 Z_{2}, Z_{3}  ζ_{4}, ζ_{5}, ζ_{6}, ζ_{7}  16 Z_{222}, …, Z_{245} none
2 Z_{4}, Z_{5}, Z_{6}, Z_{7}  ζ_{8}, ζ_{9}, ζ_{10}, ζ_{11}, ζ_{12} 17 Z_{246}, …, Z_{260}
3 Z_{8}, Z_{9}, Z_{10}, Z_{11}, Z_{12} ζ_{13}, ζ_{14}, ζ_{15}, ζ_{16}, ζ_{17} 18 Z_{261}, …, Z_{271}
4 Z_{13}, …, Z_{21}  ζ_{18}, …, ζ_{24}  19 Z_{272}, Z_{273}
5 Z_{22}, …, Z_{32}  ζ_{25}, …, ζ_{30}  20 Z_{274}, Z_{275}
⋮  21 Z_{276}, Z_{277}
14 Z_{179}, …, Z_{200}  ζ_{54}, ζ_{55}  22 none

Table 4: Progress of the calculation. Sets Z_{q} expressed in terms of ζ_{j} can be found in Tab. 2. Elements ζ_{j} are listed in Tab. 3.

The calculation continues in the same way for k = 3. For each q ∈ {4, 5, 6, 7}, we substitute the set Z_{q} into (24) for Z(n). Evaluation of Z(N) requires sets D_{0}(ζ_{j}) and D_{1}(ζ_{j}) for j = 1, …, 12. Some of them are known from our previous calculation (j = 1, …, 7), others can be calculated similarly now (j = 8, …, 12). In this way we find eight sets Z(N), namely

Z(n) = Z_{4} ⇒ Z(N) = Z_{7} or Z(N) = Z_{10} ,
Z(n) = Z_{5} ⇒ Z(N) = Z_{8} or Z(N) = Z_{11} ,
Z(n) = Z_{6} ⇒ Z(N) = Z_{9} or Z(N) = Z_{12} ,
Z(n) = Z_{7} ⇒ Z(N) = Z_{5} or Z(N) = Z_{7} .

(30)

Their structure is shown in Table 2.

In the next step we use Lemma 7 again. The eight sets found in (30) should be plugged in equations (24), which will lead to sets Z(N) for N having 5-digit representations (k = 4). Note, however, that the eight sets obtained in (30) are of two types:

• three of them (Z_{7} occurring 2 times and Z_{5}) had been found in earlier steps;

• five of them (Z_{8}, Z_{9}, Z_{10}, Z_{11}, Z_{12}) are “new” – they have just appeared in the calculation for the first time.

Since sets Z_{5} and Z_{7} have been already explored, there is no need to apply equations (24) on them again. It suffices to use formula (24) only with Z(n) = Z_{q} for such Z_{q} that promise potential new results, i.e., q = 8, 9, 10, 11, 12. Henceforth we will proceed similarly – we will always put aside those sets Z_{q} that reappear after having been explored in earlier stages of the procedure, and queue only the “new” ones for further use in (24).

The progress of the calculation is illustrated with Table 4. We see that when k reaches the value 22, no new set Z_{q} is found. In other words, all sets Z(N) obtained by equations (24) for k = 22 have been already found (and explored) earlier. The search is then completed. We conclude: there exist altogether 277 sets Z_{1}, …, Z_{277} such that for any n ∈ ℕ, we have Z(n) = Z_{q} for a certain q ∈ {1, …, 277}.

Since every Z_{q} consists of elements ζ_{j} for j = 1, …, 56 (note that new elements ζ_{j} stop appearing already at k = 16), the set Z_{super} := {ζ_{1}, ζ_{2}, ζ_{3}, …, ζ_{55}, ζ_{56}} obviously satisfies Z_{q} ⊂ Z_{super} for all q = 1, …, 277.

The search for sets Z_{q} and elements ζ_{j} can be in principle carried out completely using pen and paper, but since the procedure is lengthy and cumbersome, it is more convenient to use a computer, which also helps to avoid mistakes. Below we provide a pseudocode of the algorithm. Note that some variables used in the pseudocode are of special types, such as sets or pairs of strings. 1: calculate Z(1) using formula (11) for R = 3 and K = 0 2: a ← number of elements of Z(1) 3: Z[1] ← the set {1, …, a} 4: M ← 1 5: M old ← 0 6: M new ← 1 7: for j = 1, …, a do 8: zeta[j] ← j-th element of Z(1) 9: end for 10: a old ← 0 11: a new ← a 12: while M old < M new do 13: for d = 0, 1 do 14: for j = a old + 1, …, a new do 15: z ← zeta[j] 16: D ← ∅ 17: calculate D_{d}(z) using formula (22) 18: for every x ∈ D_{d}(z) do 19: if an i ∈ {1, …, a} satisfies x = zeta[i] then 20: D ← D ∪ {i} 21: else 22: D ← D ∪ {a + 1} 23: zeta[a + 1] ← x 24: a ← a + 1 25: end if 26: end for 27: D[d, j] ← D 28: end for 29: end for 30: a old ← a new 31: a new ← a 32: for q = M old + 1, …, M new do 33: for d = 0, 1 do 34: D ← ∅ 35: for every j ∈ Z[q] do 36: D ← D ∪ D[d, j] 37: end for 38: if a j ∈ {1, …, M} satisfies D = Z[j] then 39: delta[q, d] ← j 40: else 41: delta[q, d] ← M + 1 42: Z[M + 1] ← D 43: M ← M + 1 44: end if 45: end for 46: end for 47: M old ← M new 48: M new ← M 49: end while

When the algorithm ends, final values of variables have the meanings as follows.

• a: cardinality of Z_{super};

• zeta[j] for j = 1, …, a: ζ_{j} (cf. Table 3);

• D[d, j] for d = 0, 1, j = 1, …, a: the set {i | ζ_{i} ∈ D_{d}(ζ_{j})} (cf. Table 3);

• M: cardinality of {Z(n) | n ∈ ℕ} (cf. Table 2);

• Z[q] for q = 1, …, M: the set {j | ζ_{j} ∈ Z_{q}} (cf. Table 2);

• delta[q, d] for q = 1, …, M, d = 0, 1: δ(q, d) (cf. Sect. 6, Table 6).

5 Range of the abelian complexity

The aim of this section is twofold:

• We illustrate that the result of Section 4 allows to examine the image of the abelian complexity function, as well as the balance bound of t.

• We express Vect(ζ_{j}) for j = 1, …, 56, and we associate each Z_{q} for q = 1, …, 277 with a certain value of the abelian complexity function. This result will be useful later in Section 6 for an explicit evaluation of ρ^{ab}(n).

Recall that for any n ∈ ℕ, the value of the abelian complexity function ρ^{ab}(n) can be determined by formula (19) if the set Z(n) is known. We have not found an explicit relation between n and Z(n) yet, and thus we cannot use (19) as it is. Nevertheless, we have demonstrated in Section 4 that Z(n) = Z_{q} for a certain q ∈ {1, …, 277}, which already gives us the possibility to restrict the range of ρ^{ab}(n).

The use of formula (19) requires Vect(ζ) for ζ ∈ Z(n). Therefore, we shall express Vect(ζ_{j}) for j = 1, …, 56. If equation (10) is applied on ζ_{1}, it gives

Vect(ζ_{1}) = Vect (\begin{matrix}0 \\ 0 \end{matrix}) = \{Ψ(s) − Ψ(r) | r is a prefix of 0, s is a prefix of 0, |s| = |r|\}
= {(0, 0, 0)}.

Similarly, for ζ_{2} and ζ_{3} we get

Vect(ζ_{2}) = Vect (\begin{matrix}01 \\ 10 \end{matrix}) = \{Ψ(s) − Ψ(r) | r is a prefix of 01, s is a prefix of 10, |s| = |r|\}
= {(−1, 1, 0), (0, 0, 0)},
Vect(ζ_{3}) = Vect (\begin{matrix}02 \\ 20 \end{matrix}) = \{Ψ(s) − Ψ(r) | r is a prefix of 02, s is a prefix of 20, |s| = |r|\}
= {(−1, 0, 1), (0, 0, 0)}.

Performing the same calculation for every value of j, we find that for all j = 1, …, 56, we have Vect(ζ_{j}) ⊂ {ψ_{0}^{r}, ψ_{1}^{r}, …, ψ_{8}^{r}}, where

ψ_{0}^{r} = (0, 0, 0) ;  ψ_{1}^{r} = (−1, 1, 0) ;  ψ_{2}^{r} = (−1, 0, 1) ;
ψ_{3}^{r} = (0, −1, 1) ;  ψ_{4}^{r} = (1, −1, 0) ;  ψ_{5}^{r} = (1, 0, −1) ;
ψ_{6}^{r} = (0, 1, −1) ;  ψ_{7}^{r} = (−1, 2, −1) ;  ψ_{8}^{r} = (−1, −1, 2) .

The structure of sets Vect(ζ_{j}) in terms of ψ_{0}^{r}, …, ψ_{8}^{r} is partly shown in Table 3.

According to (25), for every n ∈ ℕ there is a q ∈ {1, …, 277} such that Z(n) = Z_{q}. By virtue of equation (19), we have

Z(n) = Z_{q}  ⇒  ρ^{ab}(n) = # ⋃_{ζ∈Z_{q}} Vect(ζ) .  (31)

The expression # ⋃_{ζ∈Z_{q}} Vect(ζ) depends only on q. Therefore, it is convenient to introduce the function

τ(q) := # ⋃_{ζ∈Z_{q}} Vect(ζ)  (32)

for q = 1, …, 277. Evaluation of τ is a straightforward task, consisting of combining data from Tables 2 and 3:

1. Table 2 shows the structure of Z_{q} in terms of ζ_{j}.

2. Table 3 contains Vect(ζ_{j}) for ζ_{j}.

\begin{matrix}q & τ(q) & q & τ(q) & q & τ(q) & q & τ(q) & q & τ(q) & q & τ(q) & q & τ(q) \\ 1 & 3 & 7 & 4 & 13 & 4 & 19 & 4 & 25 & 4 & 31 & 4 & 37 & 4 \\ 2 & 3 & 8 & 4 & 14 & 4 & 20 & 4 & 26 & 4 & 32 & 4 & 38 & 4 \\ 3 & 4 & 9 & 4 & 15 & 3 & 21 & 4 & 27 & 4 & 33 & 5 & 39 & 4 \\ 4 & 3 & 10 & 3 & 16 & 4 & 22 & 5 & 28 & 4 & 34 & 5 & 40 & 4 \\ 5 & 4 & 11 & 4 & 17 & 4 & 23 & 5 & 29 & 4 & 35 & 4 & 41 & 3 \\ 6 & 4 & 12 & 4 & 18 & 4 & 24 & 3 & 30 & 4 & 36 & 4 & 42 & 4 \end{matrix}

Table 5: The function τ (partial list for q = 1, …, 42).

For example, for q = 1 we obtain

⋃_{ζ∈Z_{1}} Vect(ζ) =^{(a)} Vect(ζ_{1}) ∪ Vect(ζ_{2}) ∪ Vect(ζ_{3}) =^{(b)} {ψ_{0}^{r}} ∪ {ψ_{0}^{r}, ψ_{1}^{r}} ∪ {ψ_{0}^{r}, ψ_{2}^{r}} = {ψ_{0}^{r}, ψ_{1}^{r}, ψ_{2}^{r}} ,

where we used data from Table 2 at (a) and data from Table 3 at (b). Hence τ(1) = # ⋃_{ζ∈Z_{1}} Vect(ζ) = 3. We proceed similarly for q = 2, …, 277. The values τ(q) obtained by the calculation are listed in Table 5. The list is only partial by reason of saving space, however, in the full list we could see that τ(q) ∈ {3, 4, 5, 6, 7} for all q ∈ {1, …, 277}. Consequently, ρ^{ab}(n) ∈ {3, 4, 5, 6, 7} for all n ∈ ℕ.

Moreover, one can show similarly that for any q = 1, …, 277, the absolute values of the elements of the difference vector ψ_{i}^{r} − ψ_{j}^{r} for ψ_{i}^{r}, ψ_{j}^{r} ∈ ⋃_{ζ∈Z_{q}} Vect(ζ) do not exceed 2. This fact implies that the Tribonacci word is 2-balanced. However, this bound as well as the result ρ^{ab}(n) ∈ {3, 4, 5, 6, 7} are not new; they have been derived already in [14].

6 Evaluation of the abelian complexity

As we have noticed at the beginning of Section 5, there is one last step to do before we can calculate ρ^{ab}(n) explicitly. Namely, we need to associate each n ∈ ℕ with the number q ∈ {1, …, 277} such that Z(n) = Z_{q}. The task will be solved in this section.

We introduce the map (the “transition function”) δ(q, d) for q ∈ {1, …, 277} and d ∈ {0, 1} by the formula

δ(q, d) = ℓ ⇔ ⋃_{ζ∈Z_{q}} D_{d}(ζ) = Z_{ℓ} .  (33)

Then we extend its domain to the value q = 0 by setting

δ(0, 0) = 0,  δ(0, 1) = 1.  (34)

Values δ(q, d) for q = 1, …, 277 can be naturally gathered in the course of the calculations carried out in the proof of Theorem 8. For example, we have ⋃_{ζ∈Z_{1}} D_{0}(ζ) = Z_{2} and

\begin{matrix}q & δ(q, 0) & δ(q, 1) & q & δ(q, 0) & δ(q, 1) & q & δ(q, 0) & δ(q, 1) & q & δ(q, 0) & δ(q, 1) \\ 1 & 2 & 3 & 11 & 16 & 21 & 21 & 17 & 13 & 31 & 22 & 23 \\ 2 & 4 & 6 & 12 & 17 & 13 & 22 & 33 & 39 & 32 & 17 & 13 \\ 3 & 5 & 7 & 13 & 22 & 23 & 23 & 34 & 40 & 33 & 47 & 54 \\ 4 & 7 & 10 & 14 & 23 & 28 & 24 & 7 & 41 & 34 & 48 & 55 \\ 5 & 8 & 11 & 15 & 24 & 29 & 25 & 13 & 42 & 35 & 13 & 56 \\ 6 & 9 & 12 & 16 & 14 & 19 & 26 & 35 & 43 & 36 & 49 & 57 \\ 7 & 5 & 7 & 17 & 25 & 30 & 27 & 14 & 19 & 37 & 14 & 19 \\ 8 & 13 & 18 & 18 & 26 & 31 & 28 & 36 & 44 & 38 & 14 & 19 \\ 9 & 14 & 19 & 19 & 27 & 32 & 29 & 37 & 45 & 39 & 50 & 58 \\ 10 & 15 & 20 & 20 & 22 & 23 & 30 & 38 & 46 & 40 & 17 & 13 \end{matrix}

Table 6: Values of the transition function δ(q, d) (partial list for q = 1, …, 40).

⋃_{ζ∈Z_{1}} D_{1}(ζ) = Z_{3}; hence δ(1, 0) = 2 and δ(1, 1) = 3. The values can be then tabulated; see Table 6.

The transition function δ(q, d) allows to determine Z(n) for any n ∈ ℕ, as we demonstrate in the following proposition.

Proposition 9. If ⟨n⟩_{T} = d_{k}d_{k−1} ⋯ d_{1}d_{0}, then

Z(n) = Z_{q}  for q = δ(0, d_{k}d_{k−1} ⋯ d_{1}d_{0}) ,  (35)

where the symbol δ(0, d_{k}d_{k−1} ⋯ d_{1}d_{0}) is a shorthand for δ(δ(⋯ δ(δ(0, d_{k}), d_{k−1}) ⋯, d_{1}), d_{0}) (cf. Sect. 2).

Proof. At first, let us assume that d_{k} = 1; the case d_{k} = 0 will be treated in the end. We prove the statement by induction on k.

I. Let k = 0. Then ⟨n⟩_{T} = 1, i.e., n = 1. We have δ(0, d_{0}) = δ(0, 1) = 1 from Eq. (34), thus formula (35) gives Z(1) = Z_{1}. This is obviously true with regard to the definition of Z_{1}.

II. Let the formula (35) be valid for numbers with normal T -representations having at most k digits. Let a number n have a (k + 1)-digit representation ⟨n⟩_{T} = d_{k}d_{k−1} ⋯ d_{1}d_{0}. The formula (35) is valid for ⟨n′⟩_{T} = d_{k}d_{k−1} ⋯ d_{1} (because ⟨n′⟩_{T} has only k digits), and hence Z(n′) = Z_{j} for j = δ(0, d_{k}d_{k−1} ⋯, d_{1}). From Eq. (23) we have Z(n) = ⋃_{ζ∈Z_{j}} D_{d_{0}}(ζ). Consequently, with regard to the definition of the transition function δ (cf. (33)), the equation Z(n) = Z_{q} holds for q = δ(j, d_{0}). Combining these two facts, we obtain

Z(n) = Z_{q} for q = δ(δ(0, d_{k}d_{k−1} ⋯, d_{1}), d_{0}) = δ(0, d_{k}d_{k−1} ⋯ d_{1}d_{0}) ,

which completes the inductive step.

It suffices to deal with the case d_{k} = 0, i.e., ⟨n⟩_{T} = 00 ⋯ 0d_{ℓ}d_{ℓ−1} ⋯ d_{0} for an ℓ < k and d_{ℓ} = 1. The initial block of zeros in the representation can be omitted, i.e., we can write ⟨n⟩_{T} = d_{ℓ}d_{ℓ−1} ⋯ d_{0} for d_{ℓ} = 1. Then, due to previous considerations, Z(n) = Z_{q} for q = δ(0, d_{ℓ}d_{ℓ−1} ⋯, d_{0}). At the same time, since δ(0, 0) = 0 from Eq. (34), we trivially get δ(0, 0 ⋯ 0) = 0. Hence

\begin{aligned}q & = δ(0, d_{ℓ}d_{ℓ−1} ⋯, d_{0}) = δ(δ(0, 0 ⋯ 0), d_{ℓ}d_{ℓ−1} ⋯, d_{0}) = δ(0, 0 ⋯ 0d_{ℓ}d_{ℓ−1} ⋯ d_{1}d_{0}) \\ & = δ(0, d_{k}d_{k−1} ⋯ d_{ℓ+1}d_{ℓ}d_{ℓ−1} ⋯ d_{1}d_{0}) . \end{aligned}

Proposition 9 associates any n ∈ ℕ with a q ∈ {1, …, 277} such that Z(n) = Z_{q}. Formula (31) together with (32) then gives the value of the abelian complexity as τ(q), where τ is the function tabulated in Table 5. Combining these two results, we get

Theorem 10. For any n ∈ ℕ we have

ρ^{ab}(n) = τ(δ(0, ⟨n⟩_{T})) .  (36)

Obviously, Theorem 10 together with Tables 6 and 5 allows to determine ρ^{ab}(n) for any n ∈ ℕ.

Equation (36) implies that (ρ^{ab}(n))_{n∈ℕ} is a T -automatic sequence. It is generated by the DFAO (Q, Σ, δ, q_{0}, Δ, τ), where

• Q = {0, 1, …, 277} is the set of states;

• Σ = {0, 1} is the input alphabet;

• δ is the state-transition function, cf. Table 6;

• q_{0} = 0 is the initial state;

• Δ = {3, 4, 5, 6, 7} is the output alphabet;

• τ is the output function, specified in Table 5.

The number of steps needed for evaluating ρ^{ab}(n) is proportional to the number of digits in the normal T -representation ⟨n⟩_{T}. The T_{j} grow roughly exponentially (T_{j} ≈ β^{j}, where β ≈ 1.84 is the root of x^{3} = x^{2} + x + 1), and hence the number of digits is k ∼ log n. The evaluation of ρ^{ab}(n) using formula (36) thus needs O(log n) operations. It is therefore fast even for large values of n.

Example 11. Let us calculate ρ^{ab}(n) for n = 2013. Since

(T_{j})_{j=3}^{∞} = (1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, …) ,

we have ⟨2013⟩_{T} = 1001000101011, cf. (4). Starting from the initial state 0 and applying the state-transition function δ step by step, we obtain

0 →^{1} 1 →^{0} 2 →^{0} 4 →^{1} 10 →^{0} 15 →^{0} 24 →^{0} 7 →^{1} 7 →^{0} 5 →^{1} 11 →^{0} 16 →^{1} 19 →^{1} 32 ,

thus δ(0, 1001000101011) = 32. Hence ρ^{ab}(2013) = τ(32) = 4.

7 Reduction of states of the automaton

In Section 6, we have found a DFAO that evaluates the abelian complexity function of the Tribonacci word. The automaton has 278 states (including the initial state q_{0} = 0). In this section we will show that the size of the automaton can be substantially reduced.

Obviously, if p, q ∈ {1, …, 277} (p ≠ q) satisfy

δ(p, 0) = δ(q, 0) ∧ δ(p, 1) = δ(q, 1) ∧ τ(p) = τ(q) ,

then the states p and q can be merged into a single state.

We use this fact to reduce the size of our automaton; note that the procedure has to be repeated several times until no more mergeable vertices exist. Eventually we obtain an equivalent DFAO that has just 68 vertices. Then we update the labels of states of the new automaton to the numbers 0, 1, …, 67 (where 0 corresponds to the initial state) and recalculate accordingly the values of the transition function and the output function. The result is summarized in Table 7. Naturally, the formula

ρ^{ab}(n) = τ(δ(0, ⟨n⟩_{T}))

from Theorem 10 also remains valid with functions δ and τ tabulated in Table 7. Although the reduction method we used is quite elementary, it works well in this case: one can check, using, e.g., Moore’s algorithm, that the reduced automaton is already minimal.

Example 12. Let us calculate ρ^{ab}(n) for n = 2013 using Table 7. Since ⟨2013⟩_{T} = 1001000101011 (see Ex. 11), we obtain

0 →^{1} 1 →^{0} 2 →^{0} 4 →^{1} 9 →^{0} 13 →^{0} 4 →^{0} 3 →^{1} 3 →^{0} 5 →^{1} 6 →^{0} 8 →^{1} 6 →^{1} 10 .

Hence ρ^{ab}(2013) = τ(10) = 4.

Now we can return to the open problem proposed by Richomme, Saari and Zamboni [15] concerning the characterization of those n for which ρ^{ab}(n) = c, c ∈ {4, 5, 6, 7}. The automaton derived in this section leads to a solution. Namely, for each c ∈ {4, 5, 6, 7} it suffices to consider the deterministic finite automaton (DFA) A_{c} = (Q, Σ, δ, q_{0}, F_{c}), where Q, Σ, δ, q_{0} have the same meaning as above, and F_{c} ⊂ Q is the set of accepting states, defined by the equivalence q ∈ F_{c} ⇔ τ(q) = c. The automaton A_{c} obviously accepts ⟨n⟩_{T} if and only if ρ^{ab}(n) = c.

We noticed that Moore’s minimization algorithm reduces the size of A_{c} for each c ∈ {3, 4, 5, 6, 7}. It is interesting to compare the number of states of the reduced automata; see Table 8. The minimal automaton accepting the set {⟨n⟩_{T} | ρ^{ab}(n) = 3} has just 5 states (including the initial state), whereas the minimal automata accepting {⟨n⟩_{T} | ρ^{ab}(n) = c} for c ∈ {4, 5, 6, 7} have 66 states. The disparity in sizes explain, in our opinion, why the authors of [15] could give a simple characterization of those n satisfying AC(n) = 3, whereas the question about the n satisfying AC(n) = c for c ∈ {4, 5, 6, 7} remained open.

q δ(q, 0) δ(q, 1) τ(q) q δ(q, 0) δ(q, 1) τ(q) q δ(q, 0) δ(q, 1) τ(q)
0  0  1  - 23 26  24  4 46 51  38  6
1  2  3  3 24 28  16  5 47 52  38  6
2  4  6  3 25 29  32  5 48 53  55  5
3  5  3  4 26 30  33  4 49 54  56  4
4  3  9  3 27 31  29  4 50 37  57  5
5  7  6  4 28 34  22  5 51 58  38  6
6  8  10  4 29 35  38  5 52 59  22  6
7  11  10  4 30 11  23  4 53 24  23  5
8  12  6  4 31 19  39  5 54 43  53  4
9  13  11  3 32 36  11  5 55 60  63  5
10 14  11  4 33 37  40  5 56 61  34  5
11 15  16  4 34 41  10  6 57 62  58  5
12 16  17  4 35 42  22  6 58 58  38  7
13  4  18  3 36 25  18  5 59 58  32  7
14  7  18  4 37 43  19  5 60 43  53  5
15 19  22  5 38 36  27  5 61 19  64  5
16 20  10  5 39 21  45  4 62 30  55  4
17 21  11  4 40 44  41  5 63 48  58  5
18  8  23  4 41 46  16  6 64 54  65  4
19 24  10  5 42 47  32  6 65 66  51  5
20 25  6  5 43 16  49  4 66 19  67  5
21 12  18  4 44 30  50  4 67 54  63  4
22 21  27  4 45 48  47  4

Table 7: Reduced automaton. Values of the transition function δ(q, d) and of the output function τ.

c  3 4 5 6 7
number of states 5 66 66 66 66

Table 8: Sizes of minimal automata accepting the sets {⟨n⟩_{T} | ρ^{ab}(n) = c}.

\begin{matrix}q_{0} \\ start \end{matrix} ; q_{1} ; q_{3} ; q_{2} ; q_{4} ; 1 0 0 1 0 1 0,1 0 1

Figure 1: The minimal automaton accepting the set {⟨n⟩_{T} | ρ^{ab}(n) = 3}.

Remark 13. The minimal automaton corresponding to A_{3}, which accepts ⟨n⟩_{T} if and only if ρ^{ab}(n) = 3, has the transition diagram shown in Figure 1. Hence we obtain one more characterization of those n for which ρ^{ab}(n) = 3 on top of those that were found in [15, Prop. 3.3], namely:

ρ^{ab}(n) = 3  ⇔  ⟨n⟩_{T} is a prefix of 100100100 · · · .  (37)

8 On the abelian complexity of m-bonacci words for m ≥ 4

The m-bonacci word is defined for any integer m ≥ 2 over the alphabet A = {0, 1, 2, 3} as the fixed point of the substitution

φ_{m} : 0 ↦ 01, 1 ↦ 02, …, m − 2 ↦ 0(m − 1), m − 1 ↦ 0 .

The Fibonacci word and the Tribonacci word are its special cases for m = 2 and m = 3, respectively.

It is easy to see that the procedure, used in previous sections to examine the abelian complexity of the Tribonacci word, can be straightforwardly applied to any m-bonacci word, regardless of m. Indeed, to explore an m-bonacci word for a given m ≥ 2 by this method, it suffices to change just the constant R in Example 4 from the value 3 to m, and to use the m-bonacci representation of integers. The m-bonacci representation is a normal Urepresentation defined for U_{j} = |φ_{m}^{j}(0)|; note that the values U_{j} satisfy

U_{j} = \begin{cases}2^{j}, & if j ∈ \{0, 1, …, m − 1\}; \\ U_{j−1} + U_{j−2} + ⋯ U_{j−m}, & if j ≥ m. \end{cases}

On the other hand, the cardinality of Z_{super} seems to quickly grow with m; thus the method ceases to be efficient for high values of m.

q_{0} start q_{1} q_{3} q_{2} q_{4} q_{5} 1001010,1 0101

Figure 2: (4-bonacci word) The minimal automaton accepting the set {⟨n⟩_{Q} | ρ_{q}^{ab}(n) = 4}.

For instance, we have considered the 4-bonacci word \underline{A254990} and successfully found an explicit DFAO that evaluates its abelian complexity \underline{A255014}; the automaton has 5665 states (66881 before the reduction of states). We provide main results below. For the sake of brevity we will denote the 4-bonacci word by the symbol q. For any n ∈ ℕ, let ⟨n⟩_{Q} be the 4-bonacci representation of n, constructed for U_{j} = Q_{j+4}, where (Q_{j})_{j≥0} = (0, 0, 0, 1, 1, 2, 4, 8, 15, …) is the sequence of Tetranacci numbers \underline{A000078}.

The minimal and maximal values of the output function of the automaton evaluating ρ_{q}^{ab} are 4 and 16, respectively. Therefore, the abelian complexity function ρ_{q}^{ab} takes values between 4 and 16. However, the output function of the automaton does not attain the value 5, which implies that there exists no n ∈ ℕ such that ρ_{q}^{ab}(n) = 5. To sum up,

{ρ_{q}^{ab}(n) | n ∈ ℕ} = {4} ∪ {6, 7, …, 16}.

The existence of gaps in ranges of abelian complexity functions of m-bonacci words was already observed a few years ago by K. Břinda [4] on the basis of computer-assisted calculations performed for m ∈ {4, 5, …, 12}. Our automaton confirms his observation in the case m = 4.

Furthermore, we are able to characterize those n for which ρ_{q}^{ab}(n) = 4. We apply Moore’s minimization algorithm on the automaton accepting the set {⟨n⟩_{T} | ρ_{q}^{ab}(n) = 4}, which leads to an automaton having just 6 states. The transition diagram of the automaton is depicted in Figure 2. One can see directly from its structure that

ρ_{q}^{ab}(n) = 4  ⇔  ⟨n⟩_{Q} is a prefix of 100010001000 · · · .  (38)

This result is the 4-bonacci version of the Tribonacci equivalence (37).

Let us proceed to characterization of those n such that ρ_{q}^{ab}(n) = 6. We again apply Moore’s minimization, and again get an automaton having only 6 states; see Figure 3. It is obvious from the graph that

ρ_{q}^{ab}(n) = 6  ⇔  ⟨n⟩_{Q} ∈ {11, 110, 1100},

q_{0} start q_{1} q_{2} q_{3} q_{4} q_{5} 10010,1 01010,1

Figure 3: (4-bonacci word) The minimal automaton accepting the set {⟨n⟩_{Q} | ρ_{q}^{ab}(n) = 6}.

\begin{matrix}c & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ states & 6 & – & 6 & 66 & 4649 & 4683 & 4735 & 5004 & 5256 & 5299 & 5322 & 5324 & 5032 \end{matrix}

Table 9: (4-bonacci word) Sizes of minimal automata accepting the sets {⟨n⟩_{Q} | ρ_{q}^{ab}(n) = c}.

i.e., the value 6 is attained only for n ∈ {3, 6, 12}. The fact that the function ρ_{q}^{ab} takes a certain value only finitely many times is remarkable, because it implies a significant qualitative difference between abelian complexity functions of the Tribonacci and the 4-bonacci word. Recall that each value in the range of ρ_{t}^{ab} is attained infinitely often [15, 19].

Now we will comment on the remaining values of ρ_{q}^{ab}, i.e., c ∈ {7, …, 16}. Although one can again construct minimal automata accepting {⟨n⟩_{Q} | ρ_{q}^{ab}(n) = c}, they are not useful for obtaining a nice characterization of the numbers n such that ρ_{q}^{ab}(n) = c. This follows from Table 9: the automata are too large, especially for c ≥ 8. Nevertheless, we are still able to demonstrate that each value in the set {7, …, 16} is attained infinitely many times. For every c ∈ {7, …, 16}, we give in Table 10 an infinite family of normal Q-representations ⟨n⟩_{Q} such that ρ_{q}^{ab}(n) = c.

Let us summarize the results obtained on the 4-bonacci word.

Theorem 14. The abelian complexity function of the 4-bonacci word has the following properties.

• {ρ_{q}^{ab}(n) | n ∈ ℕ} = {4} ∪ {6, 7, …, 16}.

• ρ_{q}^{ab}(n) = 4 if and only if ⟨n⟩_{Q} is a prefix of 100010001000 · · ·.

• ρ_{q}^{ab}(n) = 6 if and only if n ∈ {3, 6, 12}.

• For every value c ∈ {7, …, 16} there exist infinitely many integers n ∈ ℕ such that ρ_{q}^{ab}(n) = c.

c  ⟨n⟩_{Q}  c  ⟨n⟩_{Q}
7 (1000)^{j}0 (∀j ≥ 1) 12  10^{j}1  (∀j ≥ 19)
8 (100)^{j} (∀j ≥ 3) 13  10^{j}  (∀j ≥ 19)
9 (10)^{j} (∀j ≥ 11) 14 (10000)^{j} (∀j ≥ 6)
10 10^{j}11 (∀j ≥ 19) 15 (10000)^{j}0 (∀j ≥ 6)
11 (10)^{j}0 (∀j ≥ 11) 16 (10000)^{j}00 (∀j ≥ 6)

Table 10: (4-bonacci word) Examples of infinite families of normal Q-representations ⟨n⟩_{Q} such that ρ_{q}^{ab}(n) = c for c ∈ {7, …, 16}. The data in the table were obtained by trial and error: we used the automaton evaluating ρ_{q}^{ab}(n) to explore several periodic expansions, some with an aperiodic part at the end, and noted down those expansions that were useful. Many other such examples can be found.

We are convinced that the existence of gaps in the range of the abelian complexity function, as well as the existence of values that are attained only finitely many times, are common properties of all m-bonacci words with m ≥ 4.

We finish the section by a remark on the minimal value of the m-bonacci word for a general m. Let u be an m-bonacci word. One can easily show that for every n ∈ ℕ and ℓ ∈ {0, 1, …, m − 1}, the factor ℓu_{[n−1]} is a factor of u, thus ρ_{u}^{ab}(n) ≥ 4. At the same time we have ρ_{u}^{ab}(1) = m. To sum up, min_{n∈ℕ} ρ_{u}^{ab}(n) = m for any m-bonacci word. Results of K. Břinda’s calculations [4] together with proven formulas (37) and (38) suggest a conjecture on a precise characterization of the numbers for which the abelian complexity function of an m-bonacci word u attains its minimum:

ρ_{u}^{ab}(n) = m  ⇔  ⟨n⟩_{U} is a prefix of 10^{m−1}10^{m−1}10^{m−1} ⋯;  (39)

the symbol ⟨n⟩_{U} stands here for the m-bonacci representation of n. We are able to prove the implication ⇐ in (39) for a general m by the abelian co-decomposition method, introduced earlier [19]. The implication ⇒ remains so far open, although we expect that it is probably not difficult to be proven either.

9 Conclusions and generalizations

In this paper we focused on the abelian complexity of the Tribonacci word (or, more generally, m-bonacci words), but the method can be easily adapted for application on any simple Parry word. Let us consider the fixed point u of a substitution (6). The calculation naturally takes advantage of the numeration system associated with φ, i.e., of the normal U-representation for U_{j} = |φ^{j}(0)|. Let us briefly sketch the procedure. First of all, for the sake of generality, we slightly reformulate the definition of Dec( \begin{matrix}v \\ w \end{matrix} ) by imposing an additional technical assumption on the decomposition (8). Namely, we assume that for every j ∈ {1, …, h}, the factor z̃ has the prefix 0, and require that h is maximal subject to this condition. We also need to introduce maps D_{0}, D_{1}, …, D_{α_{0}}, defined in a way analogous to equations (22), i.e.,

D_{j}(ζ) := Dec (\begin{matrix}φ(z) \\ 0^{−j}φ(z̃)0^{j} \end{matrix}) for ζ = \binom{z}{z̃} , j ∈ \{0, 1, …, α_{0}\} .

The search for sets Z_{1}, …, Z_{M} starts with calculating Z_{u}(n) by formula (11) for every n ∈ {1, …, α_{0}}. Then we take the bunch of sets Z_{u}(1), …, Z_{u}(α_{0}), which we denote by Z_{1}, …, Z_{α_{0}}, and apply the maps D_{0}, D_{1}, …, D_{α_{0}} on each of the sets, similarly as in the proof of Theorem 8. In this way we obtain a new bunch of sets, we apply D_{0}, D_{1}, …, D_{α_{0}} on them again, and so forth. However, unlike in the case of m-bonacci words, one needs to keep track of the admissibility of the normal U-representations ⟨n⟩_{U} during the calculation. Briefly speaking, if a normal U-representation, examined at a given moment, cannot be validly extended by a certain specific digit d, then the map D_{d} is not applied at that stage. The procedure ends when the application of D_{0}, D_{1}, …, D_{α_{0}} generates no new data.

The abelian co-decomposition method also allows us to deal with the other type of Parry words, called non-simple Parry words, which are fixed points of substitutions

φ :  0  ↦ 0^{α_{0}}1
1  ↦ 0^{α_{1}}2
⋮
m  ↦ 0^{α_{m}}(m + 1)
⋮
m + p − 2 ↦ 0^{α_{m+p−2}}(m + p − 1)
m + p − 1 ↦ 0^{α_{m+p−1}}m

where α_{j} satisfy α_{0} ≥ 1, α_{ℓ} ≤ α_{0} for all ℓ ∈ A, and (∃ℓ ∈ {m, m+1, …, m+p−1})(α_{ℓ} ≥ 1). Although we have not explicitly discussed non-simple Parry words in previous sections, the implementation of the procedure would be the same; we just need to replace the value m in the definition of R (12) by m + p. To sum up, the approach is applicable on any Parry word; but one shall keep in mind that in practice it will more likely work well in cases when the image of the abelian complexity function is a set of low cardinality. Nevertheless, it can still give new results for various words for which other methods fail.

Those Parry words, for which this approach turns out to be inefficient, can be perhaps treated by a newer technique, which replaces pairs \binom{z}{z̃} by certain conveniently chosen triples [20]. That technique is more involved, but it is expected to have smaller memory requirements in most cases and to work faster.

A potentially interesting question is whether this approach (possibly after a certain improvement) can be used for dealing with a word that depends on a parameter, i.e., whether one can explore a parametric family of words as a whole. Consider for instance the m-bonacci word for a general m ≥ 2. We are convinced that the procedure could be implemented with a parameter as well, although the calculation would be of course intricate and lengthy.

The procedure also gives, as a by-product, the optimal balance bound of the examined word. The optimal bound is equal to the maximal entries of vectors ψ having the form ψ = v_{i} − v_{j} for v_{i}, v_{j} belonging to the same set ⋃_{ζ∈Z_{q}} Vect(ζ). For example, one can check in this way that the 4-bonacci word is 3-balanced. Consequently, we can regard the method not only as a tool for evaluating abelian complexity, but also as a tool for exploring balance properties of words. In particular, it is possible that this approach can lead to the optimal balance bound for the m-bonacci word for any m. Recall that the optimal bound for the m-bonacci word is not known yet, despite the fact that an upper bound has been already determined [5].

10 Acknowledgements

The author thanks J.-P. Allouche for useful comments and suggestions, and the referees for valuable hints and corrections that helped to improve the manuscript.

References

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

[2] H. Ardal, T. Brown, V. Jungić, and J. Sahasrabudhe, On abelian and additive complexity in infinite words, Integers 12 (2012), #A21.

[3] L’. Balková, K. Břinda, and O. Turek, Abelian complexity of infinite words associated with quadratic Parry numbers, Theor. Comput. Sci. 412 (2011), 6252–6260.

[4] K. Břinda, Abelian complexity of infinite words and Abelian return words, Research project, Czech Technical University in Prague, 2012.

[5] K. Břinda, E. Pelantová, and O. Turek, Balances of m-bonacci words, Fundam. Inform. 132 (2014), 33–61.

[6] J. Cassaigne, G. Richomme, K. Saari, and L. Q. Zamboni, Avoiding Abelian powers in binary words with bounded Abelian complexity, Int. J. Found. Comp. Sci. 22 (2011), 905–920.

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

[8] J. Currie and N. Rampersad, Recurrent words with constant Abelian complexity, Adv. Appl. Math. 47 (2011), 116–124.

[9] S. Fabre, Substitutions et β-systèmes de numération, Theor. Comput. Sci. 137 (1995), 219–236.

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

[11] B. Madill and N. Rampersad, The abelian complexity of the paperfolding word, Discrete Math. 313 (2013), 831–838.

[12] H. Mousavi and J. Shallit, Mechanical proofs of properties of the Tribonacci word,

    preprint, 2014. Available at http://arxiv.org/abs/1407.5841.

[13] W. Parry, On the β-expansions of real numbers, Acta Math. Hungar. 11 (1960), 401– 416.

[14] G. Richomme, K. Saari, and L. Q. Zamboni, Abelian complexity in minimal subshifts, J. London Math. Soc. 83 (2011), 79–95.

[15] G. Richomme, K. Saari, and L. Q. Zamboni, Balance and Abelian complexity of the Tribonacci word, Adv. Appl. Math. 45 (2010), 212–231.

[16] J. Shallit, A generalization of automatic sequences, Theor. Comput. Sci. 61 (1988), 1–16.

[17] W. Thurston, Groups, tilings and finite state automata, AMS Colloquium Lecture Notes,

    1989. Available at http://timo.jolivet.free.fr/docs/ThurstonLectNotes.pdf.

[18] O. Turek, Balances and Abelian complexity of a certain class of infinite ternary words, RAIRO Theoret. Informatics Appl. 44 (2010), 313–337.

[19] O. Turek, Abelian complexity and abelian co-decomposition, Theor. Comput. Sci. 469 (2013), 77–91.

[20] O. Turek, Abelian properties of Parry words, Theor. Comput. Sci. 566 (2015), 26–38.

2010 Mathematics Subject Classification: Primary 11B85; Secondary 68R15. Keywords: abelian complexity, Tribonacci word, finite automaton, 4-bonacci word.

(Concerned with sequences \underline{A000073}, \underline{A000078}, \underline{A080843}, \underline{A216190}, \underline{A254990}, and \underline{A255014}.)

Received October 7 2014; revised version received February 12 2015. Published in Journal of Integer Sequences, February 14 2015.

Return to Journal of Integer Sequences home page.