Universal binary sequences

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

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

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

An even more ambitious concept is that of bounded universality:
Definition. We say that a sequence $⟨f_{\alpha }:\omega \to 2\mid \alpha <\kappa ⟩$ is b-universal, if for every $a\in \mathcal{Q}(\kappa )$, there exists $n(a)<\omega$, such that $$\{h^i\mid i<n(a)\}={}^{a}2\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 \to 2$ 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 $⟨f_{\alpha }\mid \alpha <\omega ⟩$ is b-universal, fix $a\in [\omega {]}^{<\omega }$. We claim that $n(a):=|\prod _{n\in a}{p}_n|$ works. Indeed, given $h:a\to \omega$ and $b\in {}^{a}2$, 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$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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

Observation. If $\kappa >2^{{\mathrm{\aleph }}_0}$, then no sequence $⟨f_{\alpha }:\omega \to 2\mid \alpha <\kappa ⟩$ 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\to \omega$, and every bijection $g:a\leftrightarrow 2$, we have $$g\notin \{h^i\mid i<\omega \}.\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$$

Thus, the best we can hope for is establishing the existence of a universal sequence of length $\kappa =2^{{\mathrm{\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,\dots ,x_k\}$ is a finite subset of $[0,1]$
such that $1,x_1,\dots ,x_k$ are linearly independent over $\mathbb{Q}$. Then for every $\epsilon >0$, there exists $n(a,\epsilon )\in \mathbb{N}$ such that for every  $v_1,\dots ,v_k\in \mathbb{R}$, there exists $m\in \mathbb{N},m<n(a,\epsilon )$, and $z_1,\dots ,z_k$ in $\mathbb{Z}$ such that $|m{x}_i-v_i-z_i|<\epsilon$ for all $i<k$.

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

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

$▸$ If $b(\alpha )=1$, then $|m{x}_{\alpha }-\frac{3-4\cdot h(\alpha )\cdot x_{\alpha }}{4}-z_{\alpha }|<\frac{1}{8}$. That is $$z_{\alpha }+\frac{5}{8}<(m+h(\alpha ))x_{\alpha }<z_{\alpha }+\frac{7}{8}.$$ Recalling that $f_{\alpha }(h(\alpha )+m)=0$ iff there exists $z\in \mathbb{Z}$ such that$$z+\frac{1}{8}<(m+h(\alpha ))x_{\alpha }<z+\frac{3}{8},$$ we conclude that $f_{\alpha }(\alpha (\alpha )+m)=1$, as desired. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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^{{\mathrm{\aleph }}_0})$. The proof will appear elsewhere.