Gröbner Basis

It is almost impossible for me to read contemporary mathematicians who, instead of saying “Petya washed his hands,” write simply: “There is a \(t_1 < 0\) such that the image of \(t_1\) under the natural mapping \(t_1 \mapsto \mathit{Petya}(t_1)\) belongs to the set of dirty hands, and a \(t_2, t_1 < t_2 \le 0\), such that the image of \(t_2\) under the above-mentioned mapping belongs to the complement of the set defined in the preceding sentence.” — Vladimir Igorevich Arnol’d (Zdravkovska and Arnol’d 1987, 30)

Gröbner bases can be used for solving systems of polynomial equations. A system of multivariate equations can be seen as an ideal basis and a Gröbner basis is a particular basis that yields the same affine variety but has a structure amenable to elimination of variables.

Theorem n4. (Hilbert Basis Theorem.) For every ideal \(I \subseteq \mathbb{F}[\mathbf{x}]\), there exist \(g_1, \ldots, g_m \in I\) such that \(I = \langle g_1, \ldots, g_m \rangle\)(Cox 2015).

Definition n5. Let \(I \subseteq \mathbb{F}[\mathbf{x}]\) be an ideal different from \(\{0\}\). We denote by \(\mathrm{LT}(I) = \{\mathrm{LT}(f) \mid f \in I\}\) the set of leading terms of nonzero elements of \(I\). The ideal of leading terms of \(I\), generated by \(\mathrm{LT}(I)\), is denoted \(\langle \mathrm{LT}(I) \rangle\).

Definition nh. Fix a monomial order on \(\mathcal{M}\). A finite basis \(G \subseteq I\) of a nonzero ideal \(I \subseteq \mathbb{F}[\mathbf{x}]\) is a Gröbner basis if \[\langle \mathrm{LT}(G) \rangle = \langle \mathrm{LT}(I) \rangle.\]

A set \(\{g_1, \ldots, g_m\} \subseteq I\) is a Gröbner basis if and only if the leading term of any element of \(I\) is divisible by some \(\mathrm{LT}(g_i)\).

Proposition n7. Fix a monomial order on \(\mathcal{M}\). Then every ideal \(I \subseteq \mathbb{F}[\mathbf{x}]\) has a Gröbner basis (Cox 2015).

Definition n6. Let \(G \subseteq I\) be a Gröbner basis of \(I\). We call \(G\) a reduced Gröbner basis if for all \(g \in G\):

  1. \(\mathrm{LC}(g) = 1\).
  2. No monomial of \(g\) is in \(\langle \mathrm{LT}(G \setminus \{g\}) \rangle\).

Most computer algebra systems compute reduced Gröbner bases by default. Any ideal has a unique reduced Gröbner basis. Given \(g \in G\), let \(g’ = \overline{g}^{G \setminus \{g\}}\) and \(G’ = (G \setminus \{g\}) \cup \{g’\}\). If we keep applying this process until all elements are fully reduced, we obtain the reduced Gröbner basis.

Definition n9. Let \(I = \langle f_1, \ldots, f_m \rangle \subseteq \mathbb{F}[x_1, \ldots, x_n]\) be an ideal. The \(l\)-th elimination ideal \(I_l\) is the ideal of \(\mathbb{F}[x_{l+1}, \ldots, x_n]\) given by \(I_l = I \cap \mathbb{F}[x_{l+1}, \ldots, x_n]\).

Theorem dy. (Elimination Theorem.) Let \(G \subseteq I \subseteq \mathbb{F}[x_1, \ldots, x_n]\) be a Gröbner basis of \(I\) under the lexicographic order \(x_1 \succeq_{\mathrm{lex}} x_2 \succeq_{\mathrm{lex}} \cdots \succeq_{\mathrm{lex}} x_n\). Then, for every \(0 \le l < n\), the set \(G_l = G \cap \mathbb{F}[x_{l+1}, \ldots, x_n]\) is a Gröbner basis of the \(l\)-th elimination ideal \(I_l\).

Proof. We know that \(G_l \subseteq I_l\) by construction, so we only need to show that \(\langle \mathrm{LT}(I_l) \rangle = \langle \mathrm{LT}(G_l) \rangle\) for a fixed \(l\) between \(0\) and \(n\). The inclusion \(\langle \mathrm{LT}(I_l) \rangle \supseteq \langle \mathrm{LT}(G_l) \rangle\) is evident. To prove \(\langle \mathrm{LT}(I_l) \rangle \subseteq \langle \mathrm{LT}(G_l) \rangle\), we need to show that \(\mathrm{LT}(g) \mid \mathrm{LT}(f)\) for an arbitrary \(f \in I_l\) and some \(g \in G_l\). We know that \(f\) is also in \(I\), so \(\mathrm{LT}(g) \mid \mathrm{LT}(f)\) for some \(g \in G\) since \(G\) is a Gröbner basis of \(I\). Since \(f \in I_l\), \(\mathrm{LT}(g)\) must consist only of \(x_{l+1}, \ldots, x_n\). The crucial observation is: since \(x_1 \succeq_{\mathrm{lex}} \cdots \succeq_{\mathrm{lex}} x_n\), any monomial involving any \(x_1, \ldots, x_l\) is greater than all monomials in \(\mathbb{F}[x_{l+1}, \ldots, x_n]\). Therefore \(g \in G_l\).

Example db. Consider a system of equations where \(f_1 = f_2 = f_3 = 0\) are polynomials in \(\mathbb{R}[x, y, z]\) with \[f_1 = -16x^2 - 4xy^2 + 4xz, \quad f_2 = 4x^2 z + 2xy^2 z + z, \quad f_3 = xy^2 + 2y^2 z + 1.\] Computing the reduced Gröbner basis with \(z \succeq_{\mathrm{lex}} y \succeq_{\mathrm{lex}} x\) gives \[g_1 = x + \tfrac{1}{4}y^2 - \tfrac{1}{4}z, \quad g_2 = y^4 - z^2 - 4, \quad g_3 = y^2 z - \tfrac{1}{9}z^2, \quad g_4 = z^3 + \tfrac{81}{20}z.\] The last polynomial involves only \(z\) and has the only real solution \(z = 0\). Substituting into \(g_3\) and \(g_2\) yields \(y = \pm\sqrt{2}\), and then \(x = -\frac{1}{2}\). The reduced Gröbner basis allows solving the system by successive elimination of variables.

Definition dn. Let \(\mathbb{F}_q[x_1, \ldots, x_n]\) be a polynomial ring over the finite field \(\mathbb{F}_q\) with order \(q = p^m\) where \(p\) is prime and \(m \in \mathbb{N}_{>0}\). The field equations of \(\mathbb{F}_q\) are the polynomials \(x_i^q - x_i\) for every \(x_i \in \{x_1, \ldots, x_n\}\).

Adding the field equations into a polynomial system over \(\mathbb{F}_q\) restricts the solutions to \(\mathbb{F}_q\) and ensures the system has finitely many solutions.

Theorem dd. (Finiteness Theorem.) Let \(f_1, \ldots, f_m \in \mathbb{F}[x_1, \ldots, x_n]\) be polynomials. If \(\langle f_1, \ldots, f_m \rangle \cap \mathbb{F}[x_i] \neq 0\) for all \(x_i\), then the variety \(V(\langle f_1, \ldots, f_m \rangle) \subseteq \mathbb{F}^n\) is finite (Cox 2015).

Theorem dr. (Hilbert’s Weak Nullstellensatz.) Let \(f_1, \ldots, f_m \in \mathbb{F}[\mathbf{x}]\) be polynomials. Then the following are equivalent:

  1. There exists an extension field \(\mathbb{E}\) of \(\mathbb{F}\) and \(\mathbf{a} \in \mathbb{E}^n\) such that \(f_i(\mathbf{a}) = 0\) for all \(f_i\).
  2. \(1 \notin \langle f_1, \ldots, f_m \rangle\) (Becker 1993).

Whenever \(1\) belongs to an ideal \(I\), we have \(I = \mathbb{F}[\mathbf{x}]\), as shown in the proof of Proposition p. Therefore, if the reduced Gröbner basis consists of the single element \(1\), the polynomial system has no solutions.

It can be shown that if we have a finite field \(\mathbb{F}\) and its extension \(\mathbb{E}\), all elements from \(\mathbb{F}\) satisfy the field equations of \(\mathbb{F}\) and no element in \(\mathbb{E} \setminus \mathbb{F}\) satisfies any of them. Therefore, adding the field equations into a polynomial system restricts solutions to \(\mathbb{F}\).

Example di. Consider a system of equations where \(f_1 = f_2 = f_3 = 0\) are polynomials in \(\mathrm{GF}(2)\) with \[f_1 = x + y + z, \quad f_2 = xy + xz + yz, \quad f_3 = xyz + 1.\] Computing the reduced Gröbner basis with \(z \succeq_{\mathrm{lex}} y \succeq_{\mathrm{lex}} x\) gives \[g_1 = x + y + z, \quad g_2 = y^2 + yz + z^2, \quad g_3 = z^3 + 1.\] The only solution to the last polynomial is \(z = 1\). Substituting into \(g_2\) gives \(g_2’ = y^2 + y + 1\), which has no solution in \(\mathrm{GF}(2)\), so the system has no solution in \(\mathrm{GF}(2)\). Note that \(g_2’\) is also irreducible over \(\mathrm{GF}(2)\). By Proposition na, let \(\alpha\) be a root of \(g_2’\), i.e., the coset \(y + \langle g_2’ \rangle\)in \(\mathbb{E} = \mathrm{GF}(2)[y] / \langle g_2’ \rangle\). We get the finite field \(\mathrm{GF}(2)(\alpha) \cong \mathrm{GF}(2^2)\) with elements \(0, 1, \alpha, \alpha + 1\). The polynomial \(g_2\) has two solutions in \(\mathrm{GF}(2^2)\), namely \(y = \alpha\)and \(y = \alpha + 1\), and these lead to further solutions of the original system.

Example ds. Considering Example di, if we add the field equations of \(\mathrm{GF}(2)\) into the system, the reduced Gröbner basis is \(g_1 = 1\). By the Hilbert’s Weak Nullstellensatz, the system has no solutions in \(\mathrm{GF}(2)\).

Computing Gröbner Bases

Definition df. Let \(f, g \neq 0 \in \mathbb{F}[\mathbf{x}]\) be polynomials. If \(\mathrm{multideg}(f) = \alpha\)and \(\mathrm{multideg}(g) = \beta\), let \(\gamma = (\gamma_1, \ldots, \gamma_n)\) where \(\gamma_i = \max(\alpha_i, \beta_i)\) for each \(i\). We call \(x^\gamma\)the least common multiple of \(\mathrm{LM}(f)\) and \(\mathrm{LM}(g)\), written \(x^\gamma = \mathrm{lcm}(\mathrm{LM}(f), \mathrm{LM}(g))\). The S-polynomial of \(f\) and \(g\) is \[S(f, g) = \frac{x^\gamma}{\mathrm{LT}(f)} \cdot f - \frac{x^\gamma}{\mathrm{LT}(g)} \cdot g.\]

Example dg. Let \(f = x^2 y^3 + x\) and \(g = 2xy^5 + y\) be polynomials in \(\mathbb{R}[x, y]\) under \(\succeq_{\mathrm{grlex}}\). The least common multiple is \(x^2 y^5\) and \[S(f, g) = \frac{x^2 y^5}{x^2 y^3}(x^2 y^3 + x) - \frac{x^2 y^5}{2xy^5}(2xy^5 + y) = xy^2 - \tfrac{1}{2}xy.\] The S-polynomial is designed so that the leading terms cancel.

Theorem d8. (Buchberger’s Criterion.) A basis \(G = \{g_1, \ldots, g_m\}\) of an ideal \(I\) is a Gröbner basis if and only if \(\overline{S(g_i, g_j)}^G = 0\) for all \(i \neq j\) (Buchberger 2006).

Buchberger’s Criterion, introduced in (Buchberger 2006), allows testing whether a given basis is a Gröbner basis and naturally leads to an algorithm that constructs a Gröbner basis by adding nonzero remainders \(\overline{S(g_i, g_j)}^G\) to \(G\) until the criterion holds.

Definition de. Let \(\succeq\) be a monomial order on \(\mathcal{M}\) and let \(G = \{g_1, \ldots, g_m\} \subseteq \mathbb{F}[\mathbf{x}]\) be a set of polynomials. For any \(f \in \mathbb{F}[\mathbf{x}]\), we say that \(f\) reduces to zero modulo \(G\), written \(f \to_G 0\), if \(f\) has a standard representation \[f = \sum_{i=1}^{m} h_i g_i, \quad h_i \in \mathbb{F}[\mathbf{x}],\] which means that whenever \(h_i g_i \neq 0\), we have \(\mathrm{LM}(f) \succeq \mathrm{LM}(h_i g_i)\).

Note that \(\overline{f}^G = 0\) implies \(f \to_G 0\), but the converse does not hold.

Proposition dz. A basis \(G = \{g_1, \ldots, g_m\}\) of an ideal \(I\) is a Gröbner basis if and only if \(S(g_i, g_j) \to_G 0\) for all \(i \neq j\) (Cox 2015).

This is a more general version of Buchberger’s Criterion. Buchberger’s Criterion naturally leads to the Buchberger’s algorithm, which constructs a Gröbner basis by adding nonzero remainders \(\overline{S(g_i, g_j)}^G\) to \(G\) until the criterion holds. The F4 algorithm (Faugère 1999), introduced by Jean-Charles Faugère, uses the generalized criterion of Proposition dz and computes standard representations via matrix reduction rather than polynomial division. It is tailored for the graded reverse lexicographic order and the result can be converted to the lexicographic order using the FGLM algorithm (Faugère et al. 1993) for applying the Elimination Theorem.

Remark da. A tuple \(F\) of polynomials can be represented by a matrix \(A\) and a vector \(v\) as follows. Consider the set \(M_\succeq(F) = \{m_n, \ldots, m_0\}\) of all monomials in \(F\) under the monomial order \(\succeq\). Let \(v = (m_n, \ldots, m_0)^T\) be the vector of all monomials in decreasing order, and let \(A[i, j]\) contain the coefficient of \(m_j\) in \(f_i\). The rows of \(Av\) then represent the original polynomials in \(F\). We can think of \(v\) as being implicit and consider only the matrix \(A\), whose rows represent the polynomials in \(F\).

The F4 algorithm uses a set \(B\) of unordered pairs of polynomials for which the corresponding S-polynomials are not known to reduce to zero. The degree of a pair \(\{i, j\}\) is \(\deg(\{i, j\}) = \deg(\mathrm{lcm}(\mathrm{LM}(f_i), \mathrm{LM}(f_j)))\). In each iteration, the algorithm selects all pairs with the minimal degree (the normal selection strategy). For each selected pair \(\{i, j\}\), the set \(L\) contains the two halves \[\frac{\mathrm{lcm}(\mathrm{LM}(f_i), \mathrm{LM}(f_j))}{\mathrm{LT}(f_i)} \cdot f_i \quad \text{and} \quad \frac{\mathrm{lcm}(\mathrm{LM}(f_i), \mathrm{LM}(f_j))}{\mathrm{LT}(f_j)} \cdot f_j\] of the S-polynomial \(S(f_i, f_j)\). The sets \(L\) and \(G\) are then passed to SymbolicPreprocessing, which returns a matrix \(M\) representing a set \(H\) as in Remark da. The row reduced echelon form of \(M\) gives equations of the form \[\overline{S(f_i, f_j)} = S(f_i, f_j) - c_1 x^{\alpha(1)} f_{k_1} - c_2 x^{\alpha(2)} f_{k_2} - \cdots.\] When \(\overline{S(f_i, f_j)}\) is included in \(G\), we get a standard representation of \(S(f_i, f_j)\) so that Proposition dz holds. On line 12, we pick those polynomials (rows) whose leading terms are not divisible by the leading terms of any of the polynomials in \(M\). These new polynomials correspond to \(\overline{S(f_i, f_j)}\) and are included in \(G\).

Algorithm d3. F4 algorithm (Faugère 1999).

Input: a tuple of polynomials \(F = (f_1, \ldots, f_m)\).
Output: a Gröbner basis \(G\) of \(I = \langle f_1, \ldots, f_m \rangle\).

  1. \(G \gets F\), \(m \gets |F|\), \(B \gets \{\{i, j\} \mid 1 \le i < j \le m\}\).
  2. while \(B \neq \emptyset\):
    • \(d \gets \min\{\deg(\{i, j\}) \mid \{i, j\} \in B\}\).
    • \(B’ \gets \{\{i, j\} \in B \mid \deg(\{i, j\}) = d\}\), \(B \gets B \setminus B’\).
    • \(L \gets \left\{\frac{\mathrm{lcm}(\mathrm{LM}(f_i), \mathrm{LM}(f_j))}{\mathrm{LT}(f_i)} \cdot f_i \ \middle|\ \{i, j\} \in B’\right\}\).
    • \(M \gets \mathrm{SymbolicPreprocessing}(L, G)\).
    • \(N \gets\)row reduced echelon form of \(M\).
    • \(N^+ \gets \{n \in \mathrm{rows}(N) \mid \mathrm{LM}(n) \notin \langle \mathrm{LM}(\mathrm{rows}(M)) \rangle\}\).
    • for \(n \in N^+\):
      • \(m \gets m + 1\), \(f_m \gets\)polynomial form of \(n\).
      • \(G \gets G \cup \{f_m\}\), \(B \gets B \cup \{\{i, m\} \mid 1 \le i < m\}\).
  3. return \(G\).

The SymbolicPreprocessing function creates a matrix \(M\) representing a set \(H\) with two properties: (i) \(L \subseteq H\), and (ii) whenever \(x^\beta\)is a monomial in some \(f \in H\) and there exists some \(f_k \in G\) with \(\mathrm{LM}(f_k) \mid x^\beta\), then \(H\) contains a product \(x^\alpha f_k\) with \(\mathrm{LM}(x^\alpha f_k) = x^\beta\). The algorithm starts by including all polynomials from \(L\) into \(H\), satisfying (i). It then processes all monomials in \(H\) until none remain: for each unprocessed monomial \(x^\beta\), if there exists \(f_k \in G\) with \(\mathrm{LM}(f_k) \mid x^\beta\), the product \(\frac{x^\beta}{\mathrm{LM}(f_k)} f_k\) is included in \(H\), satisfying (ii).

Algorithm d4. Symbolic Preprocessing.

Input: a set of polynomials \(L\), a set of polynomials \(G\).
Output: a matrix \(M\).

  1. \(H \gets L\), \(\mathit{done} \gets \mathrm{LM}(H)\).
  2. while \(\mathit{done} \neq M_\succeq(H)\):
    • \(x^\beta \gets\)the largest monomial in \(M_\succeq(H) \setminus \mathit{done}\).
    • \(\mathit{done} \gets \mathit{done} \cup \{x^\beta\}\).
    • if there exists \(f_k \in G\) such that \(\mathrm{LM}(f_k) \mid x^\beta\):
      • Select any one such \(f_k\).
      • \(H \gets H \cup \left\{\frac{x^\beta}{\mathrm{LM}(f_k)} f_k\right\}\).
  3. return matrix of coefficients of \(H\) with respect to \(M_\succeq(H)\) with columns in decreasing order according to \(\succeq\).

For a better intuitive insight, consider the matrix \(M\) which represents the set \(H\). Recall that \(L \subseteq H\), so \(M\) contains both halves of \(S(f_i, f_j)\) for any \(\{i, j\}\) currently in \(B’\). The S-polynomial \(S(f_i, f_j)\) is the difference of the two halves, so it can be represented as a linear combination of the rows of \(M\). The rows of \(N\) form a basis for the vector space spanned by the rows of \(M\). This means that \(S(f_i, f_j)\) can also be represented by a linear combination of the rows of \(N\). It can be shown that this gives \(S(f_i, f_j) \to_G 0\) when we include the new polynomials from \(N\) into \(G\).

References

Becker, Thomas. 1993. Gröbner Bases : a Computational Approach to Commutative Algebra. New York: Springer-Verlag.
Buchberger, Bruno. 2006. “Bruno Buchberger’s Phd Thesis 1965: An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal.” Journal of Symbolic Computation 41 (3-4): 475–511.
Cox, David. 2015. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Cham: Springer.
Faugère, J.C., P. Gianni, D. Lazard, and T. Mora. 1993. “Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering.” Journal of Symbolic Computation 16 (4): 329–44. https://doi.org/https://doi.org/10.1006/jsco.1993.1051.
Faugère, Jean-Charles. 1999. “A new efficient algorithm for computing Gröbner bases (F4).” Journal of Pure and Applied Algebra 139 (1-3): 61–88. https://doi.org/10.1016/S0022-4049(99)00005-5.
Zdravkovska, Smilka, and Vladimir Igorevich Arnol’d. 1987. “Conversation with Vladimir Igorevich Arnol’d.” The Mathematical Intelligencer 9 (4): 28–32.
math
Dec 14, 2020