Templates for the \(k\)-binomial complexity of the Tribonacci word (Q5919292)

The $k$-binomial complexity of an infinite word $x$ maps the integer $n$ to the number of pairwise non-equivalent factors of length $n$ occurring in $x$. In this paper, based on the notion of template, the authors show that, for all $k\geq 2$, the $k$-binomial complexity of the Tribonacci word coincides with its usual factor complexity $p(n)=2n+1$. It is most significant that at first an algorithm is used to show that the 2-binomial complexity of the Tribonacci word is equal to its factor complexity, and then it can be derived under some mild conditions whether the factor complexity of a given morphic word is equal to its \(k\)-binomial complexity. It is also proven that there exist bounds on the eigenvectors that correspond to larger eigenvalues and that the number of templates that respect these bounds is always finite. Since the notion of template was first introduced in the context of avoidability of abelian powers, the technique adopted in this paper also gives a decision algorithm for the avoidability of $k$-binomial powers in morphic words and even avoidability of patterns in the $k$-binomial sense. The results are quite innovative since a similar result was already known for Sturmian words, but the proof relies on completely different techniques that seemingly could not be applied to the Tribonacci word.