Continuation of file 2004-08-02-A.PartI.ppt

Gröbner Bases:
An Overview

Bruno Buchberger
RISC and RICAM,Linz,Austria

Talk at RIMS, Kyoto University
August 2,2004

Copyright Bruno Buchberger 2004

Copyright Note:  This file may be copied and stored under the following conditions:

-  the file must be kept unchanged including the copyright note
-  a mail must be send to buchberger@risc.uni-linz.ac.at
-  if material of this talk is used the talk must be cited approrpiately.

Groebner Bases: What and How?

What are Groebner Bases?

The Linear Combination of Polynomials

Consider the two bivariate polynomials

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

We assume the power products in the polynomials "lexicographically" ordered! ( y "is ranked higher than" x.)

Consider now the following linear combination of (Subscript[f, 1]) and (Subscript[f, 2]):

g = (y) (Subscript[f, 1]) +  (-x + 2) (Subscript[f, 2])

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

Observation: 
The leading power product (x^3) of g is 
     neither a multiple of the leading power product of (Subscript[f, 1])
     nor      a multiple of the leading power product of (Subscript[f, 2]).

Definition of Groebner Bases

We consider polynomials in n indeterminates over a coefficient field K. 
(We also assume a fixed "admissible", e.g. lexicographic ordering of the power products.)

A set F of polynomials is called a Groebner basis iff the above phenomenon cannot happen, i.e. iff

for all (Subscript[f, 1]),...,(Subscript[f, m])∈ F and polynomials (Subscript[h, 1]),...,(Subscript[h, m]),

          the leading power product of  (Subscript[h, 1]) (Subscript[f, 1]) +  ...   +  
        (Subscript[h, m]) (Subscript[f, m]) 
          is a multiple of the leading power product of 
               at least one of the polynomials in F.

The Set F = {(Subscript[f, 1]), (Subscript[f, 2])} of the Above Example is Not a Groebner Bases

Example of a Groebner Basis

The following set G (results from F by adding -2 (x^2) + (x^3)) is a Groebner basis:

F = {-2 (x^2) + (x^3), -2 y + x y, -(x^2) + 
          (y^2)}

For example,

(1 + 3  y) (-2 (x^2) + (x^3)) + (8  x + 
              3  x y) (-2 y + x y) + (2 - x - 
              (y^2)) (-(x^2) + (y^2)) // Expand

(1) (-2 (x^2) + (x^3)) + (8  x) (-2 y + 
              x y) + (y) (-(x^2) + (y^2)) // Expand

Why is it difficult to check whether a given F is a Groebner basis?

How can we check whether a given F is a Groebner basis?

How can we get an "equivalent" Groebner basis G for a given F (which may not be a Groebner basis)?

Why are Groebner Bases Interesting?

Why is this litte game with +, *, and x interesting?

Fact

Dozens seemingly very different "hard" problems (like algebraic equations, Hilbert function computation, diophantine equations with poly coefficients etc.) can all be reduced to the problem of constructing Groebner bases (by various "reductions"; most of them "easy", some of them "quite intelligent".)

Examples

Literature (approx. 10 textbooks, 600 papers in journals) and the examples later in this talk.

How Can We Check Groebnerianity?

The "Main Theorem" of GB Theory (BB 1965):

F is a Gröbner basis  ⟺  
      (Underscript[∀ , (Subscript[f, 1]), (Subscript[f, 2]) ∈ F])  remainder[ 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 BB, F. Winkler: GB and Applications, Cambridge Univ. Press, 1998.).
Modern version of proof: see overview paper by BB in the same book.

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

The theorem reduces an infinite check to a finite check.

The theorem, at the same time, is an algorithm!

S-Polynomials

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

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

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

The Algorithm 'remainder'

Roughly, remainder[ F, g] results from a generalized "division" of g w.r.t. to the "divisors" in F.

Example:

Consider, again,

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

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

and

g = x y - 3 x (y^2)

A division step on g w.r.t. F:

(Subscript[g, 1]) = g  + (3 x) (Subscript[f, 3])

(Subscript[g, 1]) = g  + (3 x) (Subscript[f, 3]) // Expand

A next division step w.r.t. F:

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

(Subscript[g, 2]) = (Subscript[g, 1])  + (-1) (Subscript[f, 2])  // Expand

A next division step w.r.t. F:

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

(Subscript[g, 3]) = (Subscript[g, 2])  + (3) (Subscript[f, 1])  // Expand

This is the remainder of the division of g w.r.t. F because ...

A Remainder Algorithm is Available in Mathematica:

PolynomialReduce[g, F, {y, x}]

Now We Can Check Groebnerianity

Let's again look to the above example:

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

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

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

PolynomialReduce[(Subscript[f, 2]) y  -  (Subscript[f, 3]) x, F, {y, x}]

Remark for Rewrite Experts

S-polynomials relate to remaindering like unification to pattern matching.

How Can We Construct Groebner Bases?

The Problem

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

(Ideal(F) := the set of all linear combinations  (Subscript[h, 1]) (Subscript[f, 1]) +  ...   +  
        (Subscript[h, m]) (Subscript[f, m]) 
                 
                with (Subscript[f, 1]), ..., (Subscript[f, m]) ∈ F and  (Subscript[h, 1]),...,(Subscript[h, m]) arbitrary polynomials.)

An Algorithm

Recall the main theorem:

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

Based on the main theorem, the problem can be solved by the following algorithm (BB 1965 ...)

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

      h := remainder[ F, S–polynomial[(Subscript[f, 1]), (Subscript[f, 2])]] 
      
      If h = 0, consider the next pair.
      
      If h ≠ 0, add h to G and iterate.

Correctness of the Algorithm

Easy as soon as we know the main theorem.

Termination of the Algorithm

An application of "Dickson's Lemma" (1913, BB 1970).

Specializations

The Gröbner bases algorithm,

        for linear polynomials, specializes to Gauss' algorithm, and

        for univariate polynomials, specializes to Euclid's algorithm.

Example

Let's again look at

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

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

F is not a Groebner basis.

The S-polynomial of (Subscript[f, 1]), (Subscript[f, 2]):

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

Its remainder w.r.t. F is:

-2 (x^2) + (x^3).

All the other S-polynomials have remainder 0. Hence, we arrived at a Groebner basis.

The Groebner basis algorithm is available in Mathematica (and in all other current math software systems):

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

Applications

Application: Solving Polynomial Systems

A Simple System of Equations

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

Find x, y such that

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

We compute

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

Theorem (BB, Trinks): In Groebner bases (w.r.t. lexicographic orderings), the variables are "decoupled" and each partial solution can be continued.

Solve[-2 (x^2) + (x^3) == 0, x]

{G[[2]], G[[3]]} /. {x -> 2}

Solve[-4 + (y^2) == 0, y]

All this is already implemented in the Mathematica general Solve function:

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

Theorem (BB): The number of solutions can be predicted from the form of the Groebner basis.

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

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

One can compute with these "abstract roots" like with "square roots". For example

G0 = G  /.  zsolexact1[[2]] // Simplify

G0 /. {Root[-1 - 4 #(1^2) + 17 #(1^3) - 3 #(1^4) + 45 #(1^5) - 
                60 #(1^6) + 29 #(1^7) - 124 #(1^8) + 48 #(1^9) - 64 #(1^10) + 
                64 #(1^11) &, 1] -> α}

No more details in this talk!

Alternatively, compute numerically:

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

Gsubnum = G  /.  zsol[[1]]

PolynomialGCD[Gsubnum[[2]], Gsubnum[[3]]]

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

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

Theorem (Roider, Kalkbrener et al.): It suffices to consider the poly in y with lowest degree.

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

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

Application: Invariant Theory

A Question

Can

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

be expressed as a polynomial in

F = {((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: These polynomials are 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.

Reduction to Groebner Bases Computation

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

Theorem (Sweedler, Sturmfels et al.): h can be represented in terms of I iff remainder of h w.r.t. "Groebner basis of I with slack variables" is a polynomial in the slack variables (which gives the representation).

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

((Subscript[x, 1])^6) (Subscript[x, 2]) - (Subscript[x, 1]) ((Subscript[x, 2])^6) can not be expressed by the fundamental invariants in I.

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

Application: Automated (Dis-) Proving in Geometry

The Method

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.

Each automated proof generated also contains an explanation of the method of reducing the proof problem to the problem of constructing a couple of Groebner bases.

For  more information on Theorema see

B. B., 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

What does the theorem say geometrically?

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:

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

Notebook generated automatically by the proving algorithm based on Groebner basis algorithm:

Example: 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

Example: The Correctness of Origami Constructions (jointly with T. Ida)

Example of an Origami Construction Problem: Starting from a square A, B, C, D, find a sequence of origami steps such that, finally, we arrive at an equilateral triangle.

A first solution (does not yield maximum edge length; other solution and more complicated examples see T. Ida, BB, J. Robu et al. 2003 and 2004):

Then we fix the point A and fold so that point D will lie on line EF. (This is a legal origami operation.)

Now we can do the analogous step with corner C, fixing B and bringing C onto the current position of D.

An Origami Proof Problem: Prove that, for all squares ABCD, \(TraditionalForm\`GD\&_\) = 2 \(TraditionalForm\`ED\&_\).

The Translation into a Prove Problem on Equalities:

First, note that \(TraditionalForm\`AB\&_\) = \(TraditionalForm\`BC\&_\) = \(TraditionalForm\`CD\&_\) = \(TraditionalForm\`DA\&_\), since we start from a square. Hence, whenever the length of one of these four edges occurs, we replace it by \(TraditionalForm\`AB\&_\).

Now observe that

\(DF\&_\^2 = \(AD\&_\^2 - AF\&_\^2 = \(AB\&_\^2 - \((AB\&_/2)\)\^2 = 
          3/4 \(\( AB\&_\^2\)\(.\)\)\)\)\)

and

\(GD\&_\^2 = \(GE\&_\^2 + 
          ED\&_\^2 = \(\((DC\&_/2 - GD\&_)\)\^2 + \((EF\&_ - DF\&_)\)\^2 = \((AB\&_/2 - GD\&_)\)\^2 + \(\(\((AB\&_ - DF\&_)\)\^2\)\(.\)\)\)\)\)

We want to decide whether, under these assumptions,

\(TraditionalForm\`GD\&_ = \(2  ED\&_ = \(2 \((EF\&_ - DF\&_)\) = 
          2 \(\((AB\&_ - DF\&_)\)\(.\)\)\)\)\)

For abbreviation, let's write

\(a = AB\&_, \ b = GD\&_, f = \(\(DF\&_\)\(.\)\)\)

Then, what we want to prove is that

(Underscript[∀ , a ≠ 0, f, b])({({{(f^2) = 3/4  (a^2)}, {(b^2) = (((a/2 - b))^2) + (((a - f))^2)}})}\[Implies](b = 2 (a - f)))

The Transformation to a Groebner Basis Construction Problem:

This is equivalent to

(Underscript[(¬ ∃ ), a, f, b])({({{a ≠ 0}, {(f^2) = 3/4  (a^2)}, {(b^2) = (((a/2 - b))^2) + (((a - f))^2)}, {b ≠ 2 (a - f)}})}),

which is equivalent to

(Underscript[(¬ ∃ ), a, f, b, ξ, η])({({{a η = 1}, {(f^2) = 3/4  (a^2)}, {(b^2) = (((a/2 - b))^2) + (((a - f))^2)}, {(b - 2 (a - f)) ξ = 1}})}),

This question can be decided by computing the (reduced) Gröbner basis

J = 
      GroebnerBasis[{a η - 1, (f^2) - 3/4  (a^2), 
          (b^2) - (((a/2 - b))^2) - (((a - f))^2), (b - 
                  2 (a - f)) ξ - 1}, {ξ, η, b, f, 
          a}]

and to check whether or not this Gröbner basis is equal to {1}. Since this is the case, we know that the restricted version of the theorem is true.

Application: Graph Coloring

The Problem

Find all admissible colorings in k colors of a graph with n vertices and edges E:

An admissible coloring in 3 colors of a graph with 4 vertices and edges {1,2}, {1,3}, {2,3}, {3,4}:

Not an admissible coloring in 3 colors of the same graph:

The Translation into a Groebner Bases Problem

Theorem: The possible colorings of the above graph correspond 1-1 to the common solutions of the following set of polynomials:

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

{ -1 + 
        ((Subscript[x, 1])^3),      ...  at vertex 1 color is a 3 - 
        ary root of 1
 - 1 + 
        ((Subscript[x, 2])^3),    ...  at vertex 2 color is a 3 - 
        ary root of 1
 - 1 + 
        ((Subscript[x, 3])^3), 
-1 + 
        ((Subscript[x, 4])^3), 
((Subscript[x, 1])^2) + (Subscript[x, 1]) (Subscript[x, 2]) + 
        ((Subscript[x, 2])^2),   ... the colors at 1 and 2 must be different, 
((Subscript[x, 1])^2) + (Subscript[x, 1]) (Subscript[x, 3]) + 
        ((Subscript[x, 3])^2), 
((Subscript[x, 2])^2) + (Subscript[x, 2]) (Subscript[x, 3]) + 
        ((Subscript[x, 3])^2), 
((Subscript[x, 3])^2) + (Subscript[x, 3]) (Subscript[x, 4]) + 
        ((Subscript[x, 4])^2)}

Solution by Groebner Bases

Compute a Groebner basis of this polynomial set and compute all solutions.

GB = 
      GroebnerBasis[{-1 + (Subscript[x, 1]^3), -1 + (Subscript[x, 2]^3), -1 + 
            (Subscript[x, 3]^3), -1 + (Subscript[x, 4]^3), (Subscript[x, 1]^2) + (Subscript[x, 1]) (Subscript[x, 2]) + (Subscript[x, 2]^2), 
          (Subscript[x, 1]^2) + (Subscript[x, 1]) (Subscript[x, 3]) + (Subscript[x, 3]^2), (Subscript[x, 2]^2) + (Subscript[x, 2]) (Subscript[x, 3]) + (Subscript[x, 3]^2), 
          (Subscript[x, 3]^2) + (Subscript[x, 3]) (Subscript[x, 4]) + (Subscript[x, 4]^2)}, 
{(Subscript[x, 4]), (Subscript[x, 3]), 
          (Subscript[x, 2]), (Subscript[x, 1])}]

Solve[{-1 + (Subscript[x, 1]^3) == 0, -1 + (Subscript[x, 2]^3) == 0, -1 + (Subscript[x, 3]^3) == 
          0, -1 + (Subscript[x, 4]^3) == 0, (Subscript[x, 1]^2) + (Subscript[x, 1]) (Subscript[x, 2]) + (Subscript[x, 2]^2) == 0, 
        (Subscript[x, 1]^2) + (Subscript[x, 1]) (Subscript[x, 3]) + (Subscript[x, 3]^2) == 0, 
        (Subscript[x, 2]^2) + (Subscript[x, 2]) (Subscript[x, 3]) + (Subscript[x, 3]^2) == 0, 
        (Subscript[x, 3]^2) + (Subscript[x, 3]) (Subscript[x, 4]) + (Subscript[x, 4]^2) == 0}, 
{(Subscript[x, 4]), (Subscript[x, 3]), 
        (Subscript[x, 2]), (Subscript[x, 1])}]

Slightly re-organized output:

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

For example, {(Subscript[x, 1]) -> 1, (Subscript[x, 2]) -> -(((-1))^(1/3)), 
        (Subscript[x, 3]) -> -1 + (((-1))^(1/3)), 
        (Subscript[x, 4]) -> -(((-1))^(1/3))}corresponds to

Discussion

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 (e.g. graph colorings) 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 theorems 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.

He gave me the problem of finding "the uncovered points if the black points are given".

In my thesis (1965) and journal publication  (1970) 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".

More Info on Gröbner Bases?

Gröbner Bases 98 Conference

B. B., 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. B. Introduction to Gröbner Bases, pp. 3-31.

B. B. 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: RISA-ASIR (M. Noro, K. Yokoyama), 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, approx. 10, 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.

....

M. Maruyama. Gröbner Bases and Applications. 2002.

M. Noro, K. Yokoyama. Computational Fundamentals of Gröbner Bases.
University of Tokyo Press, 2003.

On 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.

ACA 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).

Use arbitrary linear algebra algorithms for the reduction (remaindering) process: (Faugère 1997).

... numerours applications,

Conclusions

Research topics:

the inner structure of Groebner bases: generalized Sylvester matrices

the numerics of GB computations

axiomatic characterization of Groebner rings

generalizations (e.g. non-commutative poly-rings)

speeding up the computation

Groebner bases for particular classes of ideals (avoid computation)

the study of admissible orderings

applications (problem reductions, e.g. functional analysis, BV problems, Rosenkranz 2003)