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.

This entry was posted in Blog and tagged , . Bookmark the permalink.

3 Responses to Universal binary sequences

  1. Pingback: Syndetic colorings with applications to S and L | Assaf Rinot

  2. Ashutosh says:

    It would be great if you could post your proof (with Chen Meiri) of the existence of a b-universal sequence of continuum length on your blog when you get a chance.

    • saf says:

      Thanks, Ashutosh.
      The problem is that Meiri and I never decided what to do with the proof. Does the result justify a paper? Does it give generalizations which are not covered by applications of Kronecker’s theorem?
      After proving this, we both became busy with other projects and never managed to complete the research around this.

      In any case, I can show it to you next Sunday.

Leave a Reply

Your email address will not be published. Required fields are marked *