×

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

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 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}\).

MSC:

68R15 Combinatorics on words
Full Text: DOI

References:

[1] Blanchard F., Complex Systems 11 pp 107– (1997)
[2] DOI: 10.1051/ita:2006030 · Zbl 1110.68117 · doi:10.1051/ita:2006030
[3] DOI: 10.1016/0304-3975(93)90118-D · Zbl 0784.68049 · doi:10.1016/0304-3975(93)90118-D
[4] Fife E. D., Trans. Amer. Math. Soc. 261 pp 115– (1980)
[5] DOI: 10.4064/aa140-4-5 · Zbl 1223.11096 · doi:10.4064/aa140-4-5
[6] DOI: 10.1002/sapm192761158 · JFM 53.0265.03 · doi:10.1002/sapm192761158
[7] DOI: 10.1142/S0129054108005863 · Zbl 1155.68068 · doi:10.1142/S0129054108005863
[8] DOI: 10.1007/3-540-15641-0_35 · doi:10.1007/3-540-15641-0_35
[9] DOI: 10.1007/978-3-642-22321-1_34 · Zbl 1221.68145 · doi:10.1007/978-3-642-22321-1_34
[10] DOI: 10.4213/im301 · doi:10.4213/im301
[11] Shur A. M., Diskretn. Anal. Issled. Oper., Ser. 1 pp 78–
[12] DOI: 10.1109/TCOM.1984.1096162 · Zbl 0544.94015 · doi:10.1109/TCOM.1984.1096162
[13] DOI: 10.1109/26.64649 · doi:10.1109/26.64649
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.