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:

Status badges

Description (last modified by jdemeyer)

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

Change History (10)

comment:1 follow-up: Changed 6 years ago by rws

Any nonzero characteristics computation with symbolics is broken, and rightly so.

comment:2 in reply to: ↑ 1 Changed 6 years ago by pbruin

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 rws

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 jdemeyer

  • Description modified (diff)

comment:5 Changed 6 years ago by jdemeyer

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 jdemeyer

  • Authors set to Jeroen Demeyer

comment:7 Changed 6 years ago by jdemeyer

  • Branch set to u/jdemeyer/overflow_in_conversion_of_polynomials_in_large_characteristic_to_symbolicring

comment:8 Changed 6 years ago by jdemeyer

  • Commit set to 2c0ea8fc2660bbd0dde7e4f98c800e4b664fbaa0
  • Status changed from new to needs_review

New commits:

fb9ddc3In py_get_parent_char(), return 3 if characteristic is > 2
2c0ea8fThis test takes about 30s

comment:9 Changed 6 years ago by rws

  • 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 vbraun

  • 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
Note: See TracTickets for help on using tickets.