Unary patterns under permutations (Q1659986)

Consider the \(k\)-letter alphabet \(\Sigma_{k}=\{ 0,1,\ldots,k-1\} \). A morphism (antimorphism) \(f\) of \(\Sigma_{k}^{\ast}\) is a mapping \(f:\Sigma_{k}^{\ast}\rightarrow\Sigma_{k}^{\ast}\) satisfying \(f(uv)=f(u)f(v)\) (\(f(uv)=f(v)f(u)\)) for all words \(u,v\in\Sigma_{k}^{\ast}\). Then \(f\) is uniquely determined by its values \(f(a)\) for all \(a\in\Sigma_{k}\). If \(f\) restricted to \(\Sigma_{k}\) is a permutation, then \(f\) is called an (anti-)morphic permutation. A unary pattern involving functional dependencies is a term over the word variable \(x\), function variables, where concatenation can be involved. An instance of a pattern is the result of substituting \(x\) by a word in \(\Sigma_{k}^{+}\) and every function variable by a function over \(\Sigma _{k}^{\ast}\). For example, for \(k=2\), the word \(100\mathbf{10011010}01\) contains an instance (in bold) of the pattern \(x\pi( x) \pi( \pi( x) ) x\) where \(x=10\) and \(\pi\) is the morphic permutation \(0\longmapsto1\), \(1\longmapsto0\). A pattern is avoidable in \(\Sigma_{k}\) if there is an infinite word over \(\Sigma_{k}\) that does not contain any instance of the pattern. The paper investigates avoidability of patterns with morphic or antimorphic permutations only. It is shown that, for \(k\geq3\) and \(| x| \geq2\), each pattern of the form \(\pi_{1}(x)\pi_{2}(x)\cdots\pi_{r}(x)\), \(r\geq4\), is avoidable. Besides some particular cases, the length restriction on \(x\) cannot be removed, otherwise the pattern \(x\pi^{2}(x)\pi^{56} (x)\pi^{33}(x)\) becomes unavoidable.