A conjecture on the 2-abelian complexity of the Thue-Morse word
Michel Rigo, Aline Parreau, Élise Vandomme · Open Repository and Bibliography (University of Liège) · 2014
The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k-abelian complexity is a generalization of the abelian complexity, corresponding to the case where k=1. Formally, two words u and v of the same length are k-abelian equivalent if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The aim of this talk is to study the 2-abelian complexity a(n) of the Thue-Morse word. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a work of Madill and Rampersad (2012) where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will present some arguments supporting our conjecture. They are based on functions counting some subword of length 2 occuring in prefixes of the Thue-Morse word.