4. On the Relations between Gröbner bases and the Subgroup Problem

In this section we want to demonstrate the connection between Gröbner bases in certain group rings and solutions of the subgroup problem by rewriting techniques.

Definition 8    
Given a subset U of a group ${\cal G}$, let $\left< U \right> = \{ u_1 \circ\ldots \circ u_n \mid n \in {\bf N}, u_i \in U \cup U^{-1} \}$ denote the subgroup generated by U. The generalized word problem or subgroup problem is then to determine, given $w \in {\cal G}$, whether $w \in \left< U \right>$. $\diamond$

The following theorem links this group theoretic problem to right respectively left ideals in the respective group ring.

Theorem 2 (see 5.1.2 in [Re95])    
Let U be a finite subset of ${\cal G}$ and ${\bf K}[{\cal G}]$ the group ring corresponding to ${\cal G}$. Further let $P_U = \{ s - 1 \mid s \in U \}$ be a set of polynomials associated to U. Then the following statements are equivalent:

1.

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

2.

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

3.

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

Proof : 1.11.1 
$1 \Longrightarrow2:$