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.Thu, 20 May 2021 13:42:11 +0200How to find coefficient polynomials in an idealhttps://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/I have an ideal $I$ generated by multivariate polynomials $f,g$ over BooleanPolynomialRing.
Suppose another polynomial $h$ is in $I$. So there are two polynomials
$h_1$ and $h_2$ such that $h=h_1 f +h_2 g$. How to find $h_1, h_2$?Wed, 19 May 2021 20:10:35 +0200https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/Answer by Max Alekseyev for <p>I have an ideal $I$ generated by multivariate polynomials $f,g$ over BooleanPolynomialRing.
Suppose another polynomial $h$ is in $I$. So there are two polynomials
$h_1$ and $h_2$ such that $h=h_1 f +h_2 g$. How to find $h_1, h_2$?</p>
https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/?answer=57172#post-id-57172`h.lift(I)` should do the job. See [documentation](https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_element.html#sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict.lift) for details.
Since `lift` is not implemented for BooleanPolynomialRing, we can workaround by considering the ideal generated by $f,g$ and $x_i^2+x_i$ in $GF(2)[x_1,\dots,x_n]$. Here is a sample code:
B.<x,y> = BooleanPolynomialRing()
I = ideal(x+1,y+1)
pol = x*y + 1
#print( pol.lift(I) ) # this is not implemented
#workaround:
F = GF(2)[B.gens()]
I2 = ideal( [F(g) for g in I.gens()] + [g^2+g for g in F.gens()] )
coefs = [B(c) for c in F(pol).lift(I2)[:len(I.gens())]]
print( coefs )Wed, 19 May 2021 22:19:13 +0200https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/?answer=57172#post-id-57172Comment by Max Alekseyev for <p><code>h.lift(I)</code> should do the job. See <a href="https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_element.html#sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict.lift">documentation</a> for details.</p>
<p>Since <code>lift</code> is not implemented for BooleanPolynomialRing, we can workaround by considering the ideal generated by $f,g$ and $x_i^2+x_i$ in $GF(2)[x_1,\dots,x_n]$. Here is a sample code:</p>
<pre><code>B.<x,y> = BooleanPolynomialRing()
I = ideal(x+1,y+1)
pol = x*y + 1
#print( pol.lift(I) ) # this is not implemented
#workaround:
F = GF(2)[B.gens()]
I2 = ideal( [F(g) for g in I.gens()] + [g^2+g for g in F.gens()] )
coefs = [B(c) for c in F(pol).lift(I2)[:len(I.gens())]]
print( coefs )
</code></pre>
https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/?comment=57181#post-id-57181Then consider the ideal generated by $f,g$ and $x_i^2+x_i$ of $GF(2)[x_1,\dots,z_n]$ instead. I've added a sample code.Thu, 20 May 2021 13:42:11 +0200https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/?comment=57181#post-id-57181Comment by rburing for <p><code>h.lift(I)</code> should do the job. See <a href="https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_element.html#sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict.lift">documentation</a> for details.</p>
<p>Since <code>lift</code> is not implemented for BooleanPolynomialRing, we can workaround by considering the ideal generated by $f,g$ and $x_i^2+x_i$ in $GF(2)[x_1,\dots,x_n]$. Here is a sample code:</p>
<pre><code>B.<x,y> = BooleanPolynomialRing()
I = ideal(x+1,y+1)
pol = x*y + 1
#print( pol.lift(I) ) # this is not implemented
#workaround:
F = GF(2)[B.gens()]
I2 = ideal( [F(g) for g in I.gens()] + [g^2+g for g in F.gens()] )
coefs = [B(c) for c in F(pol).lift(I2)[:len(I.gens())]]
print( coefs )
</code></pre>
https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/?comment=57179#post-id-57179This is not implemented for multivariate polynomials over [`BooleanPolynomialRing`](https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/pbori/pbori.html).Thu, 20 May 2021 10:53:08 +0200https://ask.sagemath.org/question/57168/how-to-find-coefficient-polynomials-in-an-ideal/?comment=57179#post-id-57179