There exist infinite cube-free words over any sequence of binary alphabets

Abstract

We prove that for any sequence of binary alphabets ${\mathcal{A}}_1,{\mathcal{A}}_2,\dots$, there exists a cube-free word $c_1{c}_2\dots$ so that $c_1\in {\mathcal{A}}_1,c_2\in {\mathcal{A}}_2,\dots$. In particular, for every $n$, there are at least $1.35^n$ cube-free words in ${\mathcal{A}}_1\times {\mathcal{A}}_2\times \cdots \times {\mathcal{A}}_n$. We also prove that if the list of alphabets is computable then one of these words is computable and its $n$th letter can be computed in time polynomial in $n$.