On a group theoretic generalization of the Morse-Hedlund theorem

International audienceIn 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