Dependencies

Input: \(F = \{ f_1, \cdots , f_s \} \) (a generating set of polynomials of an ideal)

Output: \(G\) (a Gröbner basis of the ideal, containing \(F\))

• \(G := F\)

• \(t := s\)

• \(B := \{ \{ i, j\} \mid 1 \le i {\lt} j \le s\} \)

• while \(B \ne \emptyset \):

  • \(B' := \textrm{a nonempty subset of } B\)

  • \(B := B \, \backslash \, B'\)

  • \(L := \left\{ \frac{\mathrm{lcm}(\mathrm{LM}(f_i), \mathrm{LM}(f_j))}{\mathrm{LT}(f_i)} f_i \mid \{ i, j\} \in B' \right\} \)

  • \(H := SymbolicPreprocessing(L, G)\)

  • \(M := (\mathrm{coeff}(h_k, x^{\alpha _\ell }))_{k, \ell }\)
    (the matrix of coefficients of H; \(x^{\alpha _\ell }\) sorted under monomial order)

  • \(N := \textrm{row reduced echelon form of } M\)

  • \(N^+ := \{ n \in \mathrm{rows}(N) \mid \mathrm{LM}(n) \notin \left\langle \mathrm{LM}(\mathrm{rows}(N)) \right\rangle \} \)

  • for \(n \in N^+\):

    • \(t := t + 1\)

    • \(f_t := \textrm{the polynomial form of } n\)

    • \(G := G \cup \{ f_t\} \)

    • \(B := B \cup \{ \{ i, t\} \mid 1 \le i {\lt} t\} \)

  return \(G\)

The output \(G'\) of Faugère’s F4 algorithm is a Gröbner basis of the ideal generated by the input polynomial set \(G\). In particular, the output satisfies the refined Buchberger criterion; i.e. every S-polynomial within \(G'\) reduces to zero over \(G'\).

A finite subset \(G = \{ g_1, \cdots , g_t \} \ne \{ 0 \} \) of \(I \trianglelefteq k[x_1, \cdots , x_n]\) is said to be a Gröbner basis of \(I\) if

The leading monomial \(\mathrm{LM}(f)\) of \(f\) is the monomial in \(f\) maximum under the fixed monomial order. The leading coefficient \(\mathrm{LC}(f)\) of \(f\) is the coefficient of \(\mathrm{LM}(f)\) in \(f\). The leading term of \(f\) is then simply the \(\mathrm{LC}(f)\)-multiple of \(\mathrm{LM}(f)\).

An ideal \(I \trianglelefteq k[x_1, \cdots , x_n]\) is a monomial ideal if there exists a subset of exponents \(A \subseteq \mathbb {Z}_{\ge 0}^n\) such that

A monomial order on \(k[x_1, \cdots , x_n]\) is a total order \({\lt}\) on \(\mathbb {Z}_{\ge 0}^n\) satisfying:

1. if \(\alpha {\lt} \beta \), then \(\alpha + \gamma {\lt} \beta + \gamma \) for any \(\gamma \in \mathbb {Z}_{\ge 0}^n\);

2. \({\lt}\) is a well-ordering.

The monomial set of a polynomial \(f\) is the set of monomials with nonzero coefficient in \(f\), and is denoted by \(\mathrm{Mon}(f)\). For \(K \subseteq k[x_1, \cdots , x_n]\), we define as

Input: divisor set \(\{ f_1, \cdots , f_s\} \) and dividend \(f\)

Output: quotients \(q_1, \cdots , q_s\) and remainder \(r\)

• \(\forall \, i,\, q_i := 0;\, r := 0\)

• \(p := f\)

• while \(p \ne 0\):

  • \(i := 1\)

  • \(DivisionOccured := False\)

  • while \(i \le s\) and not \(DivisionOccured\):

    • if \(\mathrm{LT}(f_i) \mid \mathrm{LT}(p)\):

      • \(q_i := q_i + \mathrm{LT}(p) / \mathrm{LT}(f_i)\)

      • \(p := p - (\mathrm{LT}(p) / \mathrm{LT}(f_i))f_i\)

    • else:

      • \(i := i + 1\)

  • if not \(DivisionOccured\):

    • \(r := r + \mathrm{LT}(p)\)

    • \(p := p - \mathrm{LT}(p)\)

  return \(q_1, \cdots , q_s, r\)

Define the least common multiple \(\gamma = \mathrm{lcm}(\alpha , \beta )\) of two monomials \(\alpha , \beta \) as \(\gamma _i = \max (\alpha _i, \beta _i)\). The S-polynomial of two polynomials \(f\) and \(g\), given a monomial order, is

We say each part of above, i.e.

the S-pair of \(f\) and \(g\).

For \(G = \{ g_1, \cdots , g_t\} \subseteq k[x_1, \cdots , x_n]\) and \(f \in k[x_1, \cdots , x_n]\), a standard representation of \(f\) by \(G\) is, if exists, an equality

where \(A_k g_k = 0\) or \(\mathrm{LM}(f) \ge \mathrm{LM}(A_k g_k)\) for every \(1 \le k \le t\). If such a standard representation exists, we say \(f\) reduces to zero modulo \(G\) and notate it as

Input: \(L\), \(G = \{ f_1, \cdots , f_t \} \) (two finite sets of polynomials)

Output: \(H\) (a finite set of polynomial containing \(L\))

• \(H := L\)

• \(done := \mathrm{LM}(H)\)

• while \(done \ne \mathrm{Mon}(H)\):

  • \(x^\beta := \max _{{\lt}} (\mathrm{Mon}(H) \, \backslash \, done)\)

  • \(done := done \cup \{ x^\beta \} \)

  • if \(\exists g \in G\) such that \(\mathrm{LM}(g) \mid x^\beta \):

    • \(g :=\) one such choice of \(g\)

    • \(H := H \cup \left\{ \frac{x^\beta }{\mathrm{LM}(g)} g \right\} \)

  return \(H\)

The algorithm above with input \(L\) and \(G\) terminates and obtains as an output a set of polynomials \(H\) satisfying the following two properties:

1. \(L \subseteq H\), and

2. whenever \(x^\beta \) is a monomial in some \(f \in H\), and for some \(g \in G\) its leading monomial \(\mathrm{LM}(g)\) divides \(x^\beta \), then \(\frac{x^\beta }{\mathrm{LM}(g)} g \in H\).

Let \(I \trianglelefteq k[x_1, \cdots , x_n]\). Then a basis \(G = \{ g_1, \cdots , g_t\} \) is a Gröbner basis of \(I\) iff the remainder of each \(S(g_i, g_j)\)(\(i \ne j\)) in long division by \(G\) is zero.

Let \(I \trianglelefteq k[x_1, \cdots , x_n]\). Then a basis \(G = \{ g_1, \cdots , g_t\} \) is a Gröbner basis of \(I\) iff \(S(g_i, g_j) \to _G 0\) for each pair of \(i \ne j\).