{
  "id": "1301.3334",
  "version": "v2",
  "published": "2013-01-15T13:13:32.000Z",
  "updated": "2014-05-26T19:57:13.000Z",
  "title": "Balances of $m$-bonacci words",
  "authors": [
    "Karel Břinda",
    "Edita Pelantová",
    "Ondřej Turek"
  ],
  "journal": "Fundamenta Informaticae 132(1), pp. 33-61, 2014",
  "doi": "10.3233/fi-2014-1031",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The $m$-bonacci word is a generalization of the Fibonacci word to the $m$-letter alphabet $\\mathcal{A} = {0,...,m-1}$. It is the unique fixed point of the Pisot--type substitution $ \\varphi_m: 0\\to 01, 1\\to 02, ..., (m-2)\\to0(m-1), and (m-1)\\to0$. 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\\in \\mathcal{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\\geq2$. We show that the $m$-bonacci word is $(\\lfloor \\kappa m \\rfloor +12)$-balanced, where $\\kappa \\approx 0.58$. For $m\\leq 12$, we improve the constant $c^{(m)}$ by a computer numerical calculation to the value $\\lceil\\frac{m+1}{2}\\rceil$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-05-26T19:57:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "fibonacci word",
      "pisot-type substitution",
      "computer numerical calculation",
      "adamczewski implies",
      "length differ"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.3334B"
    }
  }
}