3

Let $x^+$ denote the infinite Thue-Morse word, $$x^+ = 0110100110010110\ldots,$$ which is defined as being the only fixed point starting with $0$ of the morphism $S$ (defined over the words on the alphabet $\{0,1\}$) given by $S(0) = 01$ and $S(1) = 10$ - that is, $$x^+ = S^{\omega}(0) = \lim\limits_{n \geqslant 1} S^n(0);$$ this is only one among many different, equivalent definitions of such word (for instance, pick $A_0 = 0$ and let $A_{n+1} = A_n\,^\frown\overline{A_{n}}$ - where $^\frown$ denotes concatenation and $\overline{A_n}$ denotes the bitwise complement of $A_n$. Then $x^+ = \lim\limits_{n \in \mathbb{N}} A_n$). From now on, let $x^+ = (t_n)_{n \in \mathbb{N}}$.

It is known that the Thue-Morse word is uniformly recorrent (meaning, for every finite subword $w$ of $x^+$ there is some $n \in \mathbb{N}$ such that, for every $i \in \mathbb{N}$, the block $t_{i + 1}t_{i + 2}\ldots t_{i + n}$ contains some ocurrence of $w$) but it is $\mathbf{\textrm{not}}$ ultimately periodic (meaning, it is not true that there are $p \geqslant 1$ and $N \geqslant 0$ such that $t_i = t_{i + p}$ for all $i \geqslant N$).

The two-sided Thue Morse sequence $x = (x_i)_i \in \mathbb{Z}$ is defined as $x = x^{-}\,^\frown x^+$, meaning that $x_n = t_n$ for all $n \geqslant 0$ and $x_{-n} = t_{n - 1}$ for all $n \geqslant 1$. So, $$x = \ldots 100101100.1101001 \ldots$$

Let $\sigma$ denote (as usual) the left shift map on $^\mathbb{Z}\{0,1\}$. The Thue-Morse subshift $X$ is the closure (in the Tychonoff topology) of the orbit $\{\sigma^n(x): n \geqslant 0\}$. Equivalently, $X$ is the family of all doubly infinite sequences $z$ such that every finite subword of $z$ is a subword of $x^+$. It is known that $X$ is a infinite, minimal subshift (that is, every point of $X$ has a dense orbit in $X$).

My question is:

Let $s = (s_i)_{i \in \mathbb{Z}}\,$ and $u = (u_i)_{i \in \mathbb{Z}}\,$ be two distinct points of the Thue-Morse subshift $X$ - that is, there is some integer $i \in \mathbb{Z}$ such that $s_i \neq u_i$. Consider the set of integers given by $$\{i \in \mathbb{Z}: s_i \neq u_i \}.$$ Is it true that such set is, necessarily, an $\mathbf{\textrm{infinite}}$ set of integers ?

My conjecture is that the answer is "yes", but I wasn't able to produce a proof.

Samuel G. Silva
  • 151

1 Answers1

1

Bonjour, it is first easy to observe that $S^n (0)$ is obtained from $S^n (1)$ changing the 0's in 1's and vice-versa. Suppose $E=\{ i\in \mathbb{Z}| s_i\not = u_i \}$ is finite and $u$ and $s$ distincts. Let say that $E$ is included in an interval of length $L$. Let $N$ such that $2^N > L$. By the recognizability result of Mossé for primitive substitutions, and shifting both sequences of the same amount if needed, there are two points $s'$ and $u'$ of the Thue-Morse shift such that $s=S^N(s')$ and $u=S^N(u')$ (this is not direct but I left it as an exercise). Then there exists $i$ such that for all $j\not \in \{ i, i+1\}$, $S^N(u'_j)=S^N (s'_j)$ and $S^N(u'_iu'_{i+1})\not =S^N (s'_is'_{i+1})$. Thus either $S^N(u'_i)\not =S^N (s'_i)$ or $S^N (u'_{i+1})\not =S^N (s'_{i+1})$. But in both case, from the first observation, it implies that the number of differences is at least $2^N$. This contradicts the facts that $L$ is strictly less than $2^N$.

Fabien Durand
  • 21