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

$\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
    Commented 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
    Commented 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
    Commented Jul 10, 2021 at 15:35
  • 1
    $\begingroup$ You really want transitive on n-tuples if distinct elements rather than $S^n$ $\endgroup$ Commented 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
    Commented Jul 10, 2021 at 18:47

2 Answers 2

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

$\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$ Commented 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$ Commented 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
    Commented 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$ Commented 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.

$\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
    Commented 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$ Commented Jul 10, 2021 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .