3. Solving the Submodule Problem in Polycyclic Group Rings

In [Si94] Sims gives the following discussion for handling finitely generated right modules over the integral group ring of any polycyclic group ${\cal G}$, which is based on the work of Baumslag, Cannonito and Miller [BaCaMi81].

Let $a_1, \ldots , a_n$ be a polycyclic generating sequence for ${\cal G}$ together with a consistent polycyclic presentation for ${\cal G}$.
In case n=1, ${\cal G}$ is cyclic and this case is well known.
Hence let us assume that n>1 and set ${\cal H}= \langle a_2, \ldots , a_n \rangle$. Then ${\cal H}$ is normal in ${\cal G}$ and ${\cal G}/ {\cal H}$ is a cyclic group generated by the image of a₁. By induction on n we may assume that we know how to describe submodules in the modules ${\bf Z}[{\cal H}]^s$, $s \in {\bf N}$. In order to show how this information can be lifted to ${\bf Z}[{\cal G}]^s$ we have to distinguish whether $1 \in I$ or not. In the following we abbreviate a₁ by a.
First suppose $1 \in I$, i.e., ${\cal G}/ {\cal H}$ is finite and w.l.o.g. let $m = \vert {\cal G}: {\cal H}\vert$. Then ${\bf Z}[{\cal G}]^s$ is isomorphic (as a ${\bf Z}[{\cal H}]$-module) to ${\bf Z}[{\cal H}]^{s \cdot m}$, as if $b_1, \ldots , b_s$ is a ${\bf Z}[{\cal G}]$-basis for ${\bf Z}[{\cal G}]^s$, then the set $\{ b_ia^j \mid 1 \leq i \leq s,0 \leq j < m \}$ is a ${\bf Z}[{\cal H}]$-basis of ${\bf Z}[{\cal G}]^s$. Now, a ${\bf Z}[{\cal H}]$-submodule M of ${\bf Z}[{\cal G}]^s$ is a ${\bf Z}[{\cal G}]$-submodule if and only if M is closed under multiplication by a from the right. If $T\subset {\bf Z}[{\cal G}]^s$ is a generating set for M as a ${\bf Z}[{\cal H}]$-module, then M is closed under multiplication by a if and only if $f \ast a$ is in M for all $f \in T$. Suppose the products $f \ast a$ do belong to M. A typical element g of M has the form $\sum_{i=1}^{r} \alpha_i \cdot f_i \ast h_i$, $\alpha_i \in {\bf Z}$,$f_i \in T$, $h_i \in {\cal H}$. Then $g \ast a = \sum_{i=1}^{r} \alpha_i \cdot f_i \ast(h_i \circ a) = \sum_{i=1}^{r} \alpha_i \cdot f_i \ast(a \circ a^{-1} \circ h_i \circ a)$, and since $a^{-1} \circ h_i \circ a \in {\cal H}$ and each $f_i \ast a \in M$, we get $g \ast a \in M$. If some $f \ast a$ is not in M, then we can add it to T and recompute the ${\bf Z}[{\cal H}]$-submodule generated by T. Because the ascending chain condition holds, this process will terminate⁶. Since we can describe submodules of ${\bf Z}[{\cal H}]^{sm}$ effectively, we can describe submodules of ${\bf Z}[{\cal G}]^s$.
Now let us suppose that ${\cal G}/ {\cal H}$ is infinite. Then ${\bf Z}[{\cal G}]^s$ is still a free ${\bf Z}[{\cal H}]$-module, but with an infinite basis $U = \{ b_ia^j \mid 1 \leq i \leq s, j \in {\bf Z}\}$. Any element $g \in {\cal G}$ can be written uniquely in the form a^jh, where $h \in {\cal H}$. In this way, $b_i \circ g$ can be expressed as b_ia^jh. Thus elements of ${\bf Z}[{\cal G}]^s$ can easily be described as ${\bf Z}[{\cal H}]$-linear combinations of the elements of U. However, it is also useful to write g in the form la^j where $l = a^j \circ h \circ a^{-j} \in {\cal H}$. When this is done, every element of ${\bf Z}[{\cal G}]^s$ can be described as

$$c_p \ast a^p + c_{p-1} \ast a^{p-1} + \ldots + c_q \ast a^q$$

where $p,q \in {\bf Z}$, $p \geq q$ and $c_i \in {\bf Z}[{\cal H}]^s$, $p \leq i \leq q$. In case $q \geq 0$ the element is called a polynomial and p is called the degree and c₀ the constant term of the polynomial.
Let T be a finite subset of ${\bf Z}[{\cal G}]^s$ and let M be the ${\bf Z}[{\cal G}]$-submodule generated by T. Since a is a unit in ${\bf Z}[{\cal G}]$ we can multiply each element in T by some power of a such that the resulting element is a polynomial, i.e., it has positive exponents in a only, and additionally we assume it has nonzero constant term c₀. Given $k \in {\bf N}$, let M_k be the set of polynomials in M with degree at most k, and let C_k be the set of coefficients of the term a^k occurring in the polynomials in M_k. Let $\sum_{i=0}^{k} c_i \ast a^i \in M_k$ and $h \in {\cal H}$. Then since also $l = a^{-k} \circ h \circ a^{k} \in {\cal H}$, we get $\sum_{i=0}^{k} c_i \ast a^il = \sum_{i=0}^{k} c_i \ast(a^i \circ a^{-k} \circ... ...i \ast(a^{i-k} \circ h \circ a^{k-i}) \ast a^i = \sum_{i=0}^{k} c_i \ast h_ia^i$ with $h_i \in {\cal H}$. Therefore, $c_k \ast h \in C_k$ for $h \in {\cal H}$, i.e., C_k is a ${\bf Z}[{\cal H}]$-submodule of ${\bf Z}[{\cal H}]^s$. Furthermore, $C_k \subseteq C_{k+1}$ holds.
Let d be the maximal degree of the polynomials in T (assuming that T has been modified to contain only polynomials as described above). Then one can show that C_k = C_d for $k \geq d$. Moreover, knowing M_d alone allows to solve the membership problem in M, as we can multiply every element $g \in {\bf Z}[{\cal G}]$ by a power of a in order to turn it into a polynomial, say of degree k. Then in case k > d we check whether $c_k \in C_d$. If not we are done, since then $g \not\in M$. Else there exists an element $h \in M_d$ with leading coefficient c_k and we can reduce g by subtracting ha^k-d. Thus we may assume that $k \leq d$ which leaves us with the decision whether $g \in M_d$. How do we get to know M_d? Let A be the ${\bf Z}[{\cal H}]$-module generated by T, B respectively C the elements in A with degree at most d-1 respectively constant term 0. Then we have $A \subseteq M_d$ and, moreover, A=M_d if and only if $Ba \subseteq A$ and $Ca^{-1} \subseteq A$.

Sims outlines how these membership problems can be treated using matrix methods. In example 8.3.  he states how to compute such a basis in the group ring of the free nilpotent group (see example 1 for a presentation of this group on the letters a₁, a₂, and a₃). Then for the right ideal M of ${\bf Z}[{\cal G}]$ generated by the set $T = \{ a_1+a_2, a_1+a_3 \}$, the membership problem can be solved using the ${\bf Z}[{\cal H}]$-basis $\{ a_1 + 1, a_2 - 1, a_2^{-1} - 1, a_3 - 1, a_3^{-1} - 1 \}$ for M₁. In the next section we will see that a Gröbner basis in our sense will contain one more polynomial, namely a₁^-1 + 1.

Notice that the constructive discussion cited above states how a solution for the membership problem for modules in ${\bf Z}[{\cal G}]^s$ can be given using a solution for the membership problem for ${\bf Z}[{\cal H}]^s$. Assuming that the solution is given by reduction methods - say given M, a ${\bf Z}[{\cal H}]$-module, we can compute a basis B of the module such that g in M iff $g \mbox{$\,\stackrel{*}{\Longrightarrow}\!\!\mbox{}^{{\rm }}_{B}\,$ } 0$ - we can the lift reduction similar to the case of polynomial rings over reduction rings. However, since elements of ${\bf Z}[{\cal G}]^s$ in order to decide membership have to be turned into polynomials, i.e., occurrences of a with negative exponents have to be made positive by multiplication with an appropriate power of a, for such a lifted reduction the translation lemma no longer holds.

Example 2    
Let ${\bf Z}[{\cal G}]$ be a group ring with ${\cal G}$ presented by $\Sigma = \{ a, a^{-1} \}$ and $T = \{ aa^{-1} \longrightarrow\lambda, a^{-1}a \longrightarrow\lambda \}$. Further let $p = 3 \cdot a^2 + 1$, then p is a basis of the right ${\bf Z}[{\cal G}]$-module as described by Sims. The polynomials $f = -2 \cdot a$ and g = a + a^-1 both do not belong to this right module. Now we have $g - f = 3 \cdot a + a^{-1}$ and we find that the ``polynomial'' $(g-f) \ast a = 3 \cdot a^2 + 1$ is ``reducible'' to 0 using p, while neither of the ``polynomials'' f nor $g \ast a$ are reducible with respect to p.
Hence we have the situation that g and f are congruent with respect to the ${\bf Z}[{\cal G}]$-module generated by p, but do not have the same ``normal form''. $\diamond$

Hence we cannot expect the resulting bases to be Gröbner bases in the strong sense that every element in ${\bf Z}[{\cal G}]^s$ has a unique normal form with respect to the module. In the following sections we show how for special cases Gröbner bases can be computed when using other definitions of reduction.

Let us close this section by sketching how Sims introduces Gröbner bases for the special case of finitely generated free Abelian groups in section 10.7 of [Si94]. The group ring then is also called the ring of Laurent polynomials.

Let the free Abelian group ${\cal G}$ be generated by $\{ a_1, a_1^{-1}, \ldots , a_n, a_n^{-1} \}$ and let the Laurent monomials $U = \{a_1^{\alpha_1} \ldots a_n^{\alpha_n} \mid \alpha_i \in {\bf Z}\}$, be ordered by a reverse lexicographic ordering (i.e. a lexicographic ordering comparing from the right to the left) in which the exponents are compared with respect to the ordering $0 < 1 < -1 < 2 < -2 < \ldots$⁷. The elements in U represent the group elements. Two elements $a_1^{\alpha_1} \ldots a_n^{\alpha_n}$ and $a_1^{\beta_1} \ldots a_n^{\beta_n}$ are called aligned, if $\alpha_i \cdot\beta_i \geq 0$ for all $1 \leq i \leq n$. Then, although the ordering on the monomials is not consistent with multiplication, one can specify certain multiples for which multiplication is stable which is done in corollary 7.6.

Suppose that u,v, and $x \in U$ such that $u \succ v$. If x and u are aligned, then $xu \succ xv$.

This corollary is in fact comparable to the lemmata 5 and 6 specialized for free Abelian groups. The property ensures that multiplying a polynomial with a monomial whose term is aligned to the head term leaves the head term in head position. Hence defining reduction based on this property remains stable, but in general will not capture the ideal congruence. This can be repaired because of theorem 7.9.

Let f be a nonzero element of ${\bf Z}[{\cal G}]$. There is a unique subset ${\cal T}(f)$ of ${\bf Z}[{\cal G}]$ such that the following hold:

1.

Each element of ${\cal T}(f)$ has the form $y \ast f$ with $y \in U$.

2.

If x is in U, then $x \ast f = y \ast g$ for a unique pair (y,g) such that g is in ${\cal T}(f)$, y is in U, and y is aligned with the leading monomial of g.

The cardinality of ${\cal T}(f)$ is at most 2^m.

Then for a finite set $T \subset {\bf Z}[{\cal G}]$ one can define the symmetrized set ${\cal S}(T)$ as the union of the sets ${\cal T}(f)$, $f \in T$, additionally assuming that all polynomials have positive leading coefficient. This in some sense corresponds to the fact that in the above proof of the Baumslag, Cannonito, Miller approach additionally to the condition $Ba \subseteq A$ one also has to ensure $Ca^{-1} \subseteq A$. Symmetrized sets can be computed as follows:

llFunctionSYMM
 
Given: 		 A finite subset T of 

${\bf Z}[{\cal G}]$.
Find: 		 

${\cal S}(T)$,
the symmetrized set for T.
 
Begin
		 

${\cal S} := T - \{ 0 \}$;
		 For i := m down to 1 do begin
				 

${\cal T} := \emptyset$;
				 For f in ${\cal S}$
do begin
						 Let u be the leading monomial of f;
						 Let $\alpha$
and $\beta$
be the algebraically largest and smallest exponents, respectively, on
								ai occurring in any monomial v of f for which the exponents on  

$a_{i+1}, \ldots , a_n$
								 in v agree with the  corresponding exponents in ui;
						 If 

$\alpha = \beta$
then 

${\cal T} := {\cal T} \cup \{ a_i^{- \alpha} \ast f \}$
						 Else begin
								 Let $\gamma$
be the greatest integer in8

$(\alpha + \beta - 1)/2$;
								 

${\cal T} := {\cal T} \cup \{ a_i^{- \gamma} \ast f, a_i^{- \gamma -1} \ast f \}$
						 End
				 End;
				 

${\cal S} := {\cal T}$
		 End;
		 For f in ${\cal S}$
do
				 If f has negative leading coefficient then replace f by -f in ${\cal S}$;
		 

${\cal S}(T) := {\cal S}$
End

For example the symmetrized set⁹  of the polynomial $g = 2 \cdot a_1^{-2}a_2^3 - 4 \cdot a_1^2a_2^3 - a_1a_2^2 + a_1a_2$ is ${\cal S}(g) = \{ 2 \cdot a_1^{-2}a_2^2 - 4 \cdot a_1^2a_2^2 - a_1a_2 + a_1, 4 ... ...2^2 + a_1^2a_2 - a_1^2, a_2^{-1} + 2 \cdot a_1^{-3}a_2 - 4 \cdot a_1a_2 - 1 \}$.

Now reduction using sets which are their own symmetrized sets is specified by the following procedure:

llFunctionREDUCE
 
Given: 		 A finite subset T of 

${\bf Z}[{\cal G}]$
which is its own symmetrized set.
		 A non-zero polynomial f in 

${\bf Z}[{\cal G}]$.
Find: 		  An element g of I + f is returned, where I is the ideal of 

${\bf Z}[{\cal G}]$
generated by T.
		 The element g is irreducible with respect to the set of products $y \ast h$,
where h is
		   in T, y is in U, and y is aligned with the leading monomial  of h.
 
Begin
		 i := 1; g := f; % At all times 

$g = c_1\cdot u_1 + \ldots + c_s \cdot u_s$. If g=0 then s=0.
		 While $i \leq s$
do
				 If there is an element h in T such that the leading term $b \cdot v$
of h satisfies 

$b \leq_{{\bf Z}} c_i$
								  and 

$u_i = y \circ v$,
where y is in U and y and v are  aligned, then begin
						 Let 

$c_i = q \cdot b + r$,
where q and r are integers and 

$0 \leq r < b$;
						 

$g := g - q \cdot y \ast h$;
% Recompute s and the terms 

$c_j \cdot u_j$ with $j \geq i$.
				 End
				 Else i := i+1; 
End

Hence reduction of a polynomial p at a monomial $c \cdot t$ by a polynomial f can be defined in case there exists u in U such that ${\sf HT}(f)$ and u are aligned, $t = u \circ{\sf HT}(f)$, and $b={\sf HC}(f) \leq_{{\bf Z}} c$. Then for $c = q \cdot b + r$, where q and r are integers and $0 \leq r < b$ we get $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{f}\,$ } p - q \cdot u \ast f$. Now critical pairs can be specified with respect to this reduction:

Let f and g be elements of ${\cal S}(T)$ with leading term u and v, respectively, and assume that u and v are aligned. Let $w = {\sf LCM}(u,v)$, $x = w \circ{\sf inv}\/(u)$, and $y = w \circ{\sf inv}\/(v)$. The leading monomial of $x \ast f$ and $y \ast g$ is w. Suppose $x \ast f \prec y \ast g$. Then $(x \ast f, y \ast g)$ is a critical pair.

 For a critical pair (f,g) let ${\sf HC}(g)\geq {\sf HC}(f)$ and ${\sf HC}(g) = q \cdot{\sf HC}(f) + r$ where q and r are integers and $0 \leq r < b$. Then we set $t(f,g) = g - q \cdot f$.

Now Gröbner bases can be computed as follows:

llFunctionGR¨OBNER  
Given: 		 A finite subset T of 

${\bf Z}[{\cal G}]$.
Find: 		  A Gröbner basis for the ideal of 

${\bf Z}[{\cal G}]$
generated by T.
 
Begin
		 B := SYMM(T);
		 Let C be the set of critical pairs obtained from B;
		 While C is not empty do begin
				 Remove a critical pair (f,g) from C;
				 h := REDUCE

(B,t(f,g));
				 If $h \neq 0$
then begin
						 S:=SYMM$(\{ h \})$;
						 Form all critical pairs obtainable from an element of S and an element of B
								  and add these pairs to C;
						 

$B := B \cup S$
				 End
		 End 
End

The output of this function will be a set which is both - a symmetrized set and a Gröbner basis.