# Branching Densities of Cube-Free and Square-Free Words
## 4 Positions Fixed by Small Cubes
### Cube-Free Words with Small Branching Density
Thus, \(|X|\) is not smaller than the minimum of the periods of words \(x_{i}y_{i},y_{i}x_{i}\). This minimum equals \(84\), which is a period of both \(y_{1}x_{1}\) and \(y_{2}x_{2}\). Hence, \(|XXX|\geq 252=2|x_{i}|+|x_{j}|+|y_{i}|\). However, an internal factor of a word must be shorter by at least two symbols than the word itself; this contradiction shows that \(XXX\) contains more than one \(x\)-block. Therefore, \(XXX\) contains either \(x_{i}y_{i}x_{i}\) or \(x_{i}x_{j}\). Let \(XXX=v_{1}x_{i}y_{i}x_{i}y_{2}\). By the choice of \(x_{i}\), \(v_{1}\) is a proper suffix of \(x_{j}\) and \(v_{2}\), if nonempty, begins with the first letter of \(x_{j}\), which differs from the first letter of \(y_{i}\). Thus, if \(|X|\) equals the minimum period of \(x_{i}y_{i}x_{i}\), which is \(|x_{i}y_{i}|\), then \(v_{2}=\lambda\) and then \(|XXX|<3|X|\), which is impossible. Hence, \(|X|>|x_{i}y_{i}|\). Therefore, for each of the two blocks, \(x_{i}\), we see that \(XXX\) contains another factor \(x_{i}\) at the distance of \(|X|\). By \((\diamond)\), these factors are \(x\)-blocks; both are inside \(v_{2}\) because \(v_{1}\) is a suffix of an \(x\)-block. Then, \(X\) contains at least one occurrence of the block \(x_{i}\). As a result, \(XXX\) contains a factor \(x_{i}wx_{i}wx_{i}\) for some word \(w\) which is a product of blocks; here, \(x_{i}w\) is a cyclic shift of \(X\). Taking the \(\phi\)-pre-image of \(x_{i}wx_{i}wx_{i}\), we obtain a factor of the form \(auaua\) or \(bubub\) in \(\mathbf{t}\), in contradiction with the overlap-freeness property. Finally, let \(XXX=v_{1}x_{i}x_{j}v_{2}\). The word \(x_{i}x_{j}\) has no periods smaller than \(|x_{i}x_{j}|-1\). Hence, \(|X|>|x_{i}|+|x_{j}|-1\) and then \(X\) contains at least one of \(x_{i}\), \(x_{j}\). Since \(v_{1}\) contains no \(x\)-blocks by the choice of \(x_{i}\), \(v_{1}x_{i}\) has no factor \(x_{j}\) by \((\diamond)\). Then, \(X\) must contain \(x_{i}\), and we arrive at a contradiction as in the previous paragraph. Thus, finally, we have proved that \(\phi(\mathbf{t})\) is cube-free. The word \(\phi(\mathbf{t})\) corresponds to an infinite walk from the node \(u\) in the subgraph of \(\mathcal{A}_{15}\) depicted in Figure 7. The walk reads \(x_{1}\) (rule 1 in the definition of \(\phi\)) and then respects rule 2; the details are as follows. Let \(x_{i}\) be just read; if the current letter of \(\mathbf{t}\) coincides with the previous one, the walk returns to the \"start\" node of the same cycle \(C_{i}\) by reading \(y_{i}\) and reads \(x_{i}\) again; otherwise, the walk reads \(x_{j}\), where \(i\
eq j\). We know the fractions of fixed states in the cycles \(C_{1},C_{2}\), and \(C_{3}\); to calculate the density of positions fixed by short squares in \(\phi(\mathbf{t})\) we use the folklore fact that the density of the sets of positions \(i\) such that \(\mathbf{t}[i..i+1]=aa\) (resp., \(ab,ba,bb\)) equals \(1/6\) (resp., \(1/3,1/3,1/6\)). Then in the partition of \(\phi(\mathbf{t})\) into blocks, the densities of the blocks \(x_{1},x_{2}\) are equal and twice bigger than the densities of the blocks \(y_{1}\) and \(y_{2}\). We group the blocks into labels of cycles \(C_{1},C_{2},C_{3}\):  
\[\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}][y_{2}x_{2}][x_{1}\ldots\]Since \(x\)-blocks appear in the labels of two cycles while \(y\)-blocks appear in the label of one cycle, all cycles appear with the same density. Thus, to get the density of fixed letters, we take the total number of fixed states in \(C_{1},C_{2}\), and \(C_{3}\) and divide it by the sum of lengths of cycles to get \(\left(86+53+53\right)/\left(156+96+96\right)=16/29\). Then the branching density of \(\phi(\mathbf{t})\) is, at most, \(13/29\). The theorem is proved. **Remark 4**. : _In fact, the branching density of \(\phi(\mathbf{t})\) is exactly \(13/29\): refining the analysis of cube-freeness of \(\phi(\mathbf{t})\), it is possible to show that this word does not contain letters fixed by long cubes._