Avoiding 2-binomial squares and cubes (Q2257294)

The concept of 2-binomial equivalence, a refinement of abelian equivalence, was recently introduced by two of the authors [\textit{M. Rigo} and \textit{P. Salimov}, Lect. Notes Comput. Sci. 8079, 217--228 (2013; Zbl 1325.68175)]. Two finite words \(u\) and \(v\) are 2-binomially equivalent if, for all words \(x\) of length at most two, the number of times \(x\) occurs as a scattered subword in \(u\) equals the number of such occurrences of \(x\) in \(v\). In this paper, the authors prove that the minimal alphabet size to construct a word with no 2-binomial squares is three (a 2-binomial square is of the form \(uv\) with \(u\) and \(v\) being 2-binomially equivalent). They also prove such a result for 2-binomial cubes, in which case the minimal alphabet size is two (a 2-binomial cube is of the form \(uvw\) with \(u\), \(v\) and \(w\) being 2-binomially equivalent). More precisely, the fixed-point of the morphism \(0 \mapsto 012\), \(1 \mapsto 02\), \(2 \mapsto 1\) is shown to avoid 2-binomial squares and the fixed-point of the morphism \(0 \mapsto 001, 1 \mapsto 011\) is shown to avoid 2-binomial cubes. The authors conclude their paper by raising a number of questions for future research.