ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 29 Mar 2019 11:47:01 -0500ideal membership and solutionhttps://ask.sagemath.org/question/45932/ideal-membership-and-solution/I gave sage the following ring and the ideal
R.<x,y,z>=GF(2)[];
f=1 + z + y*z + y^2*z + z^2 + y*z^2;
g=1 + x + y^2 + z^2;
I = R.ideal(f, g)
I found that the function h below lies in the Ideal I using
h=1 + y + z + x*z + y*z + x*y*z + y^2*z + y*z^2;
h in I
I know that in general, finding polynomials $a(x)$ and $b(x)$ such that $h = a f+ b g$ might be hard, but can I find the solutions for $a$ and $b$ to a certain degree of these polynomials, if they exist? I was wondering if sage can check this more efficiently
Thu, 28 Mar 2019 00:29:57 -0500https://ask.sagemath.org/question/45932/ideal-membership-and-solution/Answer by rburing for <p>I gave sage the following ring and the ideal</p>
<pre><code>R.<x,y,z>=GF(2)[];
f=1 + z + y*z + y^2*z + z^2 + y*z^2;
g=1 + x + y^2 + z^2;
I = R.ideal(f, g)
</code></pre>
<p>I found that the function h below lies in the Ideal I using </p>
<pre><code>h=1 + y + z + x*z + y*z + x*y*z + y^2*z + y*z^2;
h in I
</code></pre>
<p>I know that in general, finding polynomials $a(x)$ and $b(x)$ such that $h = a f+ b g$ might be hard, but can I find the solutions for $a$ and $b$ to a certain degree of these polynomials, if they exist? I was wondering if sage can check this more efficiently</p>
https://ask.sagemath.org/question/45932/ideal-membership-and-solution/?answer=45934#post-id-45934Yes, this can be done algorithmically. First you compute a Groebner basis $\langle g_1, \ldots, g_r \rangle$ of $I$, and remember the expressions $g_i = a_i f + b_i g$. Then you do multivariate polynomial division of $h$ by $\langle g_1, \ldots, g_r \rangle$. This yields $$h = c_1 g_1 + \ldots + c_r g_r = (c_1a_1 + \ldots c_ra_r)f + (c_1b_1 + \ldots c_rb_r)g.$$
In your example one Groebner basis of $I$ is $\langle f,g,f_1,f_2,f_3 \rangle$ where $f_1 = S(f,g) = f-zg$, $f_2 = S(f_1,f) - zg = (y-z)f - z(y+1)g$, $f_3 = S(f_1,f_2) = (x - z(y-z))f + z(z(y+1) - x)g$.
Multivariate polynomial division of $h$ by $\langle f,g,f_1,f_2,f_3 \rangle$ yields $$h = f + f_2 = (y-z+1)f - z(y+1)g.$$
This can all easily be automated in Sage (but I don't have time to do it now).Thu, 28 Mar 2019 07:56:30 -0500https://ask.sagemath.org/question/45932/ideal-membership-and-solution/?answer=45934#post-id-45934Comment by arpit for <p>Yes, this can be done algorithmically. First you compute a Groebner basis $\langle g_1, \ldots, g_r \rangle$ of $I$, and remember the expressions $g_i = a_i f + b_i g$. Then you do multivariate polynomial division of $h$ by $\langle g_1, \ldots, g_r \rangle$. This yields $$h = c_1 g_1 + \ldots + c_r g_r = (c_1a_1 + \ldots c_ra_r)f + (c_1b_1 + \ldots c_rb_r)g.$$</p>
<p>In your example one Groebner basis of $I$ is $\langle f,g,f_1,f_2,f_3 \rangle$ where $f_1 = S(f,g) = f-zg$, $f_2 = S(f_1,f) - zg = (y-z)f - z(y+1)g$, $f_3 = S(f_1,f_2) = (x - z(y-z))f + z(z(y+1) - x)g$.
Multivariate polynomial division of $h$ by $\langle f,g,f_1,f_2,f_3 \rangle$ yields $$h = f + f_2 = (y-z+1)f - z(y+1)g.$$</p>
<p>This can all easily be automated in Sage (but I don't have time to do it now).</p>
https://ask.sagemath.org/question/45932/ideal-membership-and-solution/?comment=45943#post-id-45943@rburing thanks for the answer. This is useful. How do I do the last step of multivariate polynomial division in Sage?Fri, 29 Mar 2019 11:47:01 -0500https://ask.sagemath.org/question/45932/ideal-membership-and-solution/?comment=45943#post-id-45943