Diamond Lemma

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 o u o^{'} < o v o^{'}$

For example under the degree-lexicographic ordering, assuming $x < y$ we have

$1 < x < y < x^{2} < x y < y x < y^{2} < x^{3} < x^{2} y < \dots$

The largest term of an element in $k ⟨ X ⟩$ is called the leading term.
Reduced Word

Given a set of relations $g_{1}, \dots, 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 ⟨ X ⟩$ 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} = a c$ and $w_{j} = c b$ , then we say $w_{i}$ and $w_{j}$ have an overlap ambiguity.

It is resolvable if the two ambiguous reductions of $a c b$ can be reduced to the same element under further reductions.
If $w_{i}$ is contained in $w_{j}$ , $w_{j} = a w_{i} b$ , we say they have an inclusion ambiguity.

Again it is resolvable if $a w_{i} b$ can be reduced to the same element under further reductions.

Diamond Lemma

Let $g_{i}$ be some relations generating an ideal $I \subset k ⟨ X ⟩$ , where $g_{i} = w_{i} - f_{i}$ . Then the following are equivalent:

The set of reduced words form a $k$ -basis of $k ⟨ X ⟩ / I$ .
Every element of $k ⟨ X ⟩$ 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.