Growth rate of binary words avoiding \(xxx^{R}\) (Q897919)

The history of the investigation of words avoiding a given pattern reaches to the very roots of the discipline of combinatorics on words. The infinite word of Thue-Morse is the first known cube-free infinite word. Words avoiding various variants of cube words have been investigated. Since it is often not difficult to find an infinite word avoiding a given pattern, the interest moved to the investigation of other related questions. One of them is the growth rate: what is the speed of growth of the function describing the number of words of length \(n\) avoiding the pattern. The current paper shows, in a non-trivial way, that the number of words avoiding the non-empty factor \(xxx^{R}\), where \(x^{R}\) is the mirror image of the word \(x\), can be bounded both from above and from below by functions of the form \(n^{\log_{2}n+o\left( \log_{2}n\right) }\), answering in this way a question of \textit{C. F. Du} et al. [``Decision algorithms for Fibonacci-automatic words, with applications to pattern avoidance'', Preprint, \url{arXiv:1406.0670}].