Home Online Manual
Top
Back: G-algebras
Forward: Syzygies and resolutions (plural)
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

7.4.2 Groebner bases in G-algebras

We follow the notations, used in the SINGULAR Manual (e.g. in Standard bases).

For a $G$-algebra $A$, we denote by ${}_{A} \langle g_1, \dots, g_s \rangle$ the left submodule of a free module $A^r$, generated by elements $\{g_1, \dots, g_s\}\subset A^r$.

Let $<$ be a fixed monomial well-ordering on the $G$-algebra $A$ with the Poincar@'e-Birkhoff-Witt (PBW) basis $\{x^{\alpha} = x^{a_1}_1 x^{a_2}_2 \dots x^{a_n}_n\}$. For a given free module $A^r$ with the basis $\{e_1,\ldots, e_r\}$, $<$ denotes also a fixed module ordering on the set of monomials $\{x^{\alpha} e_i \mid \alpha\in {\bf N}^n, 1\leq i\leq r \}$.

Definition

For a set $S \subset A^r$, define $L(S)$ to be the $K$-vector space, spanned on the leading monomials of elements of $S$, $L(S) = \oplus \{K x^{\alpha} e_i \mid \exists s \in S, \hbox{LM(s)}=x^{\alpha}e_i\}$.

We call $L(S)$ the span of leading monomials of $S$.

Let $I \subset A^r$ be a left $A$-submodule. A finite set $G\subset I$ is called a left Groebner basis of $I$ if and only if $L(G)=L(I)$, that is for any $f \in I\setminus \{ 0 \}$ there exists a $g\in G$ satisfying $ \hbox{LM}(g) \mid \hbox{LM}(f)$, i.e., if $\hbox{LM}(f) = x^{\alpha}e_i$, then $\hbox{LM}(f) = x^{\beta}e_i$ with $\beta_j \leq \alpha_j, \; 1\leq j \leq n$.


Remark: In general non-commutative algorithms are working with global well-orderings only (see PLURAL, Monomial orderings and Term orderings), unless we deal with graded commutative algebras via Graded commutative algebras (SCA).

A Groebner basis $G\subset A^r$ is called minimal (or reduced) if $0\notin G$ and if $\hbox{LM}(g)\notin L(G\setminus \{ g \})$ for all $g\in G$. Note, that any Groebner basis can be made minimal by deleting successively those $g$ with $\hbox{LM}(h)\mid \hbox{LM}(g)$ for some $h\in G\setminus\{g \}$.

For $f\in A^r $ and $G\subset A^r$ we say that $f$ is completely reduced with respect to $G$ if no monomial of $f$ is contained in $L(G)$.

Left Normal Form

A map $\hbox{NF} : A^r \times \{G \mid G\ \hbox{ a (left) Groebner basis}\} \to A^r, (f\vert G) \mapsto \hbox{NF}(f\vert G)$, is called a (left) normal form on $A^r$ if for any $f\in A^r $ and any left Groebner basis $G$ the following holds:

(i) $\hbox{NF}(0\vert G) = 0$,

(ii) if $\hbox{NF}(f\vert G) \not= 0$ then $\hbox{LM}(g)$ does not divide $\hbox{LM}(\hbox{NF}(f\vert G))$ for all $g\in G$,

(iii) $f - \hbox{NF}(f\vert G)\in {}_{A}\langle G \rangle$.

$\hbox{NF}(f\vert G)$ is called a left normal form of $f$ with respect to $G$ (note that such a map is not unique).


Remark: As we have already mentioned in the definitions ideal and module (see PLURAL), by NF (or reduce) PLURAL understands a left normal form. Note, that rightNF from nctools_lib allows to compute a right normal form.

Left ideal membership (plural)

For a left Groebner basis $G$ of $I$ the following holds: $f \in I$ if and only if the left normal form $\hbox{NF}(f\vert G) = 0$.

For computing a left Groebner basis G of I, use std (plural).

For computing a left normal form of f with respect to G, use reduce (plural).

Right ideal membership (plural)

The right ideal membership is analogous to the left one:

for computing a right Groebner basis G of I, use rightStd from nctools_lib,

for computing a right normal form of f with respect to G, use rightNF from nctools_lib.

Two-sided ideal membership (plural)

Let $J$ be a two-sided ideal and $T$ be a two-sided Groebner basis of $J$.

Then $f \in J$ if and only if the left normal form $\hbox{NF}(f\vert T) = 0$.

For computing a two-sided Groebner basis T of J, use twostd (plural),

for computing a normal form of f with respect to T, use reduce (plural).