Skip to main content
added 203 characters in body
Source Link
JBrude
  • 115
  • 6

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

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.

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

Capitalise title; delete "thanks"
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

occurrence Occurrence problem for commutator subgroup

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. Thank you in advance.

occurrence problem for commutator subgroup

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. Thank you in advance.

Occurrence problem for commutator subgroup

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.

Source Link
JBrude
  • 115
  • 6

occurrence problem for commutator subgroup

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. Thank you in advance.