Balances of m-bonacci words

Citation:

Břinda, K., Pelantová, E. & Turek, O., 2014. Balances of m-bonacci words. Fundamenta informaticae , 132. Copy at http://j.mp/2KY2mg5

Date Published:

jan

Abstract:

The m-bonacci word is a generalization of the Fibonacci word to the m-letter alphabet A = {0, . . . , m − 1}. It is the unique fixed point of the Pisot–type substitution ϕm : 0 → 01, 1 → 02, . . . , (m − 2) → 0(m − 1), and (m − 1) → 0. A result of Adamczewski implies the existence of constants c (m) such that the m-bonacci word is c (m) -balanced, i.e., numbers of letter a occurring in two factors of the same length differ at most by c (m) for any letter a ∈ A. The constants c (m) have been already determined for m = 2 and m = 3. In this paper we study the bounds c (m) for a general m ≥ 2. We show that the m-bonacci word is (⌊κm⌋ + 12)-balanced, where κ ≈ 0.58. For m ≤ 12, we improve the constant c (m) by a computer numerical calculation to the value ⌈ m+1 2 ⌉.

Publisher's Version

Last updated on 12/09/2018