0
$\begingroup$

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}$.

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

2 Answers 2

2
$\begingroup$

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.)

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.