Home Online Manual
Top
Back: Free associative algebras
Forward: Letterplace correspondence
FastBack: Graded commutative algebras (SCA)
FastForward: Non-commutative libraries
Up: LETTERPLACE
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

7.6.2 Groebner bases for two-sided ideals in free associative algebras

We call a total ordering $<$ on the free monoid $X := \langle x_1,\dots,x_n \rangle$ (where $1$ is identified with the identity element) a monomial ordering if the following conditions hold:

  • $<$ is a well-ordering on $X$, that is $1 < x$ $\forall x \in X \setminus \{1\}$,
  • $\forall p,q,s,t \in X$, if $s<t$, then $p\cdot s \cdot q< p\cdot t \cdot q$,
  • $\forall p,q,s,t \in X$, if $s=p\cdot t \cdot q$ and $s\not=t$, then $t<s$.

Hence the notions like a leading monomial and a leading coefficient transfer to this situation.

We say that a monomial $v$ divides monomial $w$, if there exist monomials $p,s \in X$, such that $w = p \cdot v \cdot s$.

In other words $v$ is a proper subword of $w$.

For a subset $G \subset T := K\langle x_1,\dots,x_n \rangle$, define a leading ideal of $G$ to be the two-sided ideal $L(G) \; = \; {}_{T} \langle$ $\; \{lm(g) \;\vert\; g \in G\setminus\{0\} \}$ $\; \rangle_{T} \subseteq T$.

Let $<$ be a fixed monomial ordering on $T$. We say that a subset $G\subset I$ is a (two-sided) Groebner basis for the ideal $I$ with respect to $<$, if $L(G)=L(I)$. That is $\forall f\in I\setminus\{0\}$ there exists $g\in G$, such that $lm(g)$ divides $lm(f)$.