Gröbner Bases:
An Introduction

Bruno Buchberger
Research Institute for Symbolic Computation
A 4232 Hagenberg, Austria 
B.Buchberger@RISC.Uni-Linz.ac.at
 ->

What is the Purpose of GB?

A Uniform Approach

The method (theory plus algorithms) of Gröbner bases provides a uniform approach to solving a wide range of problems expressed in terms of sets of multivariate polynomials.

x y-2  y z - z=0
(y^2) - (x^2) z  +  x z = 0
(z^2)-(y^2) x + x=0

Example: kinematic equations of a robot.

Areas (see GB-98 Proceedings: Tutorials)

algebraic geometry, commutative algebra, polynomial ideal theory

invariant theory

automated geometrical theorem proving

coding theory

integer programming

partial differential equations

hypergeometric functions

symbolic summation

statistics

systems theory

numerics (e.g. wavelets) ->

Example Commutative Algebra (see GB-98: Intro to GB)

solvability and solving of algebraic systems of equations

ideal and radical membership

effective computation in residue class rings modulo polynomial ideals

linear diophantine equations with polynomial coefficients ("syzygies")

Hilbert functions

algebraic relations among polynomials

implicitization

inverse polynomial mappings

...

↑

How Can GB be Applied?

The general strategy: Given a set F of polynomials in K[(Subscript[x, 1]), …, (Subscript[x, n])] (that describes some problem, e.g. a system of equations):

We transform F into another set G of polynomials "with certain nice properties" (called a "Gröbner basis") such that F and G are "equivalent"  (i.e. generate the same ideal).

From the theory of GBs we know that this transformation can be carried out by an algorithm.

From the theory of GBs we know that, because of the "nice properties of GBs, many problems that are difficult for general F are "easy" for Gröbner bases G.

We solve the problem for G and transform the solution back to F.

↑

What are GB?

Division ("Reduction") of Multivariate Polynomials

g = (x^2) (y^3)+3 x (y^2)-5  x;

(Subscript[f, 1])=x y-2  y;   (Subscript[f, 2])=2  (y^2)-(x^2);    F  =  {(Subscript[f, 1]), (Subscript[f, 2])};

One possible division ("reduction") step:

h=g-(3x (y^2)/(x y))(Subscript[f, 1])                        //Expand

We write

\(TraditionalForm
    \`g\ \ \ \ \ \ \(⟶\_\(F\ \ \ \ \ \)\)h\)

for this situation.                                                                                   ->

Note that we presuppose that we have fixed some ordering of the power products in polynomials so that we can speak about the "leading power product" of polynomials.

(There are infinitely orderings that are "admissible" for the GB theory. They can be  characterized by two simple axioms.)

In General, Many Reductions are Possible

g = (x^2) (y^3)+3 x (y^2)-5  x;

(Subscript[f, 1])=x y-2  y;  (Subscript[f, 2])=2  (y^2)-(x^2);  F  =  {(Subscript[f, 1]), (Subscript[f, 2])};

Another possible division  ("reduction") step:

(Subscript[h, 2]) = 
      g - ((x^2) (y^3)/(x y)) 
            (Subscript[f, 1])                         // 
        Expand

(Subscript[h, 1]) =  -5 x + 6 (y^2) + (x^2) (y^3)

Another possible division  ("reduction") step:

(Subscript[h, 3]) = 
      g - ((x^2) (y^3)/(2 (y^2))) 
            (Subscript[f, 2])                         // 
        Expand

Multivariate Polynomial Division Always Terminates But is Not Unique

We write

\(TraditionalForm\`g\ \ \ \ \ \ \(⟶\^*\)\_F\ \ \ \ \ h\)

if g reduces to h by finitely many reduction steps w.r.t. F.

Fact (Termination): Given g and F, any sequence of reduction steps will always arrive at a polynomial h that is in reduced form w.r.t. F.

Fact (Non-uniqueness): Given g and F, it may well be that

\(TraditionalForm\`\(\(h\+_\_F\)\(\ \ \ \ \ \ \ \ \)\(\(⟵\_F\)\^*\)\(\ \ \ \ \ \ \ \ \ \ \ \)\(g\)\(\ \ \ \ \ \ \)\(\(⟶\_F\)\^*\)\(\ \ \ \ \ \ \)\(k\+_\_F\)\(\ \ \ \ \ \ \ \)\)\)

but h ≠ k.

Definition of Gröbner Bases

Definition:

          F is a  Gröbner basis  :⟺    (Subscript[⟶, F])   is unique.

\(TraditionalForm\`∀ \+\(g, h, k\)\ \ \ \(\((\ \ \ \ \ h\+_\_F\ \ \ \ \ \(\(⟵\_F\)\^*\)\ \ \ \ \ \ \ \ \ \ \ g\ \ \ \ \ \ \(\(⟶\_F\)\^*\)\ \ \ \ \ \ k\+_\_F\ \ \ \ ⟹\ \ \ \ \ h = k\ \ )\)\(.\)\)\)

How Can GB be Constructed?

The Problem

Given F,  find G   s.t. Ideal(F) = Ideal(G) and G is a Gröbner basis.

An Algorithm

This problem can be solved by the following algorithm:

Start with G:= F. 
For any pair of polynomials (Subscript[f, 1]), (Subscript[f, 2]) ∈ G:

      Compute the "S-polynomial" of (Subscript[f, 1]), (Subscript[f, 2]) and reduce it to a reduced form h w.r.t. G.
      
      If h = 0, consider the next pair.
      
      If h ≠ 0, add h to G and iterate.              ->

S-Polynomials

(Subscript[f, 1])=x y-2  y;  (Subscript[f, 2])=2  (y^2)-(x^2);

S–polynomial[(Subscript[f, 1]), (Subscript[f, 2])]=y (Subscript[f, 1])-(1/2)x (Subscript[f, 2])       //Expand

Note that the least common multiple of the "leading power products" of (Subscript[f, 1])and (Subscript[f, 2]) does not any more occur in the S-polynomial of (Subscript[f, 1])and (Subscript[f, 2])!

The notion of S-polynomials is the nucleus of algorithmic Gröbner bases theory.

Specializations

The Gröbner bases algorithm,

for linear polynomials, specializes to Gauss' algorithm, and

for univariate polynomials, specializes to Euclid's algorithm.

↑

Why Does This Work?

Termination of the Algorithm

An application of "Dickson's Lemma".

Correctness of the Algorithm

The correctness of the algorithm is based on the following "Main Theorem of Gröbner Bases Theory":

F is a Gröbner basis  :⟺  
      (Underscript[∀ , (Subscript[f, 1]), (Subscript[f, 2]) ∈ F])  RF[ F, S–polynomial[(Subscript[f, 1]), (Subscript[f, 2])]] = 0.

Proof: Nontrivial. Combinatorial. 
All details see:

BB, PhD thesis 1965, published in aequationes mathematicae 1970, (English translation in the appendix of the Proceedings of the GB Conference 1998, see below).

BB, Introduction to GB: Proceedings of the GB Conference 1998, see below.

The power of the Gröbner bases method is contained in this proof.

Examples

A Simple Set of Equations

Computation of Groebner bases

(Subscript[f, 1])=x y-2  y;
(Subscript[f, 2])=2  (y^2)-(x^2);
F  =  {(Subscript[f, 1]), (Subscript[f, 2])};

Call of the Groebner bases algorithm in Mathematica:

G = GroebnerBasis[F]

This is the (uniquely determined reduced) Groebner basis w.r.t. lexicographic ordering with x ≺ y. The ordering can also be indicated explicitly:

G = GroebnerBasis[F, {y, x}]

This is the (uniquely determined reduced) Groebner basis w.r.t. lexicographic ordering with y ≺ x:

GroebnerBasis[F, {x, y}]

Gröbner bases have - among many "nice" properties - the "elimination property"!

Solution of Systems Using Groebner Bases

(Subscript[g, 1]) = G[[1]]

Solve[{(Subscript[g, 1]) == 0}, {x}]

(Subscript[g, 2]) =  G[[2]] /. {x -> 2}

(Subscript[g, 3]) = G[[3]] /. {x -> 2}

G

Solve[(Subscript[g, 3]) == 0, y]

->

A More Complicated Set of Equations

(Subscript[f, 1])=x y-2  y z - z;
(Subscript[f, 2]) = (y^2) - (x^2) z  +  x z;
(Subscript[f, 3])=(z^2)-(y^2) x + x;

F  =  {(Subscript[f, 1]), (Subscript[f, 2]), (Subscript[f, 3])};

{time, G} = GroebnerBasis[F]  //  Timing

zsol = NSolve[G[[1]] == 0, z]

Gsub = G  /.  zsol[[1]]

PolynomialGCD[Gsub[[2]], Gsub[[3]]]

ysol = NSolve[ Gsub[[2]] == 0, y]

ysol = NSolve[ Gsub[[3]] == 0, y]

xsol = NSolve[ Gsub[[4]] == 0, x]

F /. zsol[[1]] /. ysol[[1]] /. xsol[[1]]

S = Solve[{(Subscript[f, 1]) == 0, (Subscript[f, 2]) == 0, (Subscript[f, 3]) == 0}, {x, y, z}];

S

S /. {Root[
            1 - 8 #(1^2) + 20 #(1^3) - 17 #(1^4) + 15 #(1^5) - 39 #(1^6) + 
                41 #(1^7) - 20 #(1^8) + 20 #(1^9) - 16 #(1^10) + 4 #(1^11) &, 
            1] -> α1, 
Root[
            1 - 8 #(1^2) + 20 #(1^3) - 17 #(1^4) + 15 #(1^5) - 39 #(1^6) + 
                41 #(1^7) - 20 #(1^8) + 20 #(1^9) - 16 #(1^10) + 4 #(1^11) &, 
            2] -> α2, 
Root[
            1 - 8 #(1^2) + 20 #(1^3) - 17 #(1^4) + 15 #(1^5) - 39 #(1^6) + 
                41 #(1^7) - 20 #(1^8) + 20 #(1^9) - 16 #(1^10) + 4 #(1^11) &, 
            3] -> α3, 
Root[
            1 - 8 #(1^2) + 20 #(1^3) - 17 #(1^4) + 15 #(1^5) - 39 #(1^6) + 
                41 #(1^7) - 20 #(1^8) + 20 #(1^9) - 16 #(1^10) + 4 #(1^11) &, 
            4] -> α4, 
Root[
            1 - 8 #(1^2) + 20 #(1^3) - 17 #(1^4) + 15 #(1^5) - 39 #(1^6) + 
                41 #(1^7) - 20 #(1^8) + 20 #(1^9) - 16 #(1^10) + 4 #(1^11) &, 
            5] -> α5}

Algebraic Relations

Can

((Subscript[x, 1])^7) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^7)

be expressed as a polynomial in

((Subscript[x, 1])^2) + ((Subscript[x, 2])^2)
((Subscript[x, 1])^2) ((Subscript[x, 2])^2)
((Subscript[x, 1])^3) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^3)

?

Note: The above polynomials forms a system of fundamental invariants for (Subscript[ℤ, 4]), i.e. a set of generators for the ring

{f ∈ ℂ[(Subscript[x, 1]), 
              (Subscript[x, 2])]  \[VerticalSeparator]  f ((Subscript[x, 1]), (Subscript[x, 2])) = 
        f (-(Subscript[x, 2]), (Subscript[x, 1]))},

i.e.

{((Subscript[x, 1])^2) + ((Subscript[x, 2])^2), ((Subscript[x, 1])^2) ((Subscript[x, 2])^2), ((Subscript[x, 1])^3) (Subscript[x, 2]) - 
          (Subscript[x, 1]) ((Subscript[x, 2])^3)} /. {(Subscript[x, 1]) -> -(Subscript[x, 2]), 
        (Subscript[x, 2]) -> (Subscript[x, 1])}

and all invariants can be expressed as polynomials in these invariants.

{time, GB} = 
      GroebnerBasis[{-(Subscript[i, 1]) + ((Subscript[x, 1])^2) + 
              ((Subscript[x, 2])^2), -(Subscript[i, 2]) + ((Subscript[x, 1])^2) 
                ((Subscript[x, 2])^2), -(Subscript[i, 3]) + ((Subscript[x, 1])^3) (Subscript[x, 2]) - 
              (Subscript[x, 1]) ((Subscript[x, 2])^3)}, {(Subscript[x, 2]), (Subscript[x, 1]), (Subscript[i, 3]), (Subscript[i, 2]), (Subscript[i, 1])}] // 
        Timing

PolynomialReduce[((Subscript[x, 1])^7) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^7), 
      GB, {(Subscript[x, 2]), (Subscript[x, 1]), (Subscript[i, 3]), (Subscript[i, 2]), (Subscript[i, 1])}, 
      MonomialOrder -> Lexicographic]

(Subscript[i, 1]^2) (Subscript[i, 3]) - (Subscript[i, 2]) (Subscript[i, 3]) /. {(Subscript[i, 1]) -> ((Subscript[x, 1])^2) + ((Subscript[x, 2])^2), 
          (Subscript[i, 2]) -> ((Subscript[x, 1])^2) ((Subscript[x, 2])^2), 
          (Subscript[i, 3]) -> ((Subscript[x, 1])^3) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^3)}  // 
      Expand

R = 
      PolynomialReduce[((Subscript[x, 1])^6) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^6), 
        GB, {(Subscript[x, 2]), (Subscript[x, 1]), (Subscript[i, 3]), (Subscript[i, 2]), (Subscript[i, 1])}, 
        MonomialOrder -> Lexicographic]

R[[1]]

GB

R[[1]] . GB // Expand

R[[2]]

((Subscript[x, 1])^6) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^6) /. {(Subscript[x, 1]) -> -(Subscript[x, 2]), 
        (Subscript[x, 2]) -> (Subscript[x, 1])}

->

The Groebner Bases Automated Prover for Coordinate Geometry

Example Pappus Theorem: Input to Theorema

We want to prove / disprove the following conjecture: Let A, B,  C and A1, B1,  C1 be on two lines and P = A B1 ⋂ A1 B, Q = A C1 ⋂ A1 C, S = B C1 ⋂ B1 C. Then P, Q, and S are collinear.

For this we only have to input the conjecture into Theorema in the following form:

Proposition["Pappus",  any[A, B, A1, B1, C, C1, P, Q, S], 
      point[A, B, A1, B1] ∧ pon[C, line[A, B]] ∧ 
          pon[C1, line[A1, B1]] ∧ 
          inter[P, line[A, B1], line[A1, B]] ∧ 
          inter[Q, line[A, C1], line[A1, C]] ∧ 
          inter[S, line[B, C1], line[B1, C]] \[Implies] 
        collinear[P, Q, S]]

and then to call the Theorema Groebner bases prover by the following command:

Prove[Proposition["Pappus"], by -> GeometryProver, 
      ProverOptions -> {Method -> "GroebnerProver", 
          Refutation -> True}]

Proof Generatet Automatical by Theorema

This call will generate, completely automatically, the following proof (which also contains an explanation of the proof method  by Groebner bases theory):

The proof illustrates that the proving algorithm proceeds by, first, transforming the proof problem into the problem of constructing a Groebner bases for a certain set of polynomials and checking whether this Groebner basis is equal to {1} or not. Since the construction of Groebner is possible by an algorithm, this decision can be done algorithmically.

Why are GB Called Gröbner Bases?

Professor  Wolfgang Gröbner was my PhD thesis supervisor.

In my thesis (1965) and journal publication  (1970), reprinted in the GB-98 Proceedings, I introduced:

* the concept of Gröbner bases and reduced Gröbner bases
* the S-polynomials
* the main theorem with proof
* the algorithm with termination and correctness proof
* the uniqueness of Gröbner bases
* first applications (computing in residue rings, Hilbert function, algebraic systems)
* the technique of base-change w.r.t. to different orderings
* a complete computer implementation 
* first complexity considerations

However, in the thesis, I did not use the name "Gröbner bases". I introduced this name only in 1976, when people started to become interested in my work.

My later contributions:

* the technique of criteria for eliminating unnecessary reductions
* an abstract characterization of "Gröbner bases rings"

Where Do We Find Info on GB?

Gröbner Bases 98 Conference

B. Buchberger, F. Winkler. Gröbner Bases: Theory and Applications. Cambridge University Press, 1998. 560 pages.

This book contains tutorials and original papers.

This book contains also:

B. Buchberger. Introduction to Gröbner Bases, pp. 3-31.

B. Buchberger. An Algorithmic Criterion for the Solvability of Systems of Algebraic Equations, pp. 540-560. (English translation of the original paper from 1970, in which Gröbner bases were introduced.)

A continuation of this book is the special issue of the JSC  on Gröbner bases edited by Q.N. Tran and F. Winkler, 2000.

On Your Desk

GB implementations are contained in all the current math software systems like Mathematica (see demo), Maple, Magma, Macsyma, Axiom, Derive, Reduce, Mupad, ...

Software systems specialized on Gröbner bases: CoCoA, Macaulay, Singular, ...

->

In Your Palm

Gröbner bases are now availabe on the TI-92 (implemented in Derive).

Textbooks

T. Kreuzer, L. Robbiano: Algorithmic Commutative Algebra I. Springer, Heidelber, 2000: Contains a list of all other textbooks on GB.

W.W.Adams, P. Loustenau. Introduction to Gröbner Bases. Graduate Studies in Mathematics: Amer. Math. Soc., Providence, R.I., 1994.

T.Becker, V.Weispfenning. Gröbner Bases: A Computational Approach to Commutative Algebra. Springer, New York, 1993.

D.Cox, J.Little, D.O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York, 1992.

....

->

In the Web

Search. E.g. in the Research Index you obtain ~ 3000 citations.

Original Publications

Approximately 500 papers appeared meanwhile on Gröbner bases.

J of Symbolic Computation, in particular, special issues.

ISSAC Conferences.

Mega Conferences.

...

The essential  additional original ideas in the literature:

Gröbner bases can be constructed w.r.t. arbitrary "admissible" orderings (W. Trinks 1978)

Gröbner bases w.r.t. to "lexical" orderings have the elimination property (W. Trinks 1978)

Gröbner bases can be used for computing syzygies and the S-polys generate the module of syzygies (G. Zacharias 1978)

A given F, w.r.t. the infinitely many admissible orderings, has only finitely many Gröbner bases and, hence, we can construct a "universal" Gröbner bases for F (L. Robbiano, V. Weispfenning, T. Schwarz 1988)

Starting from a Gröbner bases for F for ordering (Subscript[O, 1]) one can "walk", by changing the basis only slightly, to a basis for a "nearby" ordering (Subscript[O, 2])  and so on ... until one arrives at a Gröbner bases for a desired ordering (Subscript[O, k]) (Kalkbrener, Mall 1995).

↑