2015/05/14 by Charlier, Emilie, Puzynina, Svetlana, Zamboni, Luca Q. · 2 citations
#37B10 #Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics
paper · doi:10.48550/arxiv.1505.03848
In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word x∈ AN, 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 Sn, let 1≤ ε(G)≤ n denote the number of distinct G-orbits of \1,2,… ,n\. Since G is a subgroup of Sn, it acts on An=\a1a2⋯ an | ai∈ A\ by permutation. Thus, given an infinite word x∈ AN and an infinite sequence ω=(Gn)n≥ 1 of subgroups Gn ⊆ Sn, we consider the 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 Gn. We show that if x is aperiodic, then pω, x(n)≥ε(Gn)+1 for each n≥ 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 ω=(Gn)n≥ 1 of Abelian subgroups Gn ⊆ Sn, there exists ω'=(Gn')n≥ 1 such that for each n≥ 1: Gn'⊆ Sn is isomorphic to Gn and pω',x(n)=ε(G'n)+1. Applying the above results to the sequence (Idn)n≥ 1, where Idn is the trivial subgroup of Sn consisting only of the identity, we recover both directions of the Morse-Hedland theorem.