Abelian periods of factors of Sturmian words

Abstract: We study the abelian period sets of Sturmian words, which are codings of irrational rotations on a one-dimensional torus. The main result states that the minimum abelian period of a factor of a Sturmian word of angle

a l p h a

with continued fraction expansion

[0; a_{1}, a_{2}, l d o t s]

is either

t q_{k}

with

1 l e q t l e q a_{k + 1}

(a multiple of a denominator

q_{k}

of a convergent of

a l p h a

) or

q_{k, e l l}

(a denominator

q_{k, e l l}

of a semiconvergent of

a l p h a

). This result generalizes a result of Fici et. al stating that the abelian period set of the Fibonacci word is the set of Fibonacci numbers. A characterization of the Fibonacci word in terms of its abelian period set is obtained as a corollary.

Review text

Recall that a word \(w := w_0 w_1 \ldots w_{|w|-1}\) is said to have period \(p\) if \(w_i = w_{i+p}\) for all \(i\) with \(0 \leq i\leq |w|-1-p\). This is equivalent to saying that \(w\) is a prefix of a power of some word \(z\) of length \(p\). This notion can be generalized to an abelian framework, namely \(m\) is called an abelian period of \(w\) if \(w\) is a factor of an abelian power \(u_0 u_1 \ldots u_{n-1}\) with \(|u_0| = \ldots = |u_{n-1}| = m\), where ``abelian power means that each word \(u_j\) can be obtained by permuting the letters of \(u_0\). The main result of the paper states: If \(m\) is the minimal abelian period of a nonempty factor of a Sturmian word of slope \(\alpha\) with continued fraction expansion \([0; a_1, a_2, \ldots]\) and convergents \(p_k/q_k\), then either \(m = t q_k\), for some \(k \geq 0\) and some \(t\) such that \(1 \leq t \leq a_{k+1}\) or else \(m = \ell q_k + q_{k-1}\) for some \(k \geq 1\) and some \(\ell\) such that \(1 \leq \ell < a_{k+1}\). This result implies in particular a result described in [\textit{G. Fici} et al., Theor. Comput. Sci. 635, 16--34 (2016; Zbl 1346.68150)], namely: The set of minimal abelian periods of all factors of the binary Fibonacci sequence is the set of Fibonacci numbers. Finally note that results in the arXiv paper [\textit{D. Goč} and \textit{J. Shallit}, ``Least periods of \(k\)-automatic sequences, Preprint, \url{arXiv:1207.5450}] and more can be found in the paper [\textit{D. Goč} et al., Int. J. Found. Comput. Sci. 24, No. 6, 781--798 (2013; Zbl 1304.68143)].

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Abelian periods of factors of Sturmian words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2187128)