# "Arithmetically diverse" infinite binary string

For $$a,b \in \omega$$ with $$a > 0$$, let $$f_{a,b}: \omega\to\omega$$ be defined by $$n \mapsto an+b$$. What is an example of an infinite binary string $$s:\omega\to\{0,1\}$$ with the following property?

Whenever $$(a,b), (a_1,b_1)\in (\omega\setminus\{0\})\times \omega$$ with $$(a,b)\neq (a_1,b_1)$$, then $$s\circ f_{a,b} \neq s\circ f_{a_1,b_1}$$.

• That's right @bof - sorry for the bad variable choice, have changed the string variable to $s$. Jul 2, 2020 at 13:36

Let $$s$$ consist of $$2^{2^k}$$ zeros, followed by the same number of ones, for increasing $$k$$: $$0^21^2\, 0^{16}1^{16}\, 0^{256}1^{256}\,0^{65536}1^{65536}\dots$$ Observe that all but finitely many blocks of 1s of $$s\circ f_{a,b}$$ have size of the form $$\lfloor2^{2^{k}}/a\rfloor$$ or $$\lceil 2^{2^k}/a\rceil$$.

We claim that we cannot keep having $$k>j$$ and $$2^{2^k}/{a_1}\le 2^{2^j}/{a_2}+1$$ (and therefore all $$s\circ f_{a,b}$$ are distinct).

Indeed, when this happens then $$2^{2^k-2^j}\le a_1/{a_2}+a_1 2^{-2^j}$$ is bounded. But as $$k>j\to\infty$$, $$2^{2^k-2^j}$$ is unbounded.

(Note that $$2^k/a_1=2^{k-1}/a_2$$ with $$a_1=4$$ and $$a_2=2$$, so a single-exponential $$2^k$$ in place of a double-exponential $$2^{2^k}$$ is not enough for this construction.)

• Very neat construction - thank you very much! Sep 10, 2020 at 7:38
• @DominicvanderZypen thanks for another interesting question. Sep 10, 2020 at 8:02

2 approaches:

1. Generate $$b$$ randomly, having $$b(n)$$ be $$0$$ with probability $$1/2$$ and having each $$b(n)$$ be independent. Then for each $$(a,b)$$ and $$(a_1,b_1)$$, the probability that $$b\circ f_{a,b}=b\circ f_{a_1,b_1}$$ is $$0$$. Summing over all countably many such pairs, we still get a probability of $$0$$, so with probability $$1$$, our string works.

2. Generate $$b$$ greedily. Go through pairs $$(a,b),(a_1,b_1)$$ in some order and for each, choose two entries in our string very far out to force disagreement.

• So what does $s$ look like concretely? Given $n\in \omega$ what is $s(n)$? Jul 4, 2020 at 17:59