Opened 6 years ago
Closed 6 years ago
#21187 closed defect (fixed)
Overflow in conversion of polynomials in large characteristic to SymbolicRing
Reported by: | pbruin | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.4 |
Component: | symbolics | Keywords: | symbolic overflow |
Cc: | Merged in: | ||
Authors: | Jeroen Demeyer | Reviewers: | Ralf Stephan |
Report Upstream: | N/A | Work issues: | |
Branch: | 2c0ea8f (Commits, GitHub, GitLab) | Commit: | 2c0ea8fc2660bbd0dde7e4f98c800e4b664fbaa0 |
Dependencies: | Stopgaps: |
Description (last modified by )
Found while looking at #21186, but apparently unrelated:
sage: SR(polygen(FiniteField(next_prime(2^31)), 'y')) --------------------------------------------------------------------------- OverflowError Traceback (most recent call last) <ipython-input-2-21e732b29857> in <module>() ----> 1 SR(polygen(FiniteField(next_prime(Integer(2)**Integer(31))), 'y')) /usr/local/src/sage-config/src/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9896)() 1105 if mor is not None: 1106 if no_extra_args: -> 1107 return mor._call_(x) 1108 else: 1109 return mor._call_with_args(x, args, kwds) /usr/local/src/sage-config/src/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.NamedConvertMap._call_ (build/cythonized/sage/structure/coerce_maps.c:6048)() 236 raise TypeError("Cannot coerce {} to {}".format(x, C)) 237 cdef Map m --> 238 cdef Element e = method(C) 239 if e is None: 240 raise RuntimeError("BUG in coercion model: {} method of {} returned None".format(self.method_name, type(x))) /usr/local/src/sage-config/src/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial._symbolic_ (build/cythonized/sage/rings/polynomial/polynomial_element.c:13107)() 1232 """ 1233 d = dict([(repr(g), R.var(g)) for g in self.parent().gens()]) -> 1234 return self.subs(**d) 1235 1236 def __invert__(self): /usr/local/src/sage-config/src/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.subs (build/cythonized/sage/rings/polynomial/polynomial_element.c:7984)() 436 raise TypeError("keys do not match self's parent") 437 return self --> 438 return self(*x, **kwds) 439 substitute = subs 440 /usr/local/src/sage-config/src/sage/rings/polynomial/polynomial_zmod_flint.pyx in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint.__call__ (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:15615)() 316 nmod_poly_compose(&t.x, &self.x, &y.x) 317 return t --> 318 return Polynomial.__call__(self, *x, **kwds) 319 320 @coerce_binop /usr/local/src/sage-config/src/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.__call__ (build/cythonized/sage/rings/polynomial/polynomial_element.c:8987)() 751 752 try: --> 753 return a._evaluate_polynomial(pol) 754 except (AttributeError, NotImplementedError): 755 pass /usr/local/src/sage-config/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression._evaluate_polynomial (build/cythonized/sage/symbolic/expression.cpp:37929)() 6739 except TypeError: 6740 zero = self._parent.zero() -> 6741 return zero.add(*(pol[i]*self**i 6742 for i in xrange(pol.degree() + 1))) 6743 def collect_common_factors(self): /usr/local/src/sage-config/src/sage/symbolic/expression.pyx in genexpr (build/cythonized/sage/symbolic/expression.cpp:37696)() 6739 except TypeError: 6740 zero = self._parent.zero() -> 6741 return zero.add(*(pol[i]*self**i 6742 for i in xrange(pol.degree() + 1))) 6743 def collect_common_factors(self): /usr/local/src/sage-config/src/sage/structure/element.pyx in sage.structure.element.RingElement.__mul__ (build/cythonized/sage/structure/element.c:15549)() 1681 1682 sage: parent(QQ(1)*matrix(ZZ['x'],2,2,[1,2,3,4])) -> 1683 Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in x over Rational Field 1684 sage: parent(ZZ['x'](1)*matrix(QQ,2,2,[1,2,3,4])) 1685 Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in x over Rational Field /usr/local/src/sage-config/src/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel_cache_maps.bin_op (build/cythonized/sage/structure/coerce.c:8887)() 1037 try: 1038 xy = self.canonical_coercion(x,y) -> 1039 return PyObject_CallObject(op, xy) 1040 except TypeError as err: 1041 if xy is not None: /usr/local/src/sage-config/src/sage/structure/element.pyx in sage.structure.element.RingElement.__mul__ (build/cythonized/sage/structure/element.c:15438)() 1676 Full MatrixSpace of 2 by 2 dense matrices over Rational Field 1677 sage: parent(ZZ(1)*matrix(QQ,2,2,[1,2,3,4])) -> 1678 Full MatrixSpace of 2 by 2 dense matrices over Rational Field 1679 sage: parent(QQ(1)*matrix(QQ,2,2,[1,2,3,4])) 1680 Full MatrixSpace of 2 by 2 dense matrices over Rational Field /usr/local/src/sage-config/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression._mul_ (build/cythonized/sage/symbolic/expression.cpp:21453)() 3209 o) 3210 else: -> 3211 x = gmul(left._gobj, _right._gobj) 3212 return new_Expression_from_GEx(left._parent, x) 3213 /usr/local/src/sage-config/src/sage/symbolic/pynac.pyx in sage.symbolic.pynac.py_get_parent_char (build/cythonized/sage/symbolic/pynac.cpp:7984)() 750 cdef int py_get_parent_char(object o) except -1: 751 if isinstance(o, Element): --> 752 return (<Element>o)._parent.characteristic() 753 else: 754 return 0 OverflowError: value too large to convert to int
The underlying reason is that the function py_get_parent_char
returns a C int
, so it cannot represent numbers larger than 2^{31}.
Change History (10)
comment:1 follow-up: ↓ 2 Changed 6 years ago by
comment:2 in reply to: ↑ 1 Changed 6 years ago by
Replying to rws:
Any nonzero characteristics computation with symbolics is broken, and rightly so.
That is perfectly fine with me, as long as it is for mathematical (not programming) reasons. Also, it should be made clear to the user that this is not supported. Currently, one can do
a = SR(Mod(3, 5))
which does seem to behave as expected (e.g. (a*x)^2
returns 4*x^2
, and multiplying this by 5 returns 0).
comment:3 Changed 6 years ago by
I'm not the algebraist to make the mathematical case but I strongly suspect there is one. Of course programming plays a role in that the more we tried to support nonzero characteristics in Pynac the odder were the possible problems. It calls for a structured, i.e., algebraic approach, and symbolics do not mix with that.
The easy cases were implemented but see #18787.
What is needed for a clear error is that someone opens a ticket for it.
comment:4 Changed 6 years ago by
- Description modified (diff)
comment:5 Changed 6 years ago by
Reading the code from Pynac, it seems that it only differentiates between
- characteristic 0
- characteristic 2
- characteristic >2
So returning "3" might actually fix the problem.
comment:6 Changed 6 years ago by
comment:7 Changed 6 years ago by
- Branch set to u/jdemeyer/overflow_in_conversion_of_polynomials_in_large_characteristic_to_symbolicring
comment:8 Changed 6 years ago by
- Commit set to 2c0ea8fc2660bbd0dde7e4f98c800e4b664fbaa0
- Status changed from new to needs_review
comment:9 Changed 6 years ago by
- Reviewers set to Ralf Stephan
- Status changed from needs_review to positive_review
A fine solution to the problem, and it passes make ptestlong
.
comment:10 Changed 6 years ago by
- Branch changed from u/jdemeyer/overflow_in_conversion_of_polynomials_in_large_characteristic_to_symbolicring to 2c0ea8fc2660bbd0dde7e4f98c800e4b664fbaa0
- Resolution set to fixed
- Status changed from positive_review to closed
Any nonzero characteristics computation with symbolics is broken, and rightly so.