Opened 8 years ago
Closed 6 years ago
#11239 closed defect (fixed)
Incorrect coercion of polynomials over finite fields
Reported by:  johanbosman  Owned by:  robertwb 

Priority:  major  Milestone:  sage6.2 
Component:  coercion  Keywords:  finite fields, polynomials, coercion, sd53 
Cc:  jpflori  Merged in:  
Authors:  Peter Bruin  Reviewers:  JeanPierre Flori 
Report Upstream:  N/A  Work issues:  
Branch:  61c565b (Commits)  Commit:  61c565b7beccc1466bdac4d17fab755cbf5f9c9c 
Dependencies:  #8335  Stopgaps: 
Description (last modified by )
Trying to coerce a polynomial over a finite field into a polynomial ring over a bigger field gives a bogus result:
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
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 NotImplementedError
, which is unfortunate but in any case not incorrect. ;).
sage: Fqq(a) … /usr/local/share/sage/sage/local/lib/python2.6/sitepackages/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:
Use git branch.
Attachments (2)
Change History (42)
comment:1 Changed 8 years ago by
 Description modified (diff)
comment:2 Changed 8 years ago by
 Description modified (diff)
comment:3 followups: ↓ 4 ↓ 10 Changed 8 years ago by
 Status changed from new to needs_info
It seems that everything that can be represented as polynomial is converted in that way. The phenomenon also appears with quotient rings:
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
One way to solve this problem would be to check whether the coefficients of one polynomial rings can be converted (coerced) to the other...
comment:4 in reply to: ↑ 3 Changed 8 years ago by
Replying to dkrenn:
One way to solve this problem would be to check whether the coefficients of one polynomial rings can be converted (coerced) to the other...
I would strongly advice against the attempt to solve it on the level of conversion.
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 _element_constructor_
that does the conversion, and a separate _coerce_map_from_
, that determines whether there is a coercion (not just a conversion).
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 repeatedly, that's to say testing it for each individual polynomial to be converted, sounds like a waste of computation time to me.
comment:5 Changed 6 years ago by
 Cc pbruin added
comment:6 Changed 6 years ago by
If in the example in the ticket description, one replaces
sage: Fqq['y'](f)
by
sage: Fqq['y']._coerce_(f)
one at least gets a sensible error:
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
I tried the same example using the compatible finite fields from #8335. 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 is a coercion map between the finite fields.
comment:7 Changed 6 years ago by
The problem lies in the NTL implementation of polynomials over finite fields. (Edit: this was already discovered in comment:2 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.
The following example demonstrates this (after applying #8335 plus a patch that I will upload shortly):
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
comment:8 Changed 6 years ago by
 Cc pbruin removed
 Dependencies set to #8335
 Description modified (diff)
 Status changed from needs_info to needs_work
comment:9 Changed 6 years ago by
At this point there are two possible solutions:
 either fix the NTL polynomial constructor,
 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.
The first solution would be preferable in principle, but certainly harder and maybe even unreasonable, since the NTL polynomial constructor is a lowerlevel thing that should not have to care about maps between nontrivial finite fields.
comment:10 in reply to: ↑ 3 Changed 6 years ago by
Replying to dkrenn:
It seems that everything that can be represented as polynomial is converted in that way. The phenomenon also appears with quotient rings:
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
Debatable as it may seem, this is the behaviour currently described in the documentation of PolynomialQuotientRing_generic._element_constructor_()
. Attempting a coercion (PB.coerce(f)
) instead of a conversion (PB(f)
) does lead to
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
as expected.
comment:11 Changed 6 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
Fixing the NTL polynomial constructor turned out to be easy. With the second patch, polynomials over compatible finite fields (#8335) coerce correctly, and trying to convert polynomials over noncompatible finite fields raises a TypeError
, as it should.
comment:12 Changed 6 years ago by
comment:13 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:14 Changed 6 years ago by
 Cc jpflori added
 Keywords sd53 added
Just stumbled upon that bug while playing with finite fields. This is really a nice bug.
comment:15 followup: ↓ 16 Changed 6 years ago by
Peter, have you considered the impact of using has_coerce_map on the level of conversion? memory and time consumption.
comment:16 in reply to: ↑ 15 Changed 6 years ago by
Replying to lftabera:
Peter, have you considered the impact of using has_coerce_map on the level of conversion? memory and time consumption.
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?
comment:17 Changed 6 years ago by
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.
comment:18 Changed 6 years ago by
 Branch set to u/jpflori/ticket/11239
 Commit set to 236effb6198c6192dce0cedc0e53423c68743e3e
 Description modified (diff)
 Reviewers set to JeanPierre Flori
 Status changed from needs_review to positive_review
Anyway, the coercion framework is already called in the previous test so efficiency is already potentially screwed up.
I've just made a git branch from the patch. Otherwise looks good to me, positive review.
New commits:
236effb  Trac 11239: fix coercion of polynomials over finite fields

e46d9bf  Trac 11239: fix coercion of polynomials over finite fields, first step

comment:19 Changed 6 years ago by
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...
If someone thinks the solution is overkill and goes against the coercion model philosophy, feel free to put the ticket back to another status.
comment:20 Changed 6 years ago by
Not sure what to think about the quotients of univariate polynomial rings, except that it really feel akward.
comment:21 followup: ↓ 23 Changed 6 years ago by
 Status changed from positive_review to needs_info
Maybe this is worth a broader discussion on sagedevel...
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)?
comment:22 Changed 6 years ago by
comment:23 in reply to: ↑ 21 ; followup: ↓ 24 Changed 6 years ago by
Replying to jpflori:
Maybe this is worth a broader discussion on sagedevel...
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.
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)?
I personally think that allowing Fqq['y'](f)
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 Z[x] or another suitable ring.
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.
comment:24 in reply to: ↑ 23 Changed 6 years ago by
Replying to pbruin:
Replying to jpflori:
Maybe this is worth a broader discussion on sagedevel...
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.
I agree.
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)?
I personally think that allowing
Fqq['y'](f)
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 Z[x] or another suitable ring.
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...
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.
I agree as well, I was just menitoning it because it's already mentioned here :)
Anyway, if nobody gives a strong opinion of why to keep conversions without any mathematical sense and confusing for naive users on sagedevel, 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.
comment:25 followup: ↓ 26 Changed 6 years ago by
See my answer on sagedevel. In a nutshell: I would recommend against doing expensive tests when talking about conversion, and I would be rather permissive in conversions.
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.
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 nonexistence of certain coercions).
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 parentbyparent, but elementbyelement).
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 6 years ago by
Replying to SimonKing:
See my answer on sagedevel. In a nutshell: I would recommend against doing expensive tests when talking about conversion, and I would be rather permissive in conversions.
Conversions have no defined properties, and thus there is nothing that one could test.
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).
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 R.coerce(f)
, because the coercion map just defers to a conversion using the element constructor.)
I think the point in the above discussion was whether my solution of calling has_coerce_map_from()
is expensive; I guess not, but even if it is, it is still necessary to guarantee compatibility of conversion and coercion.
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.
That is actually what I was trying to say on sagedevel 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.
comment:27 in reply to: ↑ 26 ; followups: ↓ 28 ↓ 29 Changed 6 years ago by
Replying to pbruin:
Replying to SimonKing:
See my answer on sagedevel. In a nutshell: I would recommend against doing expensive tests when talking about conversion, and I would be rather permissive in conversions.
Conversions have no defined properties, and thus there is nothing that one could test.
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).
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 R._coerce_map_from_(S)
returns True: The return value asserts that the conversion qualifies as a coercion.
That is actually what I was trying to say on sagedevel 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;
You mean, conversion, not coercion? Coercion must be transitive. That's one of the axioms.
comment:28 in reply to: ↑ 27 Changed 6 years ago by
Replying to SimonKing:
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).
No!! It is just the other way around!
I think I see what you mean, but am still not sure. Are you suggesting that also the existing
elif self.base_ring().has_coerce_map_from(P): return C(self, [x], check=True, is_gen=False, construct=construct)
in PolynomialRing._element_constructor_()
should go away and that there should be custom coercion maps to replace this check and the similar one added by my patch?
You mean, conversion, not coercion? Coercion must be transitive. That's one of the axioms.
Yes, I meant conversion.
comment:29 in reply to: ↑ 27 Changed 6 years ago by
Replying to SimonKing:
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
R._coerce_map_from_(S)
returns True: The return value asserts that the conversion qualifies as a coercion.
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.
comment:30 Changed 6 years ago by
Here is the way in which I think this bug should be solved conceptually. It is motivated by the fact that if A is a commutative ring, the object A[x] in the category of Aalgebras represents the forgetful functor to the category of sets.
 Implement a class
PolynomialRingMorphism
modelling ring homomorphisms f: A[x] > C, where A and C are commutative rings. Note that C is not required to be a polynomial ring. Such ring homomorphisms correspond bijectively to pairs (g, c), where g: A > C is a ring homomorphism and c is an element of C, where the bijection is given by g = f_{A} and c = f(x); cf. the above motivation.  Have optimised code for the following special case: C = B[y] where B is an Aalgebra (or: has a coercion map from A), g is the composition of the obvious maps A > B > C, and c = y. In this case, f is the map A[x] > C[y] that we will declare as the coercion map. Given an element p of A[x], the
PolynomialRingMorphism
in this special case should just take the list of coefficients of p, map them to B and hence construct the desired element f(p) of B[y].  If C = B[y], where B has a coercion map from A, let
C._coerce_map_from_(A['x'])
return thePolynomialRingMorphism
for the above special case.  A general
PolynomialRingMorphism
could be implemented either in terms of this special case or independently from it. The first approach would work as follows: given a general f: A[x] > C as in the first point, represented by a pair (g, c), applying f to a polynomial p in A[x] can be implemented by first mapping p to C[y] (applying g to the coefficients as in the special case) and then substituting c for y.
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.S. The current _coerce_map_from_()
, in the case of univariate polynomial rings where there exists a coercion between the base rings, returns False
unless the variable name is the same. In the above, I chose the different letters x and y to clearly distinguish between the polynomial rings; they are not meant as Sage variable names.
P.P.S. It turns out that the special case already exists (in more generality) as RingHomomorphism_from_base
. In the above notation, it applies g elementwise to the dict
of coefficients; for univariate dense polynomials a list
would probaby be faster, but it looks like a good starting point.
comment:31 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:32 Changed 6 years ago by
 Branch changed from u/jpflori/ticket/11239 to u/pbruin/11239polynomial_coercion
 Commit changed from 236effb6198c6192dce0cedc0e53423c68743e3e to 07d774f5f0c226d866cf4ea519951f92268063ff
 Status changed from needs_info to needs_review
Here is a fix based on the existing one and the "P.P.S" from comment:30. This gets rid of the test for coercion maps in the polynomial constructor.
comment:33 Changed 6 years ago by
 Status changed from needs_review to positive_review
Looks good enough for me and passes tests.
comment:34 Changed 6 years ago by
 Commit changed from 07d774f5f0c226d866cf4ea519951f92268063ff to dbe7209abde689a03b288511db1aa8b6fa991e9c
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
dbe7209  remove unused declaration from polynomial_ring_homomorphism.pxd

comment:35 Changed 6 years ago by
 Status changed from needs_review to positive_review
I trust this latest change is OK too. (I started implementing a class PolynomialRingHomomorphism
as in comment:30, 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.)
comment:36 Changed 6 years ago by
The latest change is ok with me as it just removes something unused.
comment:37 Changed 6 years ago by
 Commit changed from dbe7209abde689a03b288511db1aa8b6fa991e9c to 61c565b7beccc1466bdac4d17fab755cbf5f9c9c
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
61c565b  distinguish between sparse and dense in PolynomialRingHomomorphism_from_base

comment:38 Changed 6 years ago by
Sorry, I realised the patch didn't take sparse polynomial rings into account. There was also a minor mistake in two existing doctests.
comment:39 Changed 6 years ago by
 Status changed from needs_review to positive_review
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!
comment:40 Changed 6 years ago by
 Branch changed from u/pbruin/11239polynomial_coercion to 61c565b7beccc1466bdac4d17fab755cbf5f9c9c
 Resolution set to fixed
 Status changed from positive_review to closed
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:
since
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.