The subword complexity of smooth words on 2-letter alphabets

Abstract

Let ${\gamma }_{a,b}(n)$ be the number of smooth words of length $n$ over the alphabet $\{a,b\}$ with $a<b$. Say that a smooth word $w$ is \emph{left fully extendable} (LFE) if both $aw$ and $bw$ are smooth. In this paper, we prove that for any positive number $\xi$ and positive integer $n_0$ such that the proportion of $b$'s is larger than $\xi$ for each LFE word of length exceeding $n_0$, there are two constants $c_1\text{and}{c}_2$ such that for each positive integer $n$, one has {eqnarray} c_{1}\cdot n^{\frac{\log (2b-1)}{\log (1+(a+b-2)(1-ξ))}}<γ_{a,b}(n)< c_2\cdot n^{\frac{\log (2b-1)}{\log (1+(a+b-2)ξ)}}. {eqnarray} In particular, taking $a=1\text{and}b=2$ in the above inequalities arrives at Huang and Weakley's result. Moreover, for 2-letter even alphabet $\{a,b\}$, there are two suitable constants $c_1,c_2$ such that \{eqnarray} c_{1}\cdot n^{\frac{\log (2b-1)}{\log ((a+b)/2)}}<γ_{a,b}(n)< c_2\cdot n^{\frac{\log (2b-1)}{\log ((a+b)/2)}}\textit{for each positive integer $n$}.\{eqnarray}

20 Pages

References in corpus (1)

• The powers of smooth words over arbitrary 2-letter alphabets

Cited by in corpus (1)

• Maximal right smooth extension chains