Ticket #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 | Work issues: | |
| Report Upstream: | N/A | Reviewers: | Alexander Dreyer |
| Authors: | Merged in: | ||
| Dependencies: | Stopgaps: |
Description (last modified by AlexanderDreyer) (diff)
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
-
trac_10340_error_msg.patch
(3.5 KB) -
added by malb 2 years ago.
Change History
comment:1 Changed 2 years ago by malb
- Cc PolyBoRi added
- Priority changed from minor to major
- Status changed from new to needs_work
- Component changed from cryptography to commutative algebra
- Authors Stas Bulygin deleted
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:3 follow-up: ↓ 4 Changed 14 months 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 14 months 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 11 months ago by AlexanderDreyer
- Status changed from needs_work to positive_review
- Description modified (diff)
Duplicate of #12655 (maybe even fixed earlier). Abusing "positive review".
Note: See
TracTickets for help on using
tickets.
