6
$\begingroup$

Let $$ X = \{x \in \{0,1\}^{\omega} \;|\; \exists m: \forall i \geq m: x_i = 0\} $$ (one-way infinite eventually zero words). Let $\{0,1\}^*$ denote the finite (not necessarily nonempty) words over $\{0,1\}$, and write $\{0,1\}^{\leq k} = \{w \in \{0,1\}^* \;|\; |w| \leq k\}$ where $|w|$ denotes length.

Is there a bijection $\phi : X \to \{0,1\}^*$ such that $$ \exists n \in \mathbb{N}: \forall a \in \{0,1\}: \forall x \in \{0,1\}^{\mathbb{N}}: \exists b, c \in \{0,1\}^{\leq n}: \exists y \in \{0,1\}^*: \phi(x) = b \cdot y \wedge \phi(a \cdot x) = c \cdot y $$ holds, where $\cdot$ is concatenation?

This is a kind of coarse uniformity / bornologousness assumption: $\phi$ needs to be bornologous between the two sets, seen as metric spaces with the path metric of the graph structure where $x$ and $y$ are adjacent if $y = ax$ or $x = ay$ for some $a \in \{0,1\}$. This seems vaguely familiar to me but I don't know from where, and I'm not seeing how to construct $\phi$. The straightforward idea of cutting out the zero tail doesn't work because it's not surjective, and I run into trouble trying to fix that. But I also didn't manage to prove impossibility because there's a lot of freedom.

The question arises in some (leisurely) research, so asking here instead of math.SE even if it might be safer to start there with this one. Geometric group theory tag because this is related to Thompson's $V$, even if I didn't elaborate and I doubt it's useful (every countable group acts freely on $\{0,1\}^*$).

$\endgroup$
8
  • $\begingroup$ The condition can be stated as $\phi$ being bornologous between the two sets, seen as metric spaces with the path metric of the graph structure where $x$ and $y$ are adjacent if $y = ax$ or $x = ay$ for some $a \in \{0,1\}$. $\endgroup$
    – Ville Salo
    May 28, 2020 at 9:32
  • 1
    $\begingroup$ The condition "$\exists n$, $\forall x$ $\exists c,d,e$, $\exists y$, $\phi(x)=cy$, $\phi(0x)=dy$, $\phi(1x)=ey$" is a priori a bit stronger (as in your condition you require one $y$ for each pair in the triple $\{\emptyset,0,1\}$), but is there really a reason you don't ask in this simpler way? $\endgroup$
    – YCor
    May 28, 2020 at 9:33
  • $\begingroup$ To clarify, do we agree they are equivalent? If not, I wonder if I've made a mistake and will have to take another look at what I've written. $\endgroup$
    – Ville Salo
    May 28, 2020 at 9:36
  • $\begingroup$ I wrote it the way that looked most symmetric to me, the point is a small prefix change should become a small prefix change in the image, for some modulus of bornologuity. $\endgroup$
    – Ville Salo
    May 28, 2020 at 9:39
  • $\begingroup$ It might be equivalent... it's just that quantifying over pairs of a 3-element set is puzzling unless there's a serious reason to do so. It looks like there's one $y=y_{\emptyset,0}$ working for $\emptyset,0$, one $y_{\emptyset,1}$, and one $y_{0,1}$. $\endgroup$
    – YCor
    May 28, 2020 at 9:44

1 Answer 1

6
$\begingroup$

I believe the following works, but I might be missing something.

If $x$ has at least two 1s, then $\phi(x)$ is the sequence cut just before the last 1: $$\phi(0011101000\cdots) = 001110 $$

If $x$ has at most one 1, then $\phi(x)$ is the sequence cut before the one, with an additional zero: $$ \phi(000\cdots) = \varnothing,\qquad \phi(001000\cdots) = 000 $$

The inverse bijection is $\psi(\varnothing)=000\cdots$, $\psi(y)=y\cdot1000\cdots$ when $y$ has at least one 1, and $\psi(y\cdot0)=y\cdot 1$ for $y$ consisting only of zeros (possibly $y=\varnothing$).

Then $\phi(a\cdot x)=a\cdot\phi(x)$ if $x$ has at least two 1s, and the case of $000\cdots$ is unimportant, up to taking a large $n$ (although $n=1$ works so far). Now if $x$ consists only of zeros, $$\phi(0\cdot y\cdot 1000\cdots)=0 \cdot y\cdot 0=00\cdot y\qquad\text{ and }\qquad\phi(1\cdot y\cdot 1000\cdots)=1\cdot y$$ while $\phi(y\cdot1000\cdots)=y\cdot0=0\cdot y$.

So the hypotheses are satisfied with $n=1$.

$\endgroup$
2
  • $\begingroup$ Seems to work, nice! However, full disclosure, this is a sort of toy model of the actual problem I'm interested in, though I only realize that now that I see your solution. I'll perhaps make another question later with stricter requirements. (I can also think of a possibly more natural and general version of the present question, I'll see if it makes a good MO question too.) $\endgroup$
    – Ville Salo
    May 28, 2020 at 19:21
  • $\begingroup$ @VilleSalo Very well, I'm glad I could help you understand your problem better. $\endgroup$
    – Pierre PC
    May 28, 2020 at 19:35

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.