ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 20 Apr 2020 08:40:08 +0200Finding polynomial solutions that belong to an idealhttps://ask.sagemath.org/question/50713/finding-polynomial-solutions-that-belong-to-an-ideal/I have a system of equations in which the variables belong to a certain ideal of a polynomial ring over a field. We can call this ideal $I$ and its generators $c_1$, $c_2$ and $c_3$. Let's take the ring to be $\mathbb{F}_2[x_1,x_2,x_3]$ and the ideal to be $I=<x_1x_2x_3-1,x_2-x_1,x_1-1>$ . Let's say the equations are $g_1+x_1w_2+x_2w_3 = x_1-1$, $g_2+x_2w_1+x_3w_3 = x_2-1$ and $g_3+x_1w_1+w_2 = x_3-1$ and one needs to find solution to the above set of equations with variables $g_i$ and $w_i$ inside the ideal $I$. There are of course more variables than equations here. One obvious solution is $g_1=x_1-1,g_2=x_2-1, g_3=x_3-1$. How does one find the full set of solutions? I thought of implementing this as a syzygy problem where I take $x_1-1$ and so on on the left but that seems to be not ideal since it is not clear whether I find all solutions or not. To simplify the problem, we can choose a cut-off for degree of polynomial solutions, for example, 1 or 2.Mon, 13 Apr 2020 00:57:46 +0200https://ask.sagemath.org/question/50713/finding-polynomial-solutions-that-belong-to-an-ideal/Comment by Sébastien for <p>I have a system of equations in which the variables belong to a certain ideal of a polynomial ring over a field. We can call this ideal $I$ and its generators $c_1$, $c_2$ and $c_3$. Let's take the ring to be $\mathbb{F}_2[x_1,x_2,x_3]$ and the ideal to be $I=<x_1x_2x_3-1,x_2-x_1,x_1-1>$ . Let's say the equations are $g_1+x_1w_2+x_2w_3 = x_1-1$, $g_2+x_2w_1+x_3w_3 = x_2-1$ and $g_3+x_1w_1+w_2 = x_3-1$ and one needs to find solution to the above set of equations with variables $g_i$ and $w_i$ inside the ideal $I$. There are of course more variables than equations here. One obvious solution is $g_1=x_1-1,g_2=x_2-1, g_3=x_3-1$. How does one find the full set of solutions? I thought of implementing this as a syzygy problem where I take $x_1-1$ and so on on the left but that seems to be not ideal since it is not clear whether I find all solutions or not. To simplify the problem, we can choose a cut-off for degree of polynomial solutions, for example, 1 or 2.</p>
https://ask.sagemath.org/question/50713/finding-polynomial-solutions-that-belong-to-an-ideal/?comment=50872#post-id-50872Is there a missing coefficient $x_3$ in front of $w_2$ in the last equation?Mon, 20 Apr 2020 08:01:04 +0200https://ask.sagemath.org/question/50713/finding-polynomial-solutions-that-belong-to-an-ideal/?comment=50872#post-id-50872Answer by Sébastien for <p>I have a system of equations in which the variables belong to a certain ideal of a polynomial ring over a field. We can call this ideal $I$ and its generators $c_1$, $c_2$ and $c_3$. Let's take the ring to be $\mathbb{F}_2[x_1,x_2,x_3]$ and the ideal to be $I=<x_1x_2x_3-1,x_2-x_1,x_1-1>$ . Let's say the equations are $g_1+x_1w_2+x_2w_3 = x_1-1$, $g_2+x_2w_1+x_3w_3 = x_2-1$ and $g_3+x_1w_1+w_2 = x_3-1$ and one needs to find solution to the above set of equations with variables $g_i$ and $w_i$ inside the ideal $I$. There are of course more variables than equations here. One obvious solution is $g_1=x_1-1,g_2=x_2-1, g_3=x_3-1$. How does one find the full set of solutions? I thought of implementing this as a syzygy problem where I take $x_1-1$ and so on on the left but that seems to be not ideal since it is not clear whether I find all solutions or not. To simplify the problem, we can choose a cut-off for degree of polynomial solutions, for example, 1 or 2.</p>
https://ask.sagemath.org/question/50713/finding-polynomial-solutions-that-belong-to-an-ideal/?answer=50873#post-id-50873We define the ring and the ideal:
sage: R.<x1,x2,x3> = GF(2)[]
sage: R
Multivariate Polynomial Ring in x1, x2, x3 over Finite Field of size 2
sage: I = R.ideal(x1*x2*x3-1, x2-x1, x1-1)
We compute the groebner basis of the ideal and we realize that these are exactly the right hand side of the three given equations:
sage: I.groebner_basis()
[x1 + 1, x2 + 1, x3 + 1]
sage: [x1-1, x2-1, x3-1]
[x1 + 1, x2 + 1, x3 + 1]
Thus, finding a solution to the 3 equations is equivalent to finding a solution to the following:
$$
x_1w_2+x_2w_3 \in I, \quad
x_2w_1+x_3w_3 \in I, \quad
x_1w_1+x_3w_2 \in I
$$
which holds by definition of ideal for all elements $w_1,w_2,w_3$ in the ideal $I$ which solves the question as it was requested that the $w_i$ are in the ideal. Now, notice that this does not include all solutions, for example:
sage: w2 = x2; w3 = x3
sage: w2 in I, w3 in I
(False, False)
sage: x1*w2 + x2*w3 in I
TrueMon, 20 Apr 2020 08:40:08 +0200https://ask.sagemath.org/question/50713/finding-polynomial-solutions-that-belong-to-an-ideal/?answer=50873#post-id-50873