Shift-rotating random number generator

Question

Let $\omega$ denote the set of non-negative integers. For $n\in\omega\setminus\{0\} $ define the rotation function $$\text{rot}_n:\{0,1\}^n \to \{0,1\}^n$$ by $x \mapsto x'$ where

• $x'_k = x_{k+1}$ for $k\in\{0,\ldots, n-2\}$, and
• $x_{n-1} = x_0$.

Let $\bar{0}_n \in \{0,1\}^n$ be the constant $0$-sequence of length $n$. Fix $s_0\in \{0,1\}^n$ and define a function $f_{n,s_0} : \omega\to \{0,1\}^n$ inductively by setting

• $f_{n,s_0}(0) = \bar{0}_n$, and
• $f_{n,s_0}(k+1) = f_{n,s_0}(k) \;\oplus \; \text{rot}_n(f_{n,s_0}(k)) \; \oplus \; s_0$.

(By $\oplus$ we denote componentwise addition in $\mathbb{Z}/2\mathbb{Z}$, or equivalently, bitwise XOR.)

Question. For what values of $n\in\omega\setminus\{0\}$ is there $s_0\in \{0,1\}^n$ such that the image of the function $f_{n,s_0} : \omega\to \{0,1\}^n$ is all of $\{0,1\}^n$ (i.e. $f_{n,s_0} : \omega\to \{0,1\}^n$ is surjective)?

Answer 1

I think only for $n=1$.

The map $x\mapsto x\oplus\mathrm{rot}(x)\oplus s_0$ is 2-to-1 since $x$ and $x\oplus 1111\ldots 1$ both map to the same value. It follows that half of the values of $\{0,1\}^n$ do not lie in the image of this map. We can capture at most one missing value with our start point $0$, but the remaining $2^{n-1}-1$ points will never occur in the image.