Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#11869 closed defect (fixed)

Horrible bug in number field conversion

Reported by: jdemeyer Owned by: davidloeffler
Priority: major Milestone: sage-4.8
Component: number fields Keywords: coercion
Cc: SimonKing Merged in: sage-4.8.alpha0
Authors: Jeroen Demeyer Reviewers: Marco Streng
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11873, #11876 Stopgaps:

Description

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

Attachments (1)

11869.patch (11.9 KB) - added by jdemeyer 8 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 8 years ago by jdemeyer

I am working on a patch...

comment:2 Changed 8 years ago by jdemeyer

  • Dependencies set to #11870

comment:3 Changed 8 years ago by jdemeyer

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

comment:4 Changed 8 years ago by jdemeyer

  • Status changed from new to needs_review

comment:5 Changed 8 years ago by jdemeyer

  • Status changed from needs_review to needs_work
  • Work issues set to p-adic embeddings, problems with #11873

comment:6 follow-up: Changed 8 years ago by nbruin

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.

comment:7 Changed 8 years ago by jdemeyer

  • Dependencies changed from #11870 to #11873
  • Work issues changed from p-adic embeddings, problems with #11873 to more examples

comment:8 in reply to: ↑ 6 Changed 8 years ago by jdemeyer

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.

comment:9 Changed 8 years ago by jdemeyer

  • Status changed from needs_work to needs_review
  • Work issues more examples deleted

comment:10 Changed 8 years ago by mstreng

  • Status changed from needs_review to needs_work
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.

comment:11 follow-ups: Changed 8 years ago by mstreng

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.

comment:12 in reply to: ↑ 11 Changed 8 years ago by jdemeyer

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.

comment:13 in reply to: ↑ 11 ; follow-up: Changed 8 years ago by jdemeyer

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?

comment:14 in reply to: ↑ 13 Changed 8 years ago by mstreng

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.

comment:15 Changed 8 years ago by jdemeyer

  • Dependencies changed from #11873 to #11873, #11876

comment:16 Changed 8 years ago by jdemeyer

  • Status changed from needs_work to needs_review

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

comment:17 Changed 8 years ago by mstreng

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" % (....)

comment:18 Changed 8 years ago by jdemeyer

Done, error message changed.

comment:19 Changed 8 years ago by jdemeyer

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

comment:20 Changed 8 years ago by jdemeyer

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

comment:21 Changed 8 years ago by mstreng

  • Cc SimonKing added

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.

Changed 8 years ago by jdemeyer

comment:22 follow-up: Changed 8 years ago by SimonKing

  • Status changed from needs_review to needs_info

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

comment:23 in reply to: ↑ 22 Changed 8 years ago by jdemeyer

Replying to SimonKing:

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.

comment:24 Changed 8 years ago by mstreng

  • Authors set to Jeroen Demeyer
  • Reviewers set to Marco Streng
  • Status changed from needs_info to needs_review

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.

comment:25 Changed 8 years ago by mstreng

  • Status changed from needs_review to positive_review

comment:26 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-4.7.3

comment:27 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.7.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:28 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:29 Changed 8 years ago by jdemeyer

  • Merged in changed from sage-4.7.3.alpha0 to sage-4.8.alpha0
  • Milestone set to sage-4.8
Note: See TracTickets for help on using tickets.