polybori / gb computation / set error

[b641ff84-2a45-43ff-8e1f-750d5a929bee]

Hello,

There is a problem with polybori in sage-5.0.beta11. It crashes with the following error message:

Traceback (most recent call last):
  File "indexingError.py", line 13, in <module>
    B = I.groebner_basis()  # maximal degree 2 extension
  File "pbori.pyx", line 4853, in sage.rings.polynomial.pbori.BooleanPolynomialIdeal.groebner_basis (sage/rings/polynomial/pbori.cpp:28211)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 149, in __call__
    return self.f(**complete_dict)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 149, in __call__
    return self.f(**complete_dict)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 149, in __call__
    return self.f(**complete_dict)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 198, in wrapper
    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 323, in other_ordering_pre
    old_ring=I[0].ring()
TypeError: 'set' object does not support indexing

The error can be consistently created with the following sage code:

# problem, if only a part of the variables appears in the problem

# slightly too large ring
pR.<s0s0, s0s1, s0s2, s0s3, s0s4, s0s5, s0s6, s0s7, s1s0, s1s1, s1s2, s1s3, s1s4, s1s5, s1s6, s1s7, s2s0, s2s1, s2s2, s2s3, s3s0, s3s1, s3s2, s3s3> = BooleanPolynomialRing()

# a problem instance
problem = [s1s0*s1s1, s0s0*s0s1 + s0s0 + s0s1 + s2s0 + s3s0*s3s1 + s3s0 + s3s1, s1s1 + s2s0 + s3s0 + s3s1 + 1, s0s0*s0s1 + s1s1 + s3s0*s3s1 + s3s0, s0s1 + s1s0 + s1s1 + s3s0, s0s0*s0s1 + s0s0 + s0s1 + s1s1 + s2s0 + s3s1, s0s1 + s1s0, s0s0*s0s1 + s0s0 + s0s1 + s1s0 + s2s0 + s3s1, s0s0 + s2s0 + s3s0*s3s1 + s3s0 + 1, s0s0 + s1s1]

# try to solve via Groebner
I = ideal(problem)
B = I.groebner_basis() # crashes exactly here
print B

I guess it's a problem when converting the result back from polybori to Sage.

I use sage 5.0-beta11 on a 64 bit machine, namely

• AMD Opteron(TM) Processor 6276 @ 2.3 GHz
• Linux 2.6.32-220.2.1.el6.x86_64 sage 5.0 was built directly from the sources.

Best, Christopher

Upstream: None of the above - read trac for reasoning.

CC: @sagetrac-PolyBoRi @alexanderdreyer

Component: commutative algebra

Keywords: polybori multivariate equation over GF(2) conversion polybory to sage

Author: Charles Bouillaguet

Reviewer: Alexander Dreyer

Merged: sage-5.6.rc0

Issue created by migration from https://trac.sagemath.org/ticket/12792

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:2

This does not crash for me, in Sage 5.5.

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

doctest to make sure it does not happen again

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:3

Attachment: 12792_add_doctest.patch.gz

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

Author: Charles Bouillaguet

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Reviewer: Alexander Dreyer

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:4

The patch makes sense and looks fine, so positive review.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Upstream: None of the above - read trac for reasoning.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:5

well, it's quite mysterious where the set came from in the crashing... I looked at the code, and it uses sets with much caution.

By the way, for most PolyBoRi code, you can use an immense number of extra variables and it will not affect performance too much.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:6

The set probably arises from eliminate_identical_variables. This issue was fixed some time ago for polybori 0.8.2, see: https://bitbucket.org/brickenstein/polybori/commits/f247a53 .

[jdemeyer]

comment:7

If the patch needs to be merged, the milestone should be an actual Sage release.

Otherwise, I might close the ticket without merging the patch.

[jdemeyer]

Merged: sage-5.6.rc0