# Branching Densities of Cube-Free and Square-Free Words
## 4 Positions Fixed by Small Cubes
### Cube-Free Words with Small Branching Density  
**Theorem 5**. : _The minimum branching density of an infinite cube-free word is less than or equal to \(13/29\approx 0.44828\)._  
Proof. : The result of Lemma 6 gives us an idea of constructing an infinite cube-free word with branching density less than \(\beta-1\). We see that \(1-d_{15}\approx 0.44792<\beta-1\) (while \(1-d_{14}\approx 0.45833>\beta-1\)). Our aim is to construct an infinite cube-free word which has the density of fixed positions very close to \(d_{15}\). Using the table \(P(j,v)\) of [PERSON]'s algorithm (see Remark 3), we find that the automaton \(\mathcal{A}_{15}\) contains exactly four cycles \(C_{1}\), \(C_{2}\), \(\tilde{C}_{1}\), and \(\tilde{C}_{2}\), each of length \(96\), reaching the minimummean cost \((1-d_{15})\). All four cycles are disjoint; the labels of cycles \(\mathcal{C}_{1},\mathcal{C}_{2}\) are complements of the labels of \(C_{1}\) and \(C_{2}\), respectively. We note that \(C_{1}\) and \(C_{2}\) are connected to each other by many edges. Let us consider a subgraph of \(\mathcal{A}_{15}\) consisting of \(C_{1}\), \(C_{2}\), and two edges connecting them as in Figure 7.  
Since in the Aho-Corasick automaton, all edges with a common endpoint have the same label (if this endpoint is distinct from \(\lambda\)), the paths from \(u\) to \(v\) and from \(u^{\prime}\) to \(v\) in Figure 7 are labeled by the same word \(x_{1}\), while the paths from both \(v\) and \(v^{\prime}\) to \(u^{\prime}\) are labeled by the same word \(x_{2}\). Denote the labels of the paths from \(v\) to \(u\) and from \(u^{\prime}\) to \(v^{\prime}\) by \(y_{1}\) and \(y_{2}\), respectively. Then the label of \(C_{1}\) is \(x_{1}y_{1}\) (starting from \(u\)), the label of \(C_{2}\) is \(x_{2}y_{2}\) (starting from \(v^{\prime}\)), and there is an \"outer\" cycle \(C_{3}\) with the label \(x_{1}x_{2}\) (starting from \(u^{\prime}\)). We also note that \(x_{1}\) and \(y_{2}\) (resp., \(x_{2}\) and \(y_{1}\)) begin with different letters. Analyzing the subgraph of \(\mathcal{A}_{15}\) generated by  
In other terms, to get \(\phi(\mathbf{t})\), we replace each \(a\) (resp., \(b\)) in \(\mathbf{t}\) with \(x_{1}\) (resp., \(x_{2}\)), and then insert \(y_{i}\) in the middle of each factor \(x_{i}x_{i}\) of the obtained word:  
\[\mathbf{t}=a bb aa bb aa bb aa ba bb a \ldots\] \[\phi(\mathbf{t})=x_{1} x_{2}y_{2}x_{2} x_{1}x_{2} x_{1}y_{1}x_{1} x_{2}y_{2}x_{2} x_{1}y_{1}x_{1} x_{2}x_{1} x_{2}y_{2}x_{2} x_{1}\ldots\]  
Thus, we naturally have a partition of \(\phi(\mathbf{t})\) into factors which we call _blocks_, distinguishing between \(x\)-blocks \(x_{1},x_{2}\) and \(y\)-blocks \(y_{1},y_{2}\). Note that  
\((\diamond)\)\(x_{1}\) and \(x_{2}\) have no occurrences in \(\phi(\mathbf{t})\) other than \(x\)-blocks. Indeed, the factor \(x_{1}[4.9]=aabba\) does not occur in \(x_{2},y_{1},y_{2}\), or on the border of any two blocks; the symmetric property holds for \(x_{2}[3..9]=bbababb\). Let us prove that \(\phi(\mathbf{t})\) is cube-free. Assume to the contrary that \(\phi(\mathbf{t})\) contains a cube; let \(XXX\) be the leftmost of the minimal cubes in \(\phi(\mathbf{t})\). A direct check shows that all words \(x_{i}y_{i}x_{i}\) and \(x_{i}x_{j}x_{i}\) are cube-free. Therefore, \(XXX\) contains a whole \(x\)-block inside; below, \(x_{i}\) denotes the leftmost such block, and \(x_{j}\) denotes the \(x\)-block distinct from \(x_{i}\). The period \(|X|\) of the cube cannot be smaller than the minimum period of \(x_{i}\). It is easy to check that the only period of \(x_{i}\) is \(|x_{i}|-3\). Thus, \(|X|\geq|x_{i}|-3\geq 74\). First, assume that \(x_{i}\) is the only \(x\)-block in \(XXX\). Since for the word \(x_{j}x_{i}x_{j}\) is cube-free, \(XXX\) is an internal factor of either \(x_{i}y_{i}x_{i}y_{i}\) or \(x_{j}x_{i}y_{i}x_{i}\). Since \(|x_{i}y_{i}x_{i}|,|y_{i}x_{i}x_{j}|\leq 175\) and \(|XXX|\geq 74\cdot 3=222\), the length argument shows that \(y_{i}x_{i}\) in the first case, and \(x_{i}y_{i}\) in the second case is a factor of \(XXX\).