Factor complexity of S-adic words generated by the Arnoux-Rauzy-Poincaré algorithm

DOI10.1016/J.AAM.2014.11.001zbMATH Open1310.68170OpenAlexW3101218601MaRDI QIDQ477772FDOQ477772

Authors Valérie Berthé, Sébastien Labbé 

Publication date 9 December 2014

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

multidimensional continued fractionssubstitutionsfactor complexity\(S\)-adic wordsArnoux-Rauzy wordsPoincaré algorithm

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Combinatorics on words (68R15)

Abstract: The Arnoux-Rauzy-Poincar'e multidimensional continued fraction algorithm is obtained by combining the Arnoux-Rauzy and Poincar'e algorithms. It is a generalized Euclidean algorithm. Its three-dimensional linear version consists in subtracting the sum of the two smallest entries to the largest if possible (Arnoux-Rauzy step), and otherwise, in subtracting the smallest entry to the median and the median to the largest (the Poincar'e step), and by performing when possible Arnoux-Rauzy steps in priority. After renormalization it provides a piecewise fractional map of the standard $2$-simplex. We study here the factor complexity of its associated symbolic dynamical system, defined as an $S$-adic system. It is made of infinite words generated by the composition of sequences of finitely many substitutions, together with some restrictions concerning the allowed sequences of substitutions expressed in terms of a regular language. Here, the substitutions are provided by the matrices of the linear version of the algorithm. We give an upper bound for the linear growth of the factor complexity. We then deduce the convergence of the associated algorithm by unique ergodicity.

Recommendations

• Convergence and factor complexity for the Arnoux-Rauzy-Poincaré algorithm
• \(S\)-adic sequences: a bridge between dynamics, arithmetic, and geometry
• \(S\)-adic expansions related to continued fractions
• A combinatorial proof of \(S\)-adicity for sequences with linear complexity
• On the number of Arnoux-Rauzy words

Cites Work

• scientific article; zbMATH DE number 3737757 (Why is no real title available?)
• scientific article; zbMATH DE number 1503600 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A unique ergodicity of minimal symbolic flows with linear block growth
• Balancedness of Arnoux-Rauzy and Brun words
• Balances for fixed points of primitive substitutions.
• Beyond substitutive dynamical systems: \(S\)-adic expansions
• Billiard complexity in rational polyhedra
• Bispecial factors in circular non-pushy D0L languages
• Complexity and special factors
• Complexity of trajectories in rectangular billiards
• Convergence and factor complexity for the Arnoux-Rauzy-Poincaré algorithm
• Deviation for interval exchange transformations
• Discrete linear objects in dimension n: the standard model
• Do the properties of an \(S\)-adic representation determine factor complexity?
• Factor complexity
• Infinite words with uniform frequencies, and invariant measures
• Minimal symbolic flows having minimal block growth
• Rank and symbolic complexity
• Représentation géométrique de suites de complexité $2n+1$
• Sequences with minimal block growth II
• Some improvements of the \(S\)-adic conjecture
• Substitutions in dynamics, arithmetics and combinatorics
• The three-dimensional Poincaré continued fraction algorithm
• Uniformly balanced words with linear complexity and prescribed letter frequencies

Cited In (17)

• \(S\)-adic sequences: a bridge between dynamics, arithmetic, and geometry
• Linear-fractional invariance of the simplex-module algorithm for expanding algebraic numbers in multidimensional continued fractions
• A local algorithm for constructing derived tilings of the two-dimensional torus
• Periodic karyon expansions of algebraic units in multidimensional continued fractions
• \(S\)-adic expansions related to continued fractions
• Characterization of infinite LSP words and endomorphisms preserving the LSP property
• Localized Pisot matrices and joint approximations of algebraic numbers
• Simplex-karyon algorithm of multidimensional continued fraction expansion
• Do the properties of an \(S\)-adic representation determine factor complexity?
• The karyon algorithm for expansion in multidimensional continued fractions
• Almost everywhere balanced sequences of complexity \(2n + 1\)
• Bispecial factors in the Brun \(S\)-adic system
• Linear-fractional invariance of multidimensional continued fractions
• On non-repetitive complexity of Arnoux-Rauzy words
• Convergence and factor complexity for the Arnoux-Rauzy-Poincaré algorithm
• The best approximation of algebraic numbers by multidimensional continued fractions
• On some symmetric multidimensional continued fraction algorithms

This page was built for publication: Factor complexity of \(S\)-adic words generated by the Arnoux-Rauzy-Poincaré algorithm

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