# Note on Groebner basis

A **Groebner basis** is a set of multivariate non-linear polynomials enjoying certain properties that allow simple algorithmic solutions for many fundamental problems in mathematics and natural and technical sciences.

There are 2 equivalent conditions by which Groebner basis can be defined.

## Definition via the Leading Power Product Property

First, let's define some terms.

- A *basis* is just a set of multivariate polynomials.
- *linear combination* of polynomials is a sum of polynomial multiples of the polynomials
- *power product* is a polynomial that is obtained from only the products of variables

We can impose some *ordering* to power products, for example as the following:

$$
1 \lt x \lt y \lt x^2 \lt xy \lt y^2 \lt x^3 \lt x^2y \lt \dots
$$

In Groebner basis theory, the ordering can be chosen freely as long as $1$ is the minimum element, and $u \lt v$ implies $ut \lt vt$ for all power products $u, v, t$.

- *leading power product* of a polynomial is the largest power product appearing in the polynomial for the pre-defined ordering.

Now, we can define Groebner basis in terms of leading power products of polynomials.

- **Groebner basis** is a set of polynomials of which all the leading power products of linear combinations are multiples of at least one leading power product of a basis.

Let's check out if the following basis is Groebner basis.

$$
B = \{ xz^2−3yz+1, x^2−2y, xy - 5z \}
$$

Consider the following linear combination.

$$
−2y^2z^2+15yz^2−5z=(−xy)(xz^2−3yz+1)+(yz^2)(x^2−2y)+(−3yz+1)(xy−5z)
$$

The leading power product of $−2y^2z^2+15yz^2−5z$ is $y^2z^2$ which is not a multiple of any of the leading power products of polynomials in the basis.($xz^2, x^2, xy$)

## Definition via Church-Rosser Property

Let's define some terms.

- A *division process* for a polynomial with respect to a basis is a repeated subtraction by multiples of basis elements to the effect of replacing a power product in the polynomial to the several power products that are smaller in the chosen ordering.
- A binary relation $\rightarrow$ is said to have *Church-Rosser* property whenever $f$ and $g$ are connected by a path of arrows and reverse arrows then $f$ and $g$ have some common successor $u$.

Now we can define Groebner basis in terms of a division process.

- **Groebner basis** is the basis which the division process with respect to has the Church-Rosser property.

Above 2 definitions are equivalent. (Why?)

## Fundamental Properties of Groebner basis

### The Elimination Property

- *Lexicographical Ordering*

### The Canonical Property

- congruence modulo $B$
- easy to decide congruence modulo $B$ when $B$ is Groebner basis, by computing remainder of polynomials w.r.t $B$

### The Syzygy Property

- *syzygy* is a representation of zero as a linear combination of some polynomials
- The *S-polynomial* of two polynomials $f$ and $g$ is as following:
$$
SPOL(f, g) := lcm(LPP(f), LPP(g))({{f} \over {LM(f)}} - {{g} \over {LM(g)}})
$$
- *cofactor tuple* is a representation of S-polynomial w.r.t to $B$ (the remainder of S-polynomial upon division by a Groebner basis containing $f$ and $g$ is 0)
- *principal syzygy* is obtained by the difference between the representations of S-polynomial
- all the syzygies of Groebner basis are represented by linear combinations of principal syzygies

## Construction of Groebner basis

Buchberger's algorithm is based on Buchberger's theorem.
Buchberger's theorem states:
> A basis is Groebner basis if and only if all S-polynomials of arbitrary two basis elements reduce to zero.

Buchberger's algorithm extends the basis whenever it encounters S-polynomial that does not reduce to zero. The algorithm may not terminate in the finite steps.

## Reference

http://www.scholarpedia.org/article/Gr%C3%B6bner_basis