2
$\begingroup$

This continues my question about prefix-continuous bijections (since the answer was "yes").

Notation and conventions: Let $A$ be a finite alphabet and $L \subset A^*$ a language. Let $G$ be a group. For words $u, w$, juxtaposition $uw$ denotes word concatenation, and if we have an action $G \curvearrowright L$ and $g \in G, u \in L$ we write $gu$ for the image of $u$ in the action of $g$; concatenation associates first.

An action $G \curvearrowright L$ is veelike (or $G$ acts veelike) if for all $g \in G$ there exists $n \in \mathbb{N}$ such that for all $u \in A^*$ with $|u| = n$ there exists $u' \in A^*$ such that $guv = u'v$ for all $uv \in L$. Now we have the following simple observation.

Thompson's $V$ acts veelike on the regular language defined by the regular expression $\emptyset + (0+1)^* 1$.

Proof. This is the regular language $L$ containing the empty word $\emptyset$ and all words ending in the symbol $1$. To find the action, recall the defining action of $V$ on the boundary of the infinite binary tree. We can see the tree as $\{0,1\}^\omega$, and elements of $V$ can be presented by picking two maximal prefix codes, bijecting them and then rewriting the prefix of the input word according to said bijection. Observe that the set $$ X = \{x \in \{0,1\}^{\omega} \;|\; \exists m: \forall i \geq m: x_i = 0\} $$ of infinite paths/words that are eventually zero is invariant under its action, and $V$ clearly acts faithfully on it (e.g. because it's a simple group and the action is nontrivial). There is an obvious bijection from $X$ to $L$: just cut out the sequence after the last $1$, if one exists, and map the all zero sequence to the empty word $\emptyset$. The action of $V$ on $L$ is "veelike" in the obvious sense (same formula); that's basically the definition. Conjugating the action of $V$ to $L$, it stays veelike since on all long enough words you do exactly the same rewrites as you would on infinite words beginning that way. Square.

(I have not written a more careful proof than that, it's natural so what could go wrong.)

My question is the following:

On which alphabets $A$ and languages $L \subset A^*$ does Thompson's $V$ admit a veelike action?

In particular:

Does Thompson's $V$ act veelike on the set of binary words $\{0,1\}^*$?

One possible way to prove this would be to find a bijection $\phi : X \to \{0,1\}^*$ such that conjugating the action of $V$ from $X$ to $\{0,1\}^*$ gives you a veelike action.

Does such a bijection exist?

I claim that the bijection of @PierrePC to my previous question does not work (the answer is correct but I did not state all the necessary properties for the bijection). Namely, after conjugation the action indeed rewrites only prefixes, but you need to see the whole word to know how they are rewritten, i.e. the action is not continuous in the right sense.

More concretely, through this bijection the element that just flips the first bit acts $$ 00000000000000001... \mapsto 10000000000000001... $$ $$ 00000000100000001... \mapsto 10000000100000001... $$ which are conjugated respectively to $$ 00000000000000000 \mapsto 1000000000000000 $$ $$ 0000000010000000 \mapsto 1000000010000000 $$ which is highly veeunlikely because the length change depends on the $1$ arbitrarily far inside the word.

$\endgroup$

0

Your Answer

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