Overflow in conversion of polynomials in large characteristic to SymbolicRing

[pbruin]

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³¹.

[rws]

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

[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).

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

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

[jdemeyer]

New commits:

​fb9ddc3	In py_get_parent_char(), return 3 if characteristic is > 2
​2c0ea8f	This test takes about 30s

[rws]

A fine solution to the problem, and it passes make ptestlong.