An explicit condition for boundedly supermultiplicative subshifts

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 \(\alpha\ge0\), such that for all \(n\), the number of words of length \(n\) in \(\mathcal{L}(\mathcal{A},\mathcal{F})\) is between \(\alpha^n\) and \(C\alpha^n\). In some settings, our condition provides a way to compute \(C\), which implies that \(\alpha\), 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.Mathematics Subject Classifications: 68R15Keywords: Subshift, supermultiplicativity, growth of languages, circular word