Balance and Abelian complexity of the Tribonacci word

G. Rauzy showed that the Tribonacci minimal subshift generated by the morphism τ : 0 ↦ 01 , 1 ↦ 02 and 2 ↦ 0 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 t...

Full description

Saved in:
Bibliographic Details
Published in:Advances in applied mathematics 2010-08, Vol.45 (2), p.212-231
Main Authors: Richomme, Gwénaël, Saari, Kalle, Zamboni, Luca Q.
Format: Article
Language:English
Subjects:
Abelian complexity
Arnoux–Rauzy words
Balanced words
Combinatorial analysis
Combinatorics. Ordered structures
Complexity
Computer Science
Discrete Mathematics
Exact sciences and technology
Fractal analysis
Fractals
General mathematics
General, history and biography
Mathematical analysis
Mathematics
Measure and integration
Numerical analysis
Numerical analysis. Scientific computation
Order, lattices, ordered algebraic structures
Parikh vectors
Proving
Sciences and techniques of general use
Spectra
Tribonacci
Uranium
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:G. Rauzy showed that the Tribonacci minimal subshift generated by the morphism τ : 0 ↦ 01 , 1 ↦ 02 and 2 ↦ 0 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 ρ ( n ) of the Tribonacci word t which is the unique fixed point of τ. We show that ρ ( n ) ∈ { 3 , 4 , 5 , 6 , 7 } for each n ⩾ 1 . 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 a ∈ { 0 , 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: The first uses the word combinatorial properties of the generating morphism, while the second exploits the spectral properties of the incidence matrix of τ. Although we show that ρ ( n ) assumes each value 3 ⩽ i ⩽ 7 , the sequence ( ρ ( n ) ) n ⩾ 1 itself seems to be rather mysterious and may reflect some deeper properties of the Rauzy fractal.
ISSN:0196-8858
1090-2074
DOI:10.1016/j.aam.2010.01.006