2 Gröbner Bases
2.1 Polynomial Reductions
Let \(P\) be a subset of \(K[X]\) and \(f\in K[X]\). Then there exists a normal form \(g\in K[X]\) of \(f\) modulo \(P\) and a family \(\mathcal{F}=\{ q_{p}\} _{p\in P}\) of elements of \(K[X]\) with
If \(P\) is finite, the ground field is computable, and the term order on \(T\) is decidable, then \(g\) and \(\{ q_{p}\} _{p\in P}\) can be computed from \(f\) and \(P\).
2.2 Gröbner Bases-Existence and Uniqueness
Let \(I\subseteq k[x_1,\dots ,x_n]\) be an ideal other than \(\{ 0\} \), and fix a monomial ordering on \(k[x_1,\dots ,x_n]\). Then:
We denote by
\[ \mathrm{LT}(I) = \{ \, c\, x^\alpha \mid \exists \, f\in I\setminus \{ 0\} \text{ with }\mathrm{LT}(f)=c\, x^\alpha \} . \]We denote by \(\langle \mathrm{LT}(I)\rangle \) the ideal generated by the elements of \(\mathrm{LT}(I)\).
Let \(I \subseteq k[x_1, \ldots , x_n]\) be an ideal different from \(\{ 0 \} \).
\(\langle \operatorname {LT}(I)\rangle \) is a monomial ideal.
There are \(g_1, \ldots , g_t \in I\) such that \(\langle \operatorname {LT}(I)\rangle = \langle \operatorname {LT}(g_1), \ldots , \operatorname {LT}(g_t)\rangle \).
Fix a monomial order \({\gt}\) on the polynomial ring \(k[x_1, \dots , x_n]\). A finite subset \(G = \{ g_1, \dots , g_t\} \) of an ideal \(I \subseteq k[x_1, \dots , x_n]\) different from \(\{ 0\} \) is said to be a Gröbner basis (or standard basis) for \(I\) if the ideal generated by the leading terms of the elements in \(G\) is equal to the ideal generated by the leading terms of all elements in \(I\). That is,
where \(\operatorname {LT}(I) = \{ \operatorname {LT}(f) \mid f \in I \setminus \{ 0\} \} \). Using the convention that \(\langle \emptyset \rangle = \{ 0\} \), we define the empty set \(\emptyset \) to be the Gröbner basis of the zero ideal \(\{ 0\} \).
Let \(I \subseteq k[x_1,\dots ,x_n]\) be an ideal and let \(G = \{ g_1,\dots ,g_t\} \) be a Gröbner basis for \(I\). Then given \(f \in k[x_1,\dots ,x_n]\) there is a unique \(r \in k[x_1,\dots ,x_n]\) with the following two properties:
No term of \(r\) is divisible by any of \(\mathrm{LT}(g_1),\dots ,\mathrm{LT}(g_t)\).
There is \(g\in I\) such that \(f = g + r\).
In particular, \(r\) is the remainder on division of \(f\) by \(G\) no matter how the elements of \(G\) are listed when using the division algorithm.
Let \(G = \{ g_1, \dots , g_t\} \) be a Gröbner basis for an ideal \(I \subseteq k[x_1, \dots , x_n]\) (with respect to a given monomial order \({\gt}\)) and let \(f \in k[x_1, \dots , x_n]\). Then \(f \in I\) if and only if the remainder on division of \(f\) by \(G\) is zero.
We will write \(\overline{f}^F\) for the remainder(normalform) on division of \(f\) by the ordered \(s\)-tuple
If \(F\) is a Gröbner basis for the ideal \(\langle f_1,\dots ,f_s\rangle \), then by Proposition 1 we may regard \(F\) as a set (without any particular order).
Let \(f,g\in k[x_1,\dots ,x_n]\) be nonzero polynomials.
If \(\operatorname {multideg}(f)=\alpha \) and \(\operatorname {multideg}(g)=\beta \), then let
\[ \gamma = (\gamma _1,\dots ,\gamma _n), \quad \gamma _i = \max (\alpha _i,\beta _i) \quad \text{for each }i. \]We call \(x^\gamma \) the least common multiple of \(\mathrm{LM}(f)\) and \(\mathrm{LM}(g)\), written
\[ x^\gamma \; =\; \mathrm{lcm}\bigl(\mathrm{LM}(f),\, \mathrm{LM}(g)\bigr). \]The \(S\)-polynomial of \(f\) and \(g\) is the combination
\[ S(f,g) \; =\; \frac{x^\gamma }{\mathrm{LT}(f)}\, f \; -\; \frac{x^\gamma }{\mathrm{LT}(g)}\, g. \]
Suppose we have a sum \(\sum _{i=1}^s p_i,\) where \(\operatorname {multideg}(p_i)=\delta \in \mathbb Z_{\ge 0}^n\) for all \(i\). If \(\operatorname {multideg}\Bigl(\sum _{i=1}^s p_i\Bigr){\lt}\delta ,\) then \(\sum _{i=1}^s p_i\) is a linear combination, with coefficients in \(k\), of the \(S\)-polynomials \(S(p_j,p_l)\quad \text{for }1\le j,\, l\le s\). Furthermore, each \(S(p_j,p_l)\) has multidegree \({\lt}\delta \).
Let \(I\) be a polynomial ideal in \(k[x_1, \dots , x_n]\). Then a basis \(G = \{ g_1, \dots , g_t\} \) of \(I\) is a Gröbner basis for \(I\) (with respect to a given monomial order \({\gt}\)) if and only if for all pairs \(i \neq j\), the remainder on division of the \(S\)-polynomial \(S(g_i, g_j)\) by \(G\) (listed in some order) is zero.
Fix a monomial order and let \(G = \left\{ g_1, \ldots , g_t\right\} \subseteq k[x_1, \ldots , x_n]\). Given \(f \in k[x_1, \ldots , x_n]\), we say that \(f\) reduces to zero modulo \(G\), written \(f \xrightarrow {G} 0\), if \(f\) has a standard representation
which means that whenever \(A_ig_i \neq 0\), we have
\(G := F\) Initialize \(G\) as the input list \(t := s\) Current number of polynomials in \(G\) \(B := \{ (i, j) \mid 1 \le i {\lt} j \le t\} \) Set of index pairs to process
\(B \neq \emptyset \) Select \((i, j)\) from \(B\) \(B := B \setminus \{ (i, j)\} \) \(S := \operatorname {S}(g_i, g_j)\) Compute S-polynomial (using indices for \(G\)) \(r := \operatorname {rem}(S, G)\) Compute remainder w.r.t. the ordered list \(G\) \(r \neq 0\) \(t := t + 1\) Append \(r\) to the list \(G\) as \(g_t\) Add non-zero remainder to end of list \(B := B \cup \{ (i, t) \mid 1 \le i {\lt} t\} \) Add new pairs involving \(g_t\)
\(G\)
Buchberger’s Algorithm ().
Input: An ordered list of polynomials \(F = (f_1, \dots , f_s)\) and a monomial order \({\gt}\). Output: A Gröbner basis \(G = (g_1, \dots , g_t)\) for \(I = \langle f_1, \dots , f_s \rangle \) such that \(F \subseteq G\).
\(G := F\)
\(t := s\)
\(B := \{ (i, j) \mid 1 \le i {\lt} j \le t\} \)
While \(B \neq \emptyset \):
Choose a pair \((i, j)\) from \(B\)
Remove \((i, j)\) from \(B\)
\(S := \operatorname {S}(g_i, g_j)\)
\(r := \operatorname {rem}(S, G)\)
If \(r \neq 0\):
\(t := t + 1\)
Append \(r\) to \(G\) as \(g_t\)
Add \(\{ (i, t) \mid 1 \le i {\lt} t\} \) to \(B\)
Return \(G\)
Let \(G\) be a Gröbner basis of \(I \subseteq k[x_1, \ldots , x_n]\). Let \(p \in G\) be a polynomial such that \(\operatorname {LT}(p) \in \langle \operatorname {LT}(G \setminus \{ p\} ) \rangle .\) Then \(G \setminus \{ p\} \) is also a Gröbner basis for \(I\).