Abelian powers and repetitions in Sturmian words

DOI10.1016/J.TCS.2016.04.039zbMATH Open1346.68150arXiv1506.02797OpenAlexW2963659561MaRDI QIDQ287434FDOQ287434

Filippo Mignosi, Thierry Lecroq, Ville Salo, Gabriele Fici, A. Lefebvre, Élise Prieur-Gaston, Alessio Langiu

Publication date: 26 May 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

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$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_{a}lpha)$ of a Sturmian word $s_{a}lpha$ of angle $alpha$ as the quantity $A(s_{a}lpha)=limsup{k}_m/m=limsupk{\text{'}}_m/m$, where $k_m$ (resp. $k{\text{'}}_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_{a}lpha)$ equals the Lagrange constant of the number $alpha$. This yields a formula for computing $A(s_{a}lpha)$ in terms of the partial quotients of the continued fraction expansion of $alpha$. Using this formula, we prove that $A(s_{a}lpha)geqsqrt5$ and that the equality holds for the Fibonacci word. We further prove that $A(s_{a}lpha)$ is finite if and only if $alpha$ has bounded partial quotients, that is, if and only if $s_{alpha}$ is $$-power-free for some real number $$. Concerning the infinite Fibonacci word, we prove that: 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; 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

Full work available at URL: https://arxiv.org/abs/1506.02797

zbMATH Keywords

critical exponentFibonacci wordabelian periodabelian powerLagrange constantSturmian word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Markov and Lagrange spectra and generalizations (11J06)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Context-Free Languages
• Substitutions in dynamics, arithmetics and combinatorics
• The index of Sturmian sequences
• Sturmian words and words with a critical exponent
• Special factors, periodicity, and an application to Sturmian words
• Three distance theorems and combinatorics on words
• Infinite words with linear subword complexity
• Characterisations of balanced words via orderings
• Characterization of repetitions in Sturmian words: a new proof
• Characterizations of finite and infinite episturmian words via lexicographic orderings
• On the complexity of algebraic numbers. II: Continued fractions
• On the complexity of algebraic numbers. I: Expansions in integer bases
• On the sum and product of continued fractions
• On Sturmian sequences which are invariant under some substitutions
• Some characterizations of Sturmian words in terms of the lexicographic order
• On abelian versions of critical factorization theorem
• On Abelian repetition threshold
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• Abelian complexity of minimal subshifts
• Initial powers of Sturmian sequences
• Sturmian and Episturmian Words
• Least Periods of Factors of Infinite Words
• Repetitions in the Fibonacci infinite word
• A note on Sturmian words
• ABELIAN PRIMITIVE WORDS
• Abelian Repetitions in Sturmian Words
• Abelian returns in Sturmian words
• Fractional powers in Sturmian words
• Some unsolved problems
• On critical exponents in fixed points of non-erasing morphisms

Cited In (14)

• On $k$-abelian equivalence and generalized Lagrange spectra
• Abelian repetitions in partial words
• Abelian periods of factors of Sturmian words
• Aperiodic two-dimensional words of small abelian complexity
• The undirected repetition threshold and undirected pattern avoidance
• More on the dynamics of the symbolic square root map
• Title not available (Why is that?)
• Title not available (Why is that?)
• Abelian-square-rich words
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Fast algorithms for abelian periods in words and greatest common divisor queries
• 2-balanced sequences coding rectangle exchange transformation
• Avoiding abelian powers cyclically
• Abelian combinatorics on words: a survey

This page was built for publication: Abelian powers and repetitions in Sturmian words

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