# Ticket #13103(closed enhancement: fixed)

Opened 12 months ago

## Makes BooleanPolynomial more compatible with MPolynomial

Reported by: Owned by: Bouillaguet malb minor sage-5.2 commutative algebra polybori malb, AlexanderDreyer, PolyBoRi None of the above - read trac for reasoning. Martin Albrecht Charles Bouillaguet sage-5.2.beta0

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

## Change History

### comment:1 Changed 12 months ago by 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!

### comment:2 follow-up: ↓ 4 Changed 12 months ago by 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
```

### comment:3 Changed 12 months ago by Bouillaguet

• Status changed from new to needs_review

### comment:4 in reply to: ↑ 2 Changed 12 months ago by malb

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.

### comment:5 Changed 12 months ago by malb

• Reviewers set to Martin Albrecht
• Status changed from needs_review to positive_review

Patch looks good to me.

### comment:6 Changed 11 months ago by jdemeyer

• Milestone changed from sage-5.1 to sage-5.2

### comment:7 Changed 11 months ago by Bouillaguet

• Description modified (diff)

### comment:8 Changed 11 months ago by AlexanderDreyer

• Report Upstream changed from N/A to None of the above - read trac for reasoning.

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

### comment:9 Changed 11 months ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-5.2.beta0
Note: See TracTickets for help on using tickets.