# 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$?

edit retag close merge delete

Sort by ยป oldest newest most voted

h.lift(I) should do the job. See documentation 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 )

more

This is not implemented for multivariate polynomials over BooleanPolynomialRing.

( 2021-05-20 10:53:08 +0200 )edit

Then 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.

( 2021-05-20 13:42:11 +0200 )edit