On a group theoretic generalization of the Morse-Hedlund theorem - Université Claude Bernard Lyon 1 Accéder directement au contenu
Article Dans Une Revue Proceedings of the American Mathematical Society Année : 2017

On a group theoretic generalization of the Morse-Hedlund theorem

Résumé

In this paper we give a broad unified framework via group actions for constructing complexity functions of infinite words x = x 0 x 1 x 2 · · · ∈ A N with values in a finite set A. Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. We consider infinite sequences of permutation groups ω = (G n) n≥1 with each G n ⊆ S n. Associated with every such sequence is a complexity function p ω,x : N → N which counts, for each length n, the number of equivalence classes of factors of x of length n under the action of G n on A n given by g * (u 1 u 2 · · · u n) = u g −1 (1) u g −1 (2) · · · u g −1 (n). Each choice of ω = (G n) n≥1 defines a unique complexity function which reflects a different combinatorial property of a given infinite word. For instance, an infinite word x has bounded Abelian complexity if and only if x is k-balanced for some positive integer k, while bounded cyclic complexity is equivalent to x being ultimately periodic. A celebrated result of G.A. Hedlund and M. Morse states that every aperiodic infinite word x ∈ A N contains at least n+1 distinct factors of each length n. Moreover x ∈ A N has exactly n + 1 distinct factors of each length n if and only if x is a Sturmian word, i.e., binary, aperiodic and balanced. We prove that this characterisation of aperiodicity and Sturmian words extends to this general framework.
Fichier principal
Vignette du fichier
Group Complexity(August 29, 2016) (1).pdf (310.4 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-01829320 , version 1 (19-03-2019)

Identifiants

Citer

Emilie Charlier, Svetlana Puzynina, Luca Q. Zamboni. On a group theoretic generalization of the Morse-Hedlund theorem. Proceedings of the American Mathematical Society, 2017, 145 (8), pp.3381-3394. ⟨10.1090/proc/13589⟩. ⟨hal-01829320⟩
91 Consultations
58 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More