Makes BooleanPolynomial more compatible with MPolynomial

[Bouillaguet]

BooleanPolynomial misses some basic function (e.g., p.is_univariate())

The class BooleanPolynomial, which is in fact a polybori interface, has a somewhat different interface compared to the "normal" !MPolynomial. This is probably not normal. Because of this, the variety() function fails on ideals of BooleanPolynomial, which primarily exist to make this particular function faster...

[Bouillaguet]

Patch adding the functions

[Bouillaguet]

With the patch, the variety() function "works":

sage: R.<x,y,z> = BooleanPolynomialRing()
sage: I = ideal( [ x*y*z + x*z + y + 1, x*y+x*z+y*z, x+y+z+1 ] )
sage: I.variety()
verbose 0 (3293: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
verbose 0 (2364: multi_polynomial_ideal.py, variety) Warning: falling back to very slow toy implementation.
[{y: 1, z: 0, x: 0}]

However, it returns a mathematically wrong result when the polynomials do not generate a zero-dimensional ideal without the field equations. In this case, the variety() function normally fails (because on non-finite fields, the variety would be infinite).

Example:

sage: R.<x,y,z> = GF(2)[]
sage: I = ideal( [ x*y*z + x*z + y + 1, x+y+z+1 ] )
sage: I.variety()
...
ValueError: The dimension of the ideal is 1, but it should be 0

If we add the field equations, then the ideal becomes zero-dimensional, and the variety() function works normally:

sage: J = I + sage.rings.ideal.FieldIdeal(R)
sage: J.variety()
[{y: 1, z: 0, x: 0}, {y: 1, z: 1, x: 1}]

But over BooleanPolynomial? things go wrong:

sage: R.<x,y,z> = BooleanPolynomialRing()
sage: I = ideal( [ x*y*z + x*z + y + 1, x+y+z+1 ] )
sage: I.variety()
verbose 0 (3293: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
verbose 0 (2364: multi_polynomial_ideal.py, variety) Warning: falling back to very slow toy implementation.
[{y: 1}]

This result does not make sense. Of course ideals of BooleanPolynomials? should have dimension zero, so that the variety() function should always work. But it should always return the right result!

[Bouillaguet]

The cause of the bug in "positive" dimension (without the field equations) is that BooleanPolynomialIdeal?.groebner_basis() computes a groebner basis modulo the field equations, but this is not a Groebner basis in general.

Obvious fix : a) Compute GB modulo field equations with BooleanPolynomialIdeal?.groebner_basis() b) cast to MPolynomial c) Add field equations d) use MPolynomial.variety()

This is guaranteed to be correct, but is probably a bit sub-optimal. Adding the field equations may destroy the Groebner basis, but my guess is that running the buchberger algorithm again should do little work.

This is implemented by the second patch.

Performance-wise, the gain is decent (as expected from the use of PolyBoRi?):

sage: n = 14
sage: R = BooleanPolynomialRing(n, ['x%d'%(i+1) for i in range(n)], order='lex')
sage: polys = [ sum([ GF(2).random_element() * R.gen(i) * R.gen(j) for i in range(n) for j in range(n)]) for k in range(n)]
sage: I = R.ideal( polys )
sage: time V1 = I.variety()
Time: CPU 0.51 s, Wall: 0.54 s

sage: R = PolynomialRing(GF(2), n, ['x%d'%(i+1) for i in range(n)], order='lex')
sage: I = R.ideal( polys )
sage: time V2 = (I + sage.rings.ideal.FieldIdeal(R)).variety()
Time: CPU 9.12 s, Wall: 9.16 s

sage: V1 == V2
True

[Bouillaguet]

overloaded variety function for BooleanPolynomialIdeal?

[malb]

Replying to Bouillaguet:

The cause of the bug in "positive" dimension (without the field equations) is that BooleanPolynomialIdeal?.groebner_basis() computes a groebner basis modulo the field equations, but this is not a Groebner basis in general.

Obvious fix : a) Compute GB modulo field equations with BooleanPolynomialIdeal?.groebner_basis() b) cast to MPolynomial c) Add field equations d) use MPolynomial.variety()

This is guaranteed to be correct, but is probably a bit sub-optimal. Adding the field equations may destroy the Groebner basis, but my guess is that running the buchberger algorithm again should do little work.

Actually, adding the field equations would not destroy the GB, as PolyBoRi? actually computes the GB with the field equations implicitly added. The result + field equations is a GB wrt to GF(2)[x1,...xn].

This is implemented by the second patch.

This strategy looks fine to me. IIRC there is some special code in PolyBoRi? to do this faster, but for now this simple approach fixes an embarrassing bug.

[malb]

Patch looks good to me.

[AlexanderDreyer]

Since it could be done more efficient low-level, I'll add p.is_univariate()-support upstream later.