2
$\begingroup$

Given a finite set of polynomials $f_1, f_2,..., f_n$ of variables $x_1,...,x_m$, generating the ideal $I$, suppose that we have one more polynomial $g\in I$.

What is the algorythm for decomposing $g$ w.r.t set of $f_i$? Namely representing $g=h_1 f_1+... h_n f_n$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Not sure if this is the best way, but we can compute a Grobner basis $B$ of $I$, expressing its generators in terms of $f_i$. Any $g\in I$ reduces to $0$ w.r.t. $B$, which gives a representation of $g$ in terms of polynomials in $B$, which then translates into a representation of $g$ in terms of $f_i$.

ADDED. Here is a more transparent way at the cost of adding a new variable $y_i$ for each $f_i$. Let $B'$ be a Grobner basis of $\langle f_i-y_i\rangle$ w.r.t. the elimination order weighting $x$'s more than $y$'s. Then a polynomial $g\in I$ reduces w.r.t. $B'$ to a polynomial $h(y_1,\dots,y_n)$ with coefficients being polynomials in $x$'s and $h(0,\dots,0)=0$, giving the required representation $g=h(f_1,\dots,f_n)$.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Actually I have a related question. How can we decompose Grobner basis elements in terms of $f_i$ using only Grobner algorythm as a blackbox and not looking inside. I heard about introducing dummy variables for each original polynomial. Just in case, could you elaborate on this? Because in Sympy, "groebner" function does that, but it does not provide actual decomposition, only gives the basis itself. $\endgroup$
    – Dmitri Scheglov
    Commented Apr 16 at 14:15
  • $\begingroup$ @DmitriScheglov: Yes, dummy variables can be used for that purpose. However, if you are willing to introduce them, you can directly solve the original problem - see update in my answer. $\endgroup$
    – Max Alekseyev
    Commented Apr 16 at 15:35
  • $\begingroup$ from your updated answer it follows that $g$ in fact lies in the ring, generated by $f_i$, not just the ideal. Can you clarify it please? $\endgroup$
    – Dmitri Scheglov
    Commented Apr 16 at 20:08
  • $\begingroup$ @DmitriScheglov: By construction, the free term of the polynomial $h$ is zero (if I got your concern correctly). $\endgroup$
    – Max Alekseyev
    Commented Apr 16 at 20:24
  • $\begingroup$ I mean that in general, $g$ does not necessarily belong to a ring , generated by $f_i$. And the very fact of existence of such $h$ implies that it does. This is my concern. $\endgroup$
    – Dmitri Scheglov
    Commented Apr 16 at 20:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .