# Branching Densities of Cube-Free and Square-Free Words
## 3 Positions Fixed by Big Cubes
Recall that \(t-i=3q-l-1\), so all are strictly above the lines \(q=\frac{l+p}{3}\) and \(q=\frac{l}{2}\) in Figure 2.  
Thus, to prove the theorem, it remains to justify the colouring of the stripe between the line \(q=\frac{l+p}{2}\) and the broken line \(\{q=\frac{l+p}{3};q=\frac{l}{2}\}\) in Figure 2. We split this stripe into zones I-IV by the lines \(q=l\), \(q=p\), and \(q=\frac{l+2p}{3}\). The arguments for all zones are very similar, so we provide maximum details for zone I and more concise proofs for zones II-IV. _Zone I: \(q>\frac{l+2p}{3}\)._ Together with \(q<2p\) (O1) and \(2q<l+p\) (O2), this gives the mutual location of the suffix \(QQQ\) and factor \(PPP^{\prime}\) of \(w\), as depicted in Figure 3. Equal letters denote equal factors; note that \(x\
eq\lambda\) since \(2q<l+p\) and \(z\
eq\lambda\), since \(q<2p\). \begin{table}
\begin{tabular}{l l} \hline \hline
**Point** & **Word \(w\) (\(PPP^{\prime}\) is bold, \(QQQ\) is underlined)** \\ \hline \(l=p/2\) & \(\cdots b\) **Xb Xu Xb Xu Xb Xb** \\ \(q=p/2\) & \\ \hline \(l=2p/5\) & \(\cdots b\) **Xb Xb Xu Xb Xb Xa Xb Xa Xb Xb Xa Xb Xb** \\ \(q=3p/5\) & \\ \hline \(l=2p\) & \(\cdots b\) **Xa Xb Xb** \\ \(q=p\) & \\ \hline \(l=8p/3\) & \(\cdots b\) **Xb Xa Xb Xa Xb Xa Xb Xa Xb Xa Xb Xa Xb** \\ \(q=5p/3\) & \\ \hline \(l=4p\) & \(\cdots b\) **Xa Xb** **Xb** **Xa Xb** \\ \(q=2p\) & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Example words \(w\) with the pair \((l,q)\) in the green corner of the red zone boundary in Figure 2. One can take \(X=abbaab\) or a longer overlap-free word of similar structure. The words \(y\), \(zy\), and \(yaxz\) are prefixes of \(Q\) (Figure 3). By the length argument, \(y\) is a prefix of \(zy\), which is a prefix of \(yaxz\). Then \(zyaxz\subseteq PP\) (Figure 3) implies \(zyx\subseteq PP\). Since \(PP\) is cube-free, \(zzz\
ot\subseteq PP\), and thus \(z\) is not a prefix of \(y\). Since \(z\) and \(y\) are both prefixes of \(Q\), we have \(z=yz^{\prime}\), \(z^{\prime}\
eq\lambda\). Further, \(yaxyaxz\subseteq QQ\) (\(Q\) begins with \(yaxz\) and ends with \(yax\)) but \((yax)^{\prime}\
ot\subseteq QQ\), because \(QQ\) is cube-free. Then, the fact that \(z\) and \(yax\) are both prefixes of \(Q\) implies that \(z=yz^{\prime}\) is a proper prefix of \(yax\), so \(ax=z^{\prime}x^{\prime}\), \(x^{\prime}\
eq\lambda\). Now compare \(zy=yz^{\prime}y\) against \(yaxz=yz^{\prime}x^{\prime}yz^{\prime}\). We see that \(y\) is a proper prefix of \(x^{\prime}y\) by the length argument. By Lemma 1 we can write \(x^{\prime}=fg,y=(fg)^{\prime}f\) for some words \(f,g\); note that \(n\leq 1\) since \(x^{\prime}y\) is cube-free. If \(n=1\), we have  
\[Q=yaxzyax=yz^{\prime}x^{\prime}yz^{\prime}yz^{\prime}x^{\prime}= fgfz^{\prime}fgfz^{\prime}fgz^{\prime}fg,\text{ and then}\] \[(fgfz^{\prime}fg)^{3}\subseteq QQ=fgfz^{\prime}fgfgz^{\prime} fgfz^{\prime}f\&\&\&\&\&\&\&\&\&\&\&\&\&\&\&\&\&  
_Zone III: \(q\leq l,q<p\)._ Together with \(q>\frac{l+p}{3}\) (O3), this gives the mutual location of the suffix \(QQQ\) and factor \(PPP^{\prime}\) of \(w\), as depicted in Figure 5 (\(v,z\
eq\lambda\) since \(q<p\); \(x,y\) can be empty). Since \(xa\) and \(vx\) are prefixes of \(Q\) and \(vQ\subseteq PP\) (Figure 5), one has \(vvx\subseteq PP\), so \(v\) is not a prefix of \(x\), and thus \(v=xav^{\prime}\) for some (possibly empty) \(v^{\prime}\). Then \(z=v^{\prime}xby\), \(Q=xav^{\prime}xby\), \(P=v^{\prime}xbyxav^{\prime}xa\). We express \(p,q\), and \(l=q+|y|\) in terms of \(|x|,|v^{\prime}|,|y|\):  
\[ \begin{array}{rcl}p&=&3(|x|+1)|+&2|v^{\prime}|+&|y|,\\ q&=&2(|x|+1)|+&|v^{\prime}|+&|y|,\\ l&=&2(|x|+1)|+&|v^{\prime}|+&2|y|.\end{array}  \tag{3}\]  
From (3), we get \(q=\frac{l+2p-|v^{\prime}|}{4}\leq\frac{l+2p}{4}\); together with the boundaries of Zone III, this line forms the green triangle in Zone III with the vertices \((\frac{p}{2},\frac{p}{2})\), \((\frac{2}{3}p,\frac{2}{3}p)\), \((2p,p)\) (Figure 2). _Zone IV: \(q>l\)._ One has \(q>p/2\) (O1) and \(2q<l+p\) (O2), and so, \(q<p\).