Horrible bug in number field conversion

[jdemeyer]

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

Depends on #11873
Depends on #11876

CC: @simon-king-jena

Component: number fields

Author: Jeroen Demeyer

Reviewer: Marco Streng

Merged: sage-4.8.alpha0

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

[jdemeyer]

comment:1

I am working on a patch...

[jdemeyer]

Dependencies: #11870

[jdemeyer]

comment:3

In the process of working on this ticket, I discovered #11870, #11872, #11873.

[jdemeyer]

Work Issues: p-adic embeddings, problems with #11873

[nbruin]

comment:6

From the patch:

If the number fields ``x.parent()`` and ``self`` have an 
embedding in the same field, then those embeddings are used to 
determine the correct conversion.  If no such compatible 
embeddings are given, then some possible conversion of ``x`` 
into ``self`` is given.  This means a non-canonical element of 
``self`` with the same minimal polynomial as ``x``.

Is that second bit absolutely necessary? I think this is horrible. Throwing an error would be much preferable. With this, it would be possible to have two fields K and L, elements a,b in K and have
L(a+b) not equal to L(a)+L(b). That looks like something that is going to be a perpetual source of problems and hard-to-find bugs.

[jdemeyer]

Changed dependencies from #11870 to #11873

[jdemeyer]

Changed work issues from p-adic embeddings, problems with #11873 to more examples

[jdemeyer]

comment:8

Replying to @nbruin:

Is that second bit absolutely necessary? I think this is horrible. Throwing an error would be much preferable. With this, it would be possible to have two fields K and L, elements a,b in K and have
L(a+b) not equal to L(a)+L(b). That looks like something that is going to be a perpetual source of problems and hard-to-find bugs.

All this should be fixed now.

[jdemeyer]

Changed work issues from more examples to none

[mstreng]

comment:10

sage: K.<a> = NumberField(x^2-5)
sage: L, phi = K.subfield(-a)
sage: phi(L.gen())
-a
sage: K(L.gen())
a

Of course the second one must equal the first one or raise an error.

[mstreng]

comment:11

In the case of my example above, there is a preferred embedding of L into K, but your patch does not find it.

In general, even if there really is no preferred embedding of L into K, then just choosing one will still lead to trouble, as you'll get non-commuting diagrams of embeddings. Instead of just choosing an embedding, I strongly think you must raise an error (but other people may say warning, as David did on sage-nt). This could be discussed on the mailing list.

[jdemeyer]

comment:12

Replying to @mstreng:

In the case of my example above, there is a preferred embedding of L into K, but your patch does not find it.

My patch does not find it because Sage does not store it, see #11876.

[jdemeyer]

comment:13

Replying to @mstreng:

In general, even if there really is no preferred embedding of L into K, then just choosing one will still lead to trouble, as you'll get non-commuting diagrams of embeddings.

So may I paraphrase your proposal as follows:
If the element x to be converted is not in QQ and the fields have no compatible embeddings, then raise ValueError?

[mstreng]

comment:14

Replying to @jdemeyer:

So may I paraphrase your proposal as follows:
If the element x to be converted is not in QQ and the fields have no compatible embeddings, then raise ValueError?

Yes.

[jdemeyer]

Changed dependencies from #11873 to #11873, #11876

[jdemeyer]

comment:16

Done (raising TypeError if no embeddings are found). For subfields, it needs the patch from #11876.

[mstreng]

comment:17

Thanks, I hope to look at the patch soon.

In the mean time: maybe the message "TypeError: No compatible embedding found for conversion" becomes clearer if you add the word "natural" or "preferred", and perhaps add the fields to the message, i.e., append "from %s to %s" % (....)

[jdemeyer]

comment:18

Done, error message changed.

[jdemeyer]

comment:19

There is one doctest error:

sage -t -long "devel/sage/sage/rings/residue_field.pyx"
**********************************************************************
File "/usr/local/src/sage-4.7.2.alpha2/devel/sage/sage/rings/residue_field.pyx", line 522:
    sage: RL(OK.1)
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/src/sage-4.7.2.alpha2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/src/sage-4.7.2.alpha2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/usr/local/src/sage-4.7.2.alpha2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_5[22]>", line 1, in <module>
        RL(OK.gen(1))###line 522:
    sage: RL(OK.1)
      File "parent.pyx", line 941, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7102)
      File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3254)
      File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3157)
      File "residue_field.pyx", line 1360, in sage.rings.residue_field.ResidueFiniteField_prime_modn._element_constructor_ (sage/rings/residue_field.c:11389)
      File "residue_field.pyx", line 545, in sage.rings.residue_field.ResidueField_generic._element_constructor_ (sage/rings/residue_field.c:6293)
    TypeError: cannot coerce <type 'sage.rings.number_field.number_field_element.OrderElement_absolute'>
**********************************************************************

[jdemeyer]

comment:20

I simply removed the failing test because it makes assumptions which are no longer valid. Also, the result of the test is mathematically anyway.

[mstreng]

comment:21

I recall some discussion on sage-nt going into that example (introduced in #8800 together with the "Horrible bug"). I'm CC'ing its author.

[simon-king-jena]

comment:22

Attachment: 11869.patch.gz

I am a bit confused: In the keywords, you name it "coercion". But in your example, you just talk about conversion. If it really is a coercion (please check: Does that conversion happens implicitly?) then I agree it is a bug.

Otherwise, I'd say that a conversion that is not a coercion is allowed to do arbitrary nasty stuff (such as ZZ(GF(2)(1)) returning the integer 1).

[jdemeyer]

comment:23

Replying to @simon-king-jena:

I am a bit confused: In the keywords, you name it "coercion". But in your example, you just talk about conversion. If it really is a coercion (please check: Does that conversion happens implicitly?) then I agree it is a bug.

It certainly used to be a stupid "conversion".

My patch actually implements something which is much closer to coercion. Essentially, it is coercion on subfields of the given number fields. Suppose I have two number fields L1 and L2 sharing a common subfield K. Even if there is no coercion map from L1 to L2, there is a coercion between the subfields K of L1 and K of L2.

[mstreng]

comment:24

I'm satisfied with the patch, and all tests pass. In the sage-nt discussion, it seems that most number field users want to disallow senseless conversions. And all the time-consuming computation happens after the point where I would have given up with an Error. So I'd like to give this a positive review.

[mstreng]

Author: Jeroen Demeyer

[mstreng]

Reviewer: Marco Streng

[jdemeyer]

Merged: sage-4.7.3.alpha0

[jdemeyer]

Milestone sage-4.7.3 deleted

[jdemeyer]

Changed merged from sage-4.7.3.alpha0 to sage-4.8.alpha0