Universal binary sequences

Notation. Write $\mathcal Q(A):=\{ a\subseteq A\mid a\text{ is finite}, a\neq\emptyset\}$.

Suppose for the moment that we are given a fixed sequence $\langle f_\alpha:\omega\rightarrow2\mid \alpha\in a\rangle$, indexed by some set $a$ of ordinals. Then, for every function $h:a\rightarrow\omega$ and $i<\omega$, we define the $i$-valuation of $h$, $h^i:a\rightarrow2$, by letting for all $\alpha\in a$:
$$h^i(\alpha):=f_\alpha(h(\alpha)+i).$$

Given an initial state $h:a\rightarrow\omega$, it is quite natural to look at the induced orbit$$\{ h^i\mid i<\omega\}\subseteq{}^a2.$$From there, we arrive to the concept of universality.
Definition. We say that a sequence $\langle f_\alpha:\omega\rightarrow 2\mid \alpha<\kappa\rangle$ is universal, if for every $a\in\mathcal Q(\kappa)$, we have:$$\{ h^i\mid i<\omega\}={}^a2\text{ for all }h\in{}^a\omega.$$

An even more ambitious concept is that of bounded universality:
Definition. We say that a sequence $\langle f_\alpha:\omega\rightarrow 2\mid \alpha<\kappa\rangle$ is b-universal, if for every $a\in\mathcal Q(\kappa)$, there exists $n(a)<\omega$, such that $$\{ h^i\mid  i<n(a)\}={}^a2\text{ for all }h\in{}^a\omega.$$

Amazingly enough, this concept is feasible!

Proposition. There exists a b-universal sequence of length $\omega$.
Proof. Let $\{ p_n\mid n<\omega\}$ be some injective enumeration of the set of prime numbers. For all $n<\omega$, define $f_n:\omega\rightarrow2$ by letting $f_n(m):=0$ iff $p_n$ divides $m$ (=there exists an integer $z$ such that $m=p_n\cdot z$).
To see that $\langle f_\alpha\mid \alpha<\omega\rangle$ is b-universal, fix $a\in[\omega]^{<\omega}$. We claim that $n(a):=|\prod_{n\in a}p_n|$ works. Indeed, given $h:a\rightarrow\omega$ and $b\in{}^a2$, we first let $c\in\prod_{n\in a}p_n$ be the unique function to satisfy $$h(n)+c(n)=b(n)(\text{mod } p_n)\text{ for all }n\in a.$$ Then, by the Chinese remainder theorem, there exists a non-negative integer $i<|\prod_{n\in a}p_n|$ such that$$i=c(n)(\text{mod }p_n)\text{ for all }n\in a.$$So $i<n(a)$ and $$h(n)+i=b(n)(\text{mod } p_n)\text{ for all }n\in a.$$In particular, for all $n\in a$:$$p_n\text{ divides }(h(n)+i)\text{ iff }b(n)=0.$$So, $$f_n(h(n)+i)=b(n)\text{ for all }n\in a.$$That is, $h^i=b$. $\square$

Now, what about longer universal sequences?
There is an obvious limit:

Observation. If $\kappa>2^{\aleph_0}$, then no sequence $\langle f_\alpha:\omega\rightarrow2\mid \alpha<\kappa\rangle$ is universal (let alone b-universal).
Proof. Towards a contradiction, suppose that the above sequence is universal. Pick $\alpha<\beta<\kappa$ such that $f_\alpha=f_\beta$. Put $\mathcal a:=\{\alpha,\beta\}$. Then for any constant function $h:a\rightarrow\omega$, and every bijection $g:a\leftrightarrow2$, we have $$g\not\in\{ h^i\mid i<\omega\}.\ \square$$

Thus, the best we can hope for is establishing the existence of a universal sequence of length $\kappa=2^{\aleph_0}$. This is indeed the case, and it follows from Kronecker’s theorem on simultaneous diophantine approximation.

Fact (Kronecker). Suppose that $a=\{x_1,\ldots,x_k\}$ is a finite subset of $[0,1]$
such that $1,x_1,\ldots,x_k$ are linearly independent over $\mathbb Q$. Then for every $\varepsilon>0$, there exists $n(a,\varepsilon)\in\mathbb N$ such that for every  $v_1,\ldots,v_k\in\mathbb R$, there exists $m\in\mathbb N, m<n(a,\varepsilon)$, and $z_1,\ldots,z_k$ in $\mathbb Z$ such that $|mx_i-v_i-z_i|<\varepsilon$ for all $i<k$.

Corollary (Moore, 2006). There exists a b-universal sequence of length $2^{\aleph_0}$.
Proof. Recursively construct a sequence $\langle x_\alpha\mid \alpha<2^{\aleph_0}\rangle$ such that $\{1\}\cup\{x_i\mid i\in I\}$ is linearly independent over $\mathbb Q$ for any choice of finite $I\subseteq 2^{\aleph_0}$. Then, for every $\alpha$ and $n<\omega$, let $f_\alpha(n)=0$ iff there exists some $z\in\mathbb Z$ such that $|nx_\alpha-{1\over 4}-z|<{1\over 8}$. To see that $\langle f_\alpha\mid\alpha<2^{\aleph_0}\rangle$ is indeed b-universal, let us fix $a\in\mathcal Q(2^{\aleph_0})$. Put $n(a):=n(\{x_\alpha\mid \alpha\in a\},{1\over 8})$. Now, given $h:a\rightarrow\omega$, and $b:a\rightarrow 2$, we define $\{ v_\alpha\mid \alpha\in a\}$ as follows: $$v_\alpha:=\begin{cases}{1-4\cdot h(\alpha)\cdot x_\alpha\over 4},&b(\alpha)=0\\{3-4\cdot h(\alpha)\cdot x_\alpha\over 4},&\text{otherwise}\end{cases}.$$ Pick $m\in\mathbb N, m<n(a)$, and $\{z_\alpha\mid \alpha\in a\}\subseteq \mathbb Z$ such that $|mx_\alpha-v_\alpha-z_\alpha|<{1\over 8}$ for all $\alpha\in a$. Fix $\alpha\in a$:

$\blacktriangleright$ If $b(\alpha)=0$, then $|mx_\alpha-{1-4\cdot h(\alpha)\cdot x_\alpha\over 4}-z_\alpha|<{1\over 8}$. That is, $|(m+h(\alpha))x_\alpha-{1\over 4}-z_\alpha|<{1\over 8}$, and hence $f_\alpha(h(\alpha)+m)=0$, as desired.

$\blacktriangleright$ If $b(\alpha)=1$, then $|mx_\alpha-{3-4\cdot h(\alpha)\cdot x_\alpha\over 4}-z_\alpha|<{1\over 8}$. That is $$z_\alpha+{5\over 8}<(m+h(\alpha))x_\alpha<z_\alpha+{7\over 8}.$$ Recalling that $f_\alpha(h(\alpha)+m)=0$ iff there exists $z\in\mathbb Z$ such that$$z+{1\over 8}<(m+h(\alpha))x_\alpha<z+{3\over 8},$$ we conclude that $f_\alpha(\alpha(\alpha)+m)=1$, as desired. $\square$

Chen Meiri and I have found a purely combinatorial proof of the preceding result, and with the added feature of having a primitive-recursive bound for $n(a)$ for every $a\in\mathcal Q(2^{\aleph_0})$. The proof will appear elsewhere.