Incorrect coercion of polynomials over finite fields

[1659f18b-8e7f-4ace-87e0-ea435f3ce618]

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/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:

Use git branch.

Depends on #8335

CC: @jpflori

Component: coercion

Keywords: finite fields, polynomials, sd53

Author: Peter Bruin

Branch/Commit: 61c565b

Reviewer: Jean-Pierre Flori

Issue created by migration from https://trac.sagemath.org/ticket/11239

[1659f18b-8e7f-4ace-87e0-ea435f3ce618]

Description changed:

--- 
+++ 
@@ -1,5 +1,3 @@
-Incorrect coercion of polynomials over finite fields
-
 Trying to coerce a polynomial over a finite field into a polynomial ring over a bigger field gives a bogus result:

[5ef57b06-33a8-4a32-80d2-0f5ab07e80d9]

comment:2

If we coerce directly from Fq to Fqq, we get a NotImplementedError, which is unfortunate ...

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:

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
]

since

sage: a.minimal_polynomial().roots(ring=F625, multiplicities=False)
[4*b^3 + 4*b^2 + 4*b + 3, b^3 + b^2 + b + 3]

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.

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

[5ef57b06-33a8-4a32-80d2-0f5ab07e80d9]

Description changed:

--- 
+++ 
@@ -8,7 +8,7 @@
 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. ;). +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)

[dkrenn]

comment:3

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

[simon-king-jena]

comment:4

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.

[pjbruin]

comment:6

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.

[pjbruin]

comment:7

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

[pjbruin]

Dependencies: #8335

[pjbruin]

Author: pbruin

[pjbruin]

Description changed:

--- 
+++ 
@@ -22,3 +22,6 @@

 NotImplementedError:

+ +Apply: attachment: trac_11239-polynomial_coercion_preliminary.patch +

[pjbruin]

comment:9

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 lower-level thing that should not have to care about maps between non-trivial finite fields.

[pjbruin]

comment:10

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.

[pjbruin]

Attachment: trac_11239-polynomial_zz_pex.patch.gz

fix coercion of polynomials over finite fields

[pjbruin]

Description changed:

--- 
+++ 
@@ -23,5 +23,5 @@
 NotImplementedError:

-Apply: attachment: trac_11239-polynomial_coercion_preliminary.patch +Apply: attachment: trac_11239-polynomial_coercion_preliminary.patch, attachment: trac_11239-polynomial_zz_pex.patch

[pjbruin]

comment:11

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 non-compatible finite fields raises a TypeError, as it should.

[pjbruin]

Changed author from pbruin to Peter Bruin

[jpflori]

Changed keywords from finite fields, polynomials to finite fields, polynomials, sd53

[jpflori]

comment:14

Just stumbled upon that bug while playing with finite fields. This is really a nice bug.

[pjbruin]

Attachment: trac_11239-polynomial_coercion_preliminary.patch.gz

update (old version had bogus doctest fix)

[lftabera]

comment:15

Peter, have you considered the impact of using has_coerce_map on the level of conversion? memory and time consumption.

[pjbruin]

comment:16

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?

[jpflori]

comment:17

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.

[jpflori]

comment:18

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

[jpflori]

Description changed:

--- 
+++ 
@@ -23,5 +23,5 @@
 NotImplementedError:

-Apply: attachment: trac_11239-polynomial_coercion_preliminary.patch, attachment: trac_11239-polynomial_zz_pex.patch +Use git branch.

[jpflori]

Branch: u/jpflori/ticket/11239

[jpflori]

Commit: 236effb

[jpflori]

Reviewer: Jean-Pierre Flori

[jpflori]

comment:19

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.

[jpflori]

comment:20

Not sure what to think about the quotients of univariate polynomial rings, except that it really feel akward.

[jpflori]

comment:21

Maybe this is worth a broader discussion on sage-devel...

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)?

[jpflori]

comment:22

Here you go:

• https://groups.google.com/d/msg/sage-devel/Z4iNgVMFoms/HxIZ98edPk0J

[pjbruin]

comment:23

Replying to @jpflori:

Maybe this is worth a broader discussion on sage-devel...

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.

[jpflori]

comment:24

Replying to @pjbruin:

Replying to @jpflori:

Maybe this is worth a broader discussion on sage-devel...

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

[simon-king-jena]

comment:25

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.

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 non-existence 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 parent-by-parent, but element-by-element).

[pjbruin]

comment:26

Replying to @simon-king-jena:

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.

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

[simon-king-jena]

comment:27

Replying to @pjbruin:

Replying to @simon-king-jena:

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.

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 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;

You mean, conversion, not coercion? Coercion must be transitive. That's one of the axioms.

[pjbruin]

comment:28

Replying to @simon-king-jena:

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.

[nbruin]

comment:29

Replying to @simon-king-jena:

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.

[pjbruin]

comment:30

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 A-algebras 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 A-algebra (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 the PolynomialRingMorphism 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.

[pjbruin]

Changed commit from 236effb to 07d774f

[pjbruin]

Changed branch from u/jpflori/ticket/11239 to u/pbruin/11239-polynomial_coercion

[pjbruin]

comment:32

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.

[jpflori]

comment:33

Looks good enough for me and passes tests.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 07d774f to dbe7209

[pjbruin]

comment:35

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

[jpflori]

comment:36

The latest change is ok with me as it just removes something unused.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dbe7209 to 61c565b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[pjbruin]

comment:38

Sorry, I realised the patch didn't take sparse polynomial rings into account. There was also a minor mistake in two existing doctests.