# Branching Densities of Cube-Free and Square-Free Words
## 5 The Bounds on Maximum Branching Density  
The branching density of infinite cube-free words can be much bigger than \(\beta-1\approx 0.45758\). The aim of this section is to prove the following theorem. **Theorem 6**. : _(1) The maximum branching density of an infinite binary cube-free word is less than \(67/93\approx 0.72043\). (2) There exists an infinite binary cube-free word with branching density \(18/25=0.72\)._  
**Example 1**. : _The branching density of the Thue-Morse word \(\mathbf{t}\) is 2/3. Indeed, \(\mathbf{t}\) is overlap-free, and thus all fixed letters in it are fixed by 1-cubes. Hence, the fixed letters are exactly the letters a (resp. b) preceded by the \(1\)-square \(bb\) (resp. by aa); in each case, the density of such positions is 1/6, as mentioned in Section 4.3. Thus, the density of fixed positions is 1/3._  
The proof of Theorem 6 is based on the analysis of positions fixed by 1 cube. The distance between two successive occurrences of the square of a letter in a cube-free word is 2 (\(aabb/bbaa\)) or 3 (\(aabaa/bbabb\)) or 4 (\(aababb/bbabaa\)) or 5 (\(aababaa/bbababb\)); it cannot be 1 (\(aaa/bbbb\)) or \(\geq 6\) (\(aababab\cdots/bbababa\cdots\)) because of cube-freeness. Hence, if we know a prefix \(w[1..i]\) of a cube-free word, this prefix ends with a 1-square, and the distance \(d\) to the next 1-square is known; then we can uniquely reconstruct \(w[1..i+d]\). We consider an auxiliary alphabet \(\Delta=\{2,3,4,5\}\) and refer to its elements as _digits_ and to the words over it as _codes_. For every cube-free word \(\mathbf{w}\in\Sigma^{\infty}\) we define its _distance code_\(\operatorname{dist}(\mathbf{w})\in\Delta^{\infty}\) as follows: \(\operatorname{dist}(\mathbf{w})[i]\) is the distance between the \(i\)th and \((i{+}1)\)th 1-squares in \(\mathbf{w}\) (counting from the left). For example, one has  
\[\begin{array}{  
**Remark 5**.: _The word \(\mathsf{word}(33)=aabababaa\) is not a proper factor of a cube-free word; \(\mathsf{word}(434)=aababababababaa\) contains \((\mathit{bb})^{3}\), as well as \(\mathsf{word}(435),\mathsf{word}(534)\), and \(\mathsf{word}(535)\). In the following list of cube-free words, letters fixed by \(p\)-cubes are underlined by \(p\) lines:_  
\[\mathsf{word}(2)=a\mathit{abb} \mathsf{word}(234)=a\mathit{abb}\mathit{b}\mathit{b}\mathit{ababab}\] \[\mathsf{word}(3)=a\mathit{abaa} \mathsf{word}(235)=  
than \(3[Y^{\prime}]-1\). Therefore, no almost-cubes are present in \(\mathbf{u}\). This proves Statement 2 of the theorem. For Statement 1, we take a cube-free word \(\mathbf{w}\) of maximum branching density and consider its code \(\operatorname{dist}(\mathbf{w})\). By Remark 5, each digit in \(\operatorname{dist}(\mathbf{w})\) corresponds to a letter fixed by a 1-cube, and a digit 5 also corresponds to a letter fixed by a 2-cube. The density of fixed positions in \(\mathbf{w}\) is at its minimum, and thus is upper-bounded by \(7/25\), which is such a density for \(\mathbf{u}\). Since \(7/25\) is closer to \(1/4\) than to \(1/3\), the majority of digits in \(\mathbf{w}\) are 4's. Since \(\mathbf{w}\) has the same branching density as each of its suffixes, we assume w.l.o.g. that \(\operatorname{dist}(\mathbf{w})\) begins with 4, and represent it as a sequence of blocks: each block consists of one or more 4's in the beginning and one or more other digits in the end. Note that the words \(\operatorname{word}(54^{4}5)\) and \(\operatorname{word}(c4^{5}d)\), for any digits \(c,d\), contain an 8-cube (cf. Case 1 above). Then, a short search reveals all blocks providing the density of fixed positions not greater than 0.3:  
\[ \begin{array}{ll}44442:5/18\approx 0.27778;&4445:5/17\approx 0.29412;\\ 44445:6/21\approx 0.28571;&442:3/10;\\ 4442:4/14\approx 0.28571.\end{array} \]  
(We recall that blocks containing 3's are restricted, as shown in Remark 5.) We note that \(\operatorname{word}((4^{4}2)^{5}4^{4})\) and \(\operatorname{word}((4^{4}2)^{5}4^{3}5)\) contain 36-cubes, while \(\operatorname{word}(4^{3}24^{3}24^{3})\) contains a 14-cube.