Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and \(\frac73\)-power-free infinite binary words (Q2800416)

The famous binary sequence of Thue-Morse \(\mathbf{t}\) (and its complement \(\mathbf{\bar{t}}\)) is well known to be overlap-free, i.e., it does not contain factors of the form \(axaxa\) where \(a\) is a symbol and \(x\) is a string. This property is fragile: If finitely many bits in the sequence are replaced by their complements, the resulting word is no more overlap-free. The authors show that this result cannot be generalized to the case when bits in infinitely many positions are flopped, even if the position set has density 0. They define \textit{similarity density} of two finite binary strings \(\mathbf{x}\), \(\mathbf{y}\) of length \(n>0\) as \(\mathrm{SD}\left(\mathbf{x},\mathbf{y}\right) =\frac{1}{n}\sum_{i=0} ^{n}\delta\left( \mathbf{x}_{i},\mathbf{y}_{i}\right) \), where \(\delta\left( a,b\right) =1\) if \(a=b,\) and \(\delta\left( a,b\right) =0\) if \(a\neq b\). Thus \(\mathrm{SD}\left(\mathbf{x},\mathbf{y}\right) =1\) if and only if \(\mathbf{x}=\mathbf{y}\). Then they consider the lower and upper similarity density of two infinite binary sequences \(\mathbf{x}\), \(\mathbf{y}\), defined respectively as \(\mathrm{LSD}\left( \mathbf{x} ,\mathbf{y}\right) =\lim\inf_{n\rightarrow\infty}\mathrm{SD}\left( \mathbf{x} _{0\dots n-1},\mathbf{y}_{0\dots n-1}\right) \) and \(\mathrm{USD}\left( \mathbf{x},\mathbf{y}\right) =\lim\sup_{n\rightarrow\infty}\mathrm{SD}\left(\mathbf{x}_{0\dots n-1},\mathbf{y}_{0\dots n-1}\right) \). The main result states that, for an overlap-free binary sequence \(\mathbf{w}\) distinct from \(\mathbf{t}\) and \(\mathbf{\bar{t}}\), one has \(\frac{1}{4}\leq\mathrm{LSD}\left( \mathbf{w},\mathbf{t}\right) \leq\mathrm{USD}\left( \mathbf{w},\mathbf{t}\right) \leq\frac{3}{4}\).