# Branching Densities of Cube-Free and Square-Free Words
## 2 Preliminaries  
We study words and languages over the binary alphabet \(\{a,b\}\) (apart from Section 4.2, where the result over a ternary alphabet is also presented), writing \(\lambda\) for the empty word and \(|w|\) for the length of a finite word \(w\). If \(w=xyz\) for some words \(x,y\), and \(z\) (any of which can be empty), then \(x,y,z\) are, respectively, a _prefix_, a _factor_, and a _suffix_ of \(w\). We write \(y\subseteq w\) to indicate that \(y\) is a factor of \(w\). The set of all finite (nonempty finite, infinite) words over an alphabet \(\Sigma\) is denoted by \(\Sigma^{*}\) (resp., \(\Sigma^{+},\Sigma^{\infty}\)). Elements of \(\Sigma^{+}\) (\(\Sigma^{\infty}\)) are treated as functions \(w:\{1,\ldots,n\}\rightarrow\Sigma\) (resp., \(\mathbf{w}:\mathbb{N}\rightarrow\Sigma\)). We write \([i..j]\) for the range \(i,i+1,\ldots,j\) of positive integers; the notation \(w[i..j]\) stands for the factor of the word \(w\) occupying this range, as well as for the particular occurrence of this factor in \(w\); \(w[i..]=w[i]\) is just the \(i\)th letter of \(w\). A factor \(w[i..j]\) is _internal_ if \(i>1\) and \(j<|w|\). By _position_ of a factor, we mean its starting (=leftmost) position. The distance between factors of a word is the difference of their positions; for example, the distance between occurrences of _aa_ in _aabaa_ is 3. A _cyclic shift_ of a finite word \(w\) is any word \(w[i..|w|]w[1..i-1]\). The _complement_ of a finite or infinite word \(w\) is the image of \(w\) under the map which replaces all \(a\)'s by \(b\)'s and all \(b\)'s by \(a\)'s. A word \(w\) has _period_\(p<|w|\) if \(w[1..|w|-p]=w[p+1..|w|]\). We use two basic properties of periodic words (see, e.g., [24]). **Lemma 1** ([PERSON], [PERSON]; [25]). : _If \(uv=vw\
eq\lambda\), then there are words \(x\
eq\lambda\), \(y\) and an integer \(n\) such that \(u=xy,w=yx\) and \(v=(xy)^{n}x\)._  
**Lemma 2** ([PERSON], [PERSON]; [26]). : _If a word \(u\) has periods \(p\) and \(q\) and \(|u|\geq p+q-\gcd(p,q)\), then \(u\) has period \(\gcd(p,q)\)._  
The _prefix tree_ of a language \(L\) is a directed tree, whose set of nodes is the set of all prefixes of words from \(L\), and the set of edges consists of all pairs \((u,uc)\) such that \(c\) is a letter. Edges are labelled by the last letter of the destination node: \(u\xrightarrow{c}uc\). The only node having no incoming edges, and thus the root of the tree, is \(\lambda\). A prefix tree is (in)finite whenever \(L\) is (in)finite. A finite prefix tree is often considered as a finite automaton and called _trie_. A _cube_ is a nonempty word of the form \(uuu\). A word is _cube-free_ if it has no cubes as factors; a cube is _minimal_ if it contains no _other_ cubes as factors. A _p-cube_ is a minimal cube with the minimal period \(p\) (i.e., \(|u|=p\)). Other important repetitions include squares (words of the form \(uu\)) and overlaps (words having a period strictly smaller than half of their length). The language \(\mathsf{CF}\) of binary cube-free words is infinite and can be represented by its prefix tree \(\mathcal{T}\), in which the nodes are precisely all cube-free words. The label of every path from the root coincides, as a word, with the terminal node of this path. A node in \(\mathcal{T}\) is either a leaf (infinite paths contain no leaves), or has a single child (_fixed_ node; its outgoing edge, the letter labeling this edge, and the position of this letter in the label of the path are also called _fixed_), or has two children (_branching point_; the outgoing edges, and their labels and positions are called _free_). A fragment of \(\mathcal{T}\) is shown in Figure 1.  
To estimate the number of branching nodes in a path, we obtain bounds on the number of fixed positions/letters in the corresponding word. Assume that some position \(i\) in a cube-free word \(w\) is fixed; w.l.o.g., \(w[i]=a\). Then the word \(w[1..i-1]b\) ends with a (unique) \(p\)-cube; in this case, we say that \(i\) (or \(w[i]\)) is _fixed by a \(p\)-cube_.