13
$\begingroup$

Let $G$ be a group acting highly transitively (and faithfully) on a set $S$. Suppose that $G$ is finitely presented, and that every stabilizer in $G$ of a finite subset of $S$ is finitely generated. I think I can prove that $G$ embeds in a finitely presented simple group, which in particular implies $G$ has decidable word problem, but I'd like a better understanding of why such a $G$ should have decidable word problem. Is there a pre-existing (and/or more direct) reason that a group admitting such an action should have decidable word problem?

(Edit: Here an action of a group $G$ on a set $S$ is called highly transitive if for all $n\in\mathbb{N}$ the induced action of $G$ on the set of $n$-tuples of distinct elements of $S$ is transitive.)

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ I would suggest that you include the definition of acting highly transitively in your post, because it is possible that some readers are not familiar with it. $\endgroup$
    – Derek Holt
    Jul 10, 2021 at 12:28
  • 1
    $\begingroup$ I think it means that the action of $G$ on $S$ is $n$-transitive for every $n$, or equivalently that the map $G\to\mathrm{Sym}(S)$ has a dense image. By the way, is there a hope to prove the same assuming that the number of orbits on $S^n$ is finite for every $n$ ("oligomorphic action")? $\endgroup$
    – YCor
    Jul 10, 2021 at 13:23
  • 1
    $\begingroup$ Note that simple groups have decidable word problem, but not uniformly. This places some constraints on what you might expect a solution to the word problem to look like. $\endgroup$
    – HJRW
    Jul 10, 2021 at 15:35
  • 1
    $\begingroup$ You really want transitive on n-tuples if distinct elements rather than $S^n$ $\endgroup$
    – Benjamin Steinberg
    Jul 10, 2021 at 17:13
  • 1
    $\begingroup$ One of the most natural oligomorphic actions of a f.p. group with f.g. stabilizers is that of Thompson's $F$ on $\mathbf{Z}[1/2]\cap \mathopen]0,1[$, or that of Thompson's $T$ on $\mathbf{Z}[1/2]/\mathbf{Z}$, they're not highly transitive, so the larger generality is welcome (although these precise groups are known to have a solvable word problem). $\endgroup$
    – YCor
    Jul 10, 2021 at 18:47

2 Answers 2

Reset to default
8
$\begingroup$

Yes. There is such a reason.

I will write a subset of $G$ is RE if the set of those words over the generators for $G$ which represent elements of the subset is recursively enumerable.

As IJL argued, since $G$ is finitely presented the subset $\{1\}$ of $G$ containing only the identity is RE. It remains to show that $G \setminus \{1\}$ is RE.

Fix $s$ and $t$ in $S$ and let $H$ be the stabiliser of $s$. Since $H$ is finitely generated $H$ is RE.

Let $f$ be some element of $G$ which moves $s$ and fixes $t$.

Let $M$ be the set of elements of $G$ which conjugate $f$ into $H$. Note that $M$ is RE and $1 \notin M$ but any element $g$ of $G$ with $(t)g = s$ is in $M$.

Let $N$ be the set of elements of $G$ conjugate to some element of $M$. Note that $N$ is RE.

$G$ acts $2$-transitively on $S$ so $N$ is in the set of elements of $G$ which move at least one point of $S$. Which is to say that $N = G \setminus \{1\}$.

In short: $G \setminus \{1\} = \left\{ g \in G \mid \textrm{there exists } h \in G \textrm{ with } f^{\left(g^h\right)} \in H \right\}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Oh wow, look at that! I'm following all of this except one step - somehow I can't tell why $M$ is RE. $\endgroup$
    – Matt Zaremsky
    Sep 3, 2021 at 11:26
  • $\begingroup$ Ah OK, if $t$ is the only point fixed by $f$, then I believe $M$ is a coset of $H$, hence RE. And if $f$ fixes only finitely many points (including $t$) then $M$ is a union of finitely many cosets of $H$, which I suppose would also be RE. But what if $f$ fixes infinitely many points (including $t$)? Then $M$ is a union of infinitely many cosets of $H$, and I don't get why it must be RE.... $\endgroup$
    – Matt Zaremsky
    Sep 4, 2021 at 12:58
  • $\begingroup$ Let $X$ be a finite symmetric generating set for $G$ and let $\phi:X^* \to G$ be the canonical homomorphism. Let $w$ be in $(f)\phi^{-1}$. Now, $u$ is in $(M)\phi^{-1}$ exactly if $u^{-1}wu$ is in $H$ which we can check because $H$ is RE. $\endgroup$
    – James Hyde
    Sep 4, 2021 at 16:24
  • $\begingroup$ Ah, of course, much more direct than I realized. Great, thank you! So this embedding result indeed passes a "smell test", very good to know. $\endgroup$
    – Matt Zaremsky
    Sep 4, 2021 at 16:50
4
$\begingroup$

Is there an algorithm to distinguish the elements of the set $S$? If so, here is a word problem algorithm. This doesn't seem to use any transitivity properties, just faithfulness.

Start with the positive integer $n=1$. Given a word $w$ in the generators for $G$, run the standard algorithm to decide if the word can be obtained by freely reducing a product of at most $n$ conjugates of relators by words of length at most $n$ in the generators. At the same time, take an enumerated list $s_1,s_2,\ldots$ consisting of all of the elements of $S$, and decide whether the $w.s_n\neq s_n$. If neither of these happens, increase $n$ by one and repeat.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ No assumption on computability of the action was made by OP. Indeed if a f.p. group has a computable faithful action on $\mathbf{N}$ then its word problem is clearly solvable. $\endgroup$
    – YCor
    Jul 10, 2021 at 13:24
  • 1
    $\begingroup$ @IJL: Ah, this is interesting! YCor is right that in my post I'm not assuming such an algorithm on $S$ exists, but the result should still be true, and I'm still curious whether there's a direct way to see it. But there is actually a special case I'm interested in where $S$ is itself another group with decidable word problem! So I think in that special case, you've explained why it "passes a smell test" that $G$ could embed in a f.p. simple group. (The transitivity and finiteness properties are just to get the simple group to be f.p., so I can believe they don't matter for the word problem.) $\endgroup$
    – Matt Zaremsky
    Jul 10, 2021 at 17:08

Your Answer

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

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