Opened 10 years ago

Closed 9 years ago

#10340 closed defect (duplicate)

Strange error in groebner_basis()

Reported by: sbulygin Owned by: mvngu
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: commutative algebra Keywords: groebner_basis, Boolean Polynomials
Cc: malb, PolyBoRi, AlexanderDreyer Merged in:
Authors: Reviewers: Alexander Dreyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by AlexanderDreyer)

There is a ValueError? occurring quite strangely when calling groebner_basis() for an ideal in BooleanPolynomialRing?. Here is the example code

R.<Y0100, Y0101, Y0102, Y0103, Y0104, Y0105, Y0106, Y0107, Y0108, Y0109, Y0110, Y0111, Y0112, Y0113, Y0114, Y0115, Y0116, Y0117, Y0118, Y0119, Y0120, Y0121, Y0122, Y0123, Y0124, Y0125, Y0126, Y0127, Y0128, Y0129, Y0130, Y0131, Y0132, Y0133, Y0134, Y0135, Y0136, Y0137, Y0138, Y0139, Y0140, Y0141, Y0142, Y0143, Y0144, Y0145, Y0146, Y0147, X0100, X0101, X0102, X0103, X0104, X0105, X0106, X0107, X0108, X0109, X0110, X0111, X0112, X0113, X0114, X0115, X0116, X0117, X0118, X0119, X0120, X0121, X0122, X0123, X0124, X0125, X0126, X0127, X0128, X0129, X0130, X0131, X0132, X0133, X0134, X0135, X0136, X0137, X0138, X0139, X0140, X0141, X0142, X0143, X0144, X0145, X0146, X0147, K00, K01, K02, K03, K04, K05, K06, K07, K08, K09, K10, K11, K12, K13, K14, K15, K16, K17, K18, K19, K20, K21, K22, K23, K24, K25, K26, K27, K28, K29, K30, K31, K32, K33, K34, K35, K36, K37, K38, K39, K40, K41, K42, K43, K44, K45, K46, K47>=BooleanPolynomialRing(order="degrevlex")

I=ideal([X0100 + K00 + 1,
X0101 + K01,
X0102 + K02 + 1,
X0103 + K03 + 1,
X0104 + K04,
X0105 + K05 + 1,
X0106 + K06,
X0107 + K07 + 1,
X0108 + K08,
X0109 + K09 + 1,
X0110 + K10 + 1,
X0111 + K11 + 1,
X0112 + K12 + 1,
X0113 + K13,
X0114 + K14 + 1,
X0115 + K15 + 1,
X0116 + K16 + 1,
X0117 + K17,
X0118 + K18,
X0119 + K19 + 1,
X0120 + K20 + 1,
X0121 + K21 + 1,
X0122 + K22 + 1,
X0123 + K23 + 1,
X0124 + K24 + 1,
X0125 + K25 + 1,
X0126 + K26,
X0127 + K27 + 1,
X0128 + K28,
X0129 + K29,
X0130 + K30,
X0131 + K31 + 1,
X0132 + K32 + 1,
X0133 + K33,
X0134 + K34,
X0135 + K35 + 1,
X0136 + K36,
X0137 + K37 + 1,
X0138 + K38 + 1,
X0139 + K39,
X0140 + K40 + 1,
X0141 + K41,
X0142 + K42 + 1,
X0143 + K43,
X0144 + K44,
X0145 + K45,
X0146 + K46,
X0147 + K47,
X0132 + 1,
X0116 + 1,
X0100,
X0133,
X0117 + 1,
X0101,
X0134,
X0118 + 1,
X0102 + 1,
X0135,
X0119,
X0103 + 1,
X0136 + 1,
X0120,
X0104,
X0137,
X0121 + 1,
X0105,
X0138,
X0122,
X0106 + 1,
X0139,
X0123,
X0107,
X0140 + 1,
X0124,
X0108 + 1,
X0141 + 1,
X0125 + 1,
X0109,
X0142,
X0126,
X0110,
X0143 + 1,
X0127 + 1,
X0111,
X0144 + 1,
X0128 + 1,
X0112,
X0145,
X0129,
X0113,
X0146 + 1,
X0130 + 1,
X0114 + 1,
X0147 + 1,
X0131 + 1,
X0115
])

I.groebner_basis() # reports an error

the error being

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/<ipython console> in <module>()

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.BooleanPolynomialIdeal.groebner_basis (sage/rings/polynomial/pbori.cpp:25491)()

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in __call__(self, *args, **kwds)
    138         if heuristic:
    139             complete_dict=self.heuristicFunction(complete_dict)
--> 140         return self.f(**complete_dict)
    141     def __init__(self,f,heuristic_function):
    142         (self.argnames,self.varargs,self.varopts,self.defaults)=getargspec(f)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in __call__(self, *args, **kwds)
    138         if heuristic:
    139             complete_dict=self.heuristicFunction(complete_dict)
--> 140         return self.f(**complete_dict)
    141     def __init__(self,f,heuristic_function):
    142         (self.argnames,self.varargs,self.varopts,self.defaults)=getargspec(f)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    185                        print "preprocessing for option:", option
    186                    
--> 187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
    188             I=f(I,**kwds)
    189             if option_set:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in llfirst_pre(I, prot)
    223     
    224 def llfirst_pre(I,prot):
--> 225     (eliminated,llnf, I)=eliminate(I,on_the_fly=False,prot=prot)
    226     return (I,eliminated)
    227 

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/ll.pyc in eliminate(polys, on_the_fly, prot, reduction_function, optimized)
    109         reduction_function=reduction_function,
    110         reduce_ll_system=(not on_the_fly),
--> 111         prot=prot)
    112   else:
    113       reductors=ll_encode(linear_leads,reduce=(not on_the_fly),prot=prot)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/ll.pyc in eliminate_ll_ranked(ll_system, to_reduce, reduction_function, reduce_ll_system, prot)
    146       return iter(Monomial(v).variables()).next().index()
    147   #sorted_var_indices=[var_index(v) for v in sorted_vars]
--> 148   to_ring=Ring(len(sorted_vars))
    149   map_back_indices = dict([(i, var_index(v)) for (i, v) in enumerate(sorted_vars)])
    150   map_from_indices = dict([(var_index(v), i) for (i, v) in enumerate(sorted_vars)])

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/PyPolyBoRi.pyc in Ring(n, order)
     17 
     18 def Ring(n, order='lp'):
---> 19     return BooleanPolynomialRing(n, 'x', order=order)
     20 
     21 BoolePolynomialVector = BooleanPolynomialVector

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.BooleanPolynomialRing.__init__ (sage/rings/polynomial/pbori.cpp:4458)()

ValueError: Number of variables must be greater than 1.

Interestingly enough, the same ideal, but without the last generator gets through

I=ideal([X0100 + K00 + 1,
X0101 + K01,
X0102 + K02 + 1,
X0103 + K03 + 1,
X0104 + K04,
X0105 + K05 + 1,
X0106 + K06,
X0107 + K07 + 1,
X0108 + K08,
X0109 + K09 + 1,
X0110 + K10 + 1,
X0111 + K11 + 1,
X0112 + K12 + 1,
X0113 + K13,
X0114 + K14 + 1,
X0115 + K15 + 1,
X0116 + K16 + 1,
X0117 + K17,
X0118 + K18,
X0119 + K19 + 1,
X0120 + K20 + 1,
X0121 + K21 + 1,
X0122 + K22 + 1,
X0123 + K23 + 1,
X0124 + K24 + 1,
X0125 + K25 + 1,
X0126 + K26,
X0127 + K27 + 1,
X0128 + K28,
X0129 + K29,
X0130 + K30,
X0131 + K31 + 1,
X0132 + K32 + 1,
X0133 + K33,
X0134 + K34,
X0135 + K35 + 1,
X0136 + K36,
X0137 + K37 + 1,
X0138 + K38 + 1,
X0139 + K39,
X0140 + K40 + 1,
X0141 + K41,
X0142 + K42 + 1,
X0143 + K43,
X0144 + K44,
X0145 + K45,
X0146 + K46,
X0147 + K47,
X0132 + 1,
X0116 + 1,
X0100,
X0133,
X0117 + 1,
X0101,
X0134,
X0118 + 1,
X0102 + 1,
X0135,
X0119,
X0103 + 1,
X0136 + 1,
X0120,
X0104,
X0137,
X0121 + 1,
X0105,
X0138,
X0122,
X0106 + 1,
X0139,
X0123,
X0107,
X0140 + 1,
X0124,
X0108 + 1,
X0141 + 1,
X0125 + 1,
X0109,
X0142,
X0126,
X0110,
X0143 + 1,
X0127 + 1,
X0111,
X0144 + 1,
X0128 + 1,
X0112,
X0145,
X0129,
X0113,
X0146 + 1,
X0130 + 1,
X0114 + 1,
X0147 + 1,
X0131 + 1
])

I.groebner_basis() # works

the result being

[X0100, X0101, X0102 + 1, X0103 + 1, X0104, X0105, X0106 + 1, X0107, X0108 + 1, X0109, X0110, X0111, X0112, X0113, X0114 + 1, X0115 + K15 + 1, X0116 + 1, X0117 + 1, X0118 + 1, X0119, X0120, X0121 + 1, X0122, X0123, X0124, X0125 + 1, X0126, X0127 + 1, X0128 + 1, X0129, X0130 + 1, X0131 + 1, X0132 + 1, X0133, X0134, X0135, X0136 + 1, X0137, X0138, X0139, X0140 + 1, X0141 + 1, X0142, X0143 + 1, X0144 + 1, X0145, X0146 + 1, X0147 + 1, K00 + 1, K01, K02, K03, K04, K05 + 1, K06 + 1, K07 + 1, K08 + 1, K09 + 1, K10 + 1, K11 + 1, K12 + 1, K13, K14, K16, K17 + 1, K18 + 1, K19 + 1, K20 + 1, K21, K22 + 1, K23 + 1, K24 + 1, K25, K26, K27, K28 + 1, K29, K30 + 1, K31, K32, K33, K34, K35 + 1, K36 + 1, K37 + 1, K38 + 1, K39, K40, K41 + 1, K42 + 1, K43 + 1, K44 + 1, K45, K46 + 1, K47 + 1]

Duplicate of #12655

Attachments (1)

trac_10340_error_msg.patch (3.5 KB) - added by malb 10 years ago.

Download all attachments as: .zip

Change History (9)

Changed 10 years ago by malb

comment:1 Changed 10 years ago by malb

  • Authors Stas Bulygin deleted
  • Cc PolyBoRi added
  • Component changed from cryptography to commutative algebra
  • Priority changed from minor to major
  • Status changed from new to needs_work

The error occurs because PolyBori? -- when eliminating some variables from the system -- attempts to create a ring with zero variables. This also explains why your second system works.

I removed that check from our wrapper, but that doesn't only makes the code fail later. Michael, should PolyBoRi? support rings with zero variables or not? In either case I think this is a bug in the upstream code.

In the process of looking into this I noticed that the error message was wrong. I fixed that in the attached patch.

PS: The author field is used to indicate who wrote the patch to fix the issue.

comment:2 Changed 10 years ago by malb

  • Cc AlexanderDreyer added

comment:3 follow-up: Changed 9 years ago by malb

This issue is fixed, I just tried it with 4.8. I suggest to close it.

comment:4 in reply to: ↑ 3 Changed 9 years ago by AlexanderDreyer

Replying to malb:

This issue is fixed, I just tried it with 4.8. I suggest to close it.

Indeed, that issue was resolved, for some reason the ticket got out of scope.

comment:5 Changed 9 years ago by AlexanderDreyer

  • Description modified (diff)
  • Status changed from needs_work to positive_review

Duplicate of #12655 (maybe even fixed earlier). Abusing "positive review".

comment:6 Changed 9 years ago by AlexanderDreyer

  • Description modified (diff)

comment:7 Changed 9 years ago by AlexanderDreyer

  • Milestone set to sage-duplicate/invalid/wontfix
  • Reviewers set to Alexander Dreyer

comment:8 Changed 9 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.