Shifting an irrational binary sequence

Question

Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be defined by $\ell_k(s)(n) = s(n+k)$ for all $n\in\mathbb{N}$.

The xor of $s,t\in\tn$, in symbols $s\oplus t \in \tn$ is defined by $(s\oplus t)(n) = s(n) + t(n)$ for all $n\in\mathbb{N}$, where $+$ denotes addition modulo $2$, which is the same as the binary XOR operation.

We say that $s\in\tn$ is irrational if for no $k\in\mathbb{N}$ the binary sequence $\ell_k(s)\in\tn$ is periodic. Otherwise we say that $s$ is rational. (Note that $s$ is rational if and only if the binary floating point number that $s$ represents is a rational number.)

Question. Is there an irrational $s\in\tn$ such that $s\oplus \ell_1(s)\in \tn$ is rational?

Answer 1

No, there's no irrational $s$ with this property. Here's a concrete hands-on argument. (This may be equivalent to Ville Salo's comment, but I'm not familiar with that terminology.)

The sequence $d = s\oplus \ell_1(s)$ is just the sequence of differences (mod 2) between successive elements of $s$. Given one entry in the sequence, $s(j)$, we can reconstruct the rest of $s$ from $d$, since: $$s(j + 1) = s(j) \oplus d(j)$$ So if $d$ has period $n$, then $s$ must have period no more than $2n$, since $$s(j + 2n) = s(j) \oplus \bigoplus_{i=0}^{2n-1} d(i) = s(j) \oplus 2 \bigoplus_{i=0}^{n-1} d(i) = s(j)$$

Answer 2

I'll prove a general theorem. Unlike in my comments, I won't use any specific theorems.

Let $A$ be a finite alphabet and $X \subset A^{\mathbb{N}}$ a subshift of finite type, or SFT, meaning $X$ is the set of sequences, or points, that avoid a finite set of forbidden words $W \subset A^*$, in the sense that $x \in A^{\mathbb{N}}$ belongs to $X$ if and only if for all $w \in W$ and $i \in \mathbb{N}$, we have $x_{[i, i+|w|-1]} \neq w$. We consider $X$ under the induced topology coming from the product topology. Note that $\sigma(X) \subset X$ where $\sigma(x)_i = x_{i+1}$ is the left shift.

We say an SFT is transitive if for every $u, v \in A^*$ that appear in its points, some word $uwv$ also does. This is equivalent to topological transitivity of the left shift map, and forces $\sigma(X) = X$.

An endomorphism is a $\sigma$-commuting continuous self-map $f : X \to X$. Equivalently, there is a radius $r \geq 0$ and a local rule $F : U \to A$ where $U \subset A^{1+r}$ is the set of words appearing in points of $X$, such that $f(x)_i = F(x_{[i, i+r]})$ for all $i \in \mathbb{N}, x \in X$. We say $f$ is left-injective if for some choice of $r, F$ (equivalently, any choice of $r, F$) we have $F(aw) \neq F(bw)$ whenever $a, b \in A, w \in A^r$ and $a \neq b$.

The poster is interested in the case $X = \{0,1\}^{\mathbb{N}}$, $r = 1$, $F(a, b) = a \oplus b$, which is clearly left-injective.

We say a point $x \in X$ is periodic if $\sigma^n(x) = x$ for some $n \geq 1$. Equivalently, $x = www...$ for some word $w \in A^*$. We say an endomorphism $f$ has property P if every preimage of a periodic point is itself necessarily periodic. This is what the poster asked about.

Theorem. An endomorphism $f : X \to X$ of a transitive SFT $X$ has property P if and only if it is left-injective.

Proof. Suppose first that $f$ is left-injective (this is the direction the poster is interested in). Let $z = wwww...$ be a periodic point, and let $x$ be any preimage. Then from $x_{[i, i+r-1]}$ and $z_{[0,i-1]}$ we can uniquely determine $x_{[0, i-1]}$ by using the left-injectivity property to determine symbols one by one from right to left (i.e. in order $i-1, i-2, ..., 0$).

These symbols are determined, in fact, by a finite state machine, which is fed with periodic input. The memory is the word $x_{[i-j, i-j+r-1]}$ determined so far, and the input is the reverse of the word $w$, repeatedly.

By the pigeonhole principle, the output of such a process must be eventually periodic, and thus $x_{[0, i-1]}$ must be eventually periodic. Furthermore, we can give an explicit bound on this period and the transient. The eventual period is seen on the left, so in fact $x$ begins with arbitrarily long periodic segments with a bounded period. In other words, $x$ is periodic.

Suppose then that $f$ is not left-injective. Then there exist $aw, bw$ with the same image under $F$. Since $X$ is a transitive SFT, there is a periodic point of the form $x = awuawuawuawu...$ whose image is necessarily periodic, since endomorphisms preserve periods. But clearly for $y = bwuawuawu...$ we have $f(y) = f(x)$, and $y$ is not periodic. Square.