#8992: Coercion of univariate quotient polynomial rings
-------------------------+--------------------------------------------------
Reporter: SimonKing | Owner: robertwb
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: coercion | Keywords: coercion quotient ring
Work_issues: | Upstream: N/A
Reviewer: PatchBot | Author: Simon King
Merged: | Dependencies:
-------------------------+--------------------------------------------------
Changes (by SimonKing):
* status: needs_work => needs_review
* work_issues: rewrite, make polynomial division work =>
Old description:
> Consider the following setting:
> {{{
> sage: P.<x> = QQ[]
> sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])
> sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])
> }}}
>
> The gcd of the moduli is {{{(x^2+1)^2}}}, and so it should be true that
> the pushout of Q1 and Q2 is the quotient ring with this gcd as modulus.
> Currently, the pushout raises an error, but with #8800 one has:
> {{{
> sage: from sage.categories.pushout import pushout
> sage: Q = pushout(Q1,Q2); Q
> Univariate Quotient Polynomial Ring in xbar over Rational Field with
> modulus x^4 + 2*x^2 + 1
> }}}
>
> However, there remain two bugs that are not covered in #8800 and that
> prevent a proper coercion of Q1 and Q2.
>
> First bug:
> {{{
> sage: Q.has_coerce_map_from(Q1)
> False
> sage: Q.has_coerce_map_from(Q2)
> False
> }}}
>
> Second bug:
> {{{
> sage: Q(Q1.gen())
> ERROR: An unexpected error occurred while tokenizing input
> The following traceback may be corrupted or invalid
> The error message is: ('EOF in multi-line statement', (932, 0))
>
> ERROR: An unexpected error occurred while tokenizing input
> The following traceback may be corrupted or invalid
> The error message is: ('EOF in multi-line statement', (932, 0))
>
> ---------------------------------------------------------------------------
> TypeError Traceback (most recent call
> last)
>
> /home/king/SAGE/sage-4.3.1/devel/<ipython console> in <module>()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/polynomial/polynomial_quotient_ring.pyc in
> __call__(self, x)
> 272 return PolynomialQuotientRingElement(self,
> self.__ring(x.lift()), check=False)
> 273 return PolynomialQuotientRingElement(
> --> 274 self, self.__ring(x) , check=True)
> 275
> 276 def _is_valid_homomorphism_(self, codomain, im_gens):
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/parent.so in
> sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6332)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3108)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3010)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/polynomial/polynomial_ring.pyc in
> _element_constructor_(self, x, check, is_gen, construct, **kwds)
> 310 x = x.Polrev()
> 311
> --> 312 return C(self, x, check, is_gen, construct=construct,
> **kwds)
> 313
> 314 def is_integral_domain(self, proof = True):
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/polynomial/polynomial_element_generic.pyc in
> __init__(self, parent, x, check, is_gen, construct)
> 654
> 655 if check:
> --> 656 x = [QQ(z) for z in x]
> 657
> 658 self.__list = list(x)
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/parent.so in
> sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6332)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3108)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3010)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/rational.so in sage.rings.rational.Rational.__init__
> (sage/rings/rational.c:5781)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/rational.so in
> sage.rings.rational.Rational.__set_value (sage/rings/rational.c:7052)()
>
> TypeError: Unable to coerce xbar (<class
> 'sage.rings.polynomial.polynomial_quotient_ring_element.PolynomialQuotientRingElement'>)
> to Rational
> sage: Q.gen()
> xbar
> }}}
>
> It could be that the following is an additional bug, but perhaps it is
> just a special case of the previous:
> {{{
> sage: Q(str(Q.gen()))
> ERROR: An unexpected error occurred while tokenizing input
> The following traceback may be corrupted or invalid
> The error message is: ('EOF in multi-line statement', (932, 0))
>
> ERROR: An unexpected error occurred while tokenizing input
> The following traceback may be corrupted or invalid
> The error message is: ('EOF in multi-line statement', (932, 0))
>
> ---------------------------------------------------------------------------
> TypeError Traceback (most recent call
> last)
>
> /home/king/SAGE/sage-4.3.1/devel/<ipython console> in <module>()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/polynomial/polynomial_quotient_ring.pyc in
> __call__(self, x)
> 272 return PolynomialQuotientRingElement(self,
> self.__ring(x.lift()), check=False)
> 273 return PolynomialQuotientRingElement(
> --> 274 self, self.__ring(x) , check=True)
> 275
> 276 def _is_valid_homomorphism_(self, codomain, im_gens):
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/parent.so in
> sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6332)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3108)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3010)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/polynomial/polynomial_ring.pyc in
> _element_constructor_(self, x, check, is_gen, construct, **kwds)
> 297 R = self.base_ring()
> 298 p = Parser(Integer, R,
> LookupNameMaker({self.variable_name(): self.gen()}, R))
> --> 299 return self(p.parse(x))
> 300 except NameError:
> 301 raise TypeError,"Unable to coerce string"
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.parse
> (sage/misc/parser.c:3481)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.parse
> (sage/misc/parser.c:3345)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.p_eqn
> (sage/misc/parser.c:5136)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.p_expr
> (sage/misc/parser.c:5456)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.p_term
> (sage/misc/parser.c:5681)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.p_factor
> (sage/misc/parser.c:6044)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.p_power
> (sage/misc/parser.c:6158)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.Parser.p_atom
> (sage/misc/parser.c:6711)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/misc/parser.so in sage.misc.parser.LookupNameMaker.__call__
> (sage/misc/parser.c:7653)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/parent.so in
> sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6332)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3108)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/structure/coerce_maps.so in
> sage.structure.coerce_maps.DefaultConvertMap_unique._call_
> (sage/structure/coerce_maps.c:3010)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/rational.so in sage.rings.rational.Rational.__init__
> (sage/rings/rational.c:5781)()
>
> /home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
> packages/sage/rings/rational.so in
> sage.rings.rational.Rational.__set_value (sage/rings/rational.c:6517)()
>
> TypeError: unable to convert xbar to a rational
> }}}
New description:
Consider the following setting:
{{{
sage: P.<x> = QQ[]
sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])
sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])
}}}
The gcd of the moduli is {{{(x^2+1)^2}}}, and so it should be true that
the pushout of Q1 and Q2 is the quotient ring with this gcd as modulus.
Currently, the pushout raises an error, but with #8800 one has:
{{{
sage: from sage.categories.pushout import pushout
sage: Q = pushout(Q1,Q2); Q
Univariate Quotient Polynomial Ring in xbar over Rational Field with
modulus x^4 + 2*x^2 + 1
}}}
However, there remain two bugs that are not covered in #8800 and that
prevent a proper coercion of Q1 and Q2.
First bug:
{{{
sage: Q.has_coerce_map_from(Q1)
False
sage: Q.has_coerce_map_from(Q2)
False
}}}
Second bug:
{{{
sage: Q(Q1.gen())
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (932, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (932, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/home/king/SAGE/sage-4.3.1/devel/<ipython console> in <module>()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/polynomial/polynomial_quotient_ring.pyc in
__call__(self, x)
272 return PolynomialQuotientRingElement(self,
self.__ring(x.lift()), check=False)
273 return PolynomialQuotientRingElement(
--> 274 self, self.__ring(x) , check=True)
275
276 def _is_valid_homomorphism_(self, codomain, im_gens):
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__
(sage/structure/parent.c:6332)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3108)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3010)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/polynomial/polynomial_ring.pyc in
_element_constructor_(self, x, check, is_gen, construct, **kwds)
310 x = x.Polrev()
311
--> 312 return C(self, x, check, is_gen, construct=construct,
**kwds)
313
314 def is_integral_domain(self, proof = True):
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/polynomial/polynomial_element_generic.pyc in
__init__(self, parent, x, check, is_gen, construct)
654
655 if check:
--> 656 x = [QQ(z) for z in x]
657
658 self.__list = list(x)
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__
(sage/structure/parent.c:6332)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3108)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3010)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/rational.so in sage.rings.rational.Rational.__init__
(sage/rings/rational.c:5781)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/rational.so in
sage.rings.rational.Rational.__set_value (sage/rings/rational.c:7052)()
TypeError: Unable to coerce xbar (<class
'sage.rings.polynomial.polynomial_quotient_ring_element.PolynomialQuotientRingElement'>)
to Rational
sage: Q.gen()
xbar
}}}
It could be that the following is an additional bug, but perhaps it is
just a special case of the previous:
{{{
sage: Q(str(Q.gen()))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (932, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (932, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/home/king/SAGE/sage-4.3.1/devel/<ipython console> in <module>()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/polynomial/polynomial_quotient_ring.pyc in
__call__(self, x)
272 return PolynomialQuotientRingElement(self,
self.__ring(x.lift()), check=False)
273 return PolynomialQuotientRingElement(
--> 274 self, self.__ring(x) , check=True)
275
276 def _is_valid_homomorphism_(self, codomain, im_gens):
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__
(sage/structure/parent.c:6332)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3108)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3010)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/polynomial/polynomial_ring.pyc in
_element_constructor_(self, x, check, is_gen, construct, **kwds)
297 R = self.base_ring()
298 p = Parser(Integer, R,
LookupNameMaker({self.variable_name(): self.gen()}, R))
--> 299 return self(p.parse(x))
300 except NameError:
301 raise TypeError,"Unable to coerce string"
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.parse
(sage/misc/parser.c:3481)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.parse
(sage/misc/parser.c:3345)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.p_eqn
(sage/misc/parser.c:5136)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.p_expr
(sage/misc/parser.c:5456)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.p_term
(sage/misc/parser.c:5681)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.p_factor
(sage/misc/parser.c:6044)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.p_power
(sage/misc/parser.c:6158)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.Parser.p_atom
(sage/misc/parser.c:6711)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/misc/parser.so in sage.misc.parser.LookupNameMaker.__call__
(sage/misc/parser.c:7653)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__
(sage/structure/parent.c:6332)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3108)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/structure/coerce_maps.so in
sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3010)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/rational.so in sage.rings.rational.Rational.__init__
(sage/rings/rational.c:5781)()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-
packages/sage/rings/rational.so in
sage.rings.rational.Rational.__set_value (sage/rings/rational.c:6517)()
TypeError: unable to convert xbar to a rational
}}}
Apply [attachment:trac8992_conversion_polynomial_quotient_ring.patch]
--
Comment:
I have produced a new patch.
Recall that most problems mentioned in the ticket description have already
been solved in sage-5.0.beta7. The only remaining was conversion from
strings.
Here, I suggest to use a tool that I have introduced in my code for
infinite polynomial rings: It is a generalisation of the gens_dict of
polynomial rings. In contrast to gens_dict, it not only considers the
generator names of the ring, but it also considers (recursively) the
generator names of the base ring. This recursive version of gens_dict is
then passed to sage_eval.
Hence, if Q has generator 'xbar' and is the quotient ring of some
polynomial ring P with generator 'x', then `Q('x*xbar')` will be correctly
evaluated as `P.gen()*Q.gen()`, which in turn evaluates as
`Q(P.gen())*Q.gen()`.
Concerning the problem with `y.divides(...)`: The problem can arise, if Q1
and Q2 are two polynomial quotient rings and one asks
`Q1.has_coerce_map_from(Q2)`. It will try to divide the moduli of Q1 and
Q2. My suggestion is: If that division fails with an error, then there is
no coerce map.
After these changes, the tests in
sage/rings/polynomial/polynomial_quotient_ring.py and
.../polynomial_quotient_ring_element.py pass.
Let's see if the patchbot finds a reason to complain...
Apply trac8992_conversion_polynomial_quotient_ring.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8992#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
