Gröbner basis

A Gröbner basis is a particular generating set of a polynomial ideal, chosen so that the ideal becomes computable^[1]^[2]. For polynomials in one variable, the Euclidean algorithm reduces any ideal to a single generator, and divisibility by it decides membership. In several variables, ideals need several generators, and dividing by an arbitrary set of them gives remainders that depend on the order of division and need not be zero for members of the ideal. A Gröbner basis, defined relative to a monomial order, repairs this: its leading terms generate the leading terms of every polynomial in the ideal, and as a consequence every polynomial has a unique remainder on division by it, the normal form, which is zero exactly for members. Bruno Buchberger defined Gröbner bases, named them after his advisor Wolfgang Gröbner, and gave an algorithm to compute them in his thesis of 1965^[1]. They underlie the polynomial system solving of every computer algebra system.

§ 01

Definition

Fix a monomial order and let $I$ be an ideal in $k [x_{1}, \dots, x_{n}]$ . A finite set $G \subseteq I$ is a Gröbner basis of $I$ if

⟨ LT (g) : g \in G ⟩ = ⟨ LT (f) : f \in I ⟩

that is, the leading term of every element of $I$ is divisible by the leading term of some element of $G$ . Then division by $G$ in any order gives the same remainder, and $f \in I$ if and only if that remainder is zero^[2]. Every ideal has a Gröbner basis, by Hilbert's basis theorem applied to the ideal of leading terms^[9], and a unique reduced one, in which every element is monic and no term of any element is divisible by the leading term of another.

§ 02

Buchberger's algorithm

For polynomials $f$ and $g$ with leading monomials whose least common multiple is $L$ , the S-polynomial

S (f, g) = \frac{L}{LT ( f )} f - \frac{L}{LT ( g )} g

cancels both leading terms. Buchberger's criterion states that $G$ is a Gröbner basis if and only if every $S (g_{i}, g_{j})$ has remainder zero on division by $G$ ^[1]^[10]. The algorithm follows: compute the remainders of all S-polynomials, add the nonzero ones to the basis, and repeat for the new pairs. It terminates because each added remainder enlarges the ideal of leading terms, and ascending chains of monomial ideals are finite.

Division, S-polynomials, and Buchberger's algorithm with the criterion that skips pairs with coprime leading monomials.

(* The S-polynomial cancels the leading terms of f and g. *)
let spoly ord f g =
  let l = lcm (lm f) (lm g) in
  sub ord (mul_term ord (mono_div l (lm f), Q.div Q.one (lc f)) f)
          (mul_term ord (mono_div l (lm g), Q.div Q.one (lc g)) g)
 
let pairs_considered = ref 0
 
(* Buchberger's algorithm. With criterion = true, pairs whose leading
   monomials are coprime are skipped (Buchberger's first criterion). *)
let buchberger ?(criterion = true) ?(trace = fun _ _ _ _ -> ()) ord (fs : poly list) =
  let basis = ref (List.filter (( <> ) []) fs) in
  let pairs = ref [] in
  List.iteri (fun i _ -> for j = 0 to i - 1 do pairs := (j, i) :: !pairs done) !basis;
  pairs := List.rev !pairs;
  while !pairs <> [] do
    let (i, j) = List.hd !pairs in
    pairs := List.tl !pairs;
    let f = List.nth !basis i and g = List.nth !basis j in
    let coprime = Array.for_all2 (fun a b -> a = 0 || b = 0) (lm f) (lm g) in
    if not (criterion && coprime) then begin
      incr pairs_considered;
      let r = remainder ord (spoly ord f g) !basis in
      trace i j (spoly ord f g) r;
      if r <> [] then begin
        let n = List.length !basis in
        basis := !basis @ [ r ];
        pairs := !pairs @ List.init n (fun k -> (k, n))
      end
    end
  done;
  !basis

A trace on the example of Cox, Little and O'Shea, in graded lexicographic order.

open Mpoly

Running it.

S(f1, f2) = -x^2  reduces to  -x^2  (added)
S(f1, f3) = -2xy  reduces to  -2xy  (added)
S(f2, f3) = -2y^2 + x  reduces to  -2y^2 + x  (added)
S(f1, f4) = -2xy^2  reduces to  0
S(f2, f4) = -2y^2 + x  reduces to  0
S(f3, f4) = 0  reduces to  0
S(f2, f5) = 1/2x^3 - 2y^3 + xy  reduces to  0
S(f4, f5) = 1/2x^2  reduces to  0
basis: x^3 - 2xy, x^2y - 2y^2 + x, -x^2, -2xy, -2y^2 + x
reduced: x^2, xy, y^2 - 1/2x

The ideal of leading terms of the example, generated by x², xy and y², covers every monomial except 1, x and y. These standard monomials form a basis of the quotient ring, which therefore has dimension 3: the system's only solution, (0, 0), has multiplicity 3.

§ 03

Applications

Ideal membership

A polynomial is in the ideal exactly when its remainder by a Gröbner basis is zero. Remainders are canonical representatives of the classes modulo the ideal, so equality in the quotient ring becomes equality of normal forms; see canonical form.

Solving systems

For lexicographic order with $x_{1} > \dots > x_{n}$ , the elimination theorem says that $G \cap k [x_{i}, \dots, x_{n}]$ is a Gröbner basis of the ideal's intersection with that subring^[2]. A lex basis of a system with finitely many solutions is therefore triangular: one polynomial in $x_{n}$ alone, then polynomials that introduce the other variables one at a time, and the system can be solved by back substitution.

Solving a system of a sphere, a paraboloid and a plane with a lexicographic basis, and testing membership.

open Mpoly
 
(* x^2 + y^2 + z^2 = 1, x^2 + z^2 = y, x = z: a lexicographic Gröbner
   basis is triangular, ending in a polynomial in z alone. *)

Running it.

  x - z
  y - 2z^2
  z^4 + 1/2z^2 - 1/4
y^2 + 2z^2 - 1 in the ideal: true
y - 1 in the ideal: false

The last polynomial, $z^{4} + \frac{1}{2} z^{2} - \frac{1}{4}$ , gives four values of $z$ ; the others determine $y = 2 z^{2}$ and $x = z$ . The number of standard monomials counts the solutions, with multiplicity, for any order. Gröbner bases are also used to find implicit equations of parametrized curves and surfaces, to prove geometric theorems, to analyze robot kinematics, and in algebraic cryptanalysis: Faugère and Joux broke the first HFE cryptographic challenge in 2002 by computing a Gröbner basis^[7].

§ 04

Complexity and faster algorithms

In the worst case Gröbner bases are expensive: Mayr and Meyer showed that ideal membership requires exponential space, and the degrees in a basis can be doubly exponential in the number of variables^[3]. In practice the cost depends heavily on the order and the strategy. Most S-polynomials reduce to zero and are wasted work; Buchberger's criteria and the refinements of Gebauer and Möller detect many of them in advance^[4].

Pairs reduced with and without Buchberger's first criterion.

open Mpoly
 
(* S-polynomials reduced, with and without skipping pairs whose leading
   monomials are coprime. The reduced bases are the same either way. *)

Running it.

system              order    pairs reduced (with criterion / without)
three quadrics      grevlex       9 / 15
three quadrics      lex          43 / 78
twisted cubic       grevlex       4 / 6
twisted cubic       lex           7 / 10
cubic system        grevlex       0 / 3
cubic system        lex         111 / 136

Faugère's F4 algorithm reduces many S-polynomials at once as rows of a sparse matrix, and F5 uses signatures to avoid reductions to zero almost entirely^[5]^[6]. These algorithms, in systems such as Magma, Singular and Maple, handle problems far beyond Buchberger's original algorithm.

§ 05

History

Hilbert's basis theorem of 1890 showed that every polynomial ideal is finitely generated^[9]. Buchberger, working under Wolfgang Gröbner at Innsbruck, gave in his 1965 thesis the definition, the criterion and the algorithm, in order to compute in quotient rings of zero-dimensional ideals^[1]; he popularized the name Gröbner basis in the 1970s^[10]. Hironaka had introduced the analogous standard bases for power series in 1964 in his work on resolution of singularities^[8]. Implementations spread in the 1980s^[4], the complexity results of Mayr and Meyer appeared in 1982^[3], and Faugère's F4 and F5 of 1999 and 2002 made large computations practical^[5]^[6]. Textbooks by Becker and Weispfenning^[11] and by Cox, Little and O'Shea^[2] made the theory standard.