On a group theoretic generalization of the Morse-Hedlund theorem

Abstract

In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word $x\in A^N,$ over a non empty finite alphabet $A,$ contains at least $n+1$ distinct factors of each length $n.$ They further showed that an infinite word $x$ has exactly $n+1$ distinct factors of each length $n$ if and only if $x$ is binary, aperiodic and balanced, i.e., $x$ is a Sturmian word. In this paper we obtain a broad generalization of the Morse-Hedlund theorem via group actions. Given a subgroup $G$ of the symmetric group $S_n,$ let $1\le \epsilon (G)\le n$ denote the number of distinct $G$-orbits of $\{1,2,\dots ,n\}.$ Since $G$ is a subgroup of $S_n,$ it acts on $A^n=\{a_1{a}_2\cdots a_n|a_i\in A\}$ by permutation. Thus, given an infinite word $x\in A^N$ and an infinite sequence $\omega =(G_n{)}_{n\ge 1}$ of subgroups $G_n\subseteq S_n,$ we consider the complexity function $p_{\omega ,x}:N\to 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.$ We show that if $x$ is aperiodic, then $p_{\omega ,x}(n)\ge \epsilon (G_n)+1$ for each $n\ge 1,$ and moreover, if equality holds for each $n,$ then $x$ is Sturmian. Conversely, let $x$ be a Sturmian word. Then for every infinite sequence $\omega =(G_n{)}_{n\ge 1}$ of Abelian subgroups $G_n\subseteq S_n,$ there exists ${\omega }^{\prime }=(G_n^{\prime }{)}_{n\ge 1}$ such that for each $n\ge 1:$ $G_n^{\prime }\subseteq S_n$ is isomorphic to $G_n$ and $p_{{\omega }^{\prime },x}(n)=\epsilon (G_n^{\prime })+1.$ Applying the above results to the sequence $(I{d}_n{)}_{n\ge 1},$ where $I{d}_n$ is the trivial subgroup of $S_n$ consisting only of the identity, we recover both directions of the Morse-Hedland theorem.