5. Relating the Generalized Word and One-Sided Ideal Membership Problems in Groups and Group Rings

This section is concerned with another fundamental decision problem introduced by Dehn in 1911 for groups.

Definition 8   Given a subgroup ${\cal U}$ of a group ${\cal G}$ the generalized word problem for ${\cal U}$ or the subgroup problem for ${\cal U}$ is to determine, given $w \in {\cal G}$, whether $w \in {\cal U}$.

Given a finite subset S of a group ${\cal G}$, we let $\left< S \right> = \{ s_1 \circ\ldots \circ s_n \mid n \in {\bf N}, s_i \in S \cup S^{-1} \}$ denote the subgroup generated by S. A subgroup ${\cal U}$ of a group ${\cal G}$ is called finitely generated if there exists a finite subset S of ${\cal G}$ such that ${\cal U}= \left< S \right>$.

The word problem for a group ${\cal G}$ is just the generalized word problem for the trivial subgroup in ${\cal G}$ since u = v holds in ${\cal G}$ if and only if $u \circ v^{-1} = \lambda$ holds in ${\cal G}$, i.e.  $u \circ v^{-1} \in \left< \lambda \right>$. Thus the existence of a group with undecidable word problem yields undecidability for the generalized word problem for this group as well. On the other hand, decidable word problem for a group does not imply decidable generalized word problem (for an overview on various decision problems for groups see e.g. [Mi91]).

Now due to the existence of inverses, the word problem for congruences on free groups can also be formulated as a special type of subgroup problem. Let T be a set of relations on a free group ${\cal F}_{\Sigma}$. Then we can associate a set $T_1 \subseteq {\cal F}_{\Sigma}$ to T by setting $T_1 = \{ l \circ_{{\cal F}_{\Sigma}} r^{-1} \mid (l,r) \in T \}$. Let ${\cal N}$ be the normal closure⁶ of T₁ in ${\cal F}_{\Sigma}$. Then in fact the word problem for the group ${\cal F}_{\Sigma}/{\cal N}$ can be reduced to the subgroup problem for ${\cal N}$ since a relation u=v holds in ${\cal F}_{\Sigma}/{\cal N}$ if and only if $u \circ v^{-1} = \lambda$ holds in ${\cal F}_{\Sigma}/{\cal N}$, i.e.  $u \circ v^{-1} \in {\cal N}$. Notice that in general ${\cal N}$ is not a finitely generated subgroup.

Subgroups of groups can be characterized by one-sided congruences on the group. In the following we restrict ourselves to the case of right congruences (left congruences can be introduced in a similar fashion). Let ${\cal U}$ be a subgroup of a group ${\cal G}$. Then for $u,v \in {\cal G}$ we can define

$$u \sim_{{\cal U}} v \mbox{ if and only if } {\cal U}u = {\cal U}v$$

where ${\cal U}u = \{ g \circ u \mid g \in {\cal U}\}$. It is easy to prove that $\sim_{{\cal U}}$ is a right congruence induced by ${\cal U}$ on ${\cal G}$. The subgroup ${\cal U}$ itself is a congruence class, namely the one generated by $\lambda$. This right congruence is a congruence if and only if ${\cal U}$ is a normal subgroup.

The fact that ${\cal U}u = {\cal U}v$ holds if and only if $v \circ u^{-1} \in {\cal U}$, is used in the proof of the next theorem, which states that the subgroup problem for a group is equivalent to a special instance of the right respectively left ideal membership problem in the corresponding group ring.

Theorem 9 ([Re95,MaRe93])   Let S be a finite subset of ${\cal G}$ and ${\bf K}[{\cal G}]$ the group ring over ${\cal G}$. Further let $P_S = \{ s - 1 \mid s \in S \}\subseteq{\bf K}[{\cal G}]$ be the set of polynomials associated to S. Then the following statements are equivalent:

(1)

$w \in \left< S \right>$.

(2)

$w-1 \in {\sf ideal}_{r}^{}(P_S)$.

(3)

$w-1 \in {\sf ideal}_{l}^{}(P_S)$.

Proof : 1.11.1 
$1 \Longrightarrow2:$