Author: Eiko

Tags: abstract algebra, grobner basis

Time: 2024-10-15 14:38:49 - 2024-10-15 14:38:49 (UTC)

Introduction

is used to determine in an algebra, if a set of monomials form a \(k\)-basis.

It is an extension of Grobner basis to non-commutative rings, with the possibility that it might not terminate.

Definitions

  • Words

    \(X\) be a set of variables, a word is a finite sequence of elements of \(X\).

  • Monomial Ordering

    We want to have a total ordering on the set of words that is multiplicative, i.e.

    \[ u < v \Rightarrow ouo' < ovo' \]

    For example under the degree-lexicographic ordering, assuming \(x<y\) we have

    \[ 1 < x < y < x^2 < xy < yx < y^2 < x^3 < x^2y < \cdots \]

    The largest term of an element in \(k\langle X \rangle\) is called the leading term.

  • Reduced Word

    Given a set of relations \(g_1, \ldots, g_n\), a word \(w\) is reduced if it is not a subword of the leading terms of any of the \(g_i\).

Reduction

Reductions are performed for each relation \(g_i\), we can reduce any word that contains the leading term of \(g_i=w_i - f_i\) by replacing \(w_i\) with \(f_i\) (which is a linear combination of words strictly smaller than \(w_i\)).

Using this process, you can reduce any word to a reduced element.

An element \(h\in k\langle X\rangle\) is called reduction-unique if for any compositions of reductions, it always reduces to the same reduced element.

Ambiguity

  • If \(w_i\) and \(w_j\) share a common part, so that \(w_i = ac\) and \(w_j = cb\), then we say \(w_i\) and \(w_j\) have an overlap ambiguity.

    It is resolvable if the two ambiguous reductions of \(acb\) can be reduced to the same element under further reductions.

  • If \(w_i\) is contained in \(w_j\), \(w_j=aw_ib\), we say they have an inclusion ambiguity.

    Again it is resolvable if \(aw_ib\) can be reduced to the same element under further reductions.

Diamond Lemma

Let \(g_i\) be some relations generating an ideal \(I\subset k\langle X\rangle\), where \(g_i = w_i - f_i\). Then the following are equivalent:

  • The set of reduced words form a \(k\)-basis of \(k\langle X\rangle/I\).

  • Every element of \(k\langle X\rangle\) is reduction-unique.

  • All two types of ambiguous reductions are resolvable.

When ambiguity are not resolvable

If \(w_i\) and \(w_j\) have ambiguity, they get reduced to elements \(c_i\) and \(c_j\), you can add a new relation \(c_i-c_j\) to the set of relations, and repeat the process.

Warning: This process might not terminate, and can be choice dependent.