Gröbner Bases:
Theory and Applications

Bruno Buchberger
Research Institute for Symbolic Computation
Johannes Kepler University, Linz, Austria 

Talk at 
Sultan Qaboos University 
 Department of Mathematics and Statistics
Sultanate of Oman

January 25, 2004

Copyright Bruno Buchberger 2004.

Copyright Note: This file can be printed, stored and distributed under the following conditions:

- the file is kept unchanged
- this copyright note is included
- a note is sent to Bruno.Buchberger@JKU.at

Please cite this talk if you use the material.

Goal of the Talk

The Gröbner bases method (BB 1965 etc.) is available in all current mathematical software systems.

E.g. "Solve" in Mathematica: Gröbner Bases are behind.

A general method that solves many problems related to sets of multivariate polynomials.

In this talk: How does the method work? How can it be applied?

Not in this talk: Why does the method work?

Application Areas

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

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

Example Commutative Algebra

See survey paper by B.Buchberger in the 1998 book.

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

...

What are Gröbner Bases?

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 and we say "g reduces in one step modulo F to h".

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.

We write

\(h\+_\_F\)

if h cannot be reduced further (is "in reduced form") 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 (Reduction is Algorithmic): There is an algorithm RF that produces a reduced form w.r.t. F for any given polynomial f:

\(TraditionalForm\`f\ \ \(\(⟶\_F\)\^*\)\ \ \ \(RF(F, f)\)\+_\_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\ \ )\)\(.\)\)\)

The "Application Theory of Gröbner Bases"

Fact: Gröbner bases have many "nice properties" and hence, for Gröbner bases, many problems, which are "difficult" for arbitrary polynomial sets, can be solved by "easy" algorithms.

Let F⊆K[(Subscript[x, 1]), …, (Subscript[x, n])]:

Example (The "Main Problem of Polynomial Ideal Theory"):

 If F is a Gröbner basis:             \(TraditionalForm\`f ∈ \(\(Ideal(
              F)\)\ \ \ \ \ \ \ ⟺\ \ \ \ \ \ \ f\)\(⟶\^*\)\_F\ 0\).

Example (The "Elimination Problem"):   For lexical ordering and i≤n,

 if F is a Gröbner basis:             Ideal(F) ⋂ K[(Subscript[x, 1]), …, (Subscript[x, i])]  =  Ideal( F ⋂ K[(Subscript[x, 1]), …, (Subscript[x, i])])

Example (The "Poly Diophantine Equations Problem"):   

If F = {(Subscript[f, 1]),  ... ,  (Subscript[f, m])} is a Gröbner basis:  the infinite module of all solutions of

(Subscript[f, 1]) . (Subscript[h, 1]) ... ,  (Subscript[f, m]) . (Subscript[h, m]) = 0

can be generated by the finitely many "S-polynomials" of F.

Example (The "Hilbert Function Problem"):  

If F is a Gröbner basis:              H(F,d) = number of power products of degree ≤ d 
                                                             that are not multiples of "leading power products" in F.

How Can Gröbner Bases 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 (Buchberger 1965 ...)

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 essence 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 the Construction 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" (Buchberger 1965, ...)

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:
B. Buchberger, PhD thesis 1965, published in aequationes mathematicae 1970, (English translation in the appendix of B. Buchberger, F. Winkler: GB and Applications, Cambridge Univ. Press, 1998).

Proof idea: The least common multiple of the "leading power products" of (Subscript[f, 1])and (Subscript[f, 2]) is "the first possible polynomial" that allows two essentially different reductions.

Given a finite F, if you "master" the finitely many S-polys, then, inductively, you master the infinitely many polynomials that allow two or more essentially different reductions.

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

Examples of Using Gröbner Bases

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}]

??  GroebnerBasis

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

??  MonomialOrder

This is the (uniquely determined reduced) Groebner basis w.r.t.  degree-lexicographic ordering with x ≺ y (first order by total degree and then lexicographically):

GroebnerBasis[F, {x, y}, 
      MonomialOrder -> DegreeLexicographic]

(Computation of GB w.r.t. degreelexicographic ordering, most times, is faster but the result does not have the "elimination property").

Solution of Systems Using Groebner Bases

G

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

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

{G[[2]], G[[3]]}

(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

Solve[G[[1]] == 
0, z]

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]]

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]]

R[[2]] /. {(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

((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])}

Automated Prover / Disprover for Geometric Propositions

Using the Gröbner bases algorithms an infinite class of interesting geometrical statements can be proved or disproved automatically. The following proofs (including the English explanatory texts) are produced automatically by the Theorema system, in which the Gröbner bases method is one of the automated proving methods. For  more information on Theorema see

B. Buchberger, C. Dupre, T. Jebelean, F. Kriftner, K. Nakagawa, D. Vasaru, W. Windsteiger.
The Theorema Project: A Progress Report.
In: Symbolic Computation and Automated Reasoning (Proceedings of CALCULEMUS 2000, Symposium on the Integration of Symbolic Computation and Mechanized Reasoning, August 6-7, 2000, St. Andrews, Scotland), M. Kerber and M. Kohlhase (eds.), A.K. Peters, Natick, Massachusetts, ISBN 1-56881-145-4, pp. 98-113.

Example Pappus' Theorem

Textbook formulation:

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.

Input to the system:

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]]

Input to the system:

Simplify[Proposition["Pappus"], by -> GraphicSimplifier]

Output generated automatically by the system

End of output

Input to the system:

KnowledgeBase["Pappus_g", 
      any[A, B, A1, B1, C, 
        C1], {{A, {10, 120}}, {B, {100, 150}}, {A1, {25, 
            60}}, {B1,  {120, 50}}, {C, {260, 
            200}}, {C1, {250, 45}}}]

Input to the system:

Simplify[Proposition["Pappus"], by -> GraphicSimplifier, 
      using -> KnowledgeBase["Pappus_g"]]

Output generated automatically by the system

End of output

Input to the system:

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

Inserted notebook generated automatically by the system

End of inserted notebook

The Butterfly Theorem

Textbook formulation:

A, B, C and D are four points on circle (O). E is the intersection of AC and BD. Through E draw a line perpendicular to OE, meeting AD at F and BC at G. Show that (OverBar[FE]) = (OverBar[GE]).

Remark:

Using the default coordinate system the algebraic methods are very slow.

Input to the system:

Proposition["Butterfly", any[O, A, B, C, D, EE, F, G], 
      point[O, A] ∧ 
pon[C, 
            circle[O, A]] ∧ 
pon[B, 
            circle[O, A]] ∧ 
pon[D, 
            circle[O, A]] ∧ 
inter[EE, line[A, C], 
            line[B, D]] ∧ inter[F, line[D, A], tline[EE, EE, O]] ∧ 
          inter[G, line[B, C], line[EE, F]]
 \[Implies] 
        distequal[EE, F, G, EE]]

Input to the system:

Simplify[Proposition["Butterfly"], 
      by -> GraphicSimplifier]

Output generated automatically by the system

End of output

Input to the system:

KnowledgeBase["Butterfly_g", 
      any[O, A, B, C, 
        D], {{ O, {100, 100}}, {A, {0, 100}}, {B, {55, 
            190}}, {C, {171, 170}}, {D, {60, 10}}}]

Input to the system:

Simplify[Proposition["Butterfly"], by -> GraphicSimplifier, 
      using -> KnowledgeBase["Butterfly_g"]]

Output generated automatically by the system

End of output

Input to the system:

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

Inserted notebook generated automatically by the system

End of inserted notebook

How Difficult is the Construction of Gröbner Bases?

Very Easy

The structure of the algorithm is easy. The operations needed in the algorithm are elementary. "Every high-school student can execute the algorithm." (See palm-top TI-98.)

Very Difficult

The inherent complexity of the problems that can be solved by the GB method is "exponential". Hence, the worst-case complexity of the GB algorithm must be high.

Sometimes Easy

Mathematically interesting examples often have a lot of "structure" and, in concrete examples, GB computations can be reasonably, even surprisingly, fast.

Enormous Potential for Improvement

More mathematical knowledge can lead to drastic speed-up:

The use of "criteria" for eliminating the consideration of certain S-polynomials.

p-adic approaches and floating point approaches.

The "Gröbner Walk" approach.

The "linear algebra" approach. (Generalized Sylvester matrices.)

Practically, tuning of the algorithm is also important:

Heuristics, strategies for choosing orderings, selecting S-polynomials etc.

Good implementation techniques.

A huge literature.

Why "Gröbner" Bases?

Professor  Wolfgang Gröbner (1899-1980) was my PhD thesis supervisor.

In my thesis (1965) and journal publication  (1970), reprinted in the B. Buchberger, F. Winkler, 1998, 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, for honoring Gröbner, 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".

Meanwhile: approx. 600 papers on Gröbner bases, 10 textbooks, 3000 citations.

More Info on Gröbner Bases?

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 600 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, Nam 2000).