Horrible bug in number field conversion

[daveloeffler]

Sage seems to allow conversions of elements between different number
fields which are mathematically meaningless. Marco Streng just spotted
this when testing #9334:

----------------------------------------------------------------------
| Sage Version 4.7.1, Release Date: 2011-08-11 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: K.<a> = NumberField(x^3+x+1)
sage: L.<b> = NumberField(x^3+2*x+2)
sage: K(b)
a

The offending code is in
NumberField_absolute._coerce_from_other_number_field, which just
converts any element of any number field into a polynomial and then
converts that into an element of K.

I suggest we change this ASAP, so it raises a warning unless the
answer makes some kind of sense. What do other people think?

[Jeroen Demeyer]

I created
http://trac.sagemath.org/sage_trac/ticket/11869

[Jeroen Demeyer]

On 2011-09-29 14:13, Jeroen Demeyer wrote:
> I created
> http://trac.sagemath.org/sage_trac/ticket/11869

And there is now a patch awaiting review.

[Simon King]

Hi Dave, hi Jeroen,

On 29 Sep., 12:53, daveloeffler <dave.loeff...@gmail.com> wrote:
> Sage seems to allow conversions of elements between different number
> fields which are mathematically meaningless.

So what?

A coercion must be a morphism (hence, meaningful). However, a
conversion that is not a coercion can do anything. Just think of the
conversion of GF(2).one_element() into ZZ.

So, if the conversion you mention is not a coercion, then it is not a
bug, IMHO.

Cheers,
Simon

[Marco Streng]

Op 1-10-2011 10:08, Simon King schreef:

Hi Simon,

I see no point in allowing mathematically meaningless conversions
between number fields. Nobody ever wants to do this. I will sometimes do
it accidentally (by mixing up variable names), and then I want to be
notified of it (by an Error) immediately.

Lifting elements from GF(2) to ZZ by explicitly converting them is fine
with me, but I don't want to allow conversions if there is no natural
map at all in either direction (such as for 2 non-embedded number fields).

I agree with David that this is a bug.

Marco

[Simon King]

Hi all,

On 1 Okt., 11:30, Marco Streng <marco.str...@gmail.com> wrote:
> I see no point in allowing mathematically meaningless conversions
> between number fields. Nobody ever wants to do this.
> I will sometimes do
> it accidentally

While coercion is supposed to prevent you from accidentally shooting
yourself in the foot, I would not name it "accidentally" when you
explicitly call a conversion.

From my point of view, the only requirement for a conversion is that
it is fast. Currently, I have no possibility to see what the patch on
the ticket is doing. Does your patch introduce a test *in the
_element_constructor_* whether the conversion has a mathematical
meaning? That test would be repeated over and over again, thus causing
a *massive* slow down. I wouldn't appreciate that, but after all I'm
not using number fields. So, may the number theorists decide whether
they want number fields to be slow...

My opinion: A conversion should be very fast. Whether the conversion
is mathematically meaningful should be checked exactly *once*, namely
in _has_coerce_map_from_. The answer of this test allows to conclude
whether the conversion is a coercion (hence, safe to use) or not
(hence, it is your own fault if you use it).

Best regards,
Simon

[Simon King]

On 1 Okt., 13:30, Simon King <simon.k...@uni-jena.de> wrote:
> ... should be checked exactly *once*, namely
> in _has_coerce_map_from_.

Sorry, typo. _coerce_map_from_, of course.

[John Cremona]

As the frist person who called this a bug, I am rather mystified. If
a is an element of a number field K and L is a quite different field
(with no useful map from K to L), why should L(a) not raise an error?

John

> --
> You received this message because you are subscribed to the Google Groups "sage-nt" group.
> To post to this group, send an email to sag...@googlegroups.com.
> To unsubscribe from this group, send email to sage-nt+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sage-nt?hl=en-GB.
>
>

[Simon King]

Hi John,

On 1 Okt., 15:40, John Cremona <john.crem...@gmail.com> wrote:
> As the frist person who called this a bug, I am rather mystified.  If
> a is an element of a number field K and L is a quite different field
> (with no useful map from K to L), why should L(a) not raise an error?

Cf.
sage: GF(3)(GF(2)(1))
1
sage: _.parent()
Finite Field of size 3
There is no "meaningful" map in either direction.

Let me ask the opposite question: Why should it raise an error?

If there is a meaningful map of number fields L into K, then the
conversion of elements of L into elements of K relies on a certain
computation. The same computation can be attempted to convert elements
of any other number field L' into K, even if it is not meaningful. If
an error occurs during that computation, then fine. But why should one
slow the computation down by *additional* sanity tests that are
executed in *any* instance of a conversion, just in order to prevent
misuse?

IIRC, a conversion into a parent P is documented as being "any way to
interprete the input as an element of P". I find it a good approach to
be very permissive in conversions - and reserve the mathematical
rigidity to coercions (where the sanity test needs to be done only
once rather than thousands of times).

Cheers,
Simon

[David Roe]

Simon is correct that conversions are intended to create an element of the codomain using whatever means possible.  But I can also see that we might want to disallow conversions between number fields for practical reasons if they are causing bugs far more often than they are actually used.

There's a mechanism to make this fast for conversions, just as there is for coercions.  Implement _convert_map_from_ with a morphism, and then the check is only done once at the time the morphism is created, just as in the coercion case.
David

[Nils Bruin]

On Oct 1, 4:30 am, Simon King <simon.k...@uni-jena.de> wrote:
> From my point of view, the only requirement for a conversion is that
> it is fast.

I'm pretty sure that you don't mean that. If that is the only
requirement, one could simply return 0 regardless of the argument.
That could be implemented to be *very* fast.

In my experience, in sage, <parent>(...) accepts a wide variety of
inputs and tries to do something sensible if reasonably possible. That
means these constructors have to analyse the nature of their arguments
to decide what they're going to do. That alone makes them a not-so-
good avenue for constructing elements *quickly*.

If you want quick code-paths, wouldn't you program special methods
<parent>.construct_element_from_specific_data(...) that make
assumptions on the nature of their input? The generic <parent>(...)
could then simply dispatch over the specific constructors depending on
the nature of the data.

[Soroosh Yazdani]

I have to agree with Nils on that.

Also, there are certain cases when there is a natural morphism that we are not including. Specifically, the number fields created as the absolute_field of a relative extension are naturally isomorphic to their relative extension. I've noticed that the natural morphism is returned by structure command, but I have no idea how that fits in the coercion model.

Soroosh

[Simon King]

Hi Nils,

On 2 Okt., 02:58, Nils Bruin <nbr...@sfu.ca> wrote:
> On Oct 1, 4:30 am, Simon King <simon.k...@uni-jena.de> wrote:
>
> > From my point of view, the only requirement for a conversion is that
> > it is fast.
>
> I'm pretty sure that you don't mean that. If that is the only
> requirement, one could simply return 0 regardless of the argument.

OK, you got me - I hyperbolised a little. But technically, the only
*general* requirement on conversion that I can recall is "If there is
a coercion then it must coincide with conversion", imposing
constraints only to those conversions that happen to be coercions.

> If you want quick code-paths, wouldn't you program special methods
> <parent>.construct_element_from_specific_data(...) that make
> assumptions on the nature of their input?

That is often the case, but of course not in <parent>.

> The generic <parent>(...)
> could then simply dispatch over the specific constructors depending on
> the nature of the data.

The generic <parent>.__call__ involves looking for a conversion map.
Often (unless _convert_map_from_ does something special), the
conversion map dispatches to _element_constructor_. And I have met
_element_constructor_ dispatching to further methods, such as
_convert_from_singular etc.

David Roe wrote:
> Implement _convert_map_from_ with a morphism, and then the check
> is only done once at the time the morphism is created, just as in the
> coercion case.

I think that sounds like a very good solution! Actually I forgot that
_convert_map_from_ exists.

Best regards,
Simon

[Jeroen Demeyer]

On 2011-10-01 19:15, Simon King wrote:
> If there is a meaningful map of number fields L into K, then the
> conversion of elements of L into elements of K relies on a certain
> computation. The same computation can be attempted to convert elements
> of any other number field L' into K, even if it is not meaningful. If
> an error occurs during that computation, then fine. But why should one
> slow the computation down by *additional* sanity tests that are
> executed in *any* instance of a conversion, just in order to prevent
> misuse?

This is not what is actually happening in the number field code. There
is some code for coercion and *different* code for conversion. So the
check is already done anyway.

[Marco Streng]

2011/10/1 David Roe <ro...@math.harvard.edu>:

> Simon is correct that conversions are intended to create an element of the
> codomain using whatever means possible.

Hi David (Roe) and Simon,

Could you explain "intended" a bit more? E.g. is this a design
decision that was made for Sage at some point? Or is it a programming
guideline that holds more generally? Is it documented somewhere?

> There's a mechanism to make this fast for conversions, just as there is for
> coercions.  Implement _convert_map_from_ with a morphism

What does "morphism" mean here? Could you point me to an example of a
class where this done? And for example, can we do the following with a
morphism?

Suppose L is a number field, and K is obtained from L.subfield(...).
Then K is constructed together with a morphism phi. Obviously coercion
from K to L should happen via phi (as in #11876). Conversion from L to
K (if allowed at all) should (in my opinion) be a section of phi. That
is, given x in L, if x==phi(y) for some y in K, then return y,
otherwise raise a ValueError.

Thanks!
Marco

p.s. About the patch at #11869: it does contain a lot of complicated
conversions that may take some time. As a bugfix, I would have written
a much shorter patch that would have simply raised ValueError a lot.
On the other hand, all the complicated and possibly time-consuming
additions of Jeroen happen after the point where I would have been
satisfies with a ValueError, so that the time he spends could be
considered free. Or would people prefer ValueError?