Lower-bounds on the growth of power-free languages over large alphabets

Abstract

We study the growth rate of some power-free languages. For any integer $k$ and real $\beta >1$, we let $\alpha (k,\beta )$ be the growth rate of the number of $\beta$-free words of a given length over the alphabet $\{1,2,\dots ,k\}$. Shur studied the asymptotic behavior of $\alpha (k,\beta )$ for $\beta \ge 2$ as $k$ goes to infinity. He suggested a conjecture regarding the asymptotic behavior of $\alpha (k,\beta )$ as $k$ goes to infinity when $1<\beta <2$. He showed that for $\frac{9}{8}\le \beta <2$ the asymptotic upper-bound holds of his conjecture holds. We show that the asymptotic lower-bound of his conjecture holds. This implies that the conjecture is true for $\frac{9}{8}\le \beta <2$.