Balance and abelian complexity of the Tribonacci word

DOI10.1016/J.AAM.2010.01.006zbMATH Open1203.68131arXiv0904.2872OpenAlexW3099530912WikidataQ60692088 ScholiaQ60692088MaRDI QIDQ984024FDOQ984024

Kalle Saari, Gwénaël Richomme, Luca Q. Zamboni

Publication date: 13 July 2010

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

Abstract: G. Rauzy showed that the Tribonacci minimal subshift generated by the morphism $au:0mapsto01,1mapsto02and2mapsto0$ is measure-theoretically conjugate to an exchange of three fractal domains on a compact set in $R^2$, each domain being translated by the same vector modulo a lattice. In this paper we study the Abelian complexity AC(n) of the Tribonacci word $t$ which is the unique fixed point of $au$. We show that $AC(n)in3,4,5,6,7$ for each $ngeq1$, and that each of these five values is assumed. Our proof relies on the fact that the Tribonacci word is 2-balanced, i.e., for all factors $U$ and $V$ of $t$ of equal length, and for every letter $ain0,1,2$, the number of occurrences of $a$ in $U$ and the number of occurrences of $a$ in $V$ differ by at most 2. While this result is announced in several papers, to the best of our knowledge no proof of this fact has ever been published. We offer two very different proofs of the 2-balance property of $t$. The first uses the word combinatorial properties of the generating morphism, while the second exploits the spectral properties of the incidence matrix of $au$.

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

Recommendations

• Abelian complexity function of the Tribonacci word
• Balances and Abelian complexity of a certain class of infinite ternary words
• Abelian complexity and abelian co-decomposition
• Abelian complexity of Thue-Morse word over a ternary alphabet
• The Tribonacci substitution

zbMATH Keywords

Arnoux-Rauzy wordsabelian complexityParikh vectorsbalanced wordsTribonacci

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Balanced words
• Title not available (Why is that?)
• Nombres algébriques et substitutions
• Représentation géométrique de suites de complexité $2n+1$
• Title not available (Why is that?)
• Sturmian and Episturmian Words
• Échanges d'intervalles et transformations induites
• Imbalances in Arnoux-Rauzy sequences
• Title not available (Why is that?)
• A generalization of Sturmian sequences: Combinatorial structure and transcendence
• Episturmian words: a survey
• Structure of three-interval exchange transformations. II: A combinatorial description of the trajectories
• Structure of three-interval exchange transformations. III: Ergodic and spectral properties
• Joinings of three-interval exchange transformations
• Structure of three interval exchange transformations. I: An arithmetic study
• On graphs of central episturmian words
• Balances for fixed points of primitive substitutions.
• RECENT RESULTS ON EXTENSIONS OF STURMIAN WORDS
• Discrete planes, \({\mathbb Z}^2\)-actions, Jacobi-Perron algorithm and substitutions
• Frequencies of factors in Arnoux–Rauzy sequences

Cited In (23)

• Templates for the \(k\)-binomial complexity of the Tribonacci word
• On the additive complexity of a Thue-Morse-like sequence
• Computing abelian complexity of binary uniform morphic words
• Initial non-repetitive complexity of infinite words
• Balance properties of Arnoux-Rauzy words
• Balances of m-bonacci Words
• Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words
• On the abelian complexity of generalized Thue-Morse sequences
• On the abelian complexity of the Rudin-Shapiro sequence
• Abelian Complexity and Synchronization
• Minimal Complexities for Infinite Words Written with d Letters
• Mechanical Proofs of Properties of the Tribonacci Word
• Sturmian jungle (or garden?) on multiliteral alphabets
• Characterizations of families of morphisms and words via binomial complexities
• Abelian properties of Parry words
• Abelian complexity of infinite words associated with quadratic Parry numbers
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Another generalization of abelian equivalence: binomial complexity of infinite words
• Relations on words
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• On a generalization of abelian equivalence and complexity of infinite words
• Abelian combinatorics on words: a survey
• Title not available (Why is that?)

Uses Software

• OEIS

This page was built for publication: Balance and abelian complexity of the Tribonacci word

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