Forbidden methods: sympy.polys.polytools.reduced, sympy.polys.polytools.groebner
Implement the multivariate polynomial division algorithm for more than one divisor.
Create a function poly_div(f, divs, mo) for dividing the polynomial f by the list of polynomials divs using the specified monomial ordering mo.
Input/Output specifications for poly_div:
f : Poly object
divs : list of Poly objects
mo : String
“q” and “r”, whose values according to the division algorithm are the list of quotient polynomials (list of Poly objects) and the remainder of the division (Poly object) w.r.t. the specified monomial ordering mo, respectively.
Poly objects see Sympy documentation.
mo can take the following values:“lex” - lexicographic order
“grlex” - graded lexicographic order
“grevlex” - graded reversed lexicographic order
Implement the Buchberger's algorithm (or its improved version) for Gröbner basis computation.
Create a function groebner_basis(F, mo) for computing a Gröbner basis of the list of polynomials F w.r.t. the monomial ordering mo.
Input/Output specifications for groebner_basis:
F : list of Poly objects
mo : String
Poly objects that is a Gröbner basis of F w.r.t. the specified monomial ordering mo.
groebner_basis is a Groebner basis (of some polynomial system):
$$$$
Suppose $G = (g_1, \dots, g_t)$ is an ordered tuple of polynomials from $\mathbb{Q}[x_1,\dots,x_n]$. Then $G$ is a Groebner basis w.r.t. a monomial ordering $\geq$ if and only if
$$ \overline{S_{\geq}(g_i, g_j)}^{(G, \geq)} = 0 \quad \forall i, j \in \{1,\dots,t\}, i \neq j. $$
2. Verifying that the return value of groebner_basis is a Groebner basis of the input polynomial system using sympy.polys.polytools.groebner
$$$$ If $F \subset \mathbb{Q}[x_1, \dots, x_n]$ is a set of polynomials and $\geq$ is a monomial ordering, then $G$ is a Groebner basis of the polynomial ideal $J = \langle F \rangle$ w.r.t. $\geq$ if
$$ G \subset J \quad \text{and} \quad \langle \{\mathrm{LM}_{\geq}(g) \;|\; g \in G \} \rangle = \langle \{\mathrm{LM}_{\geq}(f) \;|\; f \in J\} \rangle. $$
Such a definition implies that $G$ is another generating set of $J$, i.e. $\langle G \rangle = J$. Hence if we have a Groebner basis $G$ of $J$ and a subset $G' \subset J$ which we would like to test for being a Groebner basis of $J$, we need to verify that
$$ G' \subset \langle G \rangle \quad \text{and} \quad \langle \{\mathrm{LM}_{\geq}(g') \;|\; g' \in G' \} \rangle = \langle \{\mathrm{LM}_{\geq}(g) \;|\; g \in G \} \rangle. $$
In order to test whether $G' \subset \langle G \rangle$ we can use another property of a Groebner basis which states that
$$ f \in \langle G \rangle \iff \overline{f}^{(G, \geq)} = 0, $$
where $\overline{f}^{(G, \geq)}$ is the remainder of the division of $f$ by $G$ w.r.t. $\geq$. As for the equality of monomial ideals (i.e. ideals generated by monomials), if we have two sets of monomials $M_1$ and $M_2$, then
$$ \langle M_1 \rangle \subset \langle M_2 \rangle \iff \forall \mathbf{x}^{\boldsymbol{\alpha}} \in M_1: \;\exists \mathbf{x}^{\boldsymbol{\beta}} \in M_2: \;\mathbf{x}^{\boldsymbol{\beta}} \;|\; \mathbf{x}^{\boldsymbol{\alpha}}, $$
where the notation $\mathbf{x}^{\boldsymbol{\beta}} \;|\; \mathbf{x}^{\boldsymbol{\alpha}}$ means that $\mathbf{x}^{\boldsymbol{\beta}}$ divides $\mathbf{x}^{\boldsymbol{\alpha}}$. The equality $\langle M_1 \rangle = \langle M_2 \rangle$ can be then checked by verifying that the two inclusions hold true.
Upload a zip archive hw07.zip (via the course ware) containing the following files:
hw07.py - python script containing the implemented function poly_div, groebner_basis