# Branching Densities of Cube-Free and Square-Free Words
## 4 Positions Fixed by Small Cubes  
### Regular Approximations and Alo-Corasick Automata  
To estimate the number of letters in a cube-free word that are fixed by small cubes, we analyze finite automata recognizing some approximations of the language \(\mathsf{CF}\). Let \(L_{i}\) be the language of all binary words containing no cubes of period \(\leq i\). Then, \(L_{i}\) contains \(\mathsf{CF}\) and is regular (as a language defined by a finite set of forbidden factors); \(L_{i}\) is referred to as \(i\)th _regular approximation_ of \(\mathsf{CF}\). The study of regular approximations is a standard approach to power-free languages (see, e.g., [9] (Section 3)). A regular language given by a finite set of forbidden factors can be represented by a _partial_ deterministic finite automaton (dfa) built by a variation of the classical Aho-Corasick algorithm, as described in [27]. Let us provide some necessary details for regular approximations of \(\mathsf{CF}\), following a more general scheme from [28]. To get the dfa \(\mathcal{A}_{i}\) accepting the language \(L_{i}\), one proceeds in three steps. 1. List all \(p\)-cubes with periods \(p\leq i\) and build the prefix tree \(\mathcal{P}_{i}\) of these words; then, the leaves of \(\mathcal{P}_{i}\) are exactly the \(p\)-cubes, and all internal nodes are cube-free words:
2. Consider \(\mathcal{P}_{i}\) as a partial dfa with the initial state \(\lambda\) and complete this dfa, adding transitions by the Aho-Corasick rule: _if there is no transition from a state \(u\) by a letter \(c\), add the transition \(u\xrightarrow{c}v\), where \(v\) is the longest suffix of \(uc\), present in \(\mathcal{P}_{i}\)_;
3. Delete all leaves of \(\mathcal{P}_{i}\) from the obtained automaton. The resulting partial dfa is \(\mathcal{A}_{i}\); it accepts by any state and rejects if it cannot read the word. For details see, for example, [27]. Let us fix some \(i\geq 1\) and analyze the properties of \(\mathcal{A}_{i}\). We write \(u.v\) for the state of \(\mathcal{A}_{i}\) reached from the state \(u\) by the path labelled by \(v\). The following lemma connects \(\mathcal{A}_{i}\) and fixed letters in cube-free words. A letter \(w[j]\) of a cube-free word \(w\) is fixed by a \(p\)-cube with \(p\leq i\) if the state \(\lambda. (w[1..j-1])\) of the dfa \(\mathcal{A}_{i}\) has a single outgoing transition. Wl.o.g., \(w[j]=a\). Since \(w\) is cube-free, the states \(\lambda. (w[1..j-1])\) and \(\lambda. (w[1..j])\) exist and are connected by an edge labelled by \(a\). Let \(w[j]\) be fixed by a \(p\)-cube; this means that \(w[1..j-1]b\) ends with some \(p\)-cube \(uuu\); since \(p\leq i\), \(\mathcal{P}_{i}\) has the leaf \(uuu\). By the Aho-Corasick rule, the edge \(\lambda. (w[1..j-1])\xrightarrow{b}uuu\) was added to \(\mathcal{P}_{i}\) (step 2 above) and then deleted together with the leaf \(uuu\) (step 3). Thus, the state \(\lambda. (w[1..j-1])\) has a single outgoing transition. For the other direction, note that if \(\lambda. (w[1..j-1])\) has the only transition to \(\lambda. (w[1..j])\), then the state \(\lambda. (w[1..j-1]b)\) was deleted at step 3. Hence, this state is some \(p\)-cube \(uuu\) with \(p\leq i\). Since the Aho-Corasick rule implies that the state \(\lambda.v\) is always a suffix of \(v\), \(w[1..j-1]b\) has the suffix \(uuu\), whence the result. In accordance with the other notation, we call _fixed_ the states of \(\mathcal{A}_{i}\) with a single outgoing transition and the edges representing these transitions. The next lemma shows how to get an upper bound on the number of letters in a word, fixed by short cubes. Let \(d_{i}\) and \(c_{i}\) be minimal numbers such that in the automaton \(\mathcal{A}_{i}\) (a) for any \(m\), every simple cycle of length \(m\) contains, at most, \(d\);\(m\) fixed states, and (b) for any \(n\), every simple path of length \(n\) contains at most \(d_{i}n+c_{i}\) fixed states. Then, every cube-free word \(w\) contains, at most, \(d_{i}|w|+c_{i}\) positions fixed by \(p\)-cubes with \(p\leq i\)._  
Proof.