Opened 6 years ago

Last modified 11 months ago

#14367 needs_review defect

RuntimeError: There is a bug in the coercion code in Sage (number field to padic)

Reported by: lftabera Owned by: robertwb
Priority: major Milestone: sage-8.4
Component: coercion Keywords: coercion, number field, p-adic, days94
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/lftabera/ticket/14367 (Commits) Commit: fddd23bd94f2e770f886828c9828a1457b84a9f7
Dependencies: Stopgaps: wrongAnswerMarker

Description

I have found what Sage claims is a bug in the coercion code.

sage: Q7 = Qp(7)
sage: r1 = 3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 +\
           6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 +\
           4*7^18 + 6*7^19 + O(7^20)
sage: N.<b> = NumberField(x^2-2, embedding = r1)
sage: K.<t> = N[]
sage: f = t^3-2*t+1
sage: f(r1)
RuntimeError: There is a bug in the coercion code in Sage.
Both x (=1 + O(7^20)) and y (=3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 + 6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 + 4*7^18 + 6*7^19 + O(7^20)) are supposed to have identical parents but they don't.
In fact, x has parent '7-adic Field with capped relative precision 20'
whereas y has parent '7-adic Ring with capped relative precision 20'
Original elements 1 (parent Number Field in b with defining polynomial x^2 - 2) and 3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 + 6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 + 4*7^18 + 6*7^19 + O(7^20) (parent 7-adic Ring with capped relative precision 20) and maps
<type 'sage.rings.number_field.number_field_morphisms.NumberFieldEmbedding'> Generic morphism:
  From: Number Field in b with defining polynomial x^2 - 2
  To:   7-adic Ring with capped relative precision 20
  Defn: b -> 3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 + 6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 + 4*7^18 + 6*7^19 + O(7^20)
<type 'NoneType'> None

Note that here the embedding of N is into Qp(7) and that r1 is an element of Zp(7). If I define r1 as an element of Qp(7) then the evaluation of f works.

If I now do

sage: Z7 = Zp(7)
sage: r1 = Z7(3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 +\
....:         6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 +\
....:         4*7^18 + 6*7^19)
sage: M.<b> = NumberField(x^2-2, embedding = r1)
sage: K.<t> = M[]
sage: f = t^3-2*t+1
sage: f(r1)
RuntimeError
...

I see here two problems. The most obvious is that I would expect f(r1) to work. The second one is in the latter.

sage: M.coerce_embedding()
Generic morphism:
  From: Number Field in b with defining polynomial x^2 - 2
  To:   7-adic Ring with capped relative precision 20
  Defn: b -> 3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 + 6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 + 4*7^18 + 6*7^19 + O(7^20)

This morphism should NOT be an embedding. It is not defined for 1/7

sage: phi = M.coerce_embedding()
sage: phi(M(1/7))
7^-1 + O(7^19)
sage: phi(M(1/7)) in phi.codomain()
False

Change History (16)

comment:1 Changed 6 years ago by lftabera

  • Summary changed from RuntimeError: There is a bug in the coercion code in Sage to RuntimeError: There is a bug in the coercion code in Sage (number field to padic)

comment:2 Changed 6 years ago by nbruin

Should perhaps

sage: Q7 = Qp(7)
sage: r1 = 3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 +\
           6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 +\
           4*7^18 + 6*7^19 + O(7^20)
sage: N.<b> = NumberField(x^2-2, embedding = r1)

give an error if r1 (or the root of x^2-2 close to r1) is not invertible in its parent? I guess we are supposing that the embedding implied here is into parent(r1)? Note that the definition of Q7 in the above example is entirely irrelevant. The NumberField constructor is in no way indicating that an embedding into that Q7 is requested.

I guess one option would be to let embedding try to construct a parent in which the image of b is invertible, based on the parent inferred from r1.

(rant)

In general, I think the rule "when in doubt, refuse the temptation to quess" has served python extremely well and sage would do well to follow that rule as much as possible too. At least the "fundamental functionality" in sage should be free from guess-work.

If people then want to layer convenience functions and constructors on top that try to guess what the user meant from underspecified or malformed input, that's fine, but it should not contaminate the layer that provides the real functionality.

(/rant)

So perhaps just fail, citing that sending b to r1 does not map N into a subfield of parent(r1).

comment:3 Changed 6 years ago by lftabera

I agree with the idea of no guessing. There is no coercion possible form N to Zp(7) so here we should raise an error. Note that the problem is not that r1 is not invertible in its parent, because it is. The problem is that the parent of r1 does not contain any subfield. I am not sure how to deal with this. Mathematically, for a simple extension, the parent R of r1 should be such that:

  • There is a coercion from QQ to R.
  • r1 is an (approximate) root of the defining polynomial of N in R.

comment:4 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 3 years ago by jakobkroeker

  • Stopgaps set to wrongAnswerMarker

comment:9 Changed 12 months ago by lftabera

  • Keywords days94 added

comment:10 Changed 12 months ago by lftabera

  • Branch set to u/lftabera/ticket/14367
  • Commit set to fddd23bd94f2e770f886828c9828a1457b84a9f7
  • Milestone changed from sage-6.4 to sage-8.3

New commits:

fddd23bFix #14367, RuntimeError: There is a bug in the coercion code in Sage (number field to padic)

comment:11 follow-up: Changed 12 months ago by lftabera

  • Status changed from new to needs_review

I have added a patch to this issue. The code did not check if there is an embedding.

My opinion is that embeddings should be pretty explicit. So if the embedding parameter is set to an exact root of the defining polynomial and there is no embedding to the parent of the value raise a ValueError?. If the value is a (rDF, integer etc.) approximate root then the code is notchanged. This can lead to some unexpected behavior,

sage: NumberField(x-1, 'a', embedding=1)
Traceback (most recent call last):
...
ValueError: there is no embedding into Integer Ring
sage: NumberField(x-1, 'a', embedding=2).coerce_embedding()
Generic morphism:
  From: Number Field in a with defining polynomial x - 1
  To:   Real Lazy Field
  Defn: a -> 1

The alternative would be to create a new parent, but I would like to eliminate guessings as much as possible.

comment:12 in reply to: ↑ 11 Changed 12 months ago by nbruin

Replying to lftabera:

My opinion is that embeddings should be pretty explicit. So if the embedding parameter is set to an exact root of the defining polynomial and there is no embedding to the parent of the value raise a ValueError?. If the value is a (rDF, integer etc.) approximate root then the code is notchanged. This can lead to some unexpected behavior,

I don't see how that behaviour can be justified. Why is "real lazy field" guessed from embedding=2? Why is it not from embedding=1? That's just too strange.

comment:13 follow-up: Changed 12 months ago by lftabera

I have not changed the behavior of Sage, only rise an error when the current code provides a wrong result. I agree that it is strange.

Just to clarify, current behavior of Sage:

  • When there is an exact root of the polynomial, use the parent of the element to determine the codomain of the embedding (wrong, since the codomain may not contain a subfield isomorphic to the number field).
  • When the embedding provides only an approximation of the root, use real/complex lazy field. (Note that this does not work for p-addic approximation of the root for instance).

I see the following solutions. I only describe possible outcomes where given an exact root p with parent P, I would not change approximate solutions.

1) My patch approach. If there is not an embedding from QQ to P, raise a ValueError?, no exceptions.

2) Take R = coercion_model.common_parent(QQ,P) to determine the codomain of the embedding. Still check that there is an embedding from QQ to R (so no zero ring as codomain, for instance).

3) A compromise, usually in Sage, exceptions are made for Integer inputs and treat them as rationals if necessary, we could take that into account. But then, I would expect the following behaviour:

  • NumberField(x-1,'a',embedding=1) creates the number field with an embedding to QQ
  • NumberField(x-1,'a',embedding=2) creates the number field with an embedding to real lazy field.

There are other cumbersome options, like specifying the codomain, but I do not see a lot the point. Personally, I do not like 2. Nils, what would you think what would you think that would make a sensible approach?

comment:14 in reply to: ↑ 13 Changed 12 months ago by nbruin

Replying to lftabera:

  • When there is an exact root of the polynomial, use the parent of the element to determine the codomain of the embedding (wrong, since the codomain may not contain a subfield isomorphic to the number field).

At the face of it this seems reasonable behaviour. Perhaps it should check if sufficiently many elements are invertible in the codomain, but that might be too expensive to do.

  • When the embedding provides only an approximation of the root, use real/complex lazy field. (Note that this does not work for p-addic approximation of the root for instance).

I do not see how that can be reasonable. Perhaps that option should have a different name? archimedian_embedding or something like that? Or approximate embedding? Clearly the behavioural difference between approximately and exactly given embeddings is not compatible. Op perhaps the exact embedding needs a different name? Clearly, if an approximate root is allowed to lie in a ring that is not actually the target ring, we are not giving enough information. From the integer 2 one cannot see if it is an approximation of a root in RR, CC, or Qp (or some algebraic extension of Qp).

I see the following solutions. I only describe possible outcomes where given an exact root p with parent P, I would not change approximate solutions.

I think one problem is that we're trying to squeeze two functionalities into one option. So I think you can only resolve this satisfactorily by dealing with both.

1) My patch approach. If there is not an embedding from QQ to P, raise a ValueError?, no exceptions.

The check you do is probably quite reasonable. Do you really need to check that P(0) != P(1) though? is that ever a coercion map?

2) Take R = coercion_model.common_parent(QQ,P) to determine the codomain of the embedding. Still check that there is an embedding from QQ to R (so no zero ring as codomain, for instance).

Not unreasonable either.

3) A compromise, usually in Sage, exceptions are made for Integer inputs and treat them as rationals if necessary, we could take that into account. But then, I would expect the following behaviour:

I think that's a useless special case. When do people actually need to construct a number field that has a coercion into Q? That certainly doesn't need a shortcut.

There are other cumbersome options, like specifying the codomain, but I do not see a lot the point. Personally, I do not like 2. Nils, what would you think what would you think that would make a sensible approach?

First split the exact vs. approximate root specfication problem. I think that's way more confusing than any of the other problems arising here.

If you're absolutely intent on just solving the problem reported in this ticket, your option 1 seems like the least invasive. It just makes something an outright error that would otherwise fail later anyway.

comment:15 Changed 12 months ago by lftabera

Ok, I will think about this. For instance, the embedding option does not currently work for Tower extensions, Things there are a little messy. In any case, I think that the long term solution is more invasive.

Concerning P(0)!=P(1) I can only imagin one case where it is necessary. When the codomain is the zero ring (see the test section). I have no idea how or why one could arrive there, embedding is not an option one should use on a library, I see it more like an interactive option, but that map it is not an embedding. As far as I know one cannot tell from the coercion framework that a coercion is an embedding. We could eliminate that check, but then the documentation should be clear about that aspect.

comment:16 Changed 11 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

Note: See TracTickets for help on using tickets.