Abelian powers and repetitions in Sturmian words

DOI10.1016/J.TCS.2016.04.039MaRDI QIDQ287434zbMATH OpenOpenAlexFDO

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

Publication date 26 May 2016

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

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)

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

Recommendations

• Abelian repetitions in Sturmian words
• Abelian periods of factors of Sturmian words
• Special factors, periodicity, and an application to Sturmian words
• Every nonnegative real number is an abelian critical exponent
• On \(k\)-abelian equivalence and generalized Lagrange spectra

Cites work

• scientific article; zbMATH DE number 5605094 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 43747 (Why is no real title available?)
• scientific article; zbMATH DE number 3540889 (Why is no real title available?)
• scientific article; zbMATH DE number 1052825 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 783633 (Why is no real title available?)
• scientific article; zbMATH DE number 1408353 (Why is no real title available?)
• scientific article; zbMATH DE number 6272378 (Why is no real title available?)
• A note on Sturmian words
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• Abelian complexity of minimal subshifts
• Abelian primitive words
• Abelian repetitions in Sturmian words
• Abelian returns in Sturmian words
• 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
• Fractional powers in Sturmian words
• Infinite words with linear subword complexity
• Initial powers of Sturmian sequences
• Least Periods of Factors of Infinite Words
• On Abelian repetition threshold
• On Context-Free Languages
• On Sturmian sequences which are invariant under some substitutions
• On abelian versions of critical factorization theorem
• On critical exponents in fixed points of non-erasing morphisms
• On the complexity of algebraic numbers. I: Expansions in integer bases
• On the complexity of algebraic numbers. II: Continued fractions
• On the sum and product of continued fractions
• Repetitions in the Fibonacci infinite word
• Some characterizations of Sturmian words in terms of the lexicographic order
• Some unsolved problems
• Special factors, periodicity, and an application to Sturmian words
• Sturmian and Episturmian Words
• Sturmian words and words with a critical exponent
• Substitutions in dynamics, arithmetics and combinatorics
• The index of Sturmian sequences
• Three distance theorems and combinatorics on words

Cited in

(22)

• 2-balanced sequences coding rectangle exchange transformation
• Abelian periods of factors of Sturmian words
• scientific article; zbMATH DE number 7559450 (Why is no real title available?)
• More on the dynamics of the symbolic square root map
• Abelian closures of infinite binary words
• Aperiodic two-dimensional words of small abelian complexity
• Initial powers of Sturmian sequences
• Everywhere α-Repetitive Sequences and Sturmian Words
• Abelian repetitions in Sturmian words
• Abelian repetitions in partial words
• A gap of the exponents of repetitions of Sturmian words
• The undirected repetition threshold and undirected pattern avoidance
• Every nonnegative real number is an abelian critical exponent
• scientific article; zbMATH DE number 6272378 (Why is no real title available?)
• Avoiding abelian powers cyclically
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Abelian combinatorics on words: a survey
• Fractional powers in Sturmian words
• Abelian-square-rich words
• On \(k\)-abelian equivalence and generalized Lagrange spectra
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Consecutive power occurrences in Sturmian words

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)