Sage: Ticket #11239: Incorrect coercion of polynomials over finite fields
https://trac.sagemath.org/ticket/11239
<p>
Trying to coerce a polynomial over a finite field into a polynomial ring over a bigger field gives a bogus result:
</p>
<pre class="wiki">sage: Fq.<a> = GF(5^2)
sage: Fqq.<b> = GF(5^4)
sage: f = Fq['x'].random_element(); f
3*x^2 + (a + 4)*x + 2*a + 4
sage: Fqq['y'](f)
3*y^2 + (b + 4)*y + 2*b + 4
</pre><p>
In this example, Sage simply replaces every ‘a’ with ‘b’, but a is not b. If we coerce directly from Fq to Fqq, we get a <code>NotImplementedError</code>, which is unfortunate but in any case not incorrect. ;).
</p>
<pre class="wiki">sage: Fqq(a)
…
/usr/local/share/sage/sage/local/lib/python2.6/site-packages/sage/rings/finite_rings/finite_field_givaro.pyc in _coerce_map_from_(self, R)
348 elif self.degree() % R.degree() == 0:
349 # This is where we *would* do coercion from one nontrivial finite field to another...
--> 350 raise NotImplementedError
351
352 def gen(self, n=0):
NotImplementedError:
</pre><p>
Use git branch.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11239
Trac 1.1.6johanbosmanFri, 22 Apr 2011 16:47:13 GMTdescription changed
https://trac.sagemath.org/ticket/11239#comment:1
https://trac.sagemath.org/ticket/11239#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11239?action=diff&version=1">diff</a>)
</li>
</ul>
TicketfwclarkeSat, 23 Apr 2011 08:11:14 GMTdescription changed
https://trac.sagemath.org/ticket/11239#comment:2
https://trac.sagemath.org/ticket/11239#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11239?action=diff&version=2">diff</a>)
</li>
</ul>
<blockquote class="citation">
<p>
If we coerce directly from Fq to Fqq, we get a <code>NotImplementedError</code>, which is unfortunate ...
</p>
</blockquote>
<p>
It is, however, difficult to see how this could be done, because there are, in this case, two embeddings of the smaller field in the larger, neither of which can be distinguished from the other:
</p>
<pre class="wiki">sage: Fq.<a> = GF(5^2); Fqq.<b> = GF(5^4)
sage: Hom(Fq, Fqq).list()
[
Ring morphism:
From: Finite Field in a of size 5^2
To: Finite Field in b of size 5^4
Defn: a |--> 4*b^3 + 4*b^2 + 4*b + 3,
Ring morphism:
From: Finite Field in a of size 5^2
To: Finite Field in b of size 5^4
Defn: a |--> b^3 + b^2 + b + 3
]
</pre><p>
since
</p>
<pre class="wiki">sage: a.minimal_polynomial().roots(ring=F625, multiplicities=False)
[4*b^3 + 4*b^2 + 4*b + 3, b^3 + b^2 + b + 3]
</pre><p>
As for the polynomial coercion, this is seriously damaged. Bogus results are produced even when the characteristics are different. I have tracked the problem down to the following, but haven't been able to get further.
</p>
<pre class="wiki">sage: Fq.<a> = GF(2^4); Fqq.<b> = GF(3^7)
sage: PFq.<x> = Fq[]; PFqq.<y> = Fqq[]
sage: f = x^3 + (a^3 + 1)*x
sage: sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX(PFqq, f)
y^3 + (b^3 + 1)*y
</pre>
TicketdkrennWed, 19 Oct 2011 08:56:36 GMTstatus changed
https://trac.sagemath.org/ticket/11239#comment:3
https://trac.sagemath.org/ticket/11239#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
</ul>
<p>
It seems that everything that can be represented as polynomial is converted in that way. The phenomenon also appears with quotient rings:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: A.<a> = R.quotient(x^3+2); PA.<s> = A[]
sage: B.<b> = R.quotient(x^5+3); PB.<t> = B[]
sage: f = a*s^3 + a^2*s; f
a*s^3 + a^2*s
sage: PB(f)
b*t^3 + b^2*t
</pre><p>
One way to solve this problem would be to check whether the coefficients of one polynomial rings can be converted (coerced) to the other...
</p>
TicketSimonKingMon, 24 Oct 2011 11:03:38 GMT
https://trac.sagemath.org/ticket/11239#comment:4
https://trac.sagemath.org/ticket/11239#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:3" title="Comment 3">dkrenn</a>:
</p>
<blockquote class="citation">
<p>
One way to solve this problem would be to check whether the coefficients of one polynomial rings can be converted (coerced) to the other...
</p>
</blockquote>
<p>
I would strongly advice against the attempt to solve it on the level of conversion.
</p>
<p>
I know that at least some classes of polynomial rings are still following the old coercion model, and am preparing a patch that is supposed to fix that. According to the new model, there should be a method <code>_element_constructor_</code> that does the conversion, and a separate <code>_coerce_map_from_</code>, that determines whether there is a coercion (not just a conversion).
</p>
<p>
I think that it is ok to have that bogus conversion - as long as it is not used as a coercion. One could, of course, try to throw an error when doing a conversion in the case that there is no fixed embedding of the base rings. However, testing it <em>repeatedly</em>, that's to say testing it <em>for each individual polynomial to be converted</em>, sounds like a waste of computation time to me.
</p>
TicketpbruinSat, 13 Jul 2013 21:51:15 GMTcc set
https://trac.sagemath.org/ticket/11239#comment:5
https://trac.sagemath.org/ticket/11239#comment:5
<ul>
<li><strong>cc</strong>
<em>pbruin</em> added
</li>
</ul>
TicketpbruinMon, 05 Aug 2013 16:19:32 GMT
https://trac.sagemath.org/ticket/11239#comment:6
https://trac.sagemath.org/ticket/11239#comment:6
<p>
If in the example in the ticket description, one replaces
</p>
<pre class="wiki">sage: Fqq['y'](f)
</pre><p>
by
</p>
<pre class="wiki">sage: Fqq['y']._coerce_(f)
</pre><p>
one at least gets a sensible error:
</p>
<pre class="wiki">TypeError: no canonical coercion from Univariate Polynomial Ring in x over Finite Field in a of size 5^2 to Univariate Polynomial Ring in y over Finite Field in b of size 5^4
</pre><p>
I tried the same example using the compatible finite fields from <a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a>. The problem (that the coefficients are converted in the stupid way) persists, both for conversion and for coercion. This is surprising, because in that case there <em>is</em> a coercion map between the finite fields.
</p>
TicketpbruinMon, 05 Aug 2013 17:51:42 GMT
https://trac.sagemath.org/ticket/11239#comment:7
https://trac.sagemath.org/ticket/11239#comment:7
<p>
The problem lies in the <em>NTL implementation</em> of polynomials over finite fields. (Edit: this was already discovered in <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:2" title="Comment 2">comment:2</a> above.) This is the default implementation for polynomials over finite fields, even though the fields themselves are only implemented via NTL in characteristic 2, and via Givaro or PARI otherwise.
</p>
<p>
The following example demonstrates this (after applying <a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a> plus a patch that I will upload shortly):
</p>
<pre class="wiki">sage: K.<a> = GF(5^2, conway=True, prefix='z')
sage: L.<b> = GF(5^4, conway=True, prefix='z')
sage: type(K)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: R = PolynomialRing(K, 'x', implementation='NTL')
sage: S = PolynomialRing(L, 'x', implementation='NTL')
sage: f = R.gen() + a; f
x + a
sage: type(f)
<type 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>
sage: S(f)
x + b
sage: R = PolynomialRing(K, 'x', implementation='generic')
sage: S = PolynomialRing(L, 'x', implementation='generic')
sage: f = R.gen() + a; f
x + a
sage: type(f)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_field'>
sage: S(f)
x + b^3 + b^2 + b + 3
</pre>
TicketpbruinMon, 05 Aug 2013 17:56:50 GMTstatus, description changed; dependencies, author set; cc deleted
https://trac.sagemath.org/ticket/11239#comment:8
https://trac.sagemath.org/ticket/11239#comment:8
<ul>
<li><strong>cc</strong>
<em>pbruin</em> removed
</li>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_work</em>
</li>
<li><strong>dependencies</strong>
set to <em>#8335</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11239?action=diff&version=8">diff</a>)
</li>
<li><strong>author</strong>
set to <em>pbruin</em>
</li>
</ul>
TicketpbruinMon, 05 Aug 2013 18:05:19 GMT
https://trac.sagemath.org/ticket/11239#comment:9
https://trac.sagemath.org/ticket/11239#comment:9
<p>
At this point there are two possible solutions:
</p>
<ul><li>either fix the NTL polynomial constructor,
</li><li>or make the generic polynomial constructor coerce the coefficients if necessary, and make the NTL polynomial constructor raise an error if it is given a polynomial over a smaller finite field.
</li></ul><p>
The first solution would be preferable in principle, but certainly harder and maybe even unreasonable, since the NTL polynomial constructor is a lower-level thing that should not have to care about maps between non-trivial finite fields.
</p>
TicketpbruinMon, 05 Aug 2013 19:55:30 GMT
https://trac.sagemath.org/ticket/11239#comment:10
https://trac.sagemath.org/ticket/11239#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:3" title="Comment 3">dkrenn</a>:
</p>
<blockquote class="citation">
<p>
It seems that everything that can be represented as polynomial is converted in that way. The phenomenon also appears with quotient rings:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: A.<a> = R.quotient(x^3+2); PA.<s> = A[]
sage: B.<b> = R.quotient(x^5+3); PB.<t> = B[]
sage: f = a*s^3 + a^2*s; f
a*s^3 + a^2*s
sage: PB(f)
b*t^3 + b^2*t
</pre></blockquote>
<p>
Debatable as it may seem, this is the behaviour currently described in the documentation of <code>PolynomialQuotientRing_generic._element_constructor_()</code>. Attempting a coercion (<code>PB.coerce(f)</code>) instead of a conversion (<code>PB(f)</code>) does lead to
</p>
<pre class="wiki">TypeError: no canonical coercion from Univariate Polynomial Ring in s over Univariate Quotient Polynomial Ring in a over Integer Ring with modulus x^3 + 2 to Univariate Polynomial Ring in t over Univariate Quotient Polynomial Ring in b over Integer Ring with modulus x^5 + 3
</pre><p>
as expected.
</p>
TicketpbruinMon, 05 Aug 2013 23:30:41 GMTattachment set
https://trac.sagemath.org/ticket/11239
https://trac.sagemath.org/ticket/11239
<ul>
<li><strong>attachment</strong>
set to <em>trac_11239-polynomial_zz_pex.patch</em>
</li>
</ul>
<p>
fix coercion of polynomials over finite fields
</p>
TicketpbruinMon, 05 Aug 2013 23:37:52 GMTstatus, description changed
https://trac.sagemath.org/ticket/11239#comment:11
https://trac.sagemath.org/ticket/11239#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11239?action=diff&version=11">diff</a>)
</li>
</ul>
<p>
Fixing the NTL polynomial constructor turned out to be easy. With the second patch, polynomials over compatible finite fields (<a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a>) coerce correctly, and trying to convert polynomials over non-compatible finite fields raises a <code>TypeError</code>, as it should.
</p>
TicketpbruinMon, 05 Aug 2013 23:39:33 GMTauthor changed
https://trac.sagemath.org/ticket/11239#comment:12
https://trac.sagemath.org/ticket/11239#comment:12
<ul>
<li><strong>author</strong>
changed from <em>pbruin</em> to <em>Peter Bruin</em>
</li>
</ul>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/11239#comment:13
https://trac.sagemath.org/ticket/11239#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketjpfloriThu, 26 Sep 2013 18:04:51 GMTkeywords changed; cc set
https://trac.sagemath.org/ticket/11239#comment:14
https://trac.sagemath.org/ticket/11239#comment:14
<ul>
<li><strong>keywords</strong>
<em>sd53</em> added
</li>
<li><strong>cc</strong>
<em>jpflori</em> added
</li>
</ul>
<p>
Just stumbled upon that bug while playing with finite fields.
This is really a nice bug.
</p>
TicketpbruinSat, 02 Nov 2013 19:24:12 GMTattachment set
https://trac.sagemath.org/ticket/11239
https://trac.sagemath.org/ticket/11239
<ul>
<li><strong>attachment</strong>
set to <em>trac_11239-polynomial_coercion_preliminary.patch</em>
</li>
</ul>
<p>
update (old version had bogus doctest fix)
</p>
TicketlftaberaSat, 21 Dec 2013 12:54:14 GMT
https://trac.sagemath.org/ticket/11239#comment:15
https://trac.sagemath.org/ticket/11239#comment:15
<p>
Peter, have you considered the impact of using has_coerce_map on the level of conversion? memory and time consumption.
</p>
TicketpbruinSat, 21 Dec 2013 14:58:17 GMT
https://trac.sagemath.org/ticket/11239#comment:16
https://trac.sagemath.org/ticket/11239#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:15" title="Comment 15">lftabera</a>:
</p>
<blockquote class="citation">
<p>
Peter, have you considered the impact of using has_coerce_map on the level of conversion? memory and time consumption.
</p>
</blockquote>
<p>
Not really; my first priority was to get correct behaviour, preferably in a clean way. The cause of this bug appears to be precisely that the conversion currently doesn't check if a coercion exists. Do you have an example in which this patch is too inefficient?
</p>
TicketjpfloriWed, 25 Dec 2013 15:53:14 GMT
https://trac.sagemath.org/ticket/11239#comment:17
https://trac.sagemath.org/ticket/11239#comment:17
<p>
I agree with Peter.
Let's get somethig correct first.
The current behavior is just non sense and prone to horrible errors in computations.
We can speed it up later rather than let this bitrot forever.
</p>
TicketjpfloriTue, 31 Dec 2013 10:34:27 GMTstatus, description changed; reviewer, branch, commit set
https://trac.sagemath.org/ticket/11239#comment:18
https://trac.sagemath.org/ticket/11239#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jean-Pierre Flori</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11239?action=diff&version=18">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>u/jpflori/ticket/11239</em>
</li>
<li><strong>commit</strong>
set to <em>236effb6198c6192dce0cedc0e53423c68743e3e</em>
</li>
</ul>
<p>
Anyway, the coercion framework is already called in the previous test so efficiency is already potentially screwed up.
</p>
<p>
I've just made a git branch from the patch.
Otherwise looks good to me, positive review.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=236effb"><span class="icon"></span>236effb</a></td><td><code>Trac 11239: fix coercion of polynomials over finite fields</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e46d9bf"><span class="icon"></span>e46d9bf</a></td><td><code>Trac 11239: fix coercion of polynomials over finite fields, first step</code>
</td></tr></table>
TicketjpfloriTue, 31 Dec 2013 10:51:00 GMT
https://trac.sagemath.org/ticket/11239#comment:19
https://trac.sagemath.org/ticket/11239#comment:19
<p>
In the doc about the coercion framework, it's written that a conversion is not supposed to make mathematical sense, but in this case I feel it's really conterintuitive and prone to errors to let L(f) just replace the generator of a finite field with another one, especially when another conversion/coercion makes sense, whence the need for this ticket...
</p>
<p>
If someone thinks the solution is overkill and goes against the coercion model philosophy, feel free to put the ticket back to another status.
</p>
TicketjpfloriTue, 31 Dec 2013 10:52:01 GMT
https://trac.sagemath.org/ticket/11239#comment:20
https://trac.sagemath.org/ticket/11239#comment:20
<p>
Not sure what to think about the quotients of univariate polynomial rings, except that it really feel akward.
</p>
TicketjpfloriTue, 31 Dec 2013 11:48:28 GMTstatus changed
https://trac.sagemath.org/ticket/11239#comment:21
https://trac.sagemath.org/ticket/11239#comment:21
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Maybe this is worth a broader discussion on sage-devel...
</p>
<p>
Especially, should we let the stupid conversion in when there is no coercion (as it seems to fit Sage's philosophy and it is in place for quotients)?
</p>
TicketjpfloriTue, 31 Dec 2013 11:59:28 GMT
https://trac.sagemath.org/ticket/11239#comment:22
https://trac.sagemath.org/ticket/11239#comment:22
<p>
Here you go:
</p>
<ul><li><a class="ext-link" href="https://groups.google.com/d/msg/sage-devel/Z4iNgVMFoms/HxIZ98edPk0J"><span class="icon"></span>https://groups.google.com/d/msg/sage-devel/Z4iNgVMFoms/HxIZ98edPk0J</a>
</li></ul>
TicketpbruinTue, 31 Dec 2013 12:35:39 GMT
https://trac.sagemath.org/ticket/11239#comment:23
https://trac.sagemath.org/ticket/11239#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:21" title="Comment 21">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Maybe this is worth a broader discussion on sage-devel...
</p>
</blockquote>
<p>
I think it is worth thinking about whether the "stupid" conversion should be allowed between different quotients of a polynomial ring. However, for the problem addressed in this ticket, there is really only one sensible thing to do, namely applying the canonical map between the base rings.
</p>
<blockquote class="citation">
<p>
Especially, should we let the stupid conversion in when there is no coercion (as it seems to fit Sage's philosophy and it is in place for quotients)?
</p>
</blockquote>
<p>
I personally think that allowing <code>Fqq['y'](f)</code> to 'desperately' apply any available conversion, however nonsensical it may be, to the coefficients is a bad idea. I don't see what is gained by permitting this notation; it seems to make it far too easy for the user to unwittingy introduce mysterious errors in this way. If someone really wants this behaviour, it is much better to require explicitly lifting the finite field elements to <strong>Z</strong>[<em>x</em>] or another suitable ring.
</p>
<p>
I would be in favour of a less permissive approach for conversions between different polynomial ring quotients as well, but again, this ticket is not the place to decide that.
</p>
TicketjpfloriTue, 31 Dec 2013 12:45:36 GMT
https://trac.sagemath.org/ticket/11239#comment:24
https://trac.sagemath.org/ticket/11239#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:23" title="Comment 23">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:21" title="Comment 21">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Maybe this is worth a broader discussion on sage-devel...
</p>
</blockquote>
<p>
I think it is worth thinking about whether the "stupid" conversion should be allowed between different quotients of a polynomial ring. However, for the problem addressed in this ticket, there is really only one sensible thing to do, namely applying the canonical map between the base rings.
</p>
</blockquote>
<p>
I agree.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Especially, should we let the stupid conversion in when there is no coercion (as it seems to fit Sage's philosophy and it is in place for quotients)?
</p>
</blockquote>
<p>
I personally think that allowing <code>Fqq['y'](f)</code> to 'desperately' apply any available conversion, however nonsensical it may be, to the coefficients is a bad idea. I don't see what is gained by permitting this notation; it seems to make it far too easy for the user to unwittingy introduce mysterious errors in this way. If someone really wants this behaviour, it is much better to require explicitly lifting the finite field elements to <strong>Z</strong>[<em>x</em>] or another suitable ring.
</p>
</blockquote>
<p>
I completely agree, whence my previous positive review.
But the doc for coercion kind of make me think, humm, maybe some people want the stupid behavior as well...
</p>
<blockquote class="citation">
<p>
I would be in favour of a less permissive approach for conversions between different polynomial ring quotients as well, but again, this ticket is not the place to decide that.
</p>
</blockquote>
<p>
I agree as well, I was just menitoning it because it's already mentioned here :)
</p>
<p>
Anyway, if nobody gives a strong opinion of why to keep conversions without any mathematical sense and confusing for naive users on sage-devel, then I'll put this back to positive review quickly as I think that the situation with this ticket is far better.
Note that maybe some efficiency could be gained by replacing the has_coerce_map_from by something else but I have no idea what to do now and no time to think about it, I'd just like to remove the stupid conversion unless someone convinces me to keep them of course.
</p>
TicketSimonKingTue, 31 Dec 2013 17:21:34 GMT
https://trac.sagemath.org/ticket/11239#comment:25
https://trac.sagemath.org/ticket/11239#comment:25
<p>
See my answer on sage-devel. In a nutshell: I would recommend against doing expensive tests when talking about conversion, and I would be rather permissive in conversions.
</p>
<p>
Conversions have no defined properties, and thus there is nothing that one could test. They don't need to be composable. They aren't even maps (only partially defined). It is perfectly fine to have a conversion for all elements of a ring R1 into a ring R2 and of all elements of a ring R2 into a ring R3, but only some elements (e.g.: polynomials of degree zero) of R1 convert into R3 without raising an error.
</p>
<p>
Please clearly distinguish between coercion and conversion. Coercions are morphisms. They are unique (for any pair of parents). They can be composed. The identity is a morphism (which together with the uniqueness and composability can imply the non-existence of certain coercions).
</p>
<p>
I only know of one rule for conversion: If there is a coercion then conversion must coincide with it. And since the rules for conversions are so relaxed, I don't see why one should do expensive tests before applying a conversion (in particular when one thinks that conversions are not defined parent-by-parent, but element-by-element).
</p>
TicketpbruinTue, 31 Dec 2013 18:11:47 GMT
https://trac.sagemath.org/ticket/11239#comment:26
https://trac.sagemath.org/ticket/11239#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:25" title="Comment 25">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
See my answer on sage-devel. In a nutshell: I would recommend against doing expensive tests when talking about conversion, and I would be rather permissive in conversions.
</p>
<p>
Conversions have no defined properties, and thus there is nothing that one could test.
</p>
</blockquote>
<p>
Given that a conversion needs to coincide with the coercion if the latter exists, one must check for a coercion before applying the "stupid" conversion (assuming the "stupid" conversion is desired at all).
</p>
<p>
In the situation of this ticket, there is a coercion map between the polynomial rings (assuming the finite fields know that they are compatible; see the doctests, not the ticket description). The problem was that the element constructor didn't check for this and always applied the "stupid" conversion. (The same problem arises when using <code>R.coerce(f)</code>, because the coercion map just defers to a conversion using the element constructor.)
</p>
<p>
I think the point in the above discussion was whether my solution of calling <code>has_coerce_map_from()</code> is expensive; I guess not, but even if it is, it is still necessary to guarantee compatibility of conversion and coercion.
</p>
<blockquote class="citation">
<p>
They don't need to be composable. They aren't even maps (only partially defined). It is perfectly fine to have a conversion for all elements of a ring R1 into a ring R2 and of all elements of a ring R2 into a ring R3, but only some elements (e.g.: polynomials of degree zero) of R1 convert into R3 without raising an error.
</p>
</blockquote>
<p>
That is actually what I was trying to say on sage-devel in the context of polynomial ring quotients, but I wasn't very clear. I agree that the existence of coercion doesn't have to be transitive, or to satisfy any rules; in the context of this ticket, I think it is perfectly fine if the "stupid" conversion is not used at all.
</p>
TicketSimonKingTue, 31 Dec 2013 19:15:03 GMT
https://trac.sagemath.org/ticket/11239#comment:27
https://trac.sagemath.org/ticket/11239#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:26" title="Comment 26">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:25" title="Comment 25">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
See my answer on sage-devel. In a nutshell: I would recommend against doing expensive tests when talking about conversion, and I would be rather permissive in conversions.
</p>
<p>
Conversions have no defined properties, and thus there is nothing that one could test.
</p>
</blockquote>
<p>
Given that a conversion needs to coincide with the coercion if the latter exists, one must check for a coercion before applying the "stupid" conversion (assuming the "stupid" conversion is desired at all).
</p>
</blockquote>
<p>
No!! It is just the other way around! Ideally, you have a fast cheap stupid conversion, and then a potentially expensive tests tells you whether this conversion qualifies as a coercion. This, by the way, is exactly what happens when <code>R._coerce_map_from_(S)</code> returns True: The return value asserts that the conversion qualifies as a coercion.
</p>
<blockquote class="citation">
<p>
That is actually what I was trying to say on sage-devel in the context of polynomial ring quotients, but I wasn't very clear. I agree that the existence of coercion doesn't have to be transitive, or to satisfy any rules;
</p>
</blockquote>
<p>
You mean, conversion, not coercion? Coercion must be transitive. That's one of the axioms.
</p>
TicketpbruinTue, 31 Dec 2013 21:44:27 GMT
https://trac.sagemath.org/ticket/11239#comment:28
https://trac.sagemath.org/ticket/11239#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:27" title="Comment 27">SimonKing</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Given that a conversion needs to coincide with the coercion if the latter exists, one must check for a coercion before applying the "stupid" conversion (assuming the "stupid" conversion is desired at all).
</p>
</blockquote>
<p>
No!! It is just the other way around!
</p>
</blockquote>
<p>
I think I see what you mean, but am still not sure. Are you suggesting that also the existing
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">elif</span> <span class="bp">self</span><span class="o">.</span>base_ring<span class="p">()</span><span class="o">.</span>has_coerce_map_from<span class="p">(</span>P<span class="p">):</span>
<span class="k">return</span> C<span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="p">[</span>x<span class="p">],</span> check<span class="o">=</span><span class="bp">True</span><span class="p">,</span> is_gen<span class="o">=</span><span class="bp">False</span><span class="p">,</span>
construct<span class="o">=</span>construct<span class="p">)</span>
</pre></div></div><p>
in <code>PolynomialRing._element_constructor_()</code> should go away and that there should be custom coercion maps to replace this check and the similar one added by my patch?
</p>
<blockquote class="citation">
<p>
You mean, conversion, not coercion? Coercion must be transitive. That's one of the axioms.
</p>
</blockquote>
<p>
Yes, I meant conversion.
</p>
TicketnbruinTue, 31 Dec 2013 22:56:48 GMT
https://trac.sagemath.org/ticket/11239#comment:29
https://trac.sagemath.org/ticket/11239#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:27" title="Comment 27">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
No!! It is just the other way around! Ideally, you have a fast cheap stupid conversion, and then a potentially expensive tests tells you whether this conversion qualifies as a coercion. This, by the way, is exactly what happens when <code>R._coerce_map_from_(S)</code> returns True: The return value asserts that the conversion qualifies as a coercion.
</p>
</blockquote>
<p>
Actually, that is something I wondered about before. From an efficiency point of view this is a really bad idea: we have just established that between two very specific parents S and R there exists a coercion and to actually perform it we boot back to completely generic code that has to figure out exactly what conversion to apply, doing all kinds of type checks again. It would seem much better to refactor such code to immediately call the special case that the conversion code is going to arrive at anyway.
</p>
TicketpbruinFri, 03 Jan 2014 23:53:05 GMT
https://trac.sagemath.org/ticket/11239#comment:30
https://trac.sagemath.org/ticket/11239#comment:30
<p>
Here is the way in which I think this bug should be solved conceptually. It is motivated by the fact that if <em>A</em> is a commutative ring, the object <em>A</em>[<em>x</em>] in the category of <em>A</em>-algebras represents the forgetful functor to the category of sets.
</p>
<ul><li>Implement a class <code>PolynomialRingMorphism</code> modelling ring homomorphisms <em>f</em>: <em>A</em>[<em>x</em>] -> <em>C</em>, where <em>A</em> and <em>C</em> are commutative rings. Note that <em>C</em> is not required to be a polynomial ring. Such ring homomorphisms correspond bijectively to pairs (<em>g</em>, <em>c</em>), where <em>g</em>: <em>A</em> -> <em>C</em> is a ring homomorphism and <em>c</em> is an element of <em>C</em>, where the bijection is given by <em>g</em> = <em>f</em>|<sub>A</sub> and <em>c</em> = <em>f</em>(<em>x</em>); cf. the above motivation.
</li><li>Have optimised code for the following special case: <em>C</em> = <em>B</em>[<em>y</em>] where <em>B</em> is an <em>A</em>-algebra (or: has a coercion map from <em>A</em>), <em>g</em> is the composition of the obvious maps <em>A</em> -> <em>B</em> -> <em>C</em>, and <em>c</em> = <em>y</em>. In this case, <em>f</em> is the map <em>A</em>[<em>x</em>] -> <em>C</em>[<em>y</em>] that we will declare as the coercion map. Given an element <em>p</em> of <em>A</em>[<em>x</em>], the <code>PolynomialRingMorphism</code> in this special case should just take the list of coefficients of <em>p</em>, map them to <em>B</em> and hence construct the desired element <em>f</em>(<em>p</em>) of <em>B</em>[<em>y</em>].
</li><li>If <em>C</em> = <em>B</em>[<em>y</em>], where <em>B</em> has a coercion map from <em>A</em>, let <code>C._coerce_map_from_(A['x'])</code> return the <code>PolynomialRingMorphism</code> for the above special case.
</li><li>A general <code>PolynomialRingMorphism</code> could be implemented either in terms of this special case or independently from it. The first approach would work as follows: given a general <em>f</em>: <em>A</em>[<em>x</em>] -> <em>C</em> as in the first point, represented by a pair (<em>g</em>, <em>c</em>), applying <em>f</em> to a polynomial <em>p</em> in <em>A</em>[<em>x</em>] can be implemented by first mapping <em>p</em> to <em>C</em>[<em>y</em>] (applying <em>g</em> to the coefficients as in the special case) and then substituting <em>c</em> for <em>y</em>.
</li></ul><p>
This is probably not very difficult to implement. This ticket could function as a temporary solution for the bug it fixes, until we have the real solution.
</p>
<p>
P.S. The current <code>_coerce_map_from_()</code>, in the case of univariate polynomial rings where there exists a coercion between the base rings, returns <code>False</code> unless the variable name is the same. In the above, I chose the different letters <em>x</em> and <em>y</em> to clearly distinguish between the polynomial rings; they are not meant as Sage variable names.
</p>
<p>
P.P.S. It turns out that the special case already exists (in more generality) as <code>RingHomomorphism_from_base</code>. In the above notation, it applies <em>g</em> elementwise to the <code>dict</code> of coefficients; for univariate dense polynomials a <code>list</code> would probaby be faster, but it looks like a good starting point.
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/11239#comment:31
https://trac.sagemath.org/ticket/11239#comment:31
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketpbruinSun, 02 Mar 2014 23:47:38 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/11239#comment:32
https://trac.sagemath.org/ticket/11239#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>236effb6198c6192dce0cedc0e53423c68743e3e</em> to <em>07d774f5f0c226d866cf4ea519951f92268063ff</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jpflori/ticket/11239</em> to <em>u/pbruin/11239-polynomial_coercion</em>
</li>
</ul>
<p>
Here is a fix based on the existing one and the "P.P.S" from <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:30" title="Comment 30">comment:30</a>. This gets rid of the test for coercion maps in the polynomial constructor.
</p>
TicketjpfloriMon, 03 Mar 2014 13:09:48 GMTstatus changed
https://trac.sagemath.org/ticket/11239#comment:33
https://trac.sagemath.org/ticket/11239#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks good enough for me and passes tests.
</p>
TicketgitMon, 03 Mar 2014 13:29:06 GMTstatus, commit changed
https://trac.sagemath.org/ticket/11239#comment:34
https://trac.sagemath.org/ticket/11239#comment:34
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>07d774f5f0c226d866cf4ea519951f92268063ff</em> to <em>dbe7209abde689a03b288511db1aa8b6fa991e9c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=dbe7209abde689a03b288511db1aa8b6fa991e9c"><span class="icon"></span>dbe7209</a></td><td><code>remove unused declaration from polynomial_ring_homomorphism.pxd</code>
</td></tr></table>
TicketpbruinMon, 03 Mar 2014 13:32:34 GMTstatus changed
https://trac.sagemath.org/ticket/11239#comment:35
https://trac.sagemath.org/ticket/11239#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I trust this latest change is OK too. (I started implementing a class <code>PolynomialRingHomomorphism</code> as in <a class="ticket" href="https://trac.sagemath.org/ticket/11239#comment:30" title="Comment 30">comment:30</a>, but didn't include it in the branch since it isn't finished and isn't needed to fix this bug; I should have removed the declaration too.)
</p>
TicketjpfloriMon, 03 Mar 2014 13:33:41 GMT
https://trac.sagemath.org/ticket/11239#comment:36
https://trac.sagemath.org/ticket/11239#comment:36
<p>
The latest change is ok with me as it just removes something unused.
</p>
TicketgitMon, 03 Mar 2014 15:14:56 GMTstatus, commit changed
https://trac.sagemath.org/ticket/11239#comment:37
https://trac.sagemath.org/ticket/11239#comment:37
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>dbe7209abde689a03b288511db1aa8b6fa991e9c</em> to <em>61c565b7beccc1466bdac4d17fab755cbf5f9c9c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=61c565b7beccc1466bdac4d17fab755cbf5f9c9c"><span class="icon"></span>61c565b</a></td><td><code>distinguish between sparse and dense in PolynomialRingHomomorphism_from_base</code>
</td></tr></table>
TicketpbruinMon, 03 Mar 2014 15:16:52 GMT
https://trac.sagemath.org/ticket/11239#comment:38
https://trac.sagemath.org/ticket/11239#comment:38
<p>
Sorry, I realised the patch didn't take sparse polynomial rings into account. There was also a minor mistake in two existing doctests.
</p>
TicketjpfloriMon, 03 Mar 2014 15:22:39 GMTstatus changed
https://trac.sagemath.org/ticket/11239#comment:39
https://trac.sagemath.org/ticket/11239#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I should be the one being sorry... I should have seen the error in the doctest.
Anyway, it looks better now and I wasn't aware that we have saprse polynomials!
</p>
TicketvbraunWed, 05 Mar 2014 09:36:26 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/11239#comment:40
https://trac.sagemath.org/ticket/11239#comment:40
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/pbruin/11239-polynomial_coercion</em> to <em>61c565b7beccc1466bdac4d17fab755cbf5f9c9c</em>
</li>
</ul>
Ticket