A gentle (and short) introduction to Gröbner Bases

Taken from my report for a Computer Algebra course.

Motivation

We know there are plenty of methods to solve a system of linear equations (to name a few: Gauss elimination, QR or LU factorization). In fact, it is straightforward to check whether a linear system has any solutions, and if it does, how many of them there are. But what if the system is made of non-linear equations? The invention of Groebner bases and the field of computational algebra came up to answer these questions.

In this text we will recap the theory behind single-variable polynomials and extend it to multiple-variable ones, ultimately getting to the definition of Groebner bases.

In some cases, the transition from one to multiple variables is smooth and pretty much an extension of the simple case (for example for the Greatest Common Divisor algorithm). In other cases, however, there are conceptual jumps to be made. To give an example, single variable polynomials have always a finite number of roots, while this does not hold for multivariable polynomials. Intuitively, the reason is that a polynomial in one variable describes a curve in the plane, which can only intersect the x-axis a discrete and finite number of times. On the other hand, a multivariate polynomial describes a surface in space, which will always intersect the 0-plane in a continuum of points.

Preliminaries

All throughout these notes, it will be important to have in mind some basic algebra definitions.

To begin with, we ask what is the most basic (but useful) structure we can put on a set. We ask, for example, given the set of natural numbers, what do we need to do to allow basic manipulation (i.e. summation)? This leads us to the definition of group.

DEF 1: A group is made of a set $\mathcal{G}$ with one binary operation $+$ such that:

The operation is closed: $a+b \in \mathcal{G} \ \forall a,b \in \mathcal{G}$
The operation is associative: $a+(b+c)=(a+b)+c \ \forall a,b,c \in \mathcal{G}$
The operation $+$ has an identity element $0$ s.t. $g+0 = g \ \forall g \mathcal{G}$
Each element has an inverse element: $\forall g \in \mathcal{G}, \exists h \in \mathcal{G} : g+h=0$

A group is usually denoted with $(\mathcal{G}, +)$ .
Notice that we did not ask anything about commutativity!

Then, the notion of group can be made richer and more complex: first into that of ring, then into that of field.

DEF 2: A ring is a group with an extra operation $(\mathcal{G}, +, *)$ which sastisfies the following properties:

The operation $+$ is commutative: $a+b=b+a \ \forall a,b \in \mathcal{G}$
The operation $*$ is closed: $a*b \in \mathcal{G} \ \forall a,b \in \mathcal{G}$
The operation $*$ has an identity element $1$ s.t. $g*1 = g \ \forall g$
The operation $*$ is associative: $a*(b*c)=(a*b)*c \ \forall a,b,c \in \mathcal{G}$
The operation $*$ is distributive with respect to $+$

DEF. 3: A field $\mathcal{K}$ is a ring in which all elements have an inverse with respect to the operation $*$ .

All throughout these notes, the symbol $\mathcal{K}$ will denote a field.

DEF 4: A monomial is a product $x_1^{\alpha_1} \cdots x_n^{\alpha_n}$ , with $\alpha_i \in \mathbb{N}$ . Its degree is the sum of the exponents.

DEF 5: A polynomial is a linear combinations of monomials.

We conclude by noting that the space of polynomials with coefficients taken from a field $\mathcal{K}$ makes a ring, denoted with $\mathcal{K}[x_1, \cdots, x_n]$ .

Affine varieties and ideals

Our first step towards formalizing the theory for non-linear systems is to understand what the space of solutions looks like. As much as we know that linear spaces are the solutions spaces for linear systems, there is something analogous for non-linear systems, and that is affine varieties.

DEF 6: Given $f_1, \cdots, f_s$ polynomials in $\mathcal{K}[x_1, \cdots, x_n]$ , the affine variety over them is the set of their common roots:

$V(f_1, \cdots, f_s) = \{ (a_1, \cdots, a_n) \in \mathcal{K}^n : f_i(a_1, \cdots, a_n) = 0 \ \forall i = 1, \cdots, s\}$

EX 1: $V(x_1+x_2-1, x_2+1) = \{ (2, -1) \}$

When working with rings, as it is our case, the notion of ideal is important. The reason for its importance is that ideals turn out to be kernels of ring homomorphisms — or, in other words, that they are the “good sets” that can be used to take ring quotients.

DEF 7: An ideal is a subset $I \subset \mathcal{K}[x_1, \cdots, x_n]$ such that:

$0 \in I$
it is closed w.r.t +: $f+g \in I \ \forall f,g \in I$
it is closed w.r.t * for elements in the ring: $f*g \in I \ \forall f \in I, g \in \mathcal{K}[x_1, \cdots, x_n]$

Given some elements of a ring, we might wonder what is the way to build an ideal (the smallest) that would contain them.

DEF 8: Given $f_1, \cdots, f_s$ polynomials, the ideal generated by them is the set of combinations with coefficients taken from the ring:

$<f_1, \cdots, f_s> = \{ \sum_i^s h_i f_i, \ \ h_i \in \mathcal{K}[x_1, \cdots, x_n] \}$

Having introduced ideals, we immediately find a result that is linked to our purpose of non-linear systems inspection: a simple way to check if a system has solutions or not.

THEO 1: If $1 \in I=<f_1, \cdots, f_s>$ , then $V(I) = \emptyset$ .
PROOF: Since $1 \in I$ , it must be possible to write it as a combination of the form $1 = \sum h_i f_i$ . Now, if we suppose that $V(I)$ is not empty, then one of its points $a$ is a root of all the $f_i$ . This would mean that $\sum h_i f_i(a) = 0 \neq 1$ , which is absurd.

Groebner bases

Groebner bases give a computational method for solving non-linear systems of equations through an apt sequence of intersection of ideals. To state its definition, we first need to know what a monomial ordering is. Intuitively, we can think of such an ordering as a way to compare monomials — the technical definition does not add much more concept. Different orderings are possible.

Once we have a way of ordering monomials, it is also possible to define the leading monomial (denoted as $LM$ ) of a given polynomial. For single variable polynomials it is pretty straightforward, but for the multi-variate case we need to define an ordering first (some possible options are: lexicographic, graded lexicographic, graded reverse lexicographic).

DEF 9: Given a monomial ordering, a Groebner basis of an ideal $I$ w.r.t the ordering is a finite subset $G = \{ g_1, \cdots, g_s \} \subset I$ s.t. $<LM(g_1), \cdots, LM(g_s)> = LM(I)$ .

This basis is a generating set for the ideal, but notice how it depends on the ordering! Finally, it is possible to prove that every ideal has a Groebner basis (Hilbert’s basis theorem).

From here now, the rationale is that, given a system of polynomial equations, we can see the polynomials as generators of some ideal. That ideal will have a Groebner basis, and there is an algorithm to build one (Buchberger algorithm). From there, apt ideal operations will allow to solve the system by eliminating the variables.

We now describe this elimination algorithm with an example:

(1) $\begin{equation*} \begin{cases} x^2+y+z=1 \\ x + y^2 +z=1 \\ x+y+z^2=1 \end{cases} \end{equation*}$

Given the ideal

$I = <x^2+y+z-1, x + y^2 +z-1, x+y+z^2-1>,$

then a Groebner basis with respect to the (lexicographical order) is

(2) $\begin{equation*} \begin{cases} g_1=x+y+z^2-1 \\ g_2=y^2-y-z^2+z \\ g_3=2yz^2+z^4-z^2\\ g_4=z^6-4z^4+4z^3-z^2 \end{cases} \end{equation*}$

which can be used to compute the solutions of the initial system (1).

To do so, first consider the ideal $I \cap \mathbb{C}[z]$ , which practically corresponds to all polynomials in $I$ where $x,y$ are not present. In our case, we are left only with one element from the basis which only involve $z$ : $g_4=z^6-4z^4+4z^3-z^2$ . The roots of $g_4$ are $0,1,-1 \pm \sqrt{2}$ .

The values for $z$ can then be used to find the possible values for $y$ using polynomial $g_3, g_2$ , which only involve $y,z$ . Finally, once possible values for $y,z$ are known, they can be used to find the corresponding values for $x$ through $g_1$ .

This example will yield the following solutions:

(3) $\begin{equation*} \begin{cases} (1, 0, 0), (0, 1, 0), (0, 0, 1), \\ (-1 + \sqrt{2}, -1 + \sqrt{2}, -1 + \sqrt{2}), \\ (-1 - \sqrt{2}, -1 - \sqrt{2}, -1 - \sqrt{2}) \end{cases} \end{equation*}$

Was this Helpful ?
yes no

A gentle (and short) introduction to Gröbner Bases

Motivation

Preliminaries

Affine varieties and ideals

Groebner bases

Leave a Reply Cancel reply

Categories

Blog entries