On the \(k\)-abelian complexity of the Cantor sequence (Q1689047)

The Cantor sequence is the fixed point beginning with \(1\) of the \(3\)-uniform morphism \(1 \to 101\), \(0 \to 000\). It is clearly related -- after renormalization -- to the ternary Cantor set. The authors of the paper under review are interested in determining the \(k\)-abelian complexity of this infinite sequence. Recall that the \(k\)-abelian complexity is the function that counts for each length \(n\) the number, up to \(k\)-equivalence, of blocks of consecutive symbols of length \(n\) occurring in the sequence, where two blocks are called \(k\)-equivalent if they have the same prefix of length \(k-1\), the same suffix of length \(k-1\) and, for each word \(z\) of length \(k\), the same number of occurrences of this word \(z\) as a factor of the sequence (the notion of \(k\)-abelian equivalence was introduced by \textit{J. Karhumäki} [Inf. Control 47, 155--165 (1980; Zbl 0457.68079)]). Note that for \(k= \infty\) we obtain the usual (block-)complexity, while for \(k=1\) we obtain the usual abelian complexity. A typical question, beside computing the \(k\)-abelian complexity of a given sequence, is to determine its properties when the sequence itself has some kind of regularity. In this paper the authors prove that, for any \(k \geq 2\), the \(k\)-abelian complexity of the Cantor sequence is a \(3\)-regular sequence, thus supporting the conjecture that, for any \(\ell \geq 2\), the \(k\)-abelian complexity of an \(\ell\)-automatic sequence is \(\ell\)-regular (see [\textit{A. Parreau} et al., Electron. J. Comb. 22, No. 1, Research Paper P1.27, 44 p. (2015; Zbl 1317.68138)]).