Opened 8 years ago

Closed 5 years ago

#11239 closed defect (fixed)

Incorrect coercion of polynomials over finite fields

Reported by: johanbosman Owned by: robertwb
Priority: major Milestone: sage-6.2
Component: coercion Keywords: finite fields, polynomials, coercion, sd53
Cc: jpflori Merged in:
Authors: Peter Bruin Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: 61c565b (Commits) Commit: 61c565b7beccc1466bdac4d17fab755cbf5f9c9c
Dependencies: #8335 Stopgaps:

Description (last modified by jpflori)

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.

Attachments (2)

trac_11239-polynomial_zz_pex.patch (2.9 KB) - added by pbruin 6 years ago.
fix coercion of polynomials over finite fields
trac_11239-polynomial_coercion_preliminary.patch (1.7 KB) - added by pbruin 6 years ago.
update (old version had bogus doctest fix)

Download all attachments as: .zip

Change History (42)

comment:1 Changed 8 years ago by johanbosman

  • Description modified (diff)

comment:2 Changed 8 years ago by fwclarke

  • Description modified (diff)

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

comment:3 follow-ups: Changed 8 years ago by dkrenn

  • 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 SimonKing

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 pbruin

  • Cc pbruin added

comment:6 Changed 6 years ago by pbruin

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 pbruin

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
Last edited 6 years ago by pbruin (previous) (diff)

comment:8 Changed 6 years ago by pbruin

  • Authors set to pbruin
  • 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 pbruin

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.

comment:10 in reply to: ↑ 3 Changed 6 years ago by pbruin

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.

Changed 6 years ago by pbruin

fix coercion of polynomials over finite fields

comment:11 Changed 6 years ago by pbruin

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

comment:12 Changed 6 years ago by pbruin

  • Authors changed from pbruin to Peter Bruin

comment:13 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 6 years ago by jpflori

  • Cc jpflori added
  • Keywords sd53 added

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

Changed 6 years ago by pbruin

update (old version had bogus doctest fix)

comment:15 follow-up: Changed 6 years ago by lftabera

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 pbruin

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 jpflori

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 jpflori

  • Branch set to u/jpflori/ticket/11239
  • Commit set to 236effb6198c6192dce0cedc0e53423c68743e3e
  • Description modified (diff)
  • Reviewers set to Jean-Pierre 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:

236effbTrac 11239: fix coercion of polynomials over finite fields
e46d9bfTrac 11239: fix coercion of polynomials over finite fields, first step

comment:19 Changed 6 years ago by jpflori

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 jpflori

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

comment:21 follow-up: Changed 6 years ago by jpflori

  • Status changed from positive_review to needs_info

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

comment:23 in reply to: ↑ 21 ; follow-up: Changed 6 years ago by pbruin

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.

comment:24 in reply to: ↑ 23 Changed 6 years ago by jpflori

Replying to pbruin:

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.

comment:25 follow-up: Changed 6 years ago by SimonKing

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

comment:26 in reply to: ↑ 25 ; follow-up: Changed 6 years ago by pbruin

Replying to SimonKing:

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.

comment:27 in reply to: ↑ 26 ; follow-ups: Changed 6 years ago by SimonKing

Replying to pbruin:

Replying to SimonKing:

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.

comment:28 in reply to: ↑ 27 Changed 6 years ago by pbruin

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 nbruin

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 pbruin

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.

Last edited 6 years ago by pbruin (previous) (diff)

comment:31 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:32 Changed 5 years ago by pbruin

  • Branch changed from u/jpflori/ticket/11239 to u/pbruin/11239-polynomial_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 5 years ago by jpflori

  • Status changed from needs_review to positive_review

Looks good enough for me and passes tests.

comment:34 Changed 5 years ago by git

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

dbe7209remove unused declaration from polynomial_ring_homomorphism.pxd

comment:35 Changed 5 years ago by pbruin

  • 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 needed to fix this bug; I should have removed the declaration too.)

Version 0, edited 5 years ago by pbruin (next)

comment:36 Changed 5 years ago by jpflori

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

comment:37 Changed 5 years ago by git

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

61c565bdistinguish between sparse and dense in PolynomialRingHomomorphism_from_base

comment:38 Changed 5 years ago by pbruin

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 5 years ago by jpflori

  • 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 5 years ago by vbraun

  • Branch changed from u/pbruin/11239-polynomial_coercion to 61c565b7beccc1466bdac4d17fab755cbf5f9c9c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.