On a group theoretic generalization of the Morse-Hedlund theorem

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.