2
$\begingroup$

The occurrence problem asks if, given a group $G$ and a subgroup $H$ of $G$, there exists an algorithm to decide whether $x\in G$ belongs to $H$.

Let $G$ be a group that has solvable word problem.

  1. Is the occurrence problem solvable for $H=[G,G]$? In other words, Is there an algorithm to decide for any $x\in G$ whether $x$ belongs to $[G,G]$?

A slightly more general question:

  1. Is there an algorithm to decide whether $x \in G$ belongs to the $k$-derived subgroup (recall that the $k$-derived subgroup $G_k$ is defined recursively as $G_1= [G,G]$, $G_k=[G_{k-1},G_{k-1}]$).

Also, any reference to these topics is welcome.

Edit: many replies pointed me out that the question for the cases $k=1,2$ is true even without assuming that $G$ has solvable word problem. I am still interested in the general case (question 2).

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 1) Yes (assuming $G$ is meant to be finitely generated): more generally if $H$ is normal in $G$ and $G/H$ has solvable word problem then there's an algorithm, which is precisely the one solving the word problem in $H$. This applies to the derived subgroup, and also to the second derived subgroup. I don't know then, since there are f.g. solvable groups with non-solvable word problem. $\endgroup$
    – YCor
    Commented Dec 18, 2021 at 20:03
  • 1
    $\begingroup$ By the way the usual terminology is "membership problem". $\endgroup$
    – YCor
    Commented Dec 19, 2021 at 1:15
  • 1
    $\begingroup$ @YCor In the West, yes, but many Russian authors still use “occurrence problem” and historically it is this terminology which is always used there. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Dec 19, 2021 at 3:00
  • 2
    $\begingroup$ @HJRW, you probably have cited the famous paper K.A. Mihailova, The occurrence problem for direct products of groups, Dokl. Akad. Nauk SSSR 119 (1958) 1103–1105 showing the generalized word problem is undecidable for a direct product of free groups :) but I think the terminology has not been commonly used in English for quite some time. Here is a sort of exception ams.org/journals/proc/1987-101-03/S0002-9939-1987-0908639-5/… but not very recent $\endgroup$
    – Benjamin Steinberg
    Commented Dec 19, 2021 at 11:35
  • 2
    $\begingroup$ @HJRW, no worries. That's where I learned the term but probably few people read the original paper where that terminology is used $\endgroup$
    – Benjamin Steinberg
    Commented Dec 19, 2021 at 16:39

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .