Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Abelian Powers and Repetitions...

Abelian Powers and Repetitions in Sturmian Words

Gabriele Fici, Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi, Jarkko Peltomäki, Élise Prieur-Gaston, Abelian Powers and Repetitions in Sturmian Words. Theoretical Computer Science 635, 16–34, 2016.

http://dx.doi.org/10.1016/j.tcs.2016.04.039

Abstract:

Richomme, Saari and Zamboni (J.~Lond.~Math.~Soc.~83:~79--95,~2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. By considering all possible abelian periods $m$, we recover the result of Richomme, Saari and Zamboni.

As an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\alpha) = \limsup k_{m}/m=\limsup k'_{m}/m$, where $k_{m}$ (resp. $k'_{m}$) denotes the maximum exponent of an abelian power (resp.~of an abelian repetition) of abelian period $m$ (the superior limits coincide for Sturmian words). We show that $A(s_\alpha)$ equals the Lagrange constant of the number $\alpha$. This yields a formula for computing $A(s_\alpha)$ in terms of the partial quotients of the continued fraction expansion of $\alpha$. Using this formula, we prove that $A(s_\alpha) \geq \sqrt{5}$ and that the equality holds for the Fibonacci word. We further prove that $A(s_\alpha)$ is finite if and only if $\alpha$ has bounded partial quotients, that is, if and only if $s_{\alpha}$ is $\beta$-power-free for some real number $\beta$.

Concerning the infinite Fibonacci word, we prove that: \emph{i}) The longest prefix that is an abelian repetition of period $F_j$, $j>1$, has length $F_j( F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j( F_{j+1}+F_{j-1} )-2$ if $j$ is odd, where $F_{j}$ is the $j$th Fibonacci number; \emph{ii}) The minimum abelian period of any factor is a Fibonacci number.
Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words: we prove that for $j\geq 3$ the Fibonacci word $f_j$, of length $F_{j}$, has minimum abelian period equal to $F_{\lfloor{j/2}\rfloor}$ if $j = 0, 1, 2\mod{4}$ or to $F_{1+\lfloor{j/2 \rfloor}$ if $j = 3\mod{4}$.

BibTeX entry:

@ARTICLE{jFiLaLeLeMiPePr16a,
  title = {Abelian Powers and Repetitions in Sturmian Words},
  author = {Fici, Gabriele and Langiu, Alessio and Lecroq, Thierry and Lefebvre, Arnaud and Mignosi, Filippo and Peltomäki, Jarkko and Prieur-Gaston, Élise},
  journal = {Theoretical Computer Science},
  volume = {635},
  publisher = {Elsevier},
  pages = {16–34},
  year = {2016},
  ISSN = {0304-3975},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication