An explicit condition for boundedly supermultiplicative subshifts

Abstract

We study some properties of the growth rate of $\mathcal{L}(\mathcal{A},\mathcal{F})$, that is, the language of words over the alphabet $\mathcal{A}$ avoiding the set of forbidden factors $\mathcal{F}$. We first provide a sufficient condition on $\mathcal{F}$ and $\mathcal{A}$ for the growth of $\mathcal{L}(\mathcal{A},\mathcal{F})$ to be boundedly supermultiplicative. That is, there exist constants $C>0$ and $\hat{I}\pm \ge 0$, such that for all $n$, the number of words of length $n$ in $\mathcal{L}(\mathcal{A},\mathcal{F})$ is between $\hat{I}{\pm }^n$ and $C\hat{I}{\pm }^n$. In some settings, our condition provides a way to compute $C$, which implies that $\hat{I}\pm$, the growth rate of the language, is also computable whenever our condition holds. We also apply our technique to the specific setting of power-free words where the argument can be slightly refined to provide better bounds. Finally, we apply a similar idea to $\mathcal{F}$-free circular words and in particular we make progress toward a conjecture of Shur about the number of square-free circular words.

18 pages; minor revision before publication