Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


On a group theoretic generalization of the Morse-Hedlund theorem

Authors: Émilie Charlier, Svetlana Puzynina and Luca Q. Zamboni
Journal: Proc. Amer. Math. Soc. 145 (2017), 3381-3394
MSC (2010): Primary 37B10
Published electronically: January 31, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we give a broad unified framework via group actions for constructing complexity functions of infinite words $ x=x_0x_1x_2\cdots \in \mathbb{A}^{\mathbb{N}}$ with values in a finite set $ \mathbb{A}.$ Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. We consider infinite sequences of permutation groups $ \omega = (G_n)_{n\geq 1}$ with each $ G_n \subseteq S_n.$ Associated with every such sequence is a complexity function $ p_{\omega ,x}:\mathbb{N} \rightarrow \mathbb{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 $ \mathbb{A}^n$ given by $ g* (u_1u_2\cdots u_n)=u_{g^{-1}(1)}u_{g^{-1}(2)}\cdots u_{g^{-1}(n)}.$ Each choice of $ \omega =(G_n)_{n\geq 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\in \mathbb{A}^{\mathbb{N}}$ contains at least $ n+1$ distinct factors of each length $ n.$ Moreover $ x\in \mathbb{A}^{\mathbb{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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B10

Retrieve articles in all journals with MSC (2010): 37B10

Additional Information

Émilie Charlier
Affiliation: Département de Mathématique, Université de Liège, 4000 Liège, Belgium

Svetlana Puzynina
Affiliation: LIP, ENS de Lyon, Université de Lyon, 69007 Lyon, France – and – Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia

Luca Q. Zamboni
Affiliation: Institut Camille Jordan, Université Lyon 1, 69622 Villeurbanne Cedex, France

Keywords: Symbolic dynamics, complexity, Sturmian words, discrete interval exchange transformations
Received by editor(s): November 11, 2015
Received by editor(s) in revised form: August 29, 2016
Published electronically: January 31, 2017
Additional Notes: The second author was supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program Investissements d’Avenir (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR)
Communicated by: Nimish Shah
Article copyright: © Copyright 2017 American Mathematical Society