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

The word problem for a group
is just the generalized word problem
for the trivial subgroup in
since *u* = *v* holds in
if and only if
holds in ,
i.e.
.
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
.
Then we can associate a set
to *T* by setting
.
Let
be the normal closure^{6} of *T*_{1} in
.
Then in fact the word problem for the group
can be reduced to the subgroup problem for
since
a relation *u*=*v* holds in
if and only if
holds in
,
i.e.
.
Notice that in general
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
be a subgroup of a group .
Then for
we can define

where . It is easy to prove that is a right congruence induced by on . The subgroup itself is a congruence class, namely the one generated by . This right congruence is a congruence if and only if is a normal subgroup.

The fact that holds if and only if , 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.

- (1)
- .
- (2)
- .
- (3)
- .