Opened 6 years ago

Closed 4 years ago

#11670 closed defect (fixed)

fix number fields being unique parents -- this got broken over the years

Reported by: was Owned by: davidloeffler
Priority: major Milestone: sage-6.3
Component: number fields Keywords:
Cc: Merged in:
Authors: Julian Rueth Reviewers: Simon King, Peter Bruin
Report Upstream: N/A Work issues:
Branch: 8b06ff7 (Commits) Commit: 8b06ff7d7fef13bd3746a1524bc5744242f1a75e
Dependencies: Stopgaps:

Description (last modified by was)

For example, these are all wrong:

sage: K.<a> = NumberField(x^2 - x - 1)
sage: loads(dumps(K)) is K
False
sage: K.<a> = NumberField(x^3 - x - 1)
sage: loads(dumps(K)) is K
False
sage: K.<a> = CyclotomicField(7)
sage: loads(dumps(K)) is K
False

NOTE: To keep this project manageable for now, this ticket does *not* address similar issues for relative number fields, if there are any.

This is related to #10448.

Attachments (1)

trac_11670.patch (16.1 KB) - added by was 6 years ago.

Download all attachments as: .zip

Change History (43)

comment:1 Changed 6 years ago by was

  • Description modified (diff)

When working on this ticket, I also found a potentially serious bug, which is that the parameters assume_disc_small and maximize_at_primes of a number field were both lost upon pickling and unpickling. This ticket fixes that. We used to have this bug:

sage: K.<a> = NumberField(x^3-2, assume_disc_small=True, maximize_at_primes=[2], latex_name='\\alpha', embedding=2^(1/3))
sage: K._assume_disc_small
True
sage: K._maximize_at_primes
[2]
sage: L = loads(dumps(K))
sage: L._assume_disc_small
False
sage: L._maximize_at_primes  # None

Attached patch fixes that.

Changed 6 years ago by was

comment:2 Changed 6 years ago by was

  • Status changed from new to needs_review

comment:3 Changed 6 years ago by was

  • Description modified (diff)

comment:4 Changed 6 years ago by was

I should comment on UniqueFactory? and UniqueRepresentation? (from sage.structure.unique*). I made some attempt to use it, but decided against it for *this patch*. The main reason is that I want to fully maintain backward compatibility with old pickled objects, since there are a lot of pickled number field elements in the wild, and that is really opaque using UniqueRepresentation?. (Also, I am concerned using UniqueRepresentation? has some efficiency issues in terms of size and later changing how pickling works, since every time you pickle an object it wraps it in its own wrapper around other stuff, leading to another level of abstraction.) I don't claim that the current approach is the easiest to maintain in the long run -- in fact, it got broke before by bad patches. But in this new patch, I've added a ton of comments and a big warning to help prevent this in the future.

comment:5 Changed 6 years ago by was

I also applied the patch to sage-4.7.2.alpha1 and ran "make ptestlong" with complete success.

comment:6 Changed 6 years ago by SimonKing

Does that fix the issues discussed on #10448 as well?

There, I tried to fix the missing uniqueness of maximal orders in number fields using cached_method decorators. However, the most recent post on #10448 (five months ago) also mentions the problem that number fields aren't unique, and thus the maximal orders can only be as unique as the umber fields they are contained in.

comment:7 Changed 6 years ago by SimonKing

It turns out that this ticket is also related with #10667. Since #10667 (among other things) extends caching of homsets, the non-uniqueness of number fields then yields actual coercion errors.

comment:8 Changed 6 years ago by SimonKing

Some brief remarks:

  • In the test for NumberField_absolute_v2, you use NumberField_absolute_v1 (should be v2, not v1). The same for NumberField_cyclotomic_v2 and NumberField_quadratic_v2.
  • The format, if I am not mistaken, should be
           OUTPUT:
    
           - tuple of parameters that define this field; used in 
             caching and pickling 
    
    not
           OUTPUT: 
               - tuple of parameters that define this field; used in 
                 caching and pickling 
    

comment:9 Changed 6 years ago by SimonKing

One problem bugging me at #10667 remains: If one calls the method point_exact from sage.schemes.elliptic_curves.heegner with the option optimize=True then a non-unique absolute number field (namely Number Field in a with defining polynomial x^12 + 4*x^11 + 56*x^10 + 170*x^9 + 1130*x^8 + 2564*x^7 + 10791*x^6 + 18054*x^5 + 51340*x^4 + 57530*x^3 + 102986*x^2 + 53724*x + 35001) emerges.

If I can fix it then I'll post a patch here, not at #10667.

comment:10 Changed 6 years ago by SimonKing

Yep. Here is an explicit example exposing the missing uniqueness:

sage: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a')
sage: M = N.optimized_representation()[0]
sage: M
Number Field in a6 with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1
sage: N is M.change_names(names='a')
False
sage: N == M.change_names(names='a')
True

I guess it can be fixed in the change_names method.

comment:11 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_info

Aha, it boils down to one line in N.absolute_field:

        try:
            return self.__absolute_field[names]
        except KeyError:
            pass
        except AttributeError:
            self.__absolute_field = {}
        K = NumberField(self.defining_polynomial(), names, cache=False)
        K._set_structure(maps.NameChangeMap(K, self), maps.NameChangeMap(self, K))
        self.__absolute_field[names] = K
        return K

Why is the option cache=False used in that method?

comment:12 Changed 6 years ago by SimonKing

I read the comment

        # Note -- never call this on a cached number field, since
        # that could eventually lead to problems.

in N._set_structure. That might be a show stopper. But what actually happens if one applies it to a cached number field?

comment:13 Changed 6 years ago by SimonKing

I see a potential work-around. In my example, we have

sage: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a')
sage: M = N.optimized_representation()[0]
sage: K = M.change_names(names='a')
sage: N == K
True
sage: N is K
False
sage: N.structure()
(Ring Coercion endomorphism of Number Field in a with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, Ring Coercion endomorphism of Number Field in a with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1)
sage: K.structure()
(Isomorphism given by variable name change map:
  From: Number Field in a with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1
  To:   Number Field in a6 with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, Isomorphism given by variable name change map:
  From: Number Field in a6 with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1
  To:   Number Field in a with defining polynomial x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1)

Would it make sense to declare two number fields different if they have different structure()?

comment:14 Changed 6 years ago by was

  • Authors set to William Stein
  • Reviewers set to Simon King

comment:15 Changed 6 years ago by was

  • Status changed from needs_info to needs_review

comment:16 Changed 6 years ago by was

  • Status changed from needs_review to needs_work

comment:17 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:18 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:19 Changed 4 years ago by saraedum

  • Branch set to u/saraedum/ticket/11670
  • Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52

comment:20 Changed 4 years ago by saraedum

  • Commit set to cab3fe1eb4c425f0028b221494f95a03199f2936

With the branch I just pushed, I got rid of _set_structure. The structure of a number field is now always set when it is created. I know that unpickling of old objects is currently broken, I'm working on a fix. Anyway, maybe somebody already wants to have a look at what I have done so far? Any comments would be appreciated.

Should I now add old number field pickles to the pickle jar? I could not find out how to do this from the reference manual. Or is this somehow done automagically?


New commits:

c9b7129Removed number field's _set_structure() which breaks caching
16aa7ecCreate number fields in a factory to make sure they are unique parents.
835c817Implemented NumberFieldStructure classes to improve caching of (absolute) number fields.
3a11836Made assume_disc_small part of the key for the number field cache (as it used to be).
cab3fe1added missing docstrings to number field factories

comment:21 Changed 4 years ago by saraedum

  • Authors changed from William Stein to Julian Rueth
  • Status changed from needs_work to needs_review

Pickling of old and new number fields should work now. I found these issues though.

Absolute number fields used to forget about their structure, this is fixed now (of course the structure can not be recovered for old pickles):

sage: K.<a> = QuadraticField(2)
sage: L.<b> = K.change_names()
sage: M=loads(dumps(L))
sage: M.structure() # old behaviour
(Ring Coercion endomorphism of Number Field in b with defining polynomial x^2 - 2,
 Ring Coercion endomorphism of Number Field in b with defining polynomial x^2 - 2)
sage: L.structure() # this is what M.structure() returns now
(Isomorphism given by variable name change map:
  From: Number Field in b with defining polynomial x^2 - 2
  To:   Number Field in a with defining polynomial x^2 - 2,
 Isomorphism given by variable name change map:
  From: Number Field in a with defining polynomial x^2 - 2
  To:   Number Field in b with defining polynomial x^2 - 2)

Relative number fields also used to forget about their structure. Since I have not touched the pickling of relative number fields, I would rather put this into a separate ticket:

sage:             sage: Z = var('Z')
sage:             sage: K.<w> = NumberField(Z^3 + Z + 1)
sage:             sage: L.<z> = K.extension(Z^3 + 2)
sage:             sage: M.<u,v> = L.change_names()
sage:             sage: M.structure()
(Isomorphism given by variable name change map:
  From: Number Field in u with defining polynomial x^3 + 2 over its base field
  To:   Number Field in z with defining polynomial Z^3 + 2 over its base field,
 Isomorphism given by variable name change map:
  From: Number Field in z with defining polynomial Z^3 + 2 over its base field
  To:   Number Field in u with defining polynomial x^3 + 2 over its base field)
sage:             sage: M = loads(dumps(M))
sage:             sage: M.structure()
(Ring Coercion endomorphism of Number Field in u with defining polynomial x^3 + 2 over its base field,
 Ring Coercion endomorphism of Number Field in u with defining polynomial x^3 + 2 over its base field)

comment:22 Changed 4 years ago by saraedum

  • Status changed from needs_review to needs_work

comment:23 Changed 4 years ago by git

  • Commit changed from cab3fe1eb4c425f0028b221494f95a03199f2936 to 70702aa690a31cc36b9febe36462c67ebd57dcee

Branch pushed to git repo; I updated commit sha1. New commits:

71532deHash function for absolute number fields.
af58e0cFixed unpickling of absolute number fields
7bb5b88Added a test case to verify that pickling preserves the structure of a relative number field.
622b238Pickling is broken for relative number fields. The structure of a number field is lost. Added a doctest to document this behaviour.
9e8de67Relative and absolute number fields defined by the same (absolute) polynomial should not be equal.
0581f37A number field's structure() may define conversion maps between number fields
baeeb5cfixed a pickling test case
70702aaFixed a hash doctest.

comment:24 Changed 4 years ago by saraedum

  • Modified changed from 04/09/14 14:52:46 to 04/09/14 14:52:46
  • Status changed from needs_work to needs_review

comment:25 follow-up: Changed 4 years ago by pbruin

I think it is indeed important that if one considers fields equipped with a structure (in the sense of this ticket), then (1) the structure should be fixed once and for all at the time of construction, and (2) no two fields with a different structure should be considered as equal. Given (1), it would be good to to have a clear picture of what sort of things one can specify as a structure, and I would be interested in finding out how flexible this concept of structure is.

For example, it would be nice to be able to equip a number field K with an additional "piece of structure" z such that there is a category (in the mathematical sense) in which the objects are such pairs (K, z) and in which there exists at most one morphism between any two objects. Then (a suitable finite representation of) z could be taken as an especially nice type of structure in the above sense.

One particular "piece of structure" that comes to mind is an embedding z of K into a fixed algebraic closure of Q. In Sage, this means an embedding into QQbar. Since QQbar encodes field elements (roughly speaking) by a polynomial and a complex root, represented by a sufficiently small complex region to determine the root uniquely, specifying z really means giving a small complex region representing a root of the defining polynomial of K.

Now it is already the case that one can specify an embedding parameter when creating a number field. Hence (finally) the following question: does the concept of a structure in the sense of this ticket allow the existing embedding parameter to be implemented as a special case of a structure?

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

Replying to pbruin:

Now it is already the case that one can specify an embedding parameter when creating a number field. Hence (finally) the following question: does the concept of a structure in the sense of this ticket allow the existing embedding parameter to be implemented as a special case of a structure?

Not really. One difference is that two fields with different embedding are not considered equal, but two fields with different structure are. I think this makes sense since structure currently tells you how a field has been created (e.g. as the absolute field of a relative field.) However, treating two number fields with different complex embedding as being the same would most probably lead to nasty bugs.

There might be a more general concept that structure and embedding are special cases of but I would not try to abuse one of them for this (right now). There is probably too much code that expects these two attributes to have a specific format to make such a change. It could be the content of a followup ticket.

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

Replying to saraedum:

Not really. One difference is that two fields with different embedding are not considered equal, but two fields with different structure are.

OK, I misunderstood the discussion on this ticket so far (I did not yet look at the code carefully); I somehow concluded that your implementation answered Simon's question from comment:13 with "yes". So do I understand correctly that two number fields are explicitly allowed to be equal but not identical? Is this really desirable? From the manual page on unique representation:

"Instances of a class have a unique representation behavior when instances evaluate equal if and only if they are identical (i.e., share the same memory representation), if and only if they were created using equal arguments. [...] This behaviour is typically desirable for parents and categories."

comment:28 in reply to: ↑ 27 ; follow-up: Changed 4 years ago by saraedum

Replying to pbruin:

OK, I misunderstood the discussion on this ticket so far (I did not yet look at the code carefully); I somehow concluded that your implementation answered Simon's question from comment:13 with "yes".

I agree that it makes sense that two number fields are different if they have a different structure. I had a feeling that this would break too much existing code, though. I think it is a natural first step to rewrite number fields to use a factory and make them unique parents (this ticket).

I could certainly imagine helping on a followup ticket which tries to make == and is the same for number fields.

comment:29 in reply to: ↑ 28 ; follow-up: Changed 4 years ago by pbruin

Replying to saraedum:

I agree that it makes sense that two number fields are different if they have a different structure. I had a feeling that this would break too much existing code, though.

Hmm, I wonder if one could test easily if this would indeed be a problem (within the Sage library, say).

I think it is a natural first step to rewrite number fields to use a factory and make them unique parents (this ticket).

Doesn't "unique parents" mean precisely that parents are equal if and only if they are identical (see the third paragraph of this page)?

(I'm only starting to understand the finer points of all this; I thought understanding the situation for number fields would be a good first step towards the similar problem for elliptic curves in #11474.)

comment:30 in reply to: ↑ 29 ; follow-up: Changed 4 years ago by saraedum

Replying to pbruin:

Replying to saraedum:

I agree that it makes sense that two number fields are different if they have a different structure. I had a feeling that this would break too much existing code, though.

Hmm, I wonder if one could test easily if this would indeed be a problem (within the Sage library, say).

I think it is a natural first step to rewrite number fields to use a factory and make them unique parents (this ticket).

Doesn't "unique parents" mean precisely that parents are equal if and only if they are identical (see the third paragraph of this page)?

Ok. Maybe I am using the wrong vocabulary here. I meant, "uniue" as in "two fields generated from the same arguments are identical", not as in "unique representation".

comment:31 Changed 4 years ago by pbruin

I see what you mean. Maybe one could try to formalise the notion of "unique parents" more precisely as follows.

We have some Python callable NumberField() that takes as input some key (defining datum) d and outputs some Python object K depending on d and representing a number field. This NumberField() uses (implicitly) some algorithm, say same(d, e), that given two keys d and e decides whether d and e define the same number field. (The meaning of "the same" is a bit vague; one could either use a mathematical definition involving extra structure on the number field, or one could take "the same" to mean by definition that same(d, e) returns True.)

Of course, same should behave like an equivalence relation (same(d, d) == True, same(d, e) == same(e, d), and transitivity holds). I think that "K and L were created using the same arguments" should be interpreted as K and L being names assigned to the objects returned by NumberField(d) and NumberField(e) for some d and e for which same(d, e) is True. I'm not sure if we have to assume any implication between same(d, e) and d == e; it is possible that same(d, e) is actually implemented as d == e.

Now consider the following boolean-valued statements about possible keys d and e:

  1. d is e
  2. same(d, e)
  3. NumberField(d) is NumberField(e)
  4. NumberField(d) == NumberField(e)

Clearly, the implications 1 => 2 and 3 => 4 are automatic, and 2 => 4 probably holds already. It seems that saying "number fields are unique parents" is the same as saying that the implementation of NumberField() ensures that the implications 2 => 3 (hence 2 => 4) and 4 => 3 both hold, and maybe even 3 => 2.

If I understand correctly, this ticket makes sure that 2 => 3 holds, but not necessarily 4 => 3. From that perspective it makes sense to have a separate ticket to implement the "other half" of the unique parents property.

comment:32 in reply to: ↑ 30 Changed 4 years ago by SimonKing

Replying to saraedum:

Ok. Maybe I am using the wrong vocabulary here. I meant, "uniue" as in "two fields generated from the same arguments are identical", not as in "unique representation".

If you want two fields generated from the same arguments to be identical, then you can either use CachedRepresentation or UniqueFactory.

If you additionally want unique parent behaviour (which means you cannot have two distinct instance of your class that evaluate equal), you can use UniqueRepresentation, or you can add WithEqualityById (it could be that I wrongly remember the name, but it is something similar to this) as a base class.

comment:33 follow-up: Changed 4 years ago by pbruin

With your changes, Sage doesn't complain anymore if the user does not specify the name of the generator, but silently names it "a":

sage: K = NumberField(x^2 + 1); K
Number Field in a with defining polynomial x^2 + 1

I don't like this; since the name is part of the defining data, I think we should insist on the user specifying the name. If you think this should be changed, I think it is better to create a new ticket so this interface issue can be discussed separately from the technical changes made in this ticket.

comment:34 Changed 4 years ago by git

  • Commit changed from 70702aa690a31cc36b9febe36462c67ebd57dcee to 8e968244cb356aaa863eb6a3caff46c74d48f182

Branch pushed to git repo; I updated commit sha1. New commits:

f1cbe03Merge branch 'develop' into ticket/11670
8e96824Raise an error if the generator of a number field has not been specified.

comment:35 in reply to: ↑ 33 Changed 4 years ago by saraedum

Replying to pbruin:

With your changes, Sage doesn't complain anymore if the user does not specify the name of the generator, but silently names it "a":

You are right. I just implemented what the docstring used to say. I fixed the implementation and the docstring.

comment:36 Changed 4 years ago by pbruin

  • Branch changed from u/saraedum/ticket/11670 to u/pbruin/11670-NumberField_unique
  • Commit changed from 8e968244cb356aaa863eb6a3caff46c74d48f182 to 9b4deffd7823cc4e71c6122b99615d765bd9d87f
  • Reviewers changed from Simon King to Simon King, Peter Bruin

Thanks. I made a reviewer patch to fix some typos, formatting and Python 3 compatibility things; I changed the error message for name=None back to what it was to fix one failing doctest.

I would be happy give this a positive review, but I think it is better if Simon or someone else with expertise in this area takes a quick look at it as well.

comment:37 Changed 4 years ago by mmezzarobba

  • Status changed from needs_review to needs_work
  • Work issues set to merge conflicts with 6.2β8

comment:38 Changed 4 years ago by git

  • Commit changed from 9b4deffd7823cc4e71c6122b99615d765bd9d87f to 8b06ff7d7fef13bd3746a1524bc5744242f1a75e

Branch pushed to git repo; I updated commit sha1. New commits:

8b06ff7Merge branch 'develop' into ticket/11670-NumberField_unique

comment:39 Changed 4 years ago by pbruin

  • Status changed from needs_work to needs_review
  • Work issues merge conflicts with 6.2β8 deleted

New commits:

8b06ff7Merge branch 'develop' into ticket/11670-NumberField_unique

comment:40 Changed 4 years ago by pbruin

  • Status changed from needs_review to positive_review

OK, let's not leave this to bitrot. As an additional test, I checked that #11669 (which depends on this ticket) still works correctly, and it does.

comment:41 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:42 Changed 4 years ago by vbraun

  • Branch changed from u/pbruin/11670-NumberField_unique to 8b06ff7d7fef13bd3746a1524bc5744242f1a75e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.