Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and 73-power-free infinite binary words
Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and \(\frac73\)-power-free infinite binary words
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}\).
- AVOIDING APPROXIMATE SQUARES
- Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin–Shapiro sequences
- Fife’s Theorem Revisited
- Overlap-free words and finite automata
- Spectral Properties of the Thue-Morse Sequence
- Squares and overlaps in the Thue-Morse sequence and some variants
This page was built for publication: Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and \(\frac73\)-power-free infinite binary words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800416)
