---
tag: EZSWDV6ZZQ
kind: definition
name: Noncommutative Gröbner basis
msc: [16Z10, 16S15]
defines: EPPR3DAFP6
uses: [0QA8CHH8MG, 2P3Y2FRCSZ, 0DDA6CY7GJ, CV013KHVJG]
sources:
  - url: https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis
---

## Definition

Let $k$ be a [[field|0QA8CHH8MG]], let $X$ be a finite set, and let $X^*$ be the [[free monoid|CV013KHVJG]] of words in $X$.
Let $k\langle X \rangle$ be the [[free algebra|2P3Y2FRCSZ]] on $X$, whose basis is $X^*$.
Fix an *admissible order* $<$ on $X^*$: a well-order such that $u < v$ implies $p u q < p v q$ for all words $p, q$.
For a nonzero $f \in k\langle X \rangle$, its *leading word* $\operatorname{LW}(f)$ is the largest word that occurs in $f$ with a nonzero coefficient.
Let $I$ be a [[two-sided ideal|0DDA6CY7GJ]] of $k\langle X \rangle$.
A subset $G \subseteq I$ is a *(noncommutative) Gröbner basis* of $I$ if for every nonzero $f \in I$ there are $g \in G$ and words $p, q$ with
$$\operatorname{LW}(f) = p \operatorname{LW}(g)\, q.$$

## Remarks

A Gröbner basis $G$ of $I$ generates $I$ as a two-sided ideal.
The words that contain no $\operatorname{LW}(g)$, $g \in G$, as a subword are the *normal words*, and their images form a $k$-basis of $k\langle X \rangle / I$.
Example: $X = \set{x, y}$ with the degree-lexicographic order, $x < y$, and $I$ generated by $g = yx - xy$, so $\operatorname{LW}(g) = yx$.
The word $yx$ has no overlap with itself, so by the diamond lemma $\set{g}$ is a Gröbner basis; the normal words are $x^a y^b$, and $k\langle x, y \rangle / I \cong k[x, y]$.
Non-example: with the same order, let $I$ be generated by $g = xx - y$, so $\operatorname{LW}(g) = xx$.
The element $gx - xg = xy - yx$ lies in $I$, and its leading word is $yx$, which does not contain $xx$.
So $\set{g}$ is not a Gröbner basis of $I$.